5-1-(1) Link state routing algorithm: Dijkstra's 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

 

 

Dijkstra's link-state routing algorithm

 

link state

자신의 이웃들에 대한 정보

 

algorithm 시나리오

link state를 broadcast하여 다른 router(node)들과 공유한다.

=> 모든 router들이 동일한 topology 가짐(centralized)

=> 바탕으로 다른 모든 router들로 가는 least cost path 계산(Dijkstra's link-state routing algorithm)

* destination 수만큼 반복

=> 계산 바탕으로 forwarding table 작성하여 router에게 줌

 

algorithm notation

 

v가 destination이라면

- c_x,y: x에서 y로 가는 direct link cost

* direct link가 없다면 c_x,y=무한대

- D(v): 현재 iteration 단계까지 알려진 least cost path의 cost

- p(v): destintion v로의 predecessor

* v 바로 전의 node

- N': 최종적으로 least cost path가 알려진 node들의 집합

 

Dijsktra's Algorithm

 

Initialization:
	N^={u} /* 처음에는 source u로부터의 이웃 path만 알려져 있음*/
    for all nodes v /* N^에 속하지 않은 모든 노드들에 대해*/
        if v adjacent to u /* v와 u 사이에 direct link 있다면(이웃이라면)*/
            then D(v)=c_u,v /* minimum cost는 아닐 수 있음*/
        else D(v)=무한대
    
Loop:/*이웃이 아닌 노들로의 확장 => node 개수만큼(n-1)*/
	find w not in N^ such that D(w) is a minimum /*N^는, 아직 route가 결정되지 않은 것들(~N^) 중 distance가 최소인 것으로 설정해둠*/
    add w to N^ /*D(w)가 minimum인 것을 골라 N^에 집어넣음*/
    update D(v) for all v adjacent to w and not in N^:/*아직 path 확정되지 않은 노드들에 대해서*/
    	D(v)=min(D(v), D(w)+c_w,v) */N^에 새롭게 추가된 노드 w에 대해 D(w)와 w에서 건너갈 때의 cost 합*/
        
/*모든 노드가 N^에 들어갈 때까지*/

 

 

Example

 

(ex1)

다음과 같은 네트워크에서 Dijsktra's Algorithm 사용해 표를 작성해보자.

 

 

Step 0(u)

N': cost가 확정된 노드는 u뿐

D(v): u->v의 least cost path cost=2

p(v): v 이전 노드는 u

D(w): u->w의 least cost path cost=5

p(w): w 이전 노드는 u

D(x): u->x의 least cost path cost=1 "최솟값"

p(x): x 이전 노드는 u

D(y): u에서의 direct link 없으므로 무한대

D(z): u에서의 direct link 없으므로 무한대

 

Step 1(x 추가)

노드 x가 최솟값이므로 확정->N'에 속할 수 있음

아직 N'에 들어오지 못한 v,w,y,z 중 x와 adjacent한 노드들(v,w,y)에 대해 업데이트

N': cost가 확정된 노드는 u,x

D(v): u->v의 least cost path cost=2

* u->x->v 보다 u->v가 더 적은 cost

p(v): v 이전 노드는 u

D(w): u->w의 least cost path cost=4

* u->w(5)보다 u->x->w(4)가 더 적은 cost

p(w): w 이전 노드는 x

D(x), p(x)는 실행 안 함

D(y): u->y의 least cost path cost=2 "최솟값"

* u->x->y(2)

p(y): y 이전 노드는 x

D(z): x에서의 direct link 없으므로 무한대

 

Step 2(y 추가)

노드 y가 최솟값이므로 확정->N'에 속할 수 있음

아직 N'에 들어오지 못한 v,w,z 중 y와 adjacent한 노드(w,z)에 대해 업데이트

N': cost가 확정된 노드는 u,x,y

D(v): u->v의 least cost path cost=2 "최솟값"

* u->v가 가장 적은 cost

p(v): v 이전 노드는 u

D(w): u->w의 least cost path cost=3

* u->x->w(4)보다 u->x->y->w(3)가 더 적은 cost

p(w): w 이전 노드는 y

D(x), p(x)는 실행 안 함

D(y), p(y)도 실행 안 함

D(z): u->z의 least cost path cost=4

* u->x->y->z(4)

p(z): z 이전 노드는 y

 

Step 3(v 추가)

노드 v가 최솟값이므로 확정->N'에 속할 수 있음

아직 N'에 들어오지 못한 w,z 중 v와 adjacent한 노드(w)에 대해 업데이트

N': cost가 확정된 노드는 u,x,y,v

D(v), p(v) 실행 안 함

D(w): u->w의 least cost path cost=3 "최솟값"

* u->x->y->w(3)가 가장 적은 cost

p(w): w 이전 노드는 y

D(x), p(x)는 실행 안 함

D(y), p(y)도 실행 안 함

D(z): u->z의 least cost path cost=4

* u->x->y->z(4)

p(z): z 이전 노드는 y

 

Step 4(w 추가)

노드 w가 최솟값이므로 확정->N'에 속할 수 있음

아직 N'에 들어오지 못한, v와 adjacent한, 노드(z)에 대해 업데이트

N': cost가 확정된 노드는 u,x,y,v,w

D(v), p(v) 실행 안 함

D(w), p(w) 실행 안 함

D(x), p(x) 실행 안 함

D(y), p(y) 실행 안 함

D(z): u->z의 least cost path cost=4

* u->x->y->z(4)

p(z): z 이전 노드는 y

 

Step 5(z 추가)

 

 

 

그래서 least cost path tree을 표시해보면 다음 빨간색 화살표들이다.(p()끼리 연결해주면 된다.)

u로부터의 outgoing link 두 개를 각각 1, 0으로 표시할 때

v로 갈 때만 1로 나가고 나머지는 0으로 나가기 때문에 다음과 같은 forwarding table을 얻을 수 있다.

 

(ex2)

 

 

 

(ex3)

시험에 꼭 나온다니까 밑 예제도 풀어보깅

 

algorithm complexity

 

n개의 노드가 있을 때

n번을 반복해야 하고 모든 노드를 체크해야 하므로 

 

n+(n-1)+(n-2)+...+1 = n(n+1)/2 번의 비교가 필요함.

=> 복잡도: O(n^2)

 

but,,, heap을 사용한다면 복잡도가 더 적게 나올 수 있음

=> 복잡도: O(nlogn)

장점

1. global info이므로 모든 라우터들이 활용 가능

2. loop가 없는 path를 결정할 수 있음(loop가 있으면 목적지로 가지 못하고 계속 반복할 수도)

* router들이 모두 네트워크 전체 topology 아는 상황에서 path 결정할 수 있기 때문에 loop 없을 수 있음

 

message complexity

 

="root를 계산하기 위해서 네트워크 상 메시지가 얼마나 발생해야 하는지"

 

모든 edge에 대한 정보가 모든 router로 알려져야 함(broadcasting)

노드 개수=n, link 개수=E라고 하면

=> 복잡도: O(|n|*|E|)

* node가 많아질수록, edge가 많아질수록 복잡도 증가

 

 

Problem of Dijkstra's Algorithm

 

link cost가 traffic volume에 의해 발생할 때

route oscillation이 발생할 수 있음

 

D와 B는 1unit만큼의 traffic을 A에 보내길 원하고

C는 e만큼의 traffic을 A에 보내길 원한다.

 

초기 link cost가 모두 0일 때

D->A와 B->A의 cost는 1,

C->A의 cost는 e이고, B나 D를 거쳐야 한다.

가령 B를 선택했다고 한다면 다음과 같이 cost를 표현할 수 있다.

 

cost가 더 낮은 경로 선택을 선호하게 되므로 이렇게 되면 반대쪽으로 보낼 것이다.

그러면 반대로 지난 경로, 즉 빨간색 경로들의 cost가 높아진다.

 

그러면 또 반대로 cost가 비교적 낮은 반대 경로로 틀게될 것이다.

그러면 또 가격이 비교적 낮아진 반대쪽으로 경로를 틀게될 것이다.

 

이렇게, cost가 더 낮은 쪽으로 몰리는 상황을 herding effect라고 한다.

이 상황을 피하기 위해 traffic들을 내보내는 시간을 제각각으로 달리 한다고 해도 어느새 synchronize된다면

또 이 상황이 발생하게 될 것이다.

또 이렇게 dynamic한 cost보다는 static한 cost 모델을 사용하는 대안 또한 좋지 않다.

random한 시점에 advertise 함으로써 herding effect 를 좀 줄일 수 있다.