11주차: Net) Routing algorithm (link state, distance vector)

라우터의 두가지 주요 기능:

• forwarding : router의 input link로 들어온 패킷들을 적절한 output link로 이동시키는 것 (내보내는 것)
• routing : 어떤 패킷이 출발지로부터 도착지까지 이동하는 경로(path)를 결정하는 것

Global or Decentralized information: 

global: 모든 라우터가 전체 네트워크의 topology와 link cost에 대한 정보를 모두 가지고 있는 형태. Link State
decentralized: 각각의 라우터가 이웃한 라우터의 link cost 정보만을 가진 형태. (라우터간 정보교환으로 확장, 갱신) Distance Vector
*topology: 네트워크의 연결도
 

Static or Dynamic:

static: 라우터가 천천히 변함
synamic: 라우터가 빠르게 변함. link cost 등의 정보가 빈번하게 변화함.
 

A Link-State routing algorithm:

다익스트라 알고리즘을 사용한다.
 
모든 라우터들이 network topology와 link cost들을 모두 알고 있다.
그래프 탐색 알고리즘 중 다익스트라 알고리즘을 이용한다.
C(x, y): x에서 y 노드로 가는 link cost. 연결이 되어있지 않은 경우 무한대로 표기.
D(v): dest v까지 가는데 드는 cost
p(v): src에서 dest v까지  거친 직전 node
N': 다익스트라 알고리즘을 수행하며 거친 노드의 집합

다익스트라 알고리즘을 활용하여 그래프를 간소화 한다.

src관점에서 dest로 가기위한 첫번째 hop을 forwarding table에 기록한다.
 
worst case: O(n^2), n개의 노드가 있을 경우.
개선하면 O(nlog(n))까지 될 수 있지만 거기까지는 안 다룸..

oscillation이 생길 수 있다.
 

Distance Vector algorithm:

벨만-포드 알고리즘

u->z로 갈 때,
u는 v, x, w와 인접해 있고 v, x, w에서 z까지 가는 거리를 알고 있다.
u에서 v, x, w까지 가는 cost + v, x, w에서 z까지 가는 cost를 더한 후 min을 고르면 된다.

D값은 계속 변화한다. 이는 추정된 값이다.
갖고 있는 노드 간의 경로보다, 이웃으로부터 새롭게 받은 정보의 경로가 더 좋은 경로라면 수정하고,
이웃들에게 또다시 수정본 routing table 정보를 보내준다. 만약 수정사항이 생기지 않았으면 정보를 보내지 않는다.

위와 같은 작업을 거치기 때문에, Distance vector 알고리즘은 iterative하고 asynchronous이라고 할 수 있다.
 
 

Distance Vector: Count to Infinity Problem

bad news가 생긴 경우, 테이블을 갱신하는데 불필요한 연산이 많이 수행된다.
나중에 다시 보고 이해해보자,,,
Z가 Y에게 X로 향하는 길은 무한대라고 알려주면 된다.
 

안정성
LS: 망가진 path가 있으면 제외함
DV: 망가진 path가 있으면 그를 다 전파함