컴퓨터 네트워크 정리 -12주차- <네트워크 레이어/4.5 - 4.7 >

12주차

Distance Vector : link cost changes

특정 라우터간의 링크 코스트가 변경되면, good new와 bad news가 생긴다.

-      good news : 기존 명시된 코스트보다 빠른 루트가 생긴 것을 이웃에게 전달하며 DV 수정

-      bad news : 변화된 값을 적용하기 위해, infinity할 수 있는 DV 업데이트가 필요함
[Good News : Travel Fast, Bad News : Travel Slow]

Distance Vector : poisoned reverse (Count to Infinity 해결 시나리오)

재방문 되는 연결을 Infinity 처리함으로써 문제를 해결하는 방식

위 사진에서, x-z-y 루트는 사실 x-y-z-y로 이어지기에, 무한으로 표시한다.

Distance Vector : link cost changes

Link state는 과거의 정보를 갖고 있지만, DV는 이웃에 대한 정보 뿐이다.

Comparison of LS and DV Algorithms

-      message complexity
LS : n nodes, E links => O(nE) / DV : 이웃간의 교환뿐, convergence time varies

-      speed of convergence
LS : O(n^2) 알고리즘이며, O(nE) msgs를 요구한다. (반복적인 교환이 이뤄진다.)
DV : 각양각색, routing loops와 count-to-infinity problem 존재.

-      Robustness :
LS : 잘못된 link 정보를 모든 노드에게 공유, 각 노드는 자신의 테이블만 수정
DV : 잘못된 path 정보를 이웃 노드에게 공유, 각 노드의 테이블이 다른 노드들로 하여금 읽혀진다. => error propagate thru network
결론 : LS는 예측 가능하지만, DV는 성능을 예측할 수 없어 LS를 선호한다.

Hierarchical routing

-      AS(Autonomous System) : 지역별 라우터의 묶음

-      AS 내 라우터는 모두 같은 routing protocol을 사용한다.

-      AS의 ‘edge’는 다른 AS의 라우터로 갈 수 있는 ‘link’를 갖는다.

Interconnected ASes

 

 

4.6 routing in the internet

- RIP : DV

- OSPF : LS

- BGP : HR

Intra-AS Routing

-      IGP : interior gateway protocols라고도 불린다.

-      Intra-AS 라우팅 프로토콜의 대표 3개

• RIP : Routing Information Protocol (DV)
• OSPF : Open Shortest Path First (LS)
• IGRP : Interior Gateway Routing Protocol (Cisco Proprietary) (HR)

RIP (Routing Information Protocol)

-      BSD-UNIX에서 생산

-      DV Algorithm 사용

• Distance metric : # hops(max 15 hops), 각 링크 코스트 = 1
• DV는 이웃과 매 30초마다 response message를 교환한다. (advertisement)
• Advertisement : 25개의 목적지 subnets를 list up 한다.
  

 

 

RIP: example

RIP : link failure, recovery

-      180초간 advertisement가 수신되지 않으면, 이웃/링크가 죽었다고 선언

• Neighbor을 통해 invalidated 됨을 routes한다.
• 새로운 advertisements가 neighbor 들에게 송신된다. (path 사용불가 알림)
• Table의 변화가 생기면, neighborㄷ르은 또 새로운 advertisement를 송신한다. (propagating)
• Poison reverse를 사용해 ping-pong loops(infinite distance = 16hops)를 막는다.

 

RIP table processing

-      RIP routing tables는 Application-level에서 ‘daemon’이라는 process를 통해 관리된다.

-      UDP packets를 통해 주기적으로 advertisements가 된다.

OSPF(Open Shortest Path First)

-      Link state algorithm 사용

• LS packet 뿌리기
• 각 노드 마다 topology map 사용
• 라우트 연산은 다익스트라 알고리즘 사용

-      OSPF advertisement는 이웃 하나 당 하나의 entry씩 제공된다.

-      AS 전체에 광고가 물밀 듯 들어온다.

• OSPF msgs는 TCP나 UDP를 통해 들어온다.

-      IS-IS routing 프로토콜은 OSPF와 비슷하다.

OSPF “advanced” features (not in RIP)

-      Security : 모든 OSPF messages는 authenticated 되어있다. 이는 악의적 침입을 막는다.

-      Multiple same-cost paths allowed (RIP에서는 하나의 한 코스트엔 한 path만 된다.)
EX) A-r1-r2-r3-r4-B 가 4cost, A-r5-B 가 4cost 이런 식으로 존재 가능

-      TOS의 차이 때문에 각 링크는 multiple cost metrics를 갖는다.
(e.g : 인공위성 link의 코스트는 낮게, 실시간 서비스에는 높은 ToS를 배정)

-      Multicast 지원

• Multicast OSPF(MOSPF)는 OSPF와 같은 database topology를 사용한다.

-      계층형 OSPF를 큰 도메인에서 제공한다.

Internet inter-AS routing : BGP

-      BGP (Border Gateway Protocol) : the de facto inter-domain routing protocol

-      BGP는 각 AS에게 다음과 같은 의미를 부여한다.

• eBGP : 'eBGP'는 인접한 'AS’들로부터 서브넷 도달 가능성 정보를 얻는다.
• iBGP : 'iBGP'는 모든 AS-internal-router에 도달 가능성 정보를 전파한다.

-      Subnet의 존재 유무를 인터넷의 다른 영역에 전달한다.

BGP basics

-      Prefix로 시작 subnet을 잡음.

-      Semi-permanent TCP 연결을 통해 메시지 교환을 함.

BGP basics : distributing path information

-      3a와 1c간의 eBGP 연결을 통해 AS3에서 AS1으로 prefix를 전송

-      1c는 수신 받은 eBGP의 prefix를 iBGP로 subnet 내 라우터들에게 전송

-      1b는 eBGP를 통해 AS2 영역에 전달 받은 AS3의 prefix를 전송

 

 

Why different Intra-, Inter-AS routing?

-      Policy

• Inter-AS : admin이 트래픽이 얼마나 routed 되는지, 어디서 이 마을 통해 route를 하는지 control 하고 싶을 때
• Intra-AS : single admin => policy decision이 필요없다.

-      Scale

• 계층형 routing으로 table size를 아끼고, traffic update를 감소시킨다.

-      Performance

• Inter-AS : policy가 성능을 좌지우지한다.
• Intra-AS : 성능에 집중할 수 있다.

4.7 broadcast and multicast routing

Broadcast routing

In-network duplication

-      Flooding : 노드가 broadcast packet수신 시, 모든 이웃에게 copy본을 송신

• 문제점 : cycles(이웃도 내게 보내는 것) & broadcast storm

-      Controlled flooding : 노드가 이전에 똑 같은 broadcast packet을 받았는지 확인 후 안 받았을 때만, broadcast 한다. => cycle 해소

-      Spanning tree : cycles 일단 없고, storm도 없엉

Spanning tree

Spanning tree : creation

크루스칼 알고리즘

 

 

Multicat routing : problem statement