그래프 이론에서 두 정점 간에 최단 경로를 찾는 그래프 알고리즘을 이용한 라우팅입니다. 출발지로부터 최단 경로를 갖는 점들을 차례대로 찾아가면서 경로를 탐색합니다.
그래프에서는 각 노드가 라우터를 나타내며 그래프의 각 호가 통신회선을 나타냅니다.
Shortest path routing에서는 주어진 라우터 쌍 사이의 경로를 선택하기 위해 그래프에서 가장 짧은 경로를 찾습니다.
이를 풀기위해 다익스트라 알고리즘 등의 알고리즘이 사용됩니다.
다익스트라 알고리즘에 대해서는 제일 아래에서 설명드리겠습니다.
In graph theory, it is the routing using the graph algorithm to find the shortest path between two vertices. Navigate through the paths as you go through the points with the shortest path from the origin.
In the graph, each node represents a router, and each call in the graph represents a communications line.
Shortest path routing finds the shortest path in the graph to select the path between a given pair of routers.
To solve this problem, an algorithm such as a multi-extrude algorithm is used.
I will explain the extreme algorithms at the bottom.
* 플러딩(Flooding)
또 다른 정적 알고리즘으로는 플러딩(Flooding)이 이습니다. 플러딩에서는 패킷이 도착되어 있는 곳을 제외한 모든 나가는 라인에 들어오는 모든 패킷들을 전송합니다. 이것은 당연히 엄청난 수의 중복 패킷을 생성하게 됩니다. 실제로는 프로세스를 감쇠시키기 위한 조치가 취해지지 않는 한 무한한 숫자입니다. 플러딩은 대규모 네트워크에서 수정된 라우팅 정보를 모든 노드에 빠르게 배포하는 수단으로써 사용됩니다.
Another static algorithm is Flooding. Flooding sends all incoming packets to all outgoing lines except where they arrived. This, of course, creates a huge number of redundant packets. In practice, this is an infinite number unless measures are taken to attenuate the process. Flooding is used as a means of rapidly distributing modified routing information across all nodes in large networks.
* 선택적 플러딩(Selective flooding)
Selective flooding은 플러딩을 보다 실용적으로 사용하기 위해 변형된 방식입니다. 이 알고리즘에서는 들어오는 모든 패킷들을 모든 라인에 보내지 않고 거의 올바른 방향으로만 가는 라인에만 보냅니다.
Selective flooding is a variation of flooding to make it more practical. This algorithm does not send all incoming packets to all lines, but sends them only to lines that are almost in the right direction.
* 흐름 기반 라우팅(Flow-based routing)
해당 라우팅에서는 트래픽 흐름을 고려합니다. 핵심으로는, 시간이 지남에 따라 트래픽 흐름의 특성을 고려할 수 있다는 점 입니다. 트래픽 도달 속도 및 패킷 길이등, 네트워크 상태에 대해 많이 알고 있는 경우 사용할 수 있습니다. Flow-based routing은 라우팅 테이블을 찾아 서브넷을 통한 평균 패킷 지연을 최소화합니다.
This routing considers traffic flow. The key is that over time, you can consider the nature of the traffic flow. You can use it if you know a lot about network conditions, such as traffic arrival rate and packet length. Flow-based routing finds the routing table and minimizes the average packet delay over the subnet.
* 거리 벡터 라우팅(Distance vector routing)
먼저 모든 링크의 가중치(cost)는 이미 알려져 있다고 가정합니다. (가중치는 링크에 연결되어 있는 라우터가 측정할 수 있습니다.) 각 라우터는 라우팅 테이블을 가지고 있고, 이 테이블에는 주어진 서브넷의 모든 라우터에 대한 정보를 가집니다. 각 라우터에 대한 정보는 해당 라우터까지의 거리와 그 라우터로 가기 위한 값입니다. 각 라우터는 현재의 라우팅 테이블 정보를 이웃에게 보냅니다.
First, we assume that the weight of all links is already known. (Weights can be measured by the router connected to the link.) Each router has a routing table, which has information about all the routers on a given subnet. The information for each router is the distance to that router and the value to go to that router. Each router sends its current routing table information to its neighbors.
* 링크 상태 라우팅(Link state routing)
각 라우터는 주변의 링크들을 탐색하고 연결된 라우터의 주소를 알아냅니다. 그리고 각 링크의 가중치(cost)를 측정합니다. 이후 각 링크와 가중치에 대한 정보를 담은 패킷을 만듭니다. 이렇게 만들어진 LSP(Link State Packet)를 모든 라우터에게 보냅니다. 마지막으로 다른 라우터로부터 받은 LSP들을 이용하여 각 라우터로의 가장 짧은 경로를 계산합니다.
- 거리 벡터 라우팅을 이용하지 않고 링크 상태 라우팅을 사용하는 이유
1. 거리 벡터 라우팅은 라우터를 선택할 때 회선의 대역폭을 고려하지 않았습니다.
2. Count to Infinity
: A,B,C의 라우터가 존재한다고 가정합니다. 이때 A라우터가 죽었는데, C라우터에서 A라우터로 패킷을 보내려한다면 먼저 B라우터에게 패킷을 보내게 됩니다. 헌데 B라우터에서는 A라우터로 보낼 수 없기 때문에 다시 C라우터로 패킷을 보냅니다. 그리고 이러한 과정이 반복되면서 무한 루프에 빠지게 되고 이것을 Count to Infinity 라고 합니다.
Each router scans the neighboring links and obtains the address of the connected router. And we measure the weight of each link. It then creates a packet with information about each link and weight. The link state packet (LSP) is sent to all routers. Finally, the LSPs received from other routers are used to calculate the shortest route to each router.
- Why use link state routing without using distance vector routing
1. Distance vector routing did not take the bandwidth of the line into account when choosing a router.
2. Count to Infinity
: Suppose A, B, C routers exist. At this point, if the A router is dead, and the C router wants to send a packet to the A router, it will send a packet to the B router first. However, since the router B can not send it to the router A, it sends the packet back to the router C. And as this process repeats itself, it goes into an infinite loop and is called Count to Infinity.
* 계층적 라우팅(Hierarchical routing)
계층적 라우팅은 위의 그림에서와 같이, 넓은 네트워크를 몇 개의 네트워크 레벨로 크기를 분할하여 경로를 간소화 하고 계층화 합니다. 이렇게 계층화 된 것들을 각각 Regions이라고 하며 각각의 Regions 안에서 독립적으로 라우팅이 이루어집니다.
Hierarchical routing simplifies and layers the wide network by dividing it into several network levels, as shown in the figure above. Each of these layers is called Regions, and routing is done independently within each Regions.
* 다익스트라 알고리즘(Dijkstra algorithm)
다익스트라 알고리즘은 음수 가중치를 갖지 않는 그래프에서 주어진 출발점과 도착점 사이의 최단 경로문제를 푸는 알고리즘입니다. 다익스트라 알고리즘은 방문한 노드들의 집합, 방문하지 않은 노드들의 집합과 출발점으로 부터 특정 노드까지 계산된 최단 거리를 갖습니다. 각 노드들에 대해서 계산된 최단 거리의 초기값은 무한대로 잡습니다.
아래 예제를 통해 확인해보도록 하겠습니다.
예제는 나무위키에서 참고하였습니다.
The Daikstra algorithm is an algorithm that solves the shortest path problem between a given start and end point in a graph that does not have negative weight. The extreme algorithm has a set of visited nodes, a set of non-visiting nodes, and a calculated shortest distance from a starting point to a specific node. The initial value of the calculated shortest distance for each node is infinity.
Let's take a look at the example below.
An example is given in Tree Wiki.
1. 다익스트라 알고리즘에서 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡습니다.
먼저 출발지는 A로 가정했을 때, A까지의 거리는 당연히 0입니다. 따라서 d[A]는 0의 값을 갖습니다.
아직 A노드는 방문한 것이 아니고 초기화 하는 과정이기에 방문하지 않은 노드들의 집합 Q에는 A,B,C,D,E,F 의 노드가 기록되어 있으며 방문한 노드들의 집합은 공집합 입니다.
출발지 A노드를 제외한 모든 노드들 또한 아직 방문하지 않았기에 거리 값은 무한으로 기록됩니다.
1. All distances that have not yet been confirmed by the extreme algorithm are assumed to be infinite.
First, assuming that A is the starting point, the distance to A is probably zero. Therefore, d [A] has a value of 0.
Since node A is not visited yet and it is a process of initialization, nodes A, B, C, D, E, and F are recorded in the set Q of nodes that are not visited.
Since all nodes except the origin A node have not visited yet, the distance value is recorded as infinite.
2. 루프를 돌려 이웃 노드를 방문하고 거리를 계산합니다.
항상 루프의 시작은 현재 방문하지 않은 노드들의 집합 Q에서 거리 값이 최소인 노드를 탐색하는 것입니다. A노드를 제외한 나머지 노드들의 거리 값은 무한대이므로 A노드를 기준으로 탐색을 시작합니다. A노드에서 B,C,D에 대한 거리 값을 계산 하여 기록합니다.
2. Turn the loop to visit the neighboring node and calculate the distance.
The beginning of the loop always searches for the node with the minimum distance value in the set Q of the nodes that are not currently visited. Since the distance value of the remaining nodes except the A node is infinite, the search starts based on the A node. Calculate and record distance values for B, C, and D at node A.
3. 루프 이후의 그래프의 상태가 업데이트 되는 방식
위의 사진은 두번째 루프를 마치고 난 뒤의 모습입니다.
2번에서 언급한 바와 같이 두번째 루프의 시작 또한 방문하지 않은 노드들의 집합 Q에서 거리 값이 최소인 노드로 시작합니다. 따라서 거리 값이 10으로 최소인 B노드를 기준으로 탐색을 시작합니다. B노드를 방문하였으므로 집합 S에 기록하고 E의 거리값을 계산합니다. 거리 값을 계산할때는 출발지로 부터 탐색노드(기준노드)사이의 거리값과 탐색노드와 이웃노드의 거리값을 더한 값 입니다. 따라서 노드 E의 거리값은 10+20=30으로 기록됩니다.
3. How the state of the graph after the loop is updated
The picture above is the picture after the second loop is finished.
As mentioned in point 2, the start of the second loop also begins with the node with the minimum distance value in the set Q of nodes that have not visited. Thus, the search begins with respect to node B with a minimum distance value of 10. Since we visited node B, we write to set S and calculate the distance value of E. The distance value is calculated by adding the distance between the source node and the search node plus the distance between the search node and the neighboring node. Therefore, the distance value of node E is recorded as 10 + 20 = 30.
4. 더 빠른 경로를 발견한 경우
동일한 방식으로 세번째 루프에서는 D노드로 시작합니다. 이때 D노드를 기준을 탐색을 하면 C노드에 대한 거리값이 20으로 계산됩니다. 이전에 기록되어 있는 d[C]값인 30보다 더 짧은 최단 경로이므로 새롭게 계산된 값으로 업데이트를 합니다.
4. If you find a faster path
In the same way the third loop starts with the D node. At this time, when the search is performed on the basis of the D node, the distance value to the C node is calculated as 20. It is a shortest path shorter than 30, which is the previously recorded d [C] value, so it updates to the newly calculated value.
5. 방문하지 않은 노드들의 집합이 공집합이 될 때 까지 반복합니다.
위의 사진은 네번째 루프를 실행한 결과입니다. 위의 2~4번 과정에서 총 3번의 루프를 설명하였듯이 지속적으로 네번째, 다섯번째, 여섯번째 루프를 반복합니다. 마지막 루프까지 계산을 하면 최종적으로 다음과 같은 값을 가질 것 입니다.
최종 목적지가 F 였으므로, 최단 경로의 거리 값은 25이며 그 경로는 A,D,C,F 입니다.
5. Repeat until the set of non-visited nodes becomes empty.
The above picture is the result of executing the fourth loop. Repeat the 4th, 5th, and 6th loops continuously, as described in the previous two to four loops. The calculations up to the last loop will finally have the following values:
d [A] = 0 / d [B] = 10 / d [C] = 20 / d [D] = 15 /
Since the final destination was F, the distance value of the shortest path is 25, and the paths are A, D, C, and F.
