[네트워크] 5.2 라우팅 알고리즘

▶ 라우팅 알고리즘: 송신자부터 수신자까지 라우터의 네트워크를 통과하는 최소비용 경로를 찾는 것
 
▶ Global vs. Decentralized 

• Global(link-state 알고리즘): 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다.
• Decentralized(distance-vector 알고리즘): 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다.

 
▶ Static vs. Dynamic

• Static: 경로 계산 cost가 변하지 않는다. --> route 계산을 자주 할 필요가 없다.
• Dynamic: 상황에 따라 경로 계산 cost가 바뀐다. --> route 계산을 자주 해야 한다. (임계치를 넘으면, route 계산을 한다.)

 

---

5.2.1 링크 상태(LS) 알고리즘: 다익스트라 알고리즘

• Global: 모든 router가 전체 네트워크 정보를 가진다.
  <-- link state broadcast: 각 router는 모든 router의 broadcast를 듣는다.
• Dynamic: 각 router 자신으로부터 최단 경로를 매번 계산해서 업데이트한다. --> forwarding table

 

다익스트라 알고리즘: example

다익스트라 알고리즘: example

: source node로부터 시작하여, 현재 N'에 속한 노드와 인접하면서 목적지로의 cost가 가장 작은 노드를 N'에 추가한다.

• 목적지로의 cost는 새로운 노드가 N'에 추가될 때마다 업데이트된다.

 

다익스트라 알고리즘: problem

다익스트라 알고리즘: problem

: 매번 cost가 바뀜에 따라(dynamic), packet이 서로 다른 경로에 의해 전송된다. (out of order delivery)
 

---

5.2.2 거리 벡터(DV) 라우팅 알고리즘

• Link-state 알고리즘: 네트워크 전체 정보를 이용하는 알고리즘
• Distance-vector 알고리즘: 직접 연결된 이웃으로부터 정보를 받고, 계산을 수행하며, 계산된 결과를 다시 이웃에게 배포한다. 이웃끼리 더 이상 정보를 교환하지 않을 때까지 프로세스가 지속된다. 

 
▶ 벨만-포드 식: (x~v) + (v~y)의 cost를 가장 낮게 만드는 v를 선택한다.

벨만-포드: example

벨만-포드: example

▷ u --> (v | x | w) --> z
: u --> x --> z의 cost가 가장 낮으므로, 중간 node로 x를 택한다.

• Bellman-Ford 방식: 각각의 이웃(v, x, w)이 목적지(z)로 얼마만에 갈 수 있는지를 알아야 한다. (세상 모든 목적지에 대해!)

 

Distance vector(DV) 알고리즘

Distance vector(DV) 알고리즘

Source = x, Destination = y, 사이의 node = {a, b, c}라고 할 때,
Dx(y) = x로부터 y까지의 최단거리를 알기 위해서는 {a, b, c} 중 어떤 node를 거쳐야 하는지 알아야 한다.
--> 이웃끼리 자신의 distance vector를 때때로 주고받아서, 결국 모든 목적지에 대해 최단의 distance vector를 계산할 수 있어야 한다.
 
▶ Distance vector가 변하는 경우:

• x --> {a, b, c}까지의 link cost가 변할 때 (change in local link cost)
• {a, b, c} --> y까지의 link cost 변할 때 (mssage from neighbor)

1. 각각의 node는 자기 자신의 link cost가 변했는지, 이웃으로부터 link cost가 변했다는 연락이 오는지 기다린다.
2. 만약 distance vector가 변했을 수 있는 둘 중의 하나의 상황이 되면, distance vector를 다시 계산한다.
3. 계산한 결과 어떤 목적지로의 distance vector가 변하면, 이웃에게 알린다.

--> 계속 계산하다가, distance vector가 더 이상 변하지 않으면, settle된다.
 
 

Distance vector(DV) 알고리즘: example

1. Direct 이웃에 대한 distance만을 알고 있다.
2. 이웃으로부터 distance vector를 듣고, 그에 맞춰 자신의 distance vector도 업데이트한다. 업데이트된 distance vector를 이웃에게 알린다.
3. 이웃으로부터 변화된 distance vector를 듣고, 자신의 distance vector를 다시 업데이트하고, 만약 변했다면 그 새로운 distance vector를 이웃에게 알린다.

--> 나의 distance vector가 더이상 변하지 않을 때까지 반복한다.
 

Distance vector(DV): link cost changes

▷ "Good news travels fast": 인접한 link cost가 줄어들면 distance vector가 변하고, 이러한 변화는 이웃에게 빠르게 전달된다.

• 원래 경로보다 더 좋은 경로가 나타났다! Distance vector를 업데이트한다!

▷ "Bad news travels slowly"

• Count to infinity: 기존 경로가 나빠졌을 때는 바꿔야 할 경로를 알아차리는 데에 시간이 오래걸린다.

 
--> Count to infinity 문제 해결책:

• Split horizon: A --> B --> C인 상황에서는, A가 C까지의 경로를 B에게는 알리지 않는다. (혼란을 막음)
• Split horizon with poisoned reverse: A --> B --> C인 상황에서, A가 C까지의 경로를 B에게 알리기는 하지만, '무한대'라고 알린다.

--> But, it does not work for routing loops involving 3 or more nodes...
 
 

LS(Link-state routing algorithm) vs. DV(Distance vector algorithm)

LS(Link-state routing algorithm) vs. DV(Distance vector algorithm)

▶ Router가 cost 정보를 알려주는 대상, 알려주는 cost 정보:

• LS: 세상의 모든 router에게, 자신과 붙어있는 router와의 direct link cost를 broadcast한다. (Dijkstra's algorithm)
• DV: 자신과 인접한 router에게만, 세상 모든 목적지에 대해 내가 알고 있는 경로 길이를 알려준다. (Bellman-Ford algorithm)

▶ Message complexity:

• LS: O(n*E) --> More, smaller messages (더 많은 router들에게, 작은 메시지를 보낸다.)
• DV: O(n-1) --> Fewer, larger messages (자신과 인접한 router들에게만, 큰 메시지를 보낸다.)

▶ Speed of convergence:

• LS: O(n^2)
• DV: count-to-infinity problem때문에, convergence time이 경우에 따라 다르다.

▶ Robustness: What happens if router malfunctions or is compromised?

• LS: 좁은 부분에 대해서는 망가지지만, 다른 부분은 괜찮다.
• DV: Error propagates through network! (네트워크 전체에 문제가 퍼져나간다!)