라우팅 알고리즘

 라우터는 포워딩,라우팅 2가지 기능을 수행한다.라우팅 프로토콜(Routing Protocol)은 네트워크에서 호스트간에 좋은 경로를 찾는 것으로 이 좋은 경로의 기준은 비용,속도,혼잡도 등의 기준으로 평가할 수 있다.

라우팅 프로토콜

 라우팅 알고리즘은 그래프로 추상화 할 수 있다.각 노드를 라우터,간선들을 링크라하고 각각의 가중치를 표시하면 된다.

그래프 예시

라우팅 알고리즘의 분류는 다음과 같다.

라우팅 알고리즘 분류

 static은 일반적으로 고정된 라우터들을 의미하고 dynmaic은 자동차에 들어가는 네트워크처럼 동적인 형태를 취하는 것 들을 의미한다.

하지만 중요한 2가지는 Link state,Distance vector 알고리즘이다.

Link state algorithms

 링크 상태 알고리즘으로 이름으로도 유추가능하듯이 이 알고리즘은 모든 라우터들이 네트워크의 전체 토폴로지,링크 비용을 알고있다는 가정하에 동작한다.따라서 모든 라우터들은 같은 정보를 공유한다.따라서 이때는 다익스트라 알고리즘(Dijkstra's algorithm)이 사용된다.

모든 라우터들은 다익스트라 알고리즘을 사용해서 최소 비용 경로를 계산하고 이를 바탕으로 포워딩 테이블을 작성한다.이 작업은 반복적으로 실행된다.

다익스트라 알고리즘 예시

하지만 모든 정보를 각 노드가 공유해야하기에 시간 복잡도는 O($n^2$)이 된다.링크 상태 알고리즘은 모든 라우터의 정보를 확인하고 테이블을 생성하기에 정확도가 높지만 넓은 네트워크에서는 오버헤드가 매우 심해진다.또한 링크상태는 가변적이기에 다음과 같은 문제가 발생한다.

 

Oscillation issue in Dijkstra's algorithm

 링크의 비용은 트래픽 부하에 따라 달라진다.그리고 라우터들은 그때 그때 최선의 경로로 라우터들이 라우팅할 것이다.중요한건 이때 마다 트래픽이 몰릴 수 있다는 것이다.그리고 이 과정이 반복되면서 경로는 계속 바뀔 것이다.이를 Oscillation(진동)현상이라 한다.

진동현상의 예시

Distance vector alogrithm

 이 알고리즘은 Dynamic Programming(DP,동적 계획법) approach에 기반하여 만들어 졌다.정확히는 Bellman-Ford(BF) 방정식에 기반했다.

Bellman-Ford 방정식

즉,각 라우터들은 직접 연결된 라우터들한테서 링크 상태를 받는다.

Bellman-Ford example

 우선 노드들은 일정 시간 or 링크 비용이 변경될 때 이웃 노드에게 자신의 거리 벡터를 전송한다.이때 이웃 노드로부터 거리 벡터 정보를 받으면,해당 정보를 기반으로 자신의 거리 벡터를 업데이트한다.이후 벨만-포드 방정식을 사용해서 최적 경로를 다시 계산한다.

따라서 거리 벡터 알고리즘은 다음과 같은 특성을 갖는다.

1. 분산형 알고리즘:각 노드는 이웃 노드들로부터 받은 정보만을 바탕으로 자산이 알고 있는 경로 정보를 업데이트한다.(클러스터링)
2. 비동기적 동작:모든 노드가 동시에 동작하지 않아도 되고,이웃으로부터 새로운 정보가 도착할 때마다 자신이 알고 있는 경로를 갱신한다.
3. 자신의 거리 벡터가 더 이상 변경되지 않으면 자동적으로 멈춘다.

Distance vector algorithm example

하지만 이 알고리즘도 문제점이 존재한다.우선 링크의 비용이 줄어들 경우를 살펴보자 이는 Good news로 굉장히 빠르게 네트워크 전반에 퍼진다.즉시 라우터들은 거리 벡터를 갱신해서 링크를 사용할 것 이다.

Good news

그렇지만 반대의 경우 링크의 비용이 어떠한 이유로 증가했거나 끊어졌다 생각해보면 달라진다.우선 다른 노드에게 똑같이 거리벡터를 갱신하고 이웃하게 알려지지만 일종의 순환문제가 발생한다.

Bad news

위의 예를 보면 y노드는 x까지의 거리벡터가 비용60으로 늘어남을 z에게 알릴 것 이다.그리고 y는 x까지 가는데 6임을 z에게 알릴 것 이다.하지만 이 알고리즘 특성상 이웃으로부터 받은정보를 신뢰하게 된다.따라서 z는 z -> y -> z -> x 이런식으로 경로를 판단하고 이를 y한테 알릴 것 이다.즉 점차 비용이 1씩 계속 늘어나서 60이될때까지 반복된다.이를 경로 비용을 무한대로 증가시키는 Count-to-Infinity문제라 한다.