sehee

[TCP/IP Protocol #11] Part 2 | Chapter 11. 유니캐스트 라우팅 프로토콜(RIP, OSPF and BGP)

유니캐스트 라우팅 프로토콜1(거리 벡터 RIP, 링크 상태 OSPF)

RIP(Routing Information Protocol): 거리 벡터 프로토콜

OSPF(Open Shortest Path First): 링크 상태 프로토콜

BGP(Border Gateway Protocol): 경로 벡터 프로토콜

3. 경로 벡터 라우팅

거리 벡터와 링크 상태 라우팅은 모두 도메인 내부 라우팅 프로토콜이다. 하지만 이 두 프로토콜은 확장성으로 인해 도메인 간 라우팅에는 대부분 적합하지 않다.

- 거리 벡터 라우팅은 동작하는 도메인에 수 홉 이상이 존재하게 되면 불안정해질 수 있다.

- 링크 상태 라우팅은 라우팅 테이블을 계산하기 위해 아주 많은 양의 자원을 필요로 한다. + 플러딩으로 인해 많은 트래픽을 유발할 수도 있다.

* 플러딩: 모든 다른 라우터로 효과적이며 안전한 방법으로 LSP들을 발송하는 것

→ 제 3의 라우팅 프로토콜이 필요, 이것이 경로 벡터 라우팅(path vector routing)

경로 벡터 라우팅의 원리는 거리 벡터 라우팅과 유사하다.(각 자율 시스템에 하나의 스피커 노드만이 다른 것들과 통신할 수 있다는 것을 제외하고는)

자율 시스템 내에 있는 하나의 노드를 스피커 노드(speaker node)라고 부른다.

(다른 AS들에 정보를 제공하기 위해 각 AS는 그 AS에 있는 각 망의 도달 가능성 정보를 모으는 적어도 하나의 경로 벡터 라우팅을 가져야만 한다.)

BGP

경계 게이트웨이 프로토콜(BGP: Border Gateway Protocol), 자율 시스템 간의 라우팅 프로토콜

자율 시스템의 유형

인터넷은 자율 시스템이라고 불리는 계층적 도메인으로 나뉜다.

3개의 범주로 나눌 수 있음: 스터브, 멀티홈, 경유(transit) 시스템

스터브 AS

Stub AS, 다른 자율 시스템과 단 하나의 연결만을 가진다.

스터브 AS 내의 도메인 간 데이터 트래픽은 AS 내에서 생성되거나 사라질 수 있다. 그러나 데이터 트래픽은 스터브 AS를 통해 지나갈 수는 없다. 스터브 AS는 송신자 이거나 수신자 일 수 있다.

멀티홈 AS

Multihomed AS, 다른 자율 시스템과 하나 이상의 연결을 가진다.

하나의 자율 시스템에서 다른 시스템으로 지나가는 트래픽은 허용되지 않고, 데이터 트래픽의 송신자나 수신자만 될 수 있다.

e.g., 지나가는 트래픽을 허용하지 않는 하나 이상의 지역혹은 국가 AS에 연결된 큰 조직이 될 수 있다.

경유 AS

지나가는 트래픽을 허용하는 멀티홈 AS

e.g., 국가 혹은 국제 ISP(인터넷 백본)

CIDR

BGP는 클래스 없는 도메인 간 라우팅 어드레스(CIDR)을 사용한다.

경로 속성

경로는 자율 시스템의 목록으로 표현되었지만 사실은 속성(attributes)들의 목록이라고 할 수 있다.

각 속성은 경로에 대한 정보를 제공한다.

속성들은 두 개의 큰 영역으로 나뉜다. 하나는 잘 알려진 것이고 하나는 옵션이다.

1) 잘 알려진 속성들: 모든 BGP 라우터가 반드시 인식해야만 하는 것들

- 필수 속성: 경로를 기술하는 데 반드시 있어야 한다.

(e.g., ORIGIN: 경로 정보(RIP, OSPF 등)를 제공하는 발신지를 나타낸다.

AS_PATH: 목적지에 도달하기 위해 거쳐야 하는 자율 시스템의 목록

NEXT-HOP: 데이터 패킷이 보내져야 할 다음 라우터

- 임의(discretionary) 속성: 각 라우터가 반드시 인식할 수 있어야 하나 모든 갱신 메시지에 포함되지 않아도 되는 것

2) 선택적인 속성들(옵션): 모든 라우터에서 인식될 필요는 없는 것들

- 천이(transitive): 이 라우터가 이 속성을 지원하지 않더라도 다음 라우터로 전달되어야만 하는 것

- 비천이(nontransitive): 수신한 라우터가 이 속성을 지원하지 않으면 버려지는 것

BGP 세션

BGP를 사용해서 두 라우터 간 라우팅 정보를 교환하는 것은 세션에서 일어난다.

세션은 라우팅 정보를 교환하기 위해서만 두 BGP 라우터들 간에 설정되는 연결이다.

신뢰성 있는 환경을 만들기 위해 BGP는 TCP 서비스를 사용한다. 그러나 BGP를 위해 만들어진 TCP 연결은 다른 응용 프로그램에서와는 다른 약간의 차이가 있다. BGP를 위해 TCP 연결이 만들어지면 무언가 일반적이지 않은 일이 발생하기 전까지 오랜 시간 동안 유지된다.

→ BGP 세션은 반영구적 연결이라고도 불린다.

외부 및  내부 BGP

BGP에는 두 가지 종류의 세션이 있다.

1) 외부(external) BGP(E-BGP) 세션: 서로 다른 자율 시스템에 속하는 두 스피커 노드들 간에 정보 교환을 위해 사용된다.

- 두 스피커 라우터들은 인터넷에 있는 네트워크에 관해 자신이 아는 정보를 교환한다.

e.g., AS1과 AS2 사이에 설정된 세션

2) 내부(internal) BGP(I-BGP) 세션: 자율 시스템 내의 두 라우터 간에 정보 교환을 위해 사용된다.

- 스피커 라우터들이 자율 시스템 내의 다른 라우터로부터 정보를 수집하기 위해 필요하다.

패킷 형식

4가지 패킷 종류: open, update, keepalive, notification

개방(Open) 메시지

BGP가 동작중인 라우터가 이웃 관계를 생성하기 위해서는 그 이웃과 TCP 연결을 열고 개방 메시지를 전송한다.

이웃 관계를 받아들이면 두 라우터 간 이웃 관계가 성립되었다는 뜻으로 킵얼라이브(keepalive) 메시지를 보내게 된다.

- 필드: BGP 버전(현재는 4), 자율 시스템 번호, 유지 시간, BGP 식별자(개방 메시지를 전송한 라우터), 선택 매개 변수들 및 길이

갱신(Update) 메시지

BGP 프로토콜의 중심, 라우터로 하여금 전에 광고된 목적지를 취소하거나 새로운 목적지로의 경로를 알리는 데 사용된다.

- 필드: 불가능 경로 길이(다음 필드의 길이), 취소된 경로(광고된 목록 중에서 삭제되어야 하는 모든 경로를 나열), 경로 속성 및 길이(도달 가능한 네트워크까지의 경로에 대한 속성), 네트워크 계층 도달 가능 정보

킵얼라이브(Keepalive) 메시지

BGP가 동작되는 라우터들은 상대방에게 자신들이 살아있음을 알리기 위해 유지 시간이 만료되기 전에 정기적으로 킵얼라이브 메시지를 교환한다.

- 필드: 공통 헤더만으로 구성됨

통지(Notification) 메시지

오류 상황이 감지되거나 연결을 닫기 원할 때 라우터에 의해 전송된다.

- 필드; 오류 코드, 오류 서브 코드(유형), 오류 데이터

캡슐화

BGP 메시지는 잘 알려진 포트 179를 사용하여 TCP 세그먼트에 캡슐화된다. 이는 오류 제어나 흐름 제어가 필요하지 않음을 의미한다.

TCP 연결이 개설되면 종료(cease) 유형의 통지(notification) 메시지가 전송될 때까지 갱신, 킵얼라이브, 통지 메시지의 교환이 게속된다.

Reference

Behrouz A. Forouzan (2009), TCP/IP 프로토콜(Protoccol Suite), 4th Edition

[TCP/IP Protocol #11] Part 2 | Chapter 11. 유니캐스트 라우팅 프로토콜(RIP, OSPF and BGP)

유니캐스트 통신: 하나의 송신자와 하나의 수신자 간의 통신을 의미, one-to-one 통신

유니캐스트 통신을 지원하기 위해 라우터에 생성되는 라우팅 테이블에 관해 논의할 것

자율 시스템(AS: Autonomous System)

비용 또는 메트릭

라우터가 패킷을 수신했을 때, 어느 네트워크로 패킷을 보내야 하는가? 이 결정은 최적화 과정에 기반을 둔다.
그렇다면 최적의 경로란 무엇인가? 최적이라는 용어의 정의는 무엇인가?

망을 통해 전달되는 비용(cost)를 할당하는 것, 이 비용을 메트릭(metric))이라 부른다.

망에서 성능을 최대한 혹은 지연 시간을 최소로 하고 싶다면 성능이 높은 것/낮은 지연 시간이 낮은 비용을 의미한다.

도메인 내 및 도메인 간 라우팅

근래 들어 인터넷은 한 가지 라우팅 프로토콜로 모든 라우터의 라우팅 테이블을 갱신하는 작업을 수행하기에는 부족할 정도로 너무 많이 확장되었다. 이런 이유로 인터넷은 자율 시스템(AS: Autonomous System)으로 나눠진다.

- 자율 시스템: 하나의 단일 관리 기관 하에 있는 라우터와 네트워크의 그룹

- 도메인 내(intradomain) 라우팅: 자율 시스템 내에서의 라우팅 (e.g., 거리 벡터(RIP), 링크 상태(OSPF))

- 도메인 간(interdomain) 라우팅: 자율 시스템 간의 라우팅 (e.g., 경로 벡터(BGP))

RIP(Routing Information Protocol): 거리 벡터 프로토콜

OSPF(Open Shortest Path First): 링크 상태 프로토콜

BGP(Border Gateway Protocol): 경로 벡터 프로토콜

1. 거리 벡터 라우팅

distance vector routing

모든 라우터와 망들로 구성된 AS를 노드의 집합과 이 노드들을 연결하는 선(에지)들로 구성된 그래프로 간주한다.

그래프 이론은 노드들 간의 거리가 주어진 망에서 노드들 간의 최단 거리를 찾기 위해 Bellman-Ford(또는 Ford-Fulkerson)라고 불리는 알고리즘을 사용한다.

Bellman-Ford 알고리즘

임의의 두 노드 쌍 간의 비용을 안다면 두 노드 간의 최소 비용(최단 거리)을 찾을 수 있다.

1) 각 노드와 자신 간의 최단 거리 및 비용을 0으로 초기화함

2) 각 노드와 다른 노드와의 최단 거리를 무한대로 설정함. 그 후 노드와 다른 노드 간의 비용을 주어진 값으로 설정하되 연결이 없으면 무한대로 유지함

3) 최단 거리 벡터에 변경 사항이 더 없을 때까지 알고리즘을 반복함

거리 벡터 라우팅 알고리즘

Bellman-Ford 알고리즘은 도시 간의 도로 지도에 매우 잘 적용된다. (∵ 동일한 지역에 있는 각 노드 간의 초기 정보가 모두 주어지기 때문)

비용: 홉 수 (즉, 목적지에 도달하기 위해 얼마나 많은 망을 거쳐 가야 하는 가, 두 노드 간의 비용은 1로 설정)

각 라우터 필수 보유 정보: 목적지 망, 비용, 다음 홉(next-hop) 정보

무한대로의 카운트

라우팅 프로토콜이 잘 동작하기 위해서는 링크가 고장 나서 비용이 무한대로 바뀌었을 때 모든 다른 라우터들이 이를 즉시 인식할 수 있어야 하는데, 거리 벡터 라우팅에서는 이에 시간이 소요된다.

이 문제: 무한대로의 카운트

두 노드 루프

노드 A와 B는 노드 X에 도달하는 방법을 알고 있다. 그러나 갑자기 A와 X 사이의 링크가 실패했다고 하며 노드 A는 자신의 테이블을 변경한다.

만약 노드 A가 즉각적으로 B에게 테이블을 전송하면 문제가 없다. 그러나 만약 B가 라우팅 테이블을 A로부터 받기 전에 자신의 라우팅 테이블을 보내게 되면 시스템이 불안정해진다.

무한대의 정의

첫 번째 해결책, 무한대를 16과 같은 작은 수로 재정의 (거리 벡터 라우팅의 대부부 구현에서 16을 무한대로 정의)

→ 각 방향으로의 망의 크기가 15 홉을 넘을 수 없음
→ 거리 벡터 라우팅이 큰 시스템에서 사용될 수 없음을 의미

수평 분할

각 인터페이스를 통해 테이블을 플러딩(flooding)하는 대신에 각 인터페이스를 통해 자신 테이블의 일부만을 전송

노드 B가 X에 도달하는 최적의 경로가 A를 거치는 것이라는 것을 안다면 다시 알릴 필요 없음 (이미 A는 알고 있기 때문)

수평 분할과 poison reverse

보통 거리 벡터 프로토콜은 타이머를 사용하고, 경로 상에 새로운 소식이 없으면 테이블에서 이 경로를 제거함

혹은 수평 분할 시나리오에서 노드 B가 A로 보내는 광고에 X로의 경로를 제거해 버림

→ (수평 분할 정책의 단점) 노드 A: 수평 분할 정책 때문에 그런 것인지, B가 최근에 X에 관한 소식을 받지 못해서인지 예측할 수 없음

→ (poison reverse) 동일하게 광고하되, 거리 값을 무한대로 설정해서 "이 값을 사용하지 말라"고 경고함

세 노드 불안정성

X가 도달 가능하지 않음을 발견한 후 노드 A가 이 상황을 노드 B와 C에 패킷을 전송해 알림

노드 B는 즉각적으로 테이블을 갱신했으나 노드 C로 가는 패킷은 유실

RIP

경로 정보 프로토콜
RIP에서 사용되는 메트릭으로, 거리는 목적지에 도달하기 위해 사용되어야만 하는 링크(네트워크)의 수로 정의된다. 이런 이유로 RIP에서의 메트릭은 홉 수라고 불린다.

2. 링크 상태 라우팅

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

라우팅 테이블 만들기

1) 각 노드에 의해 링크 상태를 생성하는 것: 이는 링크 상태 패킷(LSP: link state packet)이라고 함

2) 모든 다른 라우터로 효과적이며 안전한 방법으로 LSP들을 발송하는 것: 플러딩(flooding)이라고 부름

3) 각 노드에서 최단 경로 트리의 생성

4) 최단 경로 트리에 기반을 둔 라우팅 테이블의 계산

OSPF

Open Shortest Path First 프로토콜, 라우팅을 적절하게 수행하기 위해 OSPF는 자율 시스템을 여러 지역으로 나눈다.

지역(areas)이란 자율 시스템 내에 포함되는 호스트, 라우터 및 네트워크의 모음이다.

하나의 자율 시스템은 여러 개의 다른 지역들로 나뉠 수 있다. 지역 내의 모든 네트워크들은 연결되어야만 한다.

링크의 유형

네트워크는 링크(link)라고 불린다. 4가지 유형의 링크가 정의 되는데 각각 점-대-점(point-to-point), 경유(transient), 스터브(stub), 가상(virtual) 링크이다.

점-대-점 링크

라우터 간을 그 사이에 어떤 다른 호스트나 라우터 없이 직접 연결하는 것, 링크(네트워크)의 목적은 단지 라우터 간을 연결하는 것

경유 링크

몇 개의 라우터가 연결되어 있는 네트워크, 데이터는 어떤 라우터로도 들어갈 수 있고 어떤 라우터로부터도 떠날 수 있다.

각 라우터가 하나의 단일 네트워크를 통해 다른 라우터들과 연결되어 있다는 것을 보여주기 위해 네트워크 자체는 단일 노드로 표현되어야 한다. 그러나 여기서 문제가 되는 것은 네트워크가 장치가 아니므로 라우터로 동작할 수 없다는 것이다.

따라서 네트워크에 있는 라우터 중 하나가 이런 책임을 맡아야 한다. 이 라우터에게는 두 가지 목적이 주어지는데 하나는 실제 라우터로서 이고, 다른 하나는 지정(designated) 라우터로서 이다.

스터브 링크

단지 하나의 라우터에만 연결된 네트워크이다. 데이터 패킷은 이 단일 라우터를 통해서만 네트워크에 들어가거나 나갈 수 있다.

이런 상황을 나타내기 위해서는 라우터를 노드로, 네트워크를 지정 라우터로 표시해야 한다.

가상 링크

두 라우터간의 연결이 끊어지면 관리자는 여러 라우터를 거쳐 돌아가는 더 긴 경로를 사용하더라도 그 둘 사이에 가상 링크를 연결해야 한다.

Reference

Behrouz A. Forouzan (2009), TCP/IP 프로토콜(Protoccol Suite), 4th Edition