5-1-(1) Routing algorithm classification

chapter 5 goal: network control plane의 원칙들 이해

 

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

(1) Routing algorithm classification

- 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

 

 

Routing algorithms

 

Routing prototcol: path selection + message format & action

 

Routing protocol goal: 좋은 path란 어떤 것인지 결정하는 것

- least cost: 좋은 path란 보통, 최소한의 cost만을 사용하는 path

* Path: source host로부터 destination host까지 지나는 router 순서

* routing path의 cost가 특정하게 표현되지 않는다면 가장 적은 link를 사용하는 최단 경로

- fastest

- least congested

 

 

network의 graph적 추상화

 

G=(N,E)

graph는 node와 edge로 구성

- router ~= node

- link ~= edge

 

Cost of link

cost of link는 c(u,v) 또는 c_u,v라고 표현됨

- cost값이 명시되지 않으면 1

- bandwidth가 작을수록, congestion이 클수록 좋은 것이므로 cost 낮게 잡는 게 좋음

 

다음과 같은 네트워크가 존재한다고 할 때

c(u,w)=5

c(u,z)=무한대 => link 없으므로

 

 

Cost of path

cost of path는 지나는 노드들에 의해 결정됨

노드 순서가 x1->x2->...->xp 라고 하면

cost of path(x1, x2, x3, ..., xp)= c(x1,x2)+c(x2,x3)+ ... + c(x_p-1, xp)

 

 

=> key question

- u부터 z까지 가는 가장 good path는?

least cost 또는 shortest path를 찾으려면 routing algorithm 사용하면 됨

 

Routing algorithm classification

 

<정보를 어떻게 얻느냐에 따라>

- global: 모든 router가 똑같은 topology를 가짐

* 모든 router가 connectivity, link cost에 대한 정보 알고 있음

* "link state" algorithm이 해당

 

- decentralized: 각자 주변 이웃에게 정보 들음

* 처음에 이웃 정보만 알고 있음 => for문 사용해 route 계산

* 이웃으로 가는 path cost = link cost

* 나에게는 네트워크 전체에 대한 정보가 없지만 iteration하면 점점 아는 destination이 늘어나고 그 destination까지 가는 경로도 파악 가능

* 이웃으로부터 정보를 얻어 path 결정 가능

ex. A라는 이웃을 거치는 비용은 10, B라는 이웃을 거치는 비용은 5라고 하면 B를 선택에 path 결정을 함

* "distance vector" algorithm이 해당

 

 

<routing이 바뀌는 속도에 따라>

- static: route 가 천천히 변화

* route cost 자체가 static하기 때문 => 변화가 발생할 때마다 업데이트 가능

 

- dynamic

* network의 변화에 따라 route를 업데이트해야 하므로 route가 자주 바뀜

* link가 바뀌는 일은 거의 없지만 link의 bandwidth, level of congestion은 자주 바뀌기 때문에 

이렇게 변하는 link cost에 적응하려면 dynamic한 algorithm이 필요

* network 변화에 민감하게 반응한다는 것은 장점이지만, dynamic한 정도(큰 변화가 있을 때마다/작은 변화가 있을 때마다 등..)가 천차만별이므로 업데이트할 때가 불분명 => periodic하게, 또는 triggered update 실행