지난 시간 배운 내용

각각의 router가 control plan을 갖고 있고, 독립적으로 path selection algorithm을 running하는 decentralized routing protocol을 보고 있음.

Link State Algorithm

내가 속한 ISP의 각 link의 상태 정보를 global하게 수집해 와서,

path selection algorithm을 running 하기 전에 내가 속한 ISP 안의 나를 제외한 N-1개의 라우터까지의 least cost path를 계산해야 하는데, 그것들이 어떤 link 정보를 가지고 있는지 complete topology 정보를 다 얻은 후 path selection algorithm을 running하는 방식은 Dijkstra's algorithm.

Dijkstra's algorithm에 의해 결정된 route로 user pkt이 가게 되는 길만을 따라 topology를 그리면 loop이 없는 tree 구조가 됨. (RIP에 비해 loop가 생기지 않으니 높은 신뢰도, but complexity가 높음)

→ global 정보를 다 받고 Dijkstra's algorithm을 running

Ex. OSPF (나머지 router들과 broadcast로 통신)

Distance Vector Algorithm

물리적으로 직접 연결된 neighbor router와만 communication 하여 나 제외 나머지 라우터로 가는 path의 local한 정보(distance vector = routing table)를 주고 받음.

msg exchange → path selection → msg exchange → path selection → ... iteration

라우터들이 linear하게 배치 되어있을 때 나와 가장 먼 라우터로부터 도달하는 라우팅 정보는 n-1번 iteration 하면 됨.

→ physically connected된 neighbor 라우터에게서 받은 정보로 estimate 값을 계산.

Ex. RIP, BGP

• static: link의 상태가 update되는 것에 반응이 느림

• dynamic: nw가 정보를 자체적으로 update

• 우리가 알고있는 routing protocol들은 link의 cost를 variable하게 가지지 않음. 고정된 값을 가짐

→ 실시간으로 변하는 load-sensitive한 정보를 사용하게 되면, OSPF 같은 경우 특정 destination으로 가는 traffic들이 한 방향으로 갔다가, 다시 반대 방향으로 갔다가 oscillation 할 수 있음.

• 어떤 src로부터 dst까지 가는 path: src로부터 dst까지 가는데 거치는 router들의 집합
  주로, number of hops가 path의 cost가 됨

---

DV algorithm

• iterative, asynchronous 반복적, 비동기적
  each local iteration caused by
• local link cost change
• DV update message from neighbor
  이웃끼리 더 이상 정보를 교환하지 않을 때까지 프로세스가 지속된다는 점에서 반복적이다.
  모든 노드가 서로 정확히 맞물려 동작할 필요가 없다는 점에서 비동기적이다.
• distributed 분산적.
  each node notifies neighbors only when its DV changes
  각 라우터는 직접 연결된 이웃으로부터 정보를 받고, 계산을 수행하며, 계산된 결과를 다시 그 이웃들에게 배포한다는 점에서 분산적이다.
  **(RIP는 30초마다 node 정보를 갱신, DGP는 ISP단위로 작동하기 때문에 바뀌었을 때만 갱신)
• each node
  wait for chane in local link cost or msg from neighbor
  recompute estimates my Distance Vector
  notify If DV to any dest has changed

굉장히 작은 망이라 2 time이 지나니 모든 라우터가 똑같은 routing table을 갖게 됨.

DV: link cost changes

count to infinity (라우팅 루프)

• node detects local link cost change
• updates routing info, recalculates distance vector
• if DV changes, notify neighbors

DV algorithm 내에서 link cost가 좋아졌으면(작아졌으면) 반영이 빠르나, link cost가 나빠졌으면 반영이 느림.

bad new travels slowly!

→ DV algorithm의 단점: count to infinity 현상이 일어날 수 있다.

local한 link의 cost가 안 좋아졌을 때, 나머지 모든 router들이 자신의 distance vector를 계산하는데 적용되는 시간이 굉장히 오래 걸려서 중간에 destination으로 가는 pkt들이 loop를 돌 수 있다.

Solution 1) Split horizon

A — B — C 일 때, Da(c)=C(A, B) + Db(C), A에서 B로 가는 cost, B가 알려준 B에서 C로 가는 cost.

이 B가 알려준 정보를 A가 B에게 다시 알려주는 짓은 하지 말자!

Solution 2) Split horizon with poison reverse

알려주되 너한테 얻은 정보라는 것 까지도 알려주자!

만약 z가 y를 통해 목적지 x로 가는 경로 설정을 했다면, z는 y에게 x까지의 거리가 ∞라고 알린다.

즉, z는 y에게 Dz(x) = ∞ 라고 알림으로써 y는 z에게 x로 가는 경로가 없다고 믿으므로, y는 z를 통해 x로 가는 경로를 시도하지 않을 것이다.

이 방법이 모든 블랙홀을 막아주진 않음.

세 개 이상의 router들이 involve 되어있는 loop은 이 두 방법으로도 막지 못 함.
→ RIP는 세 개 이상의 router들이 involve 되는 topology를 구성하지 않음
→ BGP는 거쳐오는 라우터들을 모두 적어서 알려줌.

Link State vs. Distance Vector algorithms

LS와 DV 알고리즘은 경로를 계산할 때 서로 대비되는 방법을 취한다.

DV 알고리즘에서 각 라우터는 오직 직접 연결된 이웃과만 메시지를 교환하지만, 자신으로부터 네트워크 내 (자신이 알고 있는) 모든 라우터들로의 최소 비용 추정값을 이웃들에게 제공한다.

LS 알고리즘은 전체 정보를 필요로 한다. 각 노드는 모든 노드와 broadcast를 통해 통신하지만, 오직 자신에 직접 연결된 링크의 비용만 알린다.

Link-State (LS) routing algorithms

모든 link의 정보를 다 알고 router가 계산을 시작 (정확한 정보를 모두에게)

Ex. OSPF, IS-IS: Dijkstra's algorithm

Distance-Vector (DV) routing algorithms

내가 예측하고 있는 모든 subnet으로 가는 정보를 내 이웃에게만 줌

Ex. RIP, BGP, ISO IDRP, Novel IPX, the original ARPAnet : Bellman-Ford algorithm

• 메세지 크기가 더 큰 것은 DV algorithm
• 네트워크에 돌아다니는 메시지 개수는 LS algorithm이 더 많음

• 최악의 경우, n개의 노드가 있을 때
  LS는 O(n*link 개수) msgs가 보내지고, → more, smaller msgs
  DV는 O(n-1)개의 이웃에게 msg를 보내게 됨. → fewer, larger msgs
  OSPF는 broadcast, RIP는 UDP로 multicast, BGP는 TCP로 unicast(ISP를 넘어가는 중요한 정보)
• convergence의 속도:
  LS는 path selection 계산하기 전 시간이 오래 걸림. but path selection은 Dijkstra 알고리즘을 사용하여 O(N^2) to O(nlogn), but load-sensitive하는 경우 converge가 안 되는 oscillation이 발생. no loop
  DV는 topology에 따라 convergence time varies, loop이 생길 수 있음 (count to inifinity problem)
• robustness: what happens if router malfunctions? 누가 신뢰도가 더 높냐? LS
  LS는 전체 topology를 제대로 알고 있을 때 한 router의 link 정보만 잘못 되었다면 크게 문제가 발생하지 X.
  → incorrect link cost를 advertise한 것. each node computes only its own table
  DV는 한 router로부터 나머지 모든 router로 가는 정보를 잘못 알려준 것.
  → incorrect least-cost path cost를 advertise한 것 : error propagates thru network

Hierarchical routing: Autonomous Systems (AS)

각 AS는 동일한 관리 제어하에 있는 라우터의 그룹으로 구성된다. 한 ISP의 라우터와 그들을 연결하는 링크가 종종 하나의 AS를 이룬다. 어떤 ISP들은 그들의 네트워크를 여러 개의 AS로 나누기도 한다.

AS들은 전세계적으로 고유한 ASN number로 식별된다.

• 같은 AS 안에 있는 라우터들은 동일한 라우팅 알고리즘을 사용하고 상대방에 대한 정보를 가지고 있다.
• AS 내부에서 동작하는 라우팅 알고리즘을 intra-AS routing protocol이라고 한다.

---

Keywords

• Distance-vector algorithm

-- iterative, asynchronous, distributed

-- may include count-to-infinity which is a temporary routing loop in the network when a link cost gets worse (usually a link goes down).

-- solution for count-to-infinity : split-horizon or split-horizon with poison reverse

• Link-state (LS) v.s. Distance vector

-- LS : smaller message size and more traffic

-- DV : larger message size and less traffic

-- If a router malfunctions,

-- for LS, only local info becomes wrong

-- for DV, route path info gets wrong  --> more serious