Routing Algorithm(라우팅 알고리즘)

라우팅 알고리즘

라우팅 알고리즘은 송신자로 부터 수신자까지 데이터를 전송할 때 라우터를 통과하는 최상의 경로를 선택하는 것이다.

우리가 고려해볼 요소는 비용, 속도, congestion이 있을 것이다.

비용은 어떻게 정의하냐에 따라 달라질 수 있다.

그러면 우리는 가장 빠르고, 가장 짧은 경로를 최상의 경로라고 생각할 수 있을 것이다.

즉, 거치는 라우터의 개수가 적거나, 아니면 라우터에서 발생하는 congestion이 적어서 빠르게 전송할 수 있는 경우를 말한다.

 

 

우리는 네트워크를 그래프로 표현할 수 있다.

네트워크 그래프

 

여기서 v, w와 같은 node는 라우터가 되고, node끼리 연결한 것을 edge라고 한다.

각 엣지에는 비용이 적혀져 있다.

예를 들어 c(w,z)는 w와 z를 연결하는 엣지의 비용이므로 5가 될 것이다.

 

그러면 노드 u에서 노드 z까지의 비용은 어떻게 될까?

c(u,z)이므로 c(u,v) + c(v, w) + c(w,z) 또는 c(u,x) + c(v, w) + c(x,y) + c(y, z) 와 같이 여러 가지 경로에 대한 비용이 나올 수 있을 것이다.

그렇다면, 이중에서 최소 비용을 가지는 경로는 어떤 것일까?

그리고, 최단 경로는 어떤 것일까? 

이러한 물음에 답하기 위해 사용하는 것이 바로 라우팅 알고리즘이다.

 

 

 

라우팅 알고리즘은 다음과 같이 분류할 수 있다.

 

1. global 또는 decentralized

 

- global네트워크 전체에 대한 정보(라우터들의 연결 상태, link 비용)를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산하는 방식이다. 최소 비용 경로를 계산하기 전에 네트워크에 대한 정보는 control agent나 아니면 각 라우터의 라우팅 모듈을 통해 복사하는 방식으로 알 수 있다.이러한 방식을 취하는 예로 link state 알고리즘이 있다.

 

- decentralized

라우터들이 자신과 실질적으로 연결된 이웃 노드(라우터)들에 대한 정보(비용)만 알고 있는 상태에서 시작한다.

라우터들은 반복된 계산과, 이웃 노드들과의 정보 교환을 통해 출발지와 목적지 사이의 최소 비용 경로를 계산한다.

이러한 방식을 취하는 예로 distance vector 알고리즘이 있다.

 

 

2. static 또는 dynamic

 

- static

라우터가 한 번 경로를 결정하면 잘 바뀌지 않는다.

 

- dynamic

주기적으로 업데이트 하여 네트워크의 link cost가 변화할 때 마다 이것에 대응하여 경로를 재설정 한다.

이 방식은 네트워크 변화에 빠르게 반응할 수 있지만, loop, oscillation 같은 문제에 취약하다는 단점이 있다.

 

 

 

---

 

 

link state

link-state broadcast 알고리즘에 의해, 모든 노드들은 네트워크 상의 모든 정보들을 알 수 있다.

하나의 노드로 부터 모든 다른 노드들까지의 최소 비용을 계산한다.

즉, n개의 다른 노드들이 있을 때, n번 반복하여 n개의 노드들 까지의 최소 비용을 계산하는 것이다.

 

이 알고리즘은 Dijkstra's 알고리즘이라고도 불린다.

 

알고리즘을 시작하기에 앞서, 몇 가지 정의할 점이 있다.

• c(x,y): 노드 x, y사이의 link cost이다. 만약 두 노드가 연결되어 있지 않다면, 이 값은 ∞일 것이다.
• D(v): 현재 반복 시점에서 출발지로 부터 목적지 v까지의 최소 경로 비용이다.
• p(v):  출발지에서 v까지의 현재 최소 비용 경로에서 v의 직전 노드이다.
• N': 노드들의 집합이다. 출발지에서 v까지의 최소 비용 경로가 구해져 있다면, v는 N'에 포함된다.

Initialization:
 N'= {u}
 for all nodes v
  if v adjacent to u
   then D(v) = c(u,v)
  else D(v) = ∞

Loop
 find w not in N such that D(w) is a minimum
  add w to N
  update D(v) for all v adjacent to 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
     shortest path cost to w plus cost from w to v */  
until all nodes in N

 

 

이렇게 말로만 설명하면 이해가 잘 되지 않으니 예시를 통해 보도록 하자.

다음과 같은 네트워크 그래프가 있을 때 link state 알고리즘을 통해 아래 표를 채워보도록 하자.

이 그래프에서 출발지는 u이고, 도착지는 z이다.

 

예시 그래프

step 0. 

u:  7,u / 3,u / 5,u / ∞ / ∞

 

step 1.

3,u가 제일 비용이 작기 때문에 w가 선택되어 N'에 들어간다.

p(v)에서 7,u 와 6,w 중 6이 더 작기 때문에 6,w가 선택된다.

uw: 6,w /   / 5,u / 11,w / ∞

 

step2.

5,u가 제일 비용이 작기 때문에 x가 N'에 들어간다.

uwx: 6,w /   /   / 11,w / 14,x

 

step3.

6,w가 제일 비용이 작기 때문에 v가 N'에 들어간다.

uwxv:   /   /   / 10,w / 14,x

 

step4.

10,w가 제일 비용이 작기 때문에 y가 N'에 들어간다.

uwxvy:   /   /   /   / 12,y

 

step5

uwxvyz

모든 노드들이 N'에 포함되었으므로 반복을 종료한다.

 

계산 과정이 쓰여진 표

 

 

 

하지만 여기서는 oscillation이라는 문제가 발생할 수 있다.

 

 

oscillation 발생 예시

노드 B는 1, C는 e, D는 1만큼의 트래픽을 가진다.

초기 상태에서 D에서 A로 갈 때는 D의 트래픽이 1이니, 1만큼의 비용이 발생하고, C에서 A로 갈 때는 e+1 만큼의 비용이 발생한다.

C의 라우터는 시계방향으로 가는 것이 반시계방향으로 가는 것보다 비용이 적게 드는 것을 감지하고, 시계방향으로 경로를 바꾼다.

그 후, B에서 시계방향으로 가는 것은 2+e 만큼의 비용이 필요하고, 반시계방향은 0만큼의 비용이 필요하다는 것을 라우터가 다시 감지한다. 

따라서 반시계방향으로 경로를 바꾸고, 다시 비용을 인지하여 다시 시계방향으로 경로를 바꾼다.

 

 

그렇다면 oscillation을 해결할 수 있는 방법이 있을까?

oscillation이 발생하는 것을 방지하려면, 모든 라우터들이 동시에 link state 알고리즘을 수행하지 못하도록 하면 된다.  

 

 

 

---

 

 

distance vector

노드 x부터 노드 y까지의 최소 비용 경로의 비용을 dx(y) 라고 하면,

최소 비용은 Bellman-Ford 식에 의해 다음과 같은 식으로 나타낼 수 있다.

 

dx(y) = min {c(x,v) + dv(y)

 

 

 

이 그림에서 Bellman-Ford 식을 적용해보자.

dv(z) = 5, dx(z) = 3, dw(z) = 3일 것이다.

그러면 du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } 라고 생각할 수 있다.

따라서 du(z) = min { 7, 4, 8 } = 4 이다.

 

 

 

그렇다면 distance vector 알고리즘은 어떻게 되는 것일까?

 

distance vector 알고리즘에서, 알고리즘을 수행하는 노드가 자신과 이웃 사이 링크의 비용이 변경된 것을 알게되면, 자신의 거리 벡터를 갱신하고, 최소 비용 경로의 비용에 변화가 있는 경우 이웃에게 새로운 거리 벡터를 보낸다.

 

예시를 한 번 보자.

 

 

 

 

 

그러면  distance vector 알고리즘에는 어떤 문제가 있을까?

 

 

이렇게 link cost가 감소하는 경우 적은 수의 iteration으로도 최소 거리 비용 계산을 업데이트 할 수 있다.

그런데 만약 link cost가 증가하였다면?

 

t0에서 y가 link cost 변화를 감지하고, x까지의 새로운 최소 비용 경로를 계산한다.

dy(x) = min { c(y,x)+dx(x), c(y,z)+dz(x) } = { 60+0, 1+5 } = 6

 

왜 이렇게 잘못된 결과가 발생했을까?

노드 y는 현재 x까지 직접 가는 비용이 60이고, 가장 최근에 z로 부터 받은 x까지 가는데 최소 비용이 5라는 것이다.

그래서 t1에서 y는 z로의 경로 설정을 하고, z는 y로의 경로 설정을 한다.

즉, 라우팅 loop가 발생하게 된다.

 

이렇게 44번의 반복된 loop 끝에 z에서 x로 가는 비용이 50임을 인지할 수 있다.