TigerCow.Door

Routing Methodologies

라우팅 알고리즘은 아래와 같이 존재합니다.

Non-adaptive (static) algorithm

Shortest path routing

Flooding: selective flooding

Flow-based routing


Adaptive (dynamic) algorithm

Distance vector routing

Link state routing

Hierarchical routing


+ Dijkstra algorithm


하나씩 알아보도록 하겠습니다.


* Shortest path routing


그래프 이론에서 두 정점 간에 최단 경로를 찾는 그래프 알고리즘을 이용한 라우팅입니다. 출발지로부터 최단 경로를 갖는 점들을 차례대로 찾아가면서 경로를 탐색합니다.



그래프에서는 각 노드가 라우터를 나타내며 그래프의 각 호가 통신회선을 나타냅니다.

Shortest path routing에서는 주어진 라우터 쌍 사이의 경로를 선택하기 위해 그래프에서 가장 짧은 경로를 찾습니다.

이를 풀기위해 다익스트라 알고리즘 등의 알고리즘이 사용됩니다.

다익스트라 알고리즘에 대해서는 제일 아래에서 설명드리겠습니다.




* 플러딩(Flooding)


또 다른 정적 알고리즘으로는 플러딩(Flooding)이 이습니다. 플러딩에서는 패킷이 도착되어 있는 곳을 제외한 모든 나가는 라인에 들어오는 모든 패킷들을 전송합니다. 이것은 당연히 엄청난 수의 중복 패킷을 생성하게 됩니다. 실제로는 프로세스를 감쇠시키기 위한 조치가 취해지지 않는 한 무한한 숫자입니다. 플러딩은 대규모 네트워크에서 수정된 라우팅 정보를 모든 노드에 빠르게 배포하는 수단으로써 사용됩니다. 




* 선택적 플러딩(Selective flooding)


Selective flooding은 플러딩을 보다 실용적으로 사용하기 위해 변형된 방식입니다. 이 알고리즘에서는 들어오는 모든 패킷들을 모든 라인에 보내지 않고 거의 올바른 방향으로만 가는 라인에만 보냅니다. 




* 흐름 기반 라우팅(Flow-based routing)


해당 라우팅에서는 트래픽 흐름을 고려합니다. 핵심으로는, 시간이 지남에 따라 트래픽 흐름의 특성을 고려할 수 있다는 점 입니다. 트래픽 도달 속도 및 패킷 길이등, 네트워크 상태에 대해 많이 알고 있는 경우 사용할 수 있습니다. Flow-based routing은 라우팅 테이블을 찾아 서브넷을 통한 평균 패킷 지연을 최소화합니다.




* 거리 벡터 라우팅(Distance vector routing)



먼저 모든 링크의 가중치(cost)는 이미 알려져 있다고 가정합니다. (가중치는 링크에 연결되어 있는 라우터가 측정할 수 있습니다.) 각 라우터는 라우팅 테이블을 가지고 있고, 이 테이블에는 주어진 서브넷의 모든 라우터에 대한 정보를 가집니다. 각 라우터에 대한 정보는 해당 라우터까지의 거리와 그 라우터로 가기 위한 값입니다. 각 라우터는 현재의 라우팅 테이블 정보를 이웃에게 보냅니다.




* 링크 상태 라우팅(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 라고 합니다.




* 계층적 라우팅(Hierarchical routing)



계층적 라우팅은 위의 그림에서와 같이, 넓은 네트워크를 몇 개의 네트워크 레벨로 크기를 분할하여 경로를 간소화 하고 계층화 합니다. 이렇게 계층화 된 것들을 각각 Regions이라고 하며 각각의 Regions 안에서 독립적으로 라우팅이 이루어집니다.




* 다익스트라 알고리즘(Dijkstra algorithm)


다익스트라 알고리즘은 음수 가중치를 갖지 않는 그래프에서 주어진 출발점과 도착점 사이의 최단 경로문제를 푸는 알고리즘입니다. 다익스트라 알고리즘은 방문한 노드들의 집합, 방문하지 않은 노드들의 집합과 출발점으로 부터 특정 노드까지 계산된 최단 거리를 갖습니다. 각 노드들에 대해서 계산된 최단 거리의 초기값은 무한대로 잡습니다.

아래 예제를 통해 확인해보도록 하겠습니다.

예제는 나무위키에서 참고하였습니다.




1. 다익스트라 알고리즘에서 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡습니다.








먼저 출발지는 A로 가정했을 때, A까지의 거리는 당연히 0입니다. 따라서 d[A]는 0의 값을 갖습니다.

아직 A노드는 방문한 것이 아니고 초기화 하는 과정이기에 방문하지 않은 노드들의 집합 Q에는 A,B,C,D,E,F 의 노드가 기록되어 있으며 방문한 노드들의 집합은 공집합 입니다.

출발지 A노드를 제외한 모든 노드들 또한 아직 방문하지 않았기에 거리 값은 무한으로 기록됩니다.




2. 루프를 돌려 이웃 노드를 방문하고 거리를 계산합니다.



항상 루프의 시작은 현재 방문하지 않은 노드들의 집합 Q에서 거리 값이 최소인 노드를 탐색하는 것입니다. A노드를 제외한 나머지 노드들의 거리 값은 무한대이므로 A노드를 기준으로 탐색을 시작합니다. A노드에서 B,C,D에 대한 거리 값을 계산 하여 기록합니다.




3. 루프 이후의 그래프의 상태가 업데이트 되는 방식



위의 사진은 두번째 루프를 마치고 난 뒤의 모습입니다.

2번에서 언급한 바와 같이 두번째 루프의 시작 또한 방문하지 않은 노드들의 집합 Q에서 거리 값이 최소인 노드로 시작합니다. 따라서 거리 값이 10으로 최소인 B노드를 기준으로 탐색을 시작합니다. B노드를 방문하였으므로 집합 S에 기록하고 E의 거리값을 계산합니다. 거리 값을 계산할때는 출발지로 부터 탐색노드(기준노드)사이의 거리값과 탐색노드와 이웃노드의 거리값을 더한 값 입니다. 따라서 노드 E의 거리값은 10+20=30으로 기록됩니다.




4. 더 빠른 경로를 발견한 경우



동일한 방식으로 세번째 루프에서는 D노드로 시작합니다. 이때 D노드를 기준을 탐색을 하면 C노드에 대한 거리값이 20으로 계산됩니다. 이전에 기록되어 있는 d[C]값인 30보다 더 짧은 최단 경로이므로 새롭게 계산된 값으로 업데이트를 합니다.




5. 방문하지 않은 노드들의 집합이 공집합이 될 때 까지 반복합니다.



위의 사진은 네번째 루프를 실행한 결과입니다. 위의 2~4번 과정에서 총 3번의 루프를 설명하였듯이 지속적으로 네번째, 다섯번째, 여섯번째 루프를 반복합니다. 마지막 루프까지 계산을 하면 최종적으로 다음과 같은 값을 가질 것 입니다.

d[A] = 0 / d[B] = 10 / d[C] = 20 / d[D] = 15 / d[E] = 30 / d[F] = 25

최종 목적지가 F 였으므로, 최단 경로의 거리 값은 25이며 그 경로는 A,D,C,F 입니다.



블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

댓글을 달아 주세요