📡 [Network] 링크 상태(Link State) 라우팅 알고리즘과 진동 문제 (Ocillations possbile)

본 포스팅은 <컴퓨터 네트워킹 하향식접근[8판] James F.Kurose, Keith W.Ross 저/최종원,강현국,김기태>을 참고하여 작성되었습니다.

Routing Protocols 라우팅 프로토콜 (알고리즘)

라우팅 프로토콜의 목표은 무엇일까? 라우팅 프로토콜의 목표는 송신자부터 수신자까지 라우터의 네트워크를 통 과하는 좋은 경로 결정하는 것이다. 이때 좋은의 의미는 상황에 따라 여러가지 의미를 가질 수 있다. (최소비용, 최고속도, 최소혼잡 등등..) 일반적으로는 최소비용을 말한다. 라우팅을 “잘” 하는 것은 10대 네트워크 도전과제 중 하나이다.

그래프로 추상화하기

라우팅 문제를 나타내는데에는 주로 그래프 자료구조가 사용된다. 그래프는 G = (N, E) 로 나타내는데 N과 E는 각각 노드와 간선의 집합이다. 하나의 간선(엣지)는 집합 N에 속하는 한쌍의 노드로 표현된다.

컴퓨터 네트워크에 대한 추상화된 그래프 모델

• undirected graph를 가정
• G = ( N , E )
• N : 라우터의 집합 = {u,v,w,x,y,z}
• E : 링크의 집합 = {(u,v),(u,x),(v,x),(v,w),(x,w),(x,y),(w,y),(w,z),(y,z)}

라우팅 문제를 나타내는 데는 그래프가 사용된다. 그래프(graph)는 G(N,E)로 나타내는데 N과 E는 각각 노드와 엣지의 집합이고, 하나의 간선에는 집합 N에 속하는 한쌍의 노드로 표시된다. 모든 링크에는 비용(cost)가 달려있다. 이를 C(a, b)와 같이 표현할 수 있다.

링크 상태 알고리즘 Link State Rounting Protocols

링크 상태 알고리즘에서는 네트워크 topology와 모든 링크 비용이 알려져 있어서 링크 상태 알고리즘의 입력값으로 사용될 수 있다. 각 노드가 자신과 직접 연결된 링크의 정보를 담은 패킷을 다른 모든 노드로 boardcast하게 함으로써 가능하다. 모든 노드는 네트워크에 대한 동일하고 완벽한 관점을 갖게된다. 각 노드는 이제 LS 알고리즘을 이용하여 다른 노드와 똑같은 최소 비용 경로 집합을 계산할 수 있다.

다익스트라 Dijstra’s link state routing algorithm

이 링크 상태 알고리즘은 발명자 다익스트라의 이름을 따서 부른다.

다익스트라 알고리즘은 하나의 출발지 노드에서 네트워크 내 다른 모든 노드로의 최소 비용을 계산하는 알고리즘이다. 이는 중앙화 centralized 알고리즘이며 전체 네트워크를 볼 수 있는 상황에 적합하다.

표기법 (정의)

• C{x, y} : 노드 x에서 y까지의 직접 연결 비용 (연결되지 않는 경우 INF로 표기)
• D(v) : 현재 시점에서 출발지노드부터 목적지 v까지의 최소 거리 비용
• p(v) : 출발지에서 c까지의 현재 최소 비용 경로에서 v의 직전 모드
• N’ : 계산 완료된 노드의 집합

알고리즘

// 초기 출발 노드의 이웃을 추가
**Initialization:** 
        N` = ( u }
        for all nodes v
        if v is a neighbor of u
                then D(v)= c(u,v) 
        else D(v) = INF

// 거리가 최소인 노드를 방문하고 비용 갱신을 반복
**Loop**
        find w not in N` such that D(w) is a minimum
        add w to N`
        update D(v) for each neighbor v of w and not in N` :
                D(v) = min (D(v), D(w) + c(W, v))
                /* new cost to v is either old cost to v or known
                 least path cost to w plus cost from w to v     */
**until** N` = N 

• 초기화와 반복 부분으로 구성된다.
• 반복 부분의 수행횟수는 네트워크의 노드 수와 같다.
• 수행이 종료되면 알고리즘은 출발지 노드 u에서 다른 모든 노드로의 최단경로를 산출 가능하다.

링크 상태 다익스트라 알고리즘이 종료된 후에 출발지 u에서 어느 목적지에 가야할때 최선의 선택을 할 수 있는 포워딩 테이블을 생성할 수 있다.

노드 u로부터의 최소비용 경로와 노드 u의 포워딩 테이블

알고리즘 복잡도

• O(n^2) : 모든 노드에 대해 반복적으로 체크해봐야한다.
• PQ를 사용하면 O(nlogn)으로 줄일 수 있다.

링크 상태 알고리즘 : 진동 문제 (ocillations possbile)

다익스트라 알고리즘은 링크의 트래픽양 (비용)에 따른다. 이는 라우터 진동(oscillations) 문제를 야기할 수 있다. 아래 링크 비용이 대칭적이지 않은 토폴로지를 살펴보자.

초기 상태는 (a)와 같다. 링크 비용은 통과하는 트래픽양에 따르고 있는 상황이다. 링크 상태 알고리즘이 다시 수행되면 (b) 노드 y는 w로가는 시계 방향의 경로 비용이 1 이지만, 반시계 방향으로의 경로 비용은 1+e임을 알게된다. 따라서 w로 가는 y의 최소비용 경로는 시계방향이다.

마찬가지로 x도 w로 가는 시계방향 경로를 새로운 최소 비용 경로로 결정한다. 링크 상태 알고리즘이 다시 한번 수행되면 노드 x, y, z 모두 w로 가는 반시계 방향의 경로 비용이 0임을 알게 되어 모든 트래픽을 반시계방향 경로로 보낸다. (c) 다음번 링크 상태 알고리즘 수행 시에는 x, y, z 모두 시계 방향으로 트래픽을 전송한다 (d)

위 상황을 보면 매번 더 나은 상황을 위해 움직이다보니, 트래픽 상황 비용을 갱신할 때마다 시계방향과 반시계방향의 경로를 계속하여 진동하듯이 방황하게 된다.

이를 해결하기 위한 한 가지 해결책은 해당 링크가 전달하는 트래픽의 양에 의존하지 않도록 하는 방법이 있다. 다른 해결책은 모든 라우터가 동시에 링크 상태 알고리즘을 실행하지 못하도록 동기화하지 않는 것이다. 하지만 흥미롭게 라우터들은 스스로 자기들끼리 점진적으로 동기화된다. (floyd synchronization) 이러한 자기 동기화는 각 노드가 링크 상태 정보를 송신하는 시각을 임의로 결정하게 함으로써 회피할 수 있다.