Link-State Routing Algorithm에 사용되는 Dijkstra's algorithm

Link-State Routing Algorithm을 사용하기 위해서는  Global Information이 필요하다. Link-State Algorithm을 사용하는 라우팅 프로토콜로는 OSPF가 있다.

Global Information이 필요하다는 것은 모든 라우터가 완전한 연결형태와 링크비용 정보를 알고 있어야 한다는 것이다.


다음 예를 통해 Dijkstra's Algorithm이 어떻게 최단경로를 설정하게 되는지 알아보자.

* 먼저 아래 D()와 p()의 의미를 기억한다.
D(v) : 노드 v로 갈수 있는 최단 경로 비용
p(v) : 노드 v로 가는 최단 경로에서 노드 v 바로 이전에 방문한 노드

노드 u(u라우터) 에서 라우팅 테이블을 작성하고자 하는 경우를 생각한다. (노드 u에서 출발)

단계     방문할수 있는 노드     D(v),p(v)    D(w),p(w)    D(x),p(x)    D(y),p(y)    D(z),p(z)
  1                   u                     2, u              5, u            1, u            ∞               ∞

먼저 첫번째 단계에서는 노드 u에서 출발하므로 노드 v,w,x로만 갈수 있다. 노드 y, z의 경우 u와 직접적인 링크가 없으므로 링크 비용은 무한대(∞)가 된다.
이 단계에서 노드 v, w, x로 가는데 필요한 비용은 u에서 직접연결된 링크의 비용이고 각 노드를 방문하기 바로 이전에 방문한 노드는 모두 노드u 가 된다.
이렇게 D()와 p()의 값을 계산한뒤 가장 적은 비용으로 방문할 수 있는 노드를 선택한다. 첫번째 단계에서 D(x)가 1로 가장 값이 작으므로 노드 x를 선택한다.

단계     방문할수 있는 노드     D(v),p(v)    D(w),p(w)    D(x),p(x)    D(y),p(y)    D(z),p(z)
  1                   u                     2, u              5, u            1, u            ∞               ∞
  2                  ux                     2, u              4, x                            2, x             ∞

다음 단계에서는 노드 u에서 출발하여 노드 u에서 직접 가거나, 노드 x를 거쳐서 갈 수 있는 노드의 최단경로 값을 계산한다.
노드 x는 이전 단계에서 방문한 것으로 선택하였으므로 이후 단계에서는 D(),p()값을 계산하지 않는다.
노드 v의 경우 단계1에서와 같지만 노드 w와 노드 y를 방문하는 비용이 변한 것을 볼 수 있다.
노드 u에서 출발하여 노드 w로 가는 최단 경로는 직접 노드 u에서 가는 비용보다 노드 x를 거쳐 노드 w로 가는 것이 비용이 더 작기 때문에 그 값인 4를 적는다.
노드 y로 가는 경로의 경우 단계1(u에서직접갈수있는경우)에서는 경로가 없었지만 노드 x를 거쳐 노드 y로 갈 수 있게 되었기 때문에 경로가 생겼다.
이번 단계에서는 방문 할 수 있는 노드중에 최단비용으로 갈 수 있는 노드가  v와 y이다.
이런 경우 어떤 노드를 선택하든 상관이 없다.
여기서는 노드 y를 선택한다.

단계     방문할수 있는 노드     D(v),p(v)    D(w),p(w)    D(x),p(x)    D(y),p(y)    D(z),p(z)
  1                   u                     2, u              5, u            1, u            ∞               ∞
  2                  ux                     2, u              4, x                            2, x              ∞
  3                 uxy                    2, u             3, y                                              4, y

이번 단계에서는 노드 u에서 출발하여 직접 갈수 있거나 노드 x나 노드 y를 통해 아직 방문하지 않은 노드를 방문할 수 있는 최단 경로의 값을 구한다.
언제나 시작점은 u라는 것을 잊으면 안된다.
노드 u에서 시작하여 노드 w로 가는 최단 경로는 u -> x -> y -> w 이기 때문에 D(w)는 3이 되고 p(w)는 y가 된다.
노드 u에서 노드 z로 가는 최단 경로는 u -> x -> y -> z 이고 D(z)는 4, p(z)는 y가 된다.
이중에서 방문할 수 있는 가장 짧은 경로는 노드 v를 방문하는 경우이므로 노드 v를 선택한다.

단계     방문할수 있는 노드     D(v),p(v)    D(w),p(w)    D(x),p(x)    D(y),p(y)    D(z),p(z)
  1                   u                     2, u              5, u            1, u            ∞               ∞
  2                  ux                     2, u              4, x                            2, x              ∞
  3                 uxy                    2, u              3, y                                              4, y
  4               uxyv                                        3, y                                             4, y

이번 단계에서는 아직 방문하지 않은 노드를 방문할 수 있는 더 짧은 경로가 생기지 않았다.
여기서 선택할 수 있는 가장 짧은 경로는 w를 방문하는 것이다.

단계     방문할수 있는 노드     D(v),p(v)    D(w),p(w)    D(x),p(x)    D(y),p(y)    D(z),p(z)
  1                   u                     2, u              5, u            1, u            ∞               ∞
  2                  ux                     2, u              4, x                            2, x              ∞
  3                 uxy                    2, u              3, y                                              4, y
  4               uxyv                                        3, y                                              4, y
  5             uxyvw                                                                                          4, y

마지막으로 z를 선택하면 모든 노드를 방문하게 된다.

이러한 과정을 통해 얻어진 최단 경로 그래프는 위와 같으며
노드 u에서 만들어진 포워딩 테이블은 다음과 같다.

목적지 노드       포워딩할 링크(출력방향)
      v                     (u, v)                    
      x                     (u, x)                    
      y                     (u, x)                    
      w                    (u, x)                    
      z                     (u, x)                    

이 포워딩 테이블의 의미는 노드 u에 들어온 패킷의 목적지가 노드 v라면 노드 v쪽으로 패킷을 포워딩 해야 한다는 것이다.
만약 목적지 노드가 w인 경우엔 노드 w로 가는 최단경로가 노드 x를 거쳐서 가는 것이므로 노드 x로 패킷을 포워딩 하게 된다.

다시 말하면 이렇게 얻어진 포워딩 테이블을 통해 자신에게 온 패킷을 어디로 보내야 가장 빨리 목적지에 도착할 수 있게 되는지 알 수 있다는 것이다.


이렇게 Link-State방식을 사용한 라우팅 알고리즘의 장점은 일단 테이블이 정해지면 링크가 변경될때 까지 control traffic이 없다는 것이다.

단점은 계산하기전에 모든 노드가 모든 링크의 값을 알기위해 링크의 정보를 주고 받는 단계가 있다는 것이다.