Per-router control (traditional routing algorithm) - LS, DV, Hierarchical routing

Per-router control Plane

모든 각각의 router에 이 알고리즘을 적용

Routing protocol의 목적 - 좋은 경로 찾기. 즉 거쳐야하는 router의 순서

• 최소 비용, 빠르게, 덜 혼잡이 발생하게

 

---

+) Network는 Graph로 표현

Graph G = (N, E)

N: set of routers, E: set of links (확정적으로 알려진 노드)

 

c(x1, x2) = cost of link (x1->x2) 

cost는 항상 1이며 bandwidth나 congestion에 대해 계산

c(x1, x2...xn)

D(v) : current value of cost of path from source to dest v

P(v) : v에 오는데 바로 이전 노드

 v로 가는데 지금까지 거쳐온 경로. 도착 후 경로를 알고 싶을 때 지나온 아이를 타고 가며 알아냄

 

routing algorithm은 least cost , shortest path 를 지향

 

---

Routing algorithm classification

Q1. global or decentralized info? 

• global : 각 router에 완전한 topology(connectivity, link cost)가 있는가 - Link State (LS) algorithm
• decentralized(이웃) : routers는 물리적으로 연결된 이웃과 그들의 link costs를 바탕으로 total cost를 파악.
  • 그래서 서로 cost 비용을 주고받는 과정이 필요 - Distance Vector (DV) algorithm
  • link cost에 변화가 발생했을 때 반드시 자신의 distance vector를 다시 계산해야 함

Q2. static or dynamic? 

• static : routes change slowly over time
• dynamic : routes changes more quickly

Q3. load-sensitive or load-insensitive? 

• load-sensitive: link cost가 link의 congestion의 정도를 반영
• load-insensitive : linke cost가 current level of congestion 반영 X

link state routing을 위해서는
 모든 라우터가 네트워크 토폴로지 전체 정보를 알아야 한다.

---

Dijkstra’s algorithm : Link State routing algorithm

global dynamic routing

net topology : 모든 노드에 대한 link cost를 앎 via link state broadcast

• 모든 노드가 같은 정보를 보유
• broadcast = flooding : 각 라우터의 incident한 link 정보가 네트워크 전체에 flooding 된다.

 

routing table을 이용하여 모든 노드에 대해 least cost path를 계산

세상에 n개의 노드가 있었다면

해당 노드에 대해 n번만 반복하여

이와 다른 애들 간의 최소 경로를 알 수 있음

만약 네트워크에 n개의 목적지가 있다면 

가장 가까운 목적지로의 경로가 가장 먼저 발견된다.

 

거쳐왔다는 표시가 안 된 노드에 대해서 반복

다익스트라 알고리즘의 복잡도

n(n+1)/2 -> O(n^2)

힙을 이용하면 O(nlogn)

 

ex1)

 

ex2)

 

Dijkstra’s Problem : Oscillation

Link cost를 traffic을 감당하는 정도라고 하고,

link 마다 cost가 똑같지 않을 때,

즉 C에서 e만큼, B,D에서 1만큼의 cost가 소요된다고 할 때

 

처음과 다른 경로로 계속 몰리는 현상이 반복됨

lightly loaded 경로로 모두가 모이다 보니

다같이 반대 방향으로 갔다가 순방향으로 갔다가

단체로 왔다리갔다리 난리남  (herding effect)

• 그림2를 보면 C -> A로 가는 shortest path가 D로 바뀌면, 패킷이 D에 몰리게 된다.
• 그렇다면 congestion이 발생하여 link cost가 올라가겠다. 따라서 C->A의 shortest path는 B로 바뀐다.
• 그러면 또 패킷이 B에 몰려 congestion이 발생한다. 같은 원리로 shortest path가 D로 바뀐다.
• 이 일이 반복되며, 통과하는 packet들은 congestion의 저주에서 빠져나오지 못한다.
• 출처 : http://csmylov.blogspot.com/2017/08/network-layer-control-plane.html

 

---

Bellman-Ford algorithm : distance vector algorithm

이웃들에 대해

목적지와의 거리가 제일 작은 이웃(경로)을 선택

핵심은 distance vector들이 갱신되면 나도 그에 맞게 수정되어 결합된다는 것

 

 

decentralized

자신의 이웃들의 distance vector를 알고 있어야 함

 

iterative, asynchronous

이웃들이 갱신되면 나도 갱신되는 일이 반복됨.

하지만 항상 동시에 갱신되는 것이 아닌

이웃(DV update)과 전선이 교체(link cost change)되어

더 좋은 경우가 생겼을 때 갱신되기에

비동기적

 

 

 

 

distributed

자신의 DV에 변화가 생겼을 때만 다른 이웃에게 알림

한 명이 바꿨을 때 그에 따라 나에게 정말로 갱신이 일어나야 한다면

갱신 후에 바뀐 DV vector 정보를 이웃에게 알림

 

Distance Vector routing에서 각 라우터가 자신의 distance vector를 다시 계산하는 경우
 - local link cost change
 - distance vector update message from neighbor

Distance Vector routing에서 라우터가 
이웃에게 자신의 distance vector를 새로 전송해야만 하는 경우
 - 자신의 distance vector에 변경이 발생했을 때

나의 이웃들 각각에 대해 목적지와의 거리가 짧은 이웃이 누구인지 탐색

 

노란색은 DV 업데이트

빨강 초록은 새로운 값으로 업데이트

마지막에 모든 노드의 table이 같은 값으로 수렴하여

안정적으로 각 노드는 shortest path를 알게 됨

 

 

Bellman-Ford 's Problem : Count to Infinity

link failure가 발생했을 때 일어남

 

!! Dz(x) = 5 이고, c(z,x)= 50 

x-y가 4에서 60으로 바뀌어도 

z는 알 수 없음

y는 x로의 경로를 y->x에서 y->z->x로 바꿈

근데 z는 x로의 경로를 z->y->x로 두고 있음 (4의 값만 기억하니까)

그래서 y->x가 결국에는 y->z->y->x가 되어버림

그렇게 44번 헛돌게 됨...

 

해결책1 - split horizon

A는 C에게 B로 가는 경로를 알리지 않아 routing loop 방지

 

해결책2 - split horizon with "poison reverse"

A는 C에게 B로 가는 경로를 무한대의 cost가 든다고 알려서 routing loop 방지

 

그래도  완전히 문제점을 해결하지 못함 - 3개 이상의 노드가 해당될 때

A가 D에게 B로 가는 경로가 무한대라서 알리지 않음

그런데 B가 C로 가는 경로가 있다보니 이로 인해 D가 B를 알게 됨

그래서 D가 A를 갈 때 C,B를 거치는 경로도 고민하게 됨

 

 

---

LS vs DV

LS : Link-State routing

각 라우터는 모든 노드에게 알림 

직빵으로 연결된 link의 비용만 제공

ex) OSPF, IS-IS, Dijkstra’s algorithm

 

DV : Distance-Vector routing

각 라우터는 자신과 연결된 노드에게만 알림 

자신으로부터 모든 노드들에 대한 최저 cost 측정치를 모든 이웃에게 제공

ex) RIP, BGP, original ARPAnet, Bellman-Ford

 

 

일시적 routing loop 문제가 발생할 수 있는 라우팅 알고리즘
 distance vector (O)
 link state (X)

네트워크에 malfunctioning router가 있을 때 
link state routing algorithm이 
distance vector algorithm에 비해 덜 취약하다.

 

---

Hierarchical routing

routing table을 모두 저장하기 어렵고, 이를 서로 교환하는 것 또한 ㅠㅠ

특히  각 network 별 admin도 제각각이기에 뚜렷하게 계산한 정보를 공유하기 힘듦

 

 

Hierarchical routing : Autonomous System (AS)

AS 집합으로 router를 나눔

고유한 숫자를 부여하여 식별

각 집단마다 동일한 routing policy(protocol)로 intra-AS routing protocol을 가짐

 하나의 owenership과 관리자에 의해 통제됨

 

Gateway router - AS의 edge에 위치한 router로, 다른 AS의 edge router와 연결됨

얘네들은 inter-AS routing protocol(BGP)를 사용

intra-AS routing

• 같은 AS 속 router와 host의 routing을 담당
• 그 AS 속 모든 router는 같은 intra-domain routing protocol을 실행
• 서로 다른 AS라면 다른 intra-domain routing protocol을 실행

inter-AS routing

• AS들 간에서
•  
• gateways perform inter-domain routing (as well as intra-domain routing)

 

forwarding table은 intra-AS, inter-AS routing algorithm에 의해 구성된다

- intra-AS는 그 AS 내에서의 목적지를 entries에 넣는다

- inter-AS, intra-AS 는 외부 목적지를 entries에 넣는다