5.1 introduction

Network-layer functions

forwarding: 라우터의 입력으로부터 적절한 출력으로의 패킷 이동 → data plane

routing: 출발지부터 목적지까지 패킷의 이동 경로 결정 → control plane

• per-router control
• logically centralized control

5.2 routing protocols

Routing protocols

목표: 라우터들을 통해서 송신측 호스트에서 수신측 호스트까지 좋은 경로를 결정

• path: 첫번째 소스 호스트부터 마지막 목적지 호스트까지 패킷의 연속된 라우터들의 순서
• good: 가장 비용이 적은, 가장 빠른, 가장 혼잡하지 않음

Routing Algorithm classification

Global

• 모든 라우터들이 완전한 위상과 링크 비용 정보를 가짐
• link state algorithms

Decentralized

• 라우터는 물리적으로 연결된 이웃 노드, 이웃 노드와의 링크 비용 정보를 가짐
• 반복적인 계산 과정과 이웃 노드와의 정보 교환
• distance vector algorithms

Static

• 경로가 매우 느리게 변함

Dynamic

• 경로가 매우 빠르게 변화
  • 주기적 갱신
  • 링크 비용 변경에 따라

Link-State Routing Algorithm

Dijkstra’s algorithm

• 네트워크 위상, 링크 비용들이 모든 노드들에게 알려짐
  • link state broadcast를 통해 달성됨
  • 모든 노드는 같은 정보를 가짐
• 한 노드로부터 모든 다른 노드까지의 최소 비용 경로를 계산
  • forwarding table 제공
• 반복적: k번 반복 후, k개의 목적지 노드에 대해 최소 비용 경로가 알려짐
• 알고리즘 복잡도
  • 각 반복: N에 포함되지 않은 모든 노드 w 검사 필요
  • n*(n+1)/2 비교: O(n^2)
  • 좀 더 효율적인 구현 가능: O(nlog n)
• 메시지 복잡도
  • 각 라우터는 다른 n개의 라우터에게 링크 상태 정보를 broadcast
  • n개의 링크를 전달
  • 복잡도: O(n^2)
• 진동 문제
  • 링크 비용이 트래픽 양에 의존하는 경우, 경로 진동이 가능
  • 해결책: 각각의 라우터들이 동일한 시간에 다익스트라 알고리즘을 사용하지 말고 시간차를 두고 동작

Distance Vector Routing Algorithm

반복적: 노드가 정보를 교환하지 않을때까지 계속

비동기: 노드는 lock 단계에서 정보를 교환할 필요가 없고, 반복할 필요가 없다.

분산적: 각 노드는 단지 직접 연결된 이웃 노드와 통신

Bellman-Ford equation

• (인접한 노드들까지의 비용 + 인접한 노드들에서 목적지까지의 비용)의 minimum

basic idea

• 각각의 노드는 주기적으로 그것의 distance vector 추정치를 이웃들에게 보낸다
• node x가 이웃으로부터 새로운 DV 추정치을 받았을때 B-F 방정식을 이용하여 업데이트 한다.
• 계속 반복하면 추정치가 최소 비용이 됨

반복적이고 비동기적임

• 반복은 로컬 링크 비용이 변경될때, 이웃으로부터 DV 업데이트 메시지를 받을 때

분산적이고, self-stop

과정: 로컬 링크비용이 바뀌거나 DV message를 받을때까지 대기 → DV 추정치를 벨만 방정식을 이용하여 재계산 → DV 추정치가 변경되면 이웃에게 알림

good news는 안정화될때까지 시간이 빠름

bad news는 안정화되기까지 시간이 오래 걸림

메시지 복잡도

• LS: n노드, E 링크에 대해, 각각 O(nE) 메시지가 전달됨
• DV: 이웃 노드들 사이에서만 교환됨 → 측정 불가

수렴 속도

• LS: O(n^2) 알고리즘은 O(nE) 메시지를 요구
  • 진동 문제 발생 가능
• 수렴시간 예측 어려움
  • 라우팅 루프가 발생 가능
  • count-to-infinity 문제

강건성: 라우터가 오작동하는 경우

• LS: 노드는 잘못된 링크 비용을 브로드캐스트 → 각 노드는 자신의 테이블만을 계산함 → 큰 문제 없음
• DV: 노드는 잘못된 경로 비용을 알림 → 각 노드의 테이블은 다른 노드들에 의해 사용됨 → 전체 네트워크로 오류가 전파됨

5.3 intra-AS routing in the Internet: RIP, OSPF

Hierarchical Routing

라우터들을 지역으로 집합화, autonomous systems (AS)

intra-AS routing

• 같은 AS에 있는 라우터들은 같은 라우팅 프로토콜 수행
• 다른 AS에서 라우터들은 다른 intra-AS 라우팅 프로토콜을 수행
• gateway router: AS의 가장자리에 위치 다른 AS에서의 라우터와 링크를 가짐

inter-AS routing

• AS들 간의 라우팅
• Gateway가 inter-domain routing을 수행

Intra-AS Routing

Interior Gateway Protocols

가장 흔한 Intra-AS routing protocols

• RIP: Routing Information Protocol
• OSPF: Open shortest Path First
• IGRP: Interior Gateway Routing Protocol

RIP(Routing Information Protocol)

distance vector algoritm

1982년 BSD-UNIX 배포판에 포함됨

Distance metic: hop 수

• 각 링크는 1의 비용을 가짐
• 최고 경로 비용은 15로 제한

Distance vectors: Response 메시지를 통해 매 30초마다 이웃끼리 교환됨 (advertisement)

각 advertiesement: AS내에서 25개 목적지 네트워크까지의 라우팅 테이블 엔트리를 포함

180초 후에 이웃으로부터 advertisement를 듣지 못하면 이웃 링크에 도달할 수 없다고 판단 → 이웃을 통한 경로는 invalidate됨 → 도달 가능한 이웃들에게 새로운 ad 전송 → 차례로 이웃은 새로운 ad를 전송 → 링크 failure 정보는 빠르게 전체 네트워크로 전파

RIP 라우팅 테이블은 routed-d(daemon)라 불리는 응용계층 레벨의 프로세스에 의해 관리됨

ad는 UDP 패킷으로 주기적으로 반복되어 전송됨

OSPF(Open Shortest Path First)

open: 라우팅 프로토콜 명세가 공용으로 유용

Link State 알고리즘 사용

• LS packet 전파
• 각 노드에서 완전한 토폴로지 맵을 가짐
• Dijkstra’s algorithm을 사용한 경로 계산

OSPF는 모든 라우터에게 라우팅 정보를 브로드캐스트

• ad는 전체 AS에 보급됨(via flooding)
• 링크 상태 변경시 또는 매 30분마다 정기적으로 브로드캐스트
• IP에 의해 직접 운반되는 OSPF 메시지로 전달됨

계층적인 특성을 가짐

• Two-level hierarchy: 로컬 영역, 백본
  • 영역 내에서만 Link-state ad
  • 각 노드는 상세한 영역 토폴로지를 가짐; 다른 영역의 네트워크로 최단 경로만을 안다
• Area border routers(ABR): 외부 영역으로의 패킷 라우팅을 책임짐
• Backbone routers: 백본에 한정된 OSPF routing 수행
• Boundary routers: 다른 AS에 연결. 다른 AS에 속한 라우터와 라우팅 정보 교환

5.4 routing among the ISPs: BGP

AS1 inter-domain routing은 AS2와 AS3를 통과하면서 도달가능한 목적지를 알아낸다 → 이러한 정보를 AS1에 모든 라우터들에게 전달한다.

BGP(Border Gateway protocol): 산업 표준

BGP는 각각의 AS에게 두가지를 전달

• eBGP: 이웃한 AS들로부터 서브넷 도달가능성 정보를 얻음
• iBPG: AS안에 있는 모든 라우터들에게 도달가능성 정보를 전파함
• 좋은 경로는 도달가능성 정보와 정책에 의존함.

라우터쌍(BGP peers)는 semi permanent한 TCP 커넥션을 통해 라우팅 정보를 교환함: BGP sessions

• BGP session은 물리적 링크가 아님
• 서로 다른 목적지 네트워크의 prefix에 대한 경로를 adverties함 (BGP는 path vector protocol)

prefix를 advertise 할때 advert는 BGP attributes를 포함함

• prefix + attributes = route

두가지 attributes

• AS-PATH: prefix에 대한 advert가 어떤 AS를 통과했는지를 포함
• NEXT-HOP: next-hp AS로 갈때 어떤 내부 AS-router로 갈지를 명시

정책 기반 라우팅

• 경로 ad를 받는 게이트웨이는 경로는 수락할지 거부 할지에 대한 중요한 정책을 사용함(예: AS Y를 통한 경로는 사용하지 않는다)
• AS정책은 또한 이웃 AS에게 경로를 advertise할건지 결정

inter domain은 BGP 사용 intra domain OSPF를 사용한다.

Hot Potato Routing

• 최소 비용의 로컬 게이트웨이를 선택 → inter domain 비용은 고려하지 않음

Router must select a route based on

• policy decison
• Shortest AS-PATH
• Closest NEXT-HOP router: hot potato routing
• Additional criteria

BGP messages

• TCP 사용하여 교환됨
• open: peer와 TCP connection을 열고 전송자를 인증
• update: 새로운 경로를 advertises
• keepalive: update를 보내지 않지만 connection이 유지되고 있음을 알림, 또한 open 메시지의 Acks으로 사용
• notification: 이전 메시지에서 에러를 보고, 또한 connection을 close하기 위해 사용됨

정리

정책

• Inter-AS 관리자는 자신의 트래픽이 어떻게 라우트되고, 누가 자신의 네트워크를 통해 라우트 되는지를 제어하기를 원함
• Intra-AS: 하나의 관리자, 따라서 정책 결정은 중요하지 않음

확장성

• 계층적 라우팅은 테이블 크기를 줄이고, update 트래픽을 줄임

성능

• Intra-AS: 성능에 초점을 맞춤
• Inter-AS: 정책이 성능보다 우선함

Broadcast and multicast routing

Multicast: 한 송신자에서 단일 송신 동작으로 다수의 수신자들에게 데이터그램을 전송하는 행동

멀티캐스트를 어떻게 달성?

• Multicast via unicast
  • 소스가 N개의 유니캐스트 데이터그램을 전송, N 수신자들 각각에 전달됨
• Network multicast
  • 라우터가 멀티캐스트에 능동적으로 참여, 필요한 만큼 패킷의 사본을 만들어 멀티캐스트 수신자들에게 전달
• Application-layer multicast
  • 종단 시스템들이 멀티캐스트에 참여, 수신 종단시스템들간에 유니캐스트 데이터그램을 복사하여 전달

Internet Multicast Service Model

multicast group: 간접주소 사용

• 호스트는 멀티캐스트 그룹으로 IP 데이터그램을 주소 지정
• 라우터는 멀티캐스트 그룹에 join한 호스트들에게 멀티캐스트 데이터그램을 전달

Multicast groups

class D: 멀티캐스트를 위해 예약된 인터넷 주소

• 1110+28bits

host group semantics

• 누구든지 멀티캐스트 그룹에 join 할 수 있음
• 누구든지 멀티캐스트 그룹에 전송할 수 있음
• 멤버들의 호스트에 네트워크 계층 식별은 아님 (class D의 주소는 호스트가 아닌 그룹의 주소)
  • 각 호스트는 유일한 IP 주소를 가지고 있음

needed: 멀티캐스트 주소 지정된 데이터그램을 멀티캐스트 그룹에 join한 모든 호스트들에게 전달하는 인프라

Joining: two-step process

local: 호스트는 로컬 멀티캐스트 라우터에게 그룹에 join하기 원한다는 것을 알림: IGMP

wide area: 로컬 라우터는 멀티캐스트 데이터그램 플로우를 수신하기 위해 다른 라우터들과 상호 작용함

IGMP(Internet Group Management Protocol)

host: 어플리케이션이 멀티캐스트 그룹에 join할 때 IGMP report를 전송

• IP_ADD_MEMBERSHIP socket option
• 멀티캐스트 그룹에서 탈퇴할 때 호스트는 명시적으로 unjoin할 필요가 없음

router: 일정한 interval로 IGMP query를 전송

• 멀티캐스트 그룹에 속한 호스트는 query에 응답해야함

IGMP

version 1

• router: 호스트 멤버쉽 커리가 모든 호스트에게 LAN으로 브로드캐스트
• host: 그룹 멤버쉽을 지시하기 위해 Host Membership Report 메시지
  • 응답하기 전에 randomized delay
  • Query에 응답하지 않음으로써 묵시적으로 탈퇴

version 2

• group-specific Query
• 명시적으로 그룹 탈퇴 메시지를 전송

Multicast Routing

Goal: 로컬 멀티캐스트 그룹 멤버를 가지는 라우터들을 연결하는 트리 발견

• tree: 라우터들 간의 모든 경로가 사용되지 않음
• source-based: 각 전송자로부터 수신자들까지 다른 tree
• shared-tree: 모든 그룹 멤버들에 의해 사용되는 동일한 tree