5.2 DV algorithm & AS
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