컴퓨터 네트워크

5.2 DV algorithm & AS

SWSEODONG 2021. 6. 12. 14:33

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을 갖게 됨.

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는 거쳐오는 라우터들을 모두 적어서 알려줌.

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

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

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

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