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

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

bad new travels slowly!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ex. RIP, BGP, ISO IDRP, Novel IPX, the original ARPAnet : Bellman-Ford 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

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

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

-- 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

-- 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