5-1-(1) Distance vector algorithm: Bellman-Ford algorithm

5-1. Traditional routing algorithms(per-router control)

(1) Routing algorithm classification

- Link state routing algorithm: Dijkstra's algorithm(OSPF)

- Distance vector algorithm: Bellman-Ford algorithm

- Hierarchical routing(BGP)

(2) Routing protocols

- RIP, OSPF/BGP

 

5-2. SDN controllers(logically centralized control)

ㄴ OpenFlow, ODL, ONOS controllers

(1) Network management, configuration

- Internet Control Message Protocol(ICMP)

- SNMP, YANG/NETCONF

 

Bellman-Ford algorithm

 

RIP, BGP 에 사용되는 알고리즘이다.

 

즉, 중간 지점 노드(예컨대 v)를 잡고 u에서 v까지 가는 cost와 v에서 목적지까지 가는 cost로 분리해 나중에 더한다는 것이다.

그리고 그 값을 각 노드마다 산출해 비교하는 것.

다음과 같은 예제를 가정하면

 

경유 노드가 각각 v, x, w인 경우 중 가장 최소 비용을 고르면 된다.

 

x를 경유하는 것이 최소 비용을 야기함

=> D_u(z) = u가 z로 가는 least cost path의 cost = 4

x를 다음 노드로 두고 최소 비용 찾는 과정을 반복한다.

계속 반복하면 최소 비용을 도출할 수 있게 된다.

 

DV algorithm

 

1. (wait) local link cost 변화 혹은 이웃으로부터의 msg를 기다린다

* local link cost에 변화가 생기거나 이웃으로부터 msg가 오면 DV가 달라짐 !

2. (recompute) 이웃으로부터의 DV를 사용해 DV를 다시 계산

3. (notify) DV가 변화하면 이웃에게 notify

* 변화하지 않았으면 굳이 알리지 않음

 

 

- 이 iteration은 각 노드가 자신의 DV를 recompute하는 시점이 제각각일 것이므로

asynchronous하다.

- DV에 변화가 있을 때만 이웃에게 알려주기 때문에 지속적으로 변화가 없다면 self-stopping

 

 

DV example

 

<이웃으로부터의 msg>

(ex1)

t=0: 모든 노드들은 자신의 이웃들로의 거리만 가지고 있음

=> 이 local distance를 각자 이웃에게 알려줌

t=1: 모든 노드들은 이웃들로부터 DV를 받음 => 새로운 local DV를 계산 => 그 결과를 다시 이웃에게 보냄

 

 

 

이 t=1일 때의 과정을 t=2, t=3, ... 일 때 반복한다.

 

(ex2)

b의 기준에서 봤을 때 

 

t=0일 때 이렇게 이웃들로부터 DV 정보가 들어오면

 

t=1일 때 b는 그 정보를 참고하여 새로운 DV들을 compute한다. (이웃노드 통해 목적지 가는 방법 추가)

그리고 b는 새로운 DV들을 통해 자신의 DV를 업데이트한다.

 

c의 입장에서 한 번 더 보자.

t=0일 때 b로부터 DV 정보를 받고

 

 

t=1일 때 새로운 DV(c로부터 각 노드로 가는 least cost path) compute를 시작한다.

이때, c의 알려진 이웃은 b뿐이므로 후보는 'b를 거쳐 각 노드로 가는 것' 딱 하나다.

 

이렇게 t=1에서 했던 과정을 반복하면 된다.

그러면 다음과 같이 한 hop을 지날 때마다 영향을 미치는 범위가 넓어져 t=4에서는 비로소 전체 네트워크에 영향을 미칠 수 있게 되는 거다.

 

<link cost change로 인한 DV 변화>

(ex1)

node가 자신 주변의 link cost에 변화를 인지

=> routing info 업데이트하고 local DV 다시 계산

=> DV가 바뀐다면 이웃에게 notify

 

 

- 좋은 시나리오

x-y link cost가 1로 줄어들 때

t=0: link cost 변화 감지 => DV 업데이트 => 이웃들에게 통보

t=1: z가 y로부터 업데이트 정보 얻음 => DV 업데이트 => 이웃들에게 통보

t=2: y가 z로부터 업데이트 정보 얻음 => DV 변화 없음 => 이웃들에게 알리지 않음

 

 

- 나쁜 시나리오

x->y link cost가 60으로 늘어날 때 count to infinity 문제 발생 => Dijkstra와 달리 loop을 하게 되면서 생기는 문제 !!

예컨대

y는 z로부터 D_z(x)=5였다는 정보를 기억하고 있다.

=> y가 D_y(x)=1+1+4=6라고 계산해 업데이트한다.

=> z가 D_z(x)=1+1+1+4=7라고 계산해 업데이트한다.

=> y가 D_y(x)=1+1+1+1+4=8라고 계산해 업데이트한다.

=> 반복..

=> DV가 50이 될 때까지 반복하고 그때서야 잘못됐음을 인지

=> "count to infinity"

 

이러한 count to infinity 문제를 다음과 같은 두 가지 방식으로 해결할 수 있다.

 

(solution1) Split horizon

"z가 x에 대한 정보를 y에게 제공하지 않기"

 

 

(solution2) Split horizon with poisoned reverse

"z가 D_x=무한대라고 말하기"

그러면 direct link 없다고 생각하고 y는 x를 거쳐가는 방법을 고려하지 않게 됨

=> y는 x로 가는 DV=60이라고 z에게 전달

=> z는 y를 통해 가지 않고 x에게 바로 가서 DV=50

 

하지만 이 두 해결법은 loop가 두 개의 노드 사이에서만 발생할 때만 도움이 된다.

세 가지 이상의 노드에서 Loop가 발생하는 경우를 살펴보자.

 

<C->D = a>

A는 DV 방향이 A->C->D이기 때문에, C에게는 무한대를 말하고, B에게는 1+a를 말한다.

=> B는 DV 방향이 B->A->C->D이기 때문에, B에게는 무한대를, C에게는 2+a를 말한다.

 

 

<C->D가 a에서 무한대로 변했을 때>

C는 B를 통해 가기로 결정하고 DV=12+a임을 A에게 말한다.

=> A는 C를 통해 가기 때문에 DV=13+a임을 B에게 말한다.

=> B는 DV=14+a임을 C에게 말한다.

=> C는 DV=24+a임을 A에게 말한다.

=> A는 DV=25+a임을 B에게 말한다.

=> ...반복...

 

LS(link state) vs DV(Direct Vector)

 

	LS	DV
소통 양상	- 모든 노드들은 다른 모든 노드들과 소통 가능 - 다른 노드들에게 알리는 것은 직접 연결된 link cost들 - ex. OSPF, IS-IS, Dijkstra's algorithm	- 모든 노드들은 자신의 이웃하고만 소통 - 이웃에게 알리는 것은 모든 노드들로의 least-cost 추정치 - ex. RIP, BGP, ISO IDRP, Novel IPX, ARPAnet: Bellman-Ford algorithm
message complexity	O(|n| * |E|) n개의 노드가 E개의 link에 대한 link cost 알면 됨 고정된 값 -> more, smaller msg	O(|n|-1) 자신을 제외한 다른 모든 노드에 대한 DV 몇 번을 주고받아야 route가 정해지는지는 모름 -> n개의 node를 가지고 있다면 n개의 DV를 포함하므로 larger msg -> 하지만 몇 번만에 끝나는지는 모르므로 fewer(?) msg
speed of convergence	- O(n^2) algorithm 사용 - 몰리는 현상이 발생하면 oscillation 발생 가능 but, cost value가 동적으로 변하진 않으므로 convergence good	- cost value가 동적으로 변하기 때문에 convergence 어려움 - routing loop가 발생하여 count-to-infinity 문제 발생 가능
robustness	- malfunctioning router 존재 가능 but 그 router를 지나지 않는 경우에는 문제 발생 x	- malfunctioning router 존재하면 큰 문제 각 노드는 모든 목적지에 대한 DV를 알리기 때문에 다 뜯어고쳐야 함