Routing algorithm - Link state

---

Routing algorithm

아래와 같이 네트워킹이 진행될때 이전에 다룬 forwarding은 router 안에서 알맞은 output port로 보내주는 단순한 역할이라면 routing은 algorithm을 갖고 적절한 router 경로를 정해주는 좀 더 복잡한 과정이다.

Routing algorithm은 최단경로를 찾는 알고리즘이다. 최단경로 알고리즘은 코딩연습을 할때나 알고리즘 수업때도 몇번 다뤄봤다. 그때도 그래프 자료형을 이용하여 최단경로를 계산하였는데 컴퓨터 네트워크에서도 똑같다.

위와 같이 N에는 경유 지점 역할이 되는 router들을 담아두고 E는 경유지간의 연결관계를 표현해둔다. 각 경로를 통과하는데 걸리는 시간은 cost로 표현하고 아래와 같이 나타낸다.

그리고 위와 같이 경유 지점들과 경유 지점간의 cost로 표현한 graph를 Topology라고 부른다.

이때 router가 천천히 변화하는 경우는 static하다고 보고 굉장히 빠르게 변화하는 경우 dynamic하다고 본다.

---

Link state

Link state는 모든 topology를 알고 있다고 고려하고 전체 범위를 분석하여 경로를 결정하는 것이다. 이때 가장 많이 쓰이는 것이 다익스트라 알고리즘(Dijkstra's algorithm)이다.

 

c(x,y):노드 x에서 y로의 링크 비용으로 직접 연결된 이웃이 아니면 무한대(∞)로 표시한다.

D(v): 소스에서 목적지까지의 경로 비용의 현재 값이다.

p(v): 소스에서 v로의 경로를 따라 이전 노드이다.

 N ′ : 최소 비용 경로가 확실히 알려진 노드 집합이다.

 

위의 요소들을 이용하여 아래와 같이 다익스트라 알고리즘을 구현할 수 있다.

예시를 통해 살펴보자.

위와 같은 Topology가 있을때 아래와 같이 step별로 표를 작성하여 결과를 도출 수 있다.

가장 가까운 노드에서 인접한 노드를 조사하며 최단 경로를 갱신하는 방식으로 최단 거리를 찾아내는 것을 볼 수 있다.

알고리즘의 복잡도는 n(n+1)/2가 되어 O(n^2)이 된다. 이를 효과적으로 개선하면 O(nlogn)까지도 개선할 수 있다.

다만 cost가 낮은 경로를 계속 선택해서 변화를 주다보면 아래와 같이 모든 데이터들이 cost가 낮은 경로를 선택하여 결국 bottle neck현상이 발생하여 계속해서 경로를 변경해야하는 문제가 존재한다.

---