sehee

[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