Chapter 11 Unicast Routing Protocols

학습목표(OBJECTIVES): 라우팅 정보 교환의 목적으로 인터넷을 더 작은 관리 영역으로 나누는 자율 시스템(AS) 개념을 소개한다. 인터넷에서 거리벡터 라우팅의 개념을 구현하기 위해 경로 정보 프로토콜(RIP: Routing Information Protocol)이 어떻게 사용되었는지를 설명한다. 인터넷에서 링크 상태 라우팅의 개념을 구현하기 위해 OSPF(Open Shortest Path First)가 어떻게 사용되는지를 설명한다. 인터넷에서 거리 벡터 라우팅의 개념을 구현하기 위해 BGP(Border Gateway Protocol)가 어떻게 사용되는지를 설명한다.

Chapter Outline 11.1 Introduction 11.2 Intra- and Inter-Domain Routing 11.3 Distance Vector Routing 11.4 RIP 11.5 Link State Routing 11.6 OSPF 11.7 Path Vector Routing 11.8 BGP Chapter Outline

11-1 개요 인터넷은 라우터들에 의해 연결된 네트워크의 조합이다. 발신지로부터 목적지까지 전송되는 데이터그램은 목적지 네트워크에 연결된 라우터에 도착할 때까지 많은 라우터를 거쳐 가게 된다. 라우터가 패킷을 수신하면 어느 라우터로 보내야 하는가? 최적의 경로란 무엇인가? 망을 통해 전달되는 비용(cost) 할당: 메트릭(metric) 적은 비용으로 높은 성능을 낮은 지연시간을 얻도록 한다

개요 정적 라우팅(static routing) 과 동적(dynamic) 라우팅 테이블(table) 라우팅 프로토콜 정적 테이블: 수동 엔트리 동적 테이블: 인터넷에 변화가 있을 때마다 자동 갱신 라우팅 프로토콜 동적 라우팅 테이블의 요구를 충족하기 위해 만들어졌음 내부 프로토콜(도메인 내 라우팅)과 외부 라우팅(도메인 간 라우팅) 으로 나뉨

11-2 INTER- AND INTRA-DOMAIN ROUTING 오늘날 인터넷은 한 가지 라우팅 프로토콜로만 모든 라우터의 라우팅 테이블을 갱신하는 작업을 수행하기에는 부족할 정도로 너무 많이 확장되었다. 이런 이유로 인터넷은 자율 시스템(AS: Autonomous System)으로 나눠진다. 자율 시스템은 하나의 단일 관리 기관 하에 있는 라우터와 네트워크의 그룹이다. 자율 시스템 내에서의 라우팅을 도메인 내(intra-domain) 라우팅이라 한다. 자율 시스템 간의 라우팅을 도메인 간(inter-domain) 라우팅이라 한다.

자율 시스템(Autonomous systems) 하나의 단일 기관 하에 있는 라우터와 네트워크 그룹

대표적인 라우팅 프로토콜

11-3 DISTANCE VECTOR 라우팅 모든 라우터와 망들로 구성된 AS를 노드의 집합과 이 노드들을 연결하는 선(에지)들로 구성된 그래프로 간주 라우터는 노드로 표시 망은 두 노드를 연결하는 링크로 주로 표시 노드들 간의 거리가 주어진 망에서 노드들 간의 최단 거리를 찾기 위해 Bellman-Ford(또는 Ford-Fulkerson)라고 불리는 알고리즘 사용

Bellman-Ford 알고리즘을 위한 그래프 그래프 이론에서 많은 응용에 사용 임의의 두 노드 쌍간의 비용을 알면 두 노드간의 최소 비용(최단거리)을 찾을 수 있다

Bellman-Ford 알고리즘 동작 원리

Bellman-Ford 알고리즘 각 노드와 자신 간의 최단 거리 및 비용을 0으로 초기화한다. 각 노드와 다른 노드와의 최단 거리를 무한대로 설정한다. 그 후 노드와 다른 노드 간의 비용을 주어진 값으로 설정하되 연결이 없으면 무한대로 유지한다. 최단 거리 벡터에 변경 사항이 더 없을 때까지 동작원리에 나타난 나타낸 알고리즘을 반복한다.

Example 11.1 다음 쪽 그림은 AS에 대한 초기 라우팅 테이블을 보여준다. 그림은 모든 라우팅 테이블이 동시에 생성되는 것을 의미하지는 않는다. 각 라우터는 부팅될 때 자신만의 라우팅 테이블을 생성하게 된다.

Example 11.1 TCP/IP Protocol Suite

Example 11.2 이제 라우터 A가 이웃 노드인 라우터 B, D 및 C에 4개의 항목을 전송한다고 가정하자. 다음 쪽 그림은 이런 항목들을 받을 때 B의 라우팅 테이블 변화를 보여준다. 다른 라우터의 라우팅 테이블 변화는 연습문제로 남겨둔다.

Example 11.2 TCP/IP Protocol Suite

Example 11.3 다음 쪽 그림은 앞 쪽 그림에 있는 라우터들에 대한 최종 라우팅 테이블을 보여준다.

Example 11.3

무한대로의 카운트(count to infinity) 거리벡터 라우팅의 문제점 비용감소와 같은 좋은 소식은 빨리 퍼지나 비용증가와 같은 나쁜 소식은 천천히 퍼진다. 링크가 고장 난 경우에 다른 모든 라우터가 이를 인식해야 하는데, 시간이 많이 소요 고장 난 링크에 대한 비용이 모든 라우터에 무한대가 되기까지 몇 차례 갱신이 필요 무한대로의 카운트 예: 두 노드 루프 문제

두 노드 불안정성(Two-node instability)

불안정 문제 해결책 무한대로의 정의(defining infinity) 수평 분할(split horizon) 무한대로 16과 같은 작은 수로 정의 수평 분할(split horizon) 각 인터페이스를 통해 테이블을 플러딩(flooding)하지 않고 테이블의 일부만 전송 수평분할과 poison reverse 정보의 송신자인 라우터에게 거리값을 무한대로 설정하고, 이 값을 사용하지말라고 경고, 당신으로부터 정보를 받았기 때문에

세 노드 불안정성(Three-node instability)

11-4 RIP 경로 정보 프로토콜인 RIP(routing information protocol)는 자율 시스템 내부에서 사용되는 도메인 내(intra-domain(interior)) 라우팅 프로토콜이다. 이는 거리 벡터 라우팅(distance vector routing)에 기반을 두는 간단한 프로토콜로서 몇 가지 고려 사항을 참고한 거리 벡터 라우팅의 구현 형태이다.

RIP를 사용하는 도메인 예

RIP 메시지 형식

RIP 메시지 형식 명령(command): 메시지 유형 - 요청:1, 응답:2 버전(version): 버전을 나타냄 계열(family): 사용된 프로토콜 계열 네트워크 주소(network address): 목적지 네트워크 주소 거리(distance): 송신 라우터에서 목적지 라우터까지 홉의 수 메시지 종류: 요청(request)과 응답(response)

요청 메시지(Request messages) 새로 생기거나 시간이 만료된 항목을 가진 라우터에 의해 전송

Example 11.4 그림 11.13은 그림 11.10의 라우터 R1에서 라우터 R2로 보내지는 갱신 메시지를 보여준다. 메시지는 130.10.0.2 인터페이스를 통해 보내진다. 메시지는 수평 분할과 poison reverse 정책의 조합을 염두에 두고 준비되었다. 라우터 R1은 195.2.4.0, 195.2.5.0 및 195.2.6.0 네트워크에 관한 정보를 라우터 R2로부터 얻었다. R1이 R2로 갱신 메시지를 보낼 때 R2가 혼란을 겪지 않도록 이 세 네트워크에 대한 홉 수를 실제 값이 아닌 16(무한대)으로 대체한다. 그림은 메시지에서 추출한 테이블도 보여주고 있다. 라우터 R2는 R1(130.10.02)으로부터의 RIP 메시지를 전송하는 IP 데이터그램의 송신자 주소를 다음 홉 주소로 사용한다. 라우터 R2는 또한 각 홉 수를 1씩 증가시키는데 이는 메시지의 값들이 R2가 아닌 R1에 해당하는 값이기 때문이다.

Example 11.4의 해

RIP 타이머(timer)

RIP 타이머 주기적(periodic) 타이머 만료(expiration) 타이머 정규 갱신 메시지 통보 제어 만료(expiration) 타이머 경로의 유효성 관리 폐 경로 수집(garbage collection) 타이머 경로의 정보가 유효하지 않음을 알리기 위해 사용

Example 11.5 라우팅 테이블이 20개의 항목을 가지고 있다. 이 라우터가 200초 동안 5개의 경로에 대한 정보를 받지 못했다고 하면 이 시간에 가동되고 있는 타이머는 몇 개인가? 정답: 21개이며 타이머는 다음과 같다 Periodic timer: 1 Expiration timer: 20 − 5 = 15 Garbage collection timer: 5

RIP 버전 2 형식 새로운 필드 경로 태그(route tag): 자율시스템의 정보와 같은 번호 전달 서브넷 마스크(subnet mask): 서브넷 마스크 전달 다음 홉 주소(next-hop address): 다음 홉의 주소

RIP 버전 2(버전 1과 차이점) 클래스 없는 주소지정 인증 멀티캐스팅 서브넷 마스크 정보를 이용 인증되지 않은 광고에 대해 메시지 보호 멀티캐스팅 라우터들만 RIP 메시지 수신 가능

인증(Authentication)

RIP uses the services of UDP on well-known port 520. 캡슐화 RIP 메시지는 UDP 사용자 데이터그램에 캡슐화 Note RIP uses the services of UDP on well-known port 520.

11-5 링크 상태 라우팅 링크 상태(Link State) 라우팅은 거리 벡터 라우팅과 다른 철학을 가진다. 링크 상태 라우팅에서 만약 도메인 내의 각 라우터가 도메인의 전체 토폴로지—노드들과 링크들의 리스트, 그 유형, 비용(메트릭) 및 링크가 살아 있는지 죽어 있는지와 같은 상태를 포함해서 그들이 어떻게 연결되어 있는지—를 알고 있다면 노드는 딕스트라(Dijkstra) 알고리즘을 사용하여 라우팅 테이블을 만들 수 있다.

Topics Discussed in the Section Building Routing tables

Link state routing 개념

Link state 지식(knowledge)

라우팅 테이블 만들기 각 노드에 의해 링크 상태 패킷(LSP: Link State Packet) 생성 도메인의 토폴로지에 변화가 있는 경우 주기적으로 생성 다른 모든 라우터에 LSP 전송: 플러딩(flooding) 각 노드에서 최단 경로 트리 생성(딕스트라 알고리즘 적용) 최단 경로 트리를 기반으로 한 테이블 계산

Continued

그래프에서 라우터 A에 대한 최단 경로 트리 생성

Figure 11.19 Continued

Figure 11.19 Continued

Example 11.6 각 노드에 대한 최단 경로 트리가 다르다는 것을 보여주기 위해 그림 11.20에 노드 C가 보는 최단 경로 트리를 찾아보았다. 자세한 사항은 연습 문제로 남겨둔다.

Figure 11.20 Example 11.6

11-6 OSPF OSPF(Open Shortest Path First) 프로토콜은 링크 상태 라우팅에 근거를 둔 도메인 내 라우팅 프로토콜이다. OSPF의 도메인도 역시 자율 시스템이다.

Topics Discussed in the Section Area Metric Types of Links Graphical Representation OSPF Packets Link State Update Packet Other Packets Encapsulation

OSPF 라우팅 라우팅을 효율적으로 수행하기 위해 여러 지역(area)으로 나누는데, 지역은 자율시스템 내에 속한 호스트, 라우터 및 네트워크 모임 백본 라우터: 백본(backbone)내의 라우터들 지역 경계 라우터(area border router): 지역 정보 요약, 다른 지역으로 전송 메트릭(metric): 관리자는 각 경로에 대한 비용 할당, 서비스 종류 기반 결정(예: 최소 지연, 최대 성능) 다른 모든 라우터에 LSP 전송: 플러딩(flooding) 각 노드에서 최단 경로 트리 생성(딕스트라 알고리즘 적용) 최단 경로 트리를 기반으로 한 테이블 계산

자율시스템에서의 지역(Area)

OSPF 라우팅 지역(area) 각 노드에 의해 링크 상태 패킷(LSP: Link State Packet) 생성 도메인의 토폴로지에 변화가 있는 경우 주기적으로 생성 다른 모든 라우터에 LSP 전송: 플러딩(flooding) 각 노드에서 최단 경로 트리 생성(딕스트라 알고리즘 적용) 최단 경로 트리를 기반으로 한 테이블 계산

링크 유형

점-대-점 링크 라우터간을 다른 호스트나 라우터없이 직접 연결하는 링크 예: 전화선이나 T-라인을 통해 연결된 라우터 가상(virtual) 링크 두 라우터간 연결이 끊어지면 여러 라우터를 거쳐 돌아가더라도 연결되는 링크

점-대-점(Point-to-point) link

경유(transient) 링크 몇 개의 라우터가 연결된 네트워크 각 라우터는 많은 이웃을 가짐 예: 모든 LAN, 2개 이상의 라우터를 갖는 WAN 각 라우터는 많은 이웃을 가짐 라우터 중 하나가 지정(designated) 라우터 역할

경유(Transient) link

스터브(Stub) 링크 단지 하나의 라우터에만 연결된 네트워크 모든 데이터는 이 라우터를 통해서만 전달

OSPF에서 AS를 그림으로 표현한 예

OSPF 패킷 유형

OSPF 공통 헤더(common header)

OSPF 공통 헤더 버전(version): 프로토콜의 버전(현재 값 2) 유형(type): 패킷의 유형( 1 ~ 5 값) 메시지 길이: 전체 메시지 길이(16 비트 필드) 발신지 라우터 IP 주소: 패킷을 보낸 라우터 주소 지역 식별자: 라우팅이 일어나는 지역 검사합: 전체 패킷의 오류 확인에 사용 인증 종류: 지역에서 사용하는 인증 방법 인증: 인증 데이터 실제 값

링크 상태 갱신(Link state update) 패킷 라우터가 링크의 상태를 광고하는데 사용

LSA 일반 헤더 각 갱신 패킷은 몇 개의 서로 다른 LSA 포함 가능

LSA 일반 헤더 링크 상태 시간: 메시지가 만들어지고 경과된 시간 E 플래그: 지역이 스터브 지역일 경우 1 T 플래그: 라우터가 복수의 서비스 유형을 처리할 수 있으면 1 링크 상태 유형: LSA 유형 링크 상태 식별자: 링크의 유형을 나타냄 광고 라우터: 메시지를 광고하는 라우터 주소 링크 상태 순서번호: 링크상태갱신 메시지에 할당된 순서번호 링크 상태 검사합: 오류 확인 길이: 전체 패킷 길이

라우터 링크(Router link) 실제 라우터의 링크를 정의

라우터 링크(Router link) LSA

라우터 링크 LSA 링크 식별자: 링크의 유형에 따라 다름(표 11.5 참조) 링크 데이터: 링크에 관한 추가 정보 제공 링크 유형: 연결된 네트워크 유형 서비스 유형: 각 링크에 알려진 서비스 유형의 갯수 TOS 0 에 대한 메트릭: 기본 서비스 TOS: 서비스 유형 메트릭: 해당 TOS에 대한 메트릭

Example 11.7 그림 11.7은 그림 11.5에 있는 라우터에 대한 최종 라우팅 테이블을 보여준다. Solution 이 라우터는 3개의 링크를 갖는다: 이 중 둘은 type 1 (point-to-point) 이고 하나는 type 3 (stub network)이다. 그림 11.34는 router link LSA를 보여준다.

Figure 11.33 Example 11.7

Figure 11.34 Example 11.7의 해

네트워크 링크(Network link) 네트워크들의 링크를 정의 지정 라우터는 경유 망을 대신해 네트워크에 연결된 모든 라우터의 존재를 알리는LSP 패킷 분배

네트워크 링크 광고(Network link advertisement) 형식 네트워크 마스크 접속(attached) 라우터: 접속된 라우터의 IP 주소

Example 11.8 그림 11.37에서 network link LSA를 보여라 . Solution 네트워크 링크를 광고하는 네트워크에는 3개의 라우터가 연결되어 있다. LSA는 마스크와 라우터 주소를 보여준다. 그림 11.38 은 네트워크 링크 LSA를 보여준다.

Figure 11.37 Example 11.8

Figure 11.38 Solution to Example 11.8

Example 11.9 그림 11.39에서, 어느 라우터가 라우터 링크 LSA를 보내는가? Solution a. R1 은 두 개의 링크 N1과 N2를 갖는다. b. R2 는 하나의 링크 N1을 갖는다. c. R3 는 두 개의 링크 N2 와 N3를 갖는다.

Figure 11.39 Examples 11.9 and 11.10

Example 11.10 그림 11.39에서, 어느 라우터가 네트워크 링크 LSA를 보내는가? Solution 3개의 네트워크 모두가 네트워크 링크를 광고해야 한다: a. N1에 대한 광고는 R1이 수행하는데, 이는 자신만이 접속 라우터이고, 따라서 지정 라우터가 되기 때문이다. b. N2에 대한 광고는 누가 지정라우터로 선택되느냐에 따라 R1, R2나 R3에 의해 기능할 수 있다. c. N3에 대한 광고는 R3에 의해 수행되는데, 이는 자신만이 접속 라우터이고 지정 라우터가 되기 때문이다.

네트워크에 대한 요약 링크(Summary link)

네트워크에 대한 요약 링크 LSA 지역 바깥의 다른 망 존재를 알리기 위해 지역 경계 라우터에 의해 사용

AS 경계 라우터에 대한 요약 링크 지역내의 라우터가 자율시스템 바깥으로 패킷을 전송하고자 하면 먼저 AS 경계 라우터의 경로를 알아야 한다 지역 경계 라우터가 이정보를 지역내에 플러딩한다

AS 경계 라우터에 대한 요약 링크 LSA

외부 링크(External link) 자율 시스템 외부에 있는 모든 네트워크를 알릴 필요가 있다

외부 링크(External link) LSA

Hello 패킷 이웃 관계를 생성하고 이웃의 도달 가능성 검사 링크 상태 라우팅의 첫 번째 과정

데이터베이스 기술(Database description) 패킷 라우터가 시스템에 연결되고 나면, 자신의 이웃과 인사하기 위해 hello메시지를 보내고 나면 이웃이 보내는 패킷

링크 상태 요청 (Link state request) 패킷 특정 경로나 경로들에 대한 정보를 필요로 하는 라우터에 의해 보내지는 패킷

링크 상태 확인응답(Link state acknowledgment) 패킷 링크 상태 요청 패킷에 대한 확인응답

OSPF packets are encapsulated in IP datagrams. Note OSPF packets are encapsulated in IP datagrams.

11-7 경로 벡터(PATH VECTOR) 라우팅 거리 벡터와 링크 상태 라우팅은 모두 도메인 내부 라우팅 프로토콜이다. 그들은 자율 시스템 내에서 사용되나 자율 시스템 간에는 사용되지 않는다. 이 두 프로토콜은 확장성으로 인해 도메인 간 라우팅에는 대부분 적합하지 않다. 이 라우팅 프로토콜들은 동작하는 도메인이 크게 되면 다루기 어렵게 된다. 거리 벡터 라우팅은 동작하는 도메인에 수 홉 이상이 존재하게 되면 불안정해질 수 있다. 링크 상태 라우팅은 라우팅 테이블을 계산하기 위해 아주 많은 양의 자원을 필요로 한다. 이는 또한 플러딩으로 인해 많은 트래픽을 유발할 수도 있다. 따라서 제 3의 라우팅 프로토콜이 필요한데 이것이 바로 경로 벡터 라우팅(path vector routing)이다.

Topics Discussed in the Section Reachability Routing Table

Example 11.11 거리 벡터 라우팅과 경로 벡터 라우팅 간의 차이는 마치 국가 지도와 국가 간 지도의 차이와 비교할 만하다. 국가 지도는 각 도시로의 도로에 대해 알려주고 우리가 특정 경로를 정하면 여행하는데 걸리는 거리를 알려준다. 반면에 국가 간 지도는 각 국가에 어떤 도시가 있는지를 알려주고 그 도시를 도달하기 전에 어느 국가들을 거쳐야 하는지를 알려준다. 도달가능성(reachability) 다른 AS에게 정보를 제공하기 위해 경계내에 존재하는 망의 목록이 필요하다

도달가능성(Reachability)

3개의 AS에 대해 안정된 테이블 각 라우터에서 경로벡터 테이블은 AS가 도달가능성 목록을 다른 것과 공유하여 생성된다

집적화된 라우팅 테이블

11-8 BGP 경계 게이트웨이 프로토콜(BGP: Border Gateway Protocol)은 자율 시스템 간의 라우팅 프로토콜이다. 1989년에 처음 나타났고 이후 4번의 버전이 갱신되었다.

Topics Discussed in the Section Types of Autonomous Systems Path Attributes BGP Sessions External and Internal BGP Types of Packets Packet Format Encapsulation

자율 시스템 유형 스터브(Stub) AS 멀티홈 (Moltihome) AS 경유(Transit) AS 다른 자율 시스템과 하나의 연결만을 가짐 예: 작은 조직이나 작은 로컬 ISP 멀티홈 (Moltihome) AS 다른 자율시스템과 하나 이상의 연결을 가짐 예: 자나가는 트래픽을 허용하지 않은 하나 이상의 지역 혹은 국가 AS에 연결된 큰 조직 경유(Transit) AS 지나가는 트래픽을 허용하는 멀티홈 AS 예: 국가 또는 국제 ISP

내부(Internal)와 외부(external) BGP 세션 BGP 세션(session): 두 라우터간 라우팅 정보를 교환하는 것

BGP 메시지 종류

BGP 패킷 헤더

BGP 패킷 헤더 표시기(marker): 인증을 위해 예약 길이(length): 전체 메시지 길이 유형(type): 패킷의 유형

Figure 11.56 Open message

개방(open)메시지 동작 증인 라우터가 이웃관계를 생성하기 위해 보내는 메시지 버전: BGP 버전 자신의 자율시스템: 자율시스템 번호 유지시간: 상대방으로부터 Keepalive나 update 메시지를 수신하기 전까지 경과할 수 있는 시간 BGP 식별자: open 메시지를 전송한 라우터 선택 매개변수 길이: 선택적 매개변수 길이 선택 매개변수들: 선택적 매개변수(예:인증)

갱신(Update) 메시지

갱신(update) 메시지 라우터가 전에 광고된 목적지를 취소하거나 새로운 목적지를 알리는데 사용 불가능 경로 길이: 다음 필드의 길이 취소된 경로: 삭제되어야 하는 경로 나열 경로 속성 길이: 다음 필드의 길이 정의 경로 속성: 메시지를 통해 광고되는 도달가능한 네트워크까지의 경로에 대한 속성 네트워크 계층 도달가능 정보: 실제로 광고되어지는 네트워크

BGP supports classless addressing and CIDR. Note BGP supports classless addressing and CIDR.

킵얼라이브(Keepalive) 메시지 상대방에게 자신이 살아있음을 알리기 위해 유지 시간이 만료되기 전에 정기적으로 메시지 교환

통지(Notification) 메시지 오류 상황이 감지되거나 연결을 닫기 원할 때 라우터에 의해 전송

BGP uses the services of TCP on port 179. Note BGP uses the services of TCP on port 179.

알림 연습문제 풀이해서 Report로 다음주까지(일주일 후) 제출해 주세요!