링크 상태(LS) 라우팅 알고리즘

각 노드가 자신과 연결된 링크의 식별자와 비용을 포함하는 링크 상태 패킷을 네트워크상의 모든 다른 노드로 브로드캐스팅

=> 네트워크 토폴로지와 모든 링크 비용이 알려져 있어 입력값으로 사용 가능

노드들의 브로드캐스트를 통해 모든 노드는 네트워크에 대한 동일하고 완벽한 관점을 갖게 된다.

각 노드는 LS 알고리즘을 이용해 다른 노드와 똑같은 최소 비용 경로 집합을 계산할 수 있다.

아래에서 설명할 링크 상태 알고리즘은 다익스트라 알고리즘(Dijkstra's algorithm)이라 하고, 프림 알고리즘(Prim's algorithm)도 해당 알고리즘과 관련되어 있다.

 

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

하나의 노드(출발지, u라고 지칭)에서 네트워크 내 모든 다른 노드로의 최소 비용 경로를 계산

다익스트라 알고리즘은 반복적이고, 알고리즘의 k 번째 반복 이후에는 k 개의 목적지 노드에 대해 최소 비용 경로가 알려지며 이 k 개의 경로는 모든 목적지 노드로의 최소 비용 경로 중에서 가장 적은 비용을 갖는 k 개의 경로이다.

기호 정의

D(v) : 알고리즘의 현재 반복 시점에서 출발지 노드부터 목적지 v까지 최소 비용 경로의 비용

p(v) : 출발지에서 v까지의 현재 최소 비용 경로에서 v의 직전 노드(v의 이웃)

N' : 노드의 집합. 출발지에서 v까지의 최소 비용 경로가 명확히 알려져 있다면, v는 N'에 포함

 

중앙 집중형 라우팅 알고리즘 => 초기화 단계와 반복 부분으로 구성

반복 부분의 수행 횟수 : 네트워크의 노드 수

루프 수행 종료 후 : 출발지 노드 u에서 네트워크상의 모든 다른 노드로의 최단 경로를 산출

 

출발지 노드 u를 대한 링크 상태 알고리즘

초기화 단계

Initialization :
    N' = {u}
    for all nodes v
        if v is a neighbor of u
            then D(v) = c(u, v)
        else D(v) = INF

 

• N'는 최단 경로가 확정된 노드들의 집합
• 시작 노드 u를 N'에 먼저 포함
• 모든 노드 v에 대해:
  • v가 u의 이웃 노드라면 → D(v)는 u에서 v까지의 직접 링크 비용 c(u, v)로 설정
  • v가 u의 이웃이 아니라면 → D(v)는 무한대(INF)로 설정

반복 단계 (Loop)

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))

 

 

• N'에 포함되지 않은 노드들 중에서 현재 D(w)값이 가장 작은 노드 w 찾기
• 찾은 노드 w를 N'에 추가 
• w의 이웃 노드들 중 N'에 포함되지 않은 모든 노드 v에 대해 거리 값 갱신:
  • 기존 D(v) 값과 (D(w) + c(w, v))를 비교하여 더 작은 값으로 갱신
  • D(w) + c(w, v)는 u에서 w를 거쳐 v로 가는 경로의 비용

종료 조건

until N' = N

 

 

• N'이 전체 노드 집합 N과 같아질 때까지 반복
• 즉, 모든 노드에 대한 최단 경로가 확정될 때까지 계속됨

주요 특징:

• 각 라우터는 자신을 출발점으로 하여 네트워크의 모든 노드까지의 최단 경로를 계산
• 각 반복마다 하나의 노드에 대한 최단 경로가 확정
• 그리디(Greedy) 방식으로 동작하며, 항상 현재까지 알려진 가장 짧은 경로를 선택
• 음수 가중치가 없는 경우에만 정상적으로 동작

 

시간 복잡도 : 

첫 번째 반복 : 이미 계산된 노드의 집합 N'에 포함되지 않은 노드 w를 결정하기 위해 모든 n개의 노드 검사

두 번째 반복 : 이미 계산된 노드의 집합 N'에 포함되지 않은 노드 w를 결정하기 위해 모든 n-1개의 노드 검사

...

=> 최악의 경우 n(n+1)/2 개 노드 검사, O(n^2) 

 

힙 자료 구조 활용한 개선된 방식은 선형 시간이 아닌 로그급수 시간으로 최솟값을 찾을 있어 시간복잡도 : O(nlogn)으로 구현 가능

 

 

 

참고 도서 :

컴퓨터 네트워킹 : 하향식 접근(7판) - James F. Kurose , Keith W.Ross 지음