컴퓨터 네트워킹 하향식 접근 - 5. 네트워크 계층 : 제어 평면

 

5.1 개요

데이터 평면이 실제 사용자의 데이터가 이동하는 경로라면, 제어 평면은 그 이동 경로를 결정하고 관리하는 부분이다. 라우팅 테이블을 만들고 업데이트하며 네트워크의 운영을 담당한다.

5.2 라우팅 알고리즘

라우팅 알고리즘은 송신자부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로(= 최소 비용 경로)를 결정한다.

링크 상태(LS) 라우팅 알고리즘

1. 처음에 u 노드에서 시작할 때, 가장 비용이 적은 w로 가는 경로가 선택된다.
2. 2단계의 u→v 경로는 직접 가는 길과 u→w→v로 가는 길 중 비용이 적은 값을 기준으로 업데이트된다.
3. 이러한 과정으로 계속해서 진행하여 다음과 같은 그래프가 만들어진다.

• 다익스트라 알고리즘의 복잡도는 O(n^2) or 개선 시 O(nlogn)
• 어느 경로로 트래픽이 몰려서 다른 경로를 택하고, 그 다른 경로로 트래픽이 몰려서 다시 이전 경로를 선택하는 것을 반복하는 진동 문제가 발생할 수 있음

거리 벡터(DV) 라우팅 알고리즘

거리 벡터 알고리즘은 특정 라우터와 연결된 이웃 라우터의 정보만을 가지고 판단한다. 대표적으로 Bellman-Form 알고리즘이 있다.

u→z 노드로 가는 최단 경로를 찾을 때,

1. Dv(z)=5, Dx(z)=3, Dw(z)=3 을 계산한다.
2. Du(z)를 벨만-포드 식을 이용해 계산한다.

벨만-포드 식 : Dx(y) = minv{ c(x, v) + Dv(y) }

이때 Dv(z), Dx(z), Dw(z) 값들은 기본적으로 이미 알고 있다고 가정하므로 u 노드 입장에서는 신경 쓰지 않는다. 즉 u 노드는 단순히 이전에 이미 같은 과정을 거쳐 나온 결과를 이용하기만 한다.

링크 비용이 감소할 때는 네트워크 전역에 빠르게 전파되는 반면, 링크 비용이 증가할 때는 라우팅 루프가 발생하여 링크 비용 증가 소식이 네트워크 상에서 느리게 전파된다. 네트워크 상황을 가정해 보자.

라우터 A, B, C, 목적지는 D일 때

• A→D로 가는 최적 경로 : A→B→D (총비용 20)
• B→D로 가는 최적 경로 : B→D (총 비용 10)
• C→D로 가는 최적 경로 : C→B→D (총 비용 20)

에서 B와 D 사이의 링크 비용이 갑자기 60으로 증가하면

1. B가 비용 변화를 감지하고 C를 통한 경로가 더 저렴하다고 잘못 판단함
2. B→D의 최적 경로를 B→C→D로 설정했지만 C의 라우팅 테이블에는 C→D의 최적 경로가 C→B→D로 되어있음
3. 이렇게 되면 B와 C 사이에서 패킷이 계속 순환함

이 문제는 포이즌 리버스라는 방법을 사용해 방지할 수 있다. 만약 z가 y를 통해서 목적지 x로 가는 경로 설정을 했다면 z는 y에게 x까지의 거리가 무한대라고 알림으로써 이 문제를 예방한다. 하지만 3개 이상의 노드를 포함한 라우팅 루프는 포이즌 리버스로는 감지할 수 없는 한계점이 있다.

링크 상태 알고리즘과 거리 벡터 라우팅 알고리즘의 비교

메시지 복잡성

• 링크 상태 알고리즘은 모든 라우터가 전체 네트워크의 상태 정보를 공유해야 하므로 네트워크에 N개 노드가 있고 E개의 링크가 있다면 메시지 복잡성은 O(NxE)가 된다.
• 거리 벡터 알고리즘은 이웃 라우터의 정보만 공유하므로 메시지 복잡성은 O(N)이다.

수렴 속도

• 링크 상태 알고리즘은 다익스트라 알고리즘을 사용하면 O(N^2)의 복잡도를 가진다.
• 거리 벡터 알고리즘은 최악의 경우 O(NxV)의 시간이 걸린다. (V는 노드의 수)

견고성

• 링크 상태 알고리즘은 각 라우터가 독립적으로 경로를 계산하므로 오류에 강함
• 거리 벡터 알고리즘은 서로의 정보에 의존하므로 오류에 취약함

→ 링크 상태 알고리즘은 더 많은 리소스를 사용하지만 더 빠르고 안정적인 반면, 거리 벡터 알고리즘은 더 단순하고 효율적이지만 오류에 취약함

5.3 인터넷에서의 AS 내부 라우팅 : OSPF

지금까지 모든 라우터가 동일한 라우팅 알고리즘을 수행하는 것처럼 설명했지만 이렇게 되면 두 가지 문제가 발생한다.

 

확장

• 라우터의 수가 증가하면 라우팅 정보의 통신, 계산, 저장에 필요한 오버헤드가 걷잡을 수 없이 증가함
• 오늘날 인터넷은 수억 개의 라우터로 구성되고 이들 각각에 모든 가능한 목적지의 라우팅 정보를 저장하기 위해서는 막대한 메모리가 필요하며 브로드캐스트 하는 데 필요한 오버헤드는 엄청날 것임

관리 자율성

• ISP들은 각각 자신의 라우터들로 구성된 네트워크를 관리함
• 이때 자신의 네트워크를 원하는 대로 운용하거나 내부 구성을 외부에 감추고 싶어 할 수 있음

→ 따라서 라우터들을 자율 시스템(autonomous system, AS)으로 조직화하여 해결했다.

각 AS는 동일한 관리 제어하에 있는 라우터의 그룹으로 구성된다. 같은 AS 안에 있는 라우터들은 동일한 라우팅 알고리즘을 사용하고 상대방에 대한 정보를 갖고 있다. 자율 시스템 내부에서 동작하는 라우팅 알고리즘을 AS 내부 라우팅 프로토콜이라고 한다.

개방형 최단 경로 우선(OSPF) 프로토콜

개방형 최단 경로 우선(open shortest path first, OSPF) 라우팅은 AS 내부 라우팅에 널리 사용된다. OSPF는 링크 상태 정보를 플러딩 하고 다익스트라 최소 비용 경로 알고리즘을 사용하는 링크 상태 알고리즘이다. 각 라우터는 전체 AS에 대한 완벽한 그래프를 얻고 각 라우터는 자신을 루트 노드로 두고 다익스트라 알고리즘을 통해 모든 서브넷에 이르는 최단 경로 트리를 결정한다. 이때 개별 링크들의 비용은 네트워크 관리자가 구성한다.

링크 상태 알고리즘에서 먼저 링크 가중치가 설정되고, OSPF 같은 라우팅 알고리즘이 수행되며, LS 알고리즘에 의해 계산된 라우팅 테이블의 내용에 따라 트래픽이 흐른다고 가정했다. 실제로는 이 원인과 결과 관계가 반대로 될 수 있다. 즉, 네트워크 운영자가 트래픽 관리 목표를 충족시키는 라우팅 경로를 얻기 위해 링크 가중치를 설정할 수 있다.

 

OSPF를 사용하는 라우터는 링크 상태가 변경될 때마다, 또한 링크 상태가 변경되지 않았더라도 주기적으로(최소 30분마다 한 번씩은) 링크 상태를 브로드캐스팅한다.

5.4 인터넷 서비스 제공업자(ISP) 간의 라우팅 : BGP 

패킷이 여러 AS를 통과하도록 라우팅 할 때는 자율 시스템 간 라우팅 프로토콜이 필요하다. AS 간 라우팅 프로토콜은 여러 AS 간의 협력이 수반되므로 통신하는 AS들은 같은 AS 간 라우팅 프로토콜을 수행해야 한다. 인터넷의 모든 AS는 경계 게이트웨이 프로토콜(Border Gateway Protocol, BGP)이라고 불리는 동일한 AS 간 라우팅 프로토콜을 사용한다.

BGP 프로토콜

목적지가 AS 외부에 있을 때 BGP가 필요하다. BGP에서는 패킷이 특정한 목적지 주소를 향해서가 아니라 CIDR 형식으로 표현된 주소의 앞쪽 프리픽스를 향해 전달된다. BGP는 각 라우터에게 다음을 제공한다 :

• 어떤 서브넷이 존재하면 BGP는 인터넷의 모든 라우터가 이 서브넷의 존재를 알 수 있도록 만든다
• 서브넷 주소 프리픽스로의 가장 좋은 경로를 결정한다.

3개의 AS를 갖는 네트워크가 있고, AS3은 주소 프리픽스가 x인 서브넷을 포함한다. BGP에서 각 라우터의 쌍들은 반영구적인 TCP 연결을 통해 라우팅 정보를 교환한다. 이 TCP 연결을 통해 모든 BGP 메시지가 전송되는데 이 연결을 BGP 연결이라고 한다. 그리고 2개의 AS를 연결하는 BGP 연결은 외부 BGP 연결이라고 하고, 같은 AS 내의 라우터 간 BGP 연결은 내부 BGP 연결이라고 한다.

프리픽스 x에 대한 도달 가능 정보를 AS1과 AS2의 모든 라우터에게 알리는 경우, 게이트웨이 라우터 3a는 2c에게 ‘AS3 x’라는 eBGP 메시지를 보낸다. 그다음 2c는 iBGP 메시지 ‘AS3 x’를 2a를 포함한 AS2 내부의 모든 라우터에게 전송하고 2a는 eBGP 메시지 ‘AS2 AS3 x’를 게이트웨이 라우터 1c에게 보낸다. 마지막으로 1c는 iBGP를 사용하여 AS1 내의 모든 라우터에게 메시지 ‘AS2 AS3 x’를 전달한다. 이 과정을 통해 AS1, AS2의 각 라우터들은 x의 존재와 x로 향하는 AS 경로를 알게 된다.

라우터가 BGP 연결을 통해 주소 프리픽스를 알릴 때 BGP 속성도 함께 포함한다.

• AS-PATH : 알림 메시지가 통과하는 AS들의 리스트
• NEXT-HOP : AS-PATH가 시작되는 라우터 인터페이스의 IP 주소. 위의 AS1에서 AS2를 우회하여 x로 가는 ‘AS3 x’ 경로의 NEXT-HOP 속성은 라우터 3d의 맨 왼쪽 인터페이스의 IP 주소다.

여기서 AS1의 각 라우터는 프리픽스 x로 가는 2개의 BGP 경로를 알게 된다.

• 라우터 2a의 맨 왼쪽 인터페이스의 IP 주소 : AS2 AS3 ; x
• 라우터 3d의 맨 왼쪽 인터페이스의 IP 주소 : AS3 ; x

최고의 경로 설정

뜨거운 감자 라우팅

뜨거운 감자 라우팅은 가장 단순한 라우팅 알고리즘 중 하나로 가능한 모든 경로 중 경로 각각의 시작점인 NEXT-HOP 라우터까지의 경로 비용이 최소가 되는 경로를 선택한다.

1. 여러 게이트웨이를 통해 서브넷 x에 도달할 수 있다는 사실을 AS 간 프로토콜로부터 알게 된다.
2. 각 게이트웨이까지의 최소 비용 경로를 정하기 위해 AS 내부 프로토콜을 통해 얻은 라우팅 정보를 이용한다.
3. 뜨거운 감자 라우팅: 가장 적은 비용의 게이트웨이를 선택한다.
4. 포워딩 테이블로부터 최소 비용 게이트웨이로의 인터페이스 I를 결정한 후 포워딩 테이블에 (x, I)를 추가한다.

위의 예시에서 라우터 1b는 주소가 x로 시작하는 서브넷으로 가는 2개의 BGP 경로를 알고 있고 NEXT-HOP 라우터 2a, 3d 각각에 대해 최소 비용을 가진 AS 내부 경로를 찾기 위해 AS 내부 라우팅 정보를 조사하여 이들 최소 비용 경로 중에서도 가장 적은 비용을 가진 경로를 선택한다. 이후 라우터 1b는 자신의 포워딩 테이블을 관찰하여 라우터 2a로 가기 위한 인터페이스 I를 찾아내고 엔트리 (x, I)를 자신의 포워딩 테이블에 추가한다.

즉, 뜨거운 감자 라우팅은 자신의 경로 중에서 자기 AS 내부 비용만 줄이려는 이기적인 알고리즘이다. 이를 사용하면 한 AS 내 2개의 라우터가 동일한 목적지 주소에 대해 각기 다른 AS 경로를 선택할 수도 있다. 위의 예시에서 라우터 1b는 AS2를 통해 서브넷 x로 패킷을 보내지만 라우터 1d는 바로 A3으로 보내 서브넷 x에 도달한다.

 

경로 선택 알고리즘 

실제로 BGP는 뜨거운 감자 알고리즘을 포함하는 더 복잡한 알고리즘을 사용한다. 뜨거운 감자 라우팅에 지역 선호도(local preference)가 경로에 할당되어

1. 최고 지역 선호 값을 가진 경로 선택
2. 최고 지역 선호 값을 가진 경로가 여러 개 있다면 이들 중에서 최단 AS-PATH를 가진 경로 선택
3. 같은 최고 지역 선호 값 및 같은 AS-PATH 길이를 가진 모든 남은 경로들에 대해 뜨거운 감자 라우팅을 수행한다.
4. 만일 아직도 하나보다 많은 경로가 남아있다면 BGP 식별자를 사용하여 경로를 선택한다.

위의 예시에서 뜨거운 감자 라우팅이 사용된다면 BGP는 AS2를 통과하는 경로로 패킷을 보낸다. 하지만 위의 경로 선택 알고리즘에서 규칙 2가 규칙 3보다 먼저 적용되므로 더 짧은 AS-PATH를 가진 AS2 우회 경로가 선택된다.

IP 애니캐스트

BGP는 IP 애니캐스트를 구현하는 데도 활용된다. CDN은 비디오 등 자료를 각기 다른 나라의 서버들에 복제해 둔다. 이런 경우 어떤 사용자가 이 복제된 콘텐츠에 접근을 원할 때 사용자에게 복제된 콘텐츠를 가진 가장 가까운 서버를 알려주기 위해 BGP가 사용된다.

CDN 사업자는 자신의 서버 여러 대에 동일한 IP 주소를 할당하고 표준 BGP를 활용하여 이 주소를 서버 각각으로부터 알린다. BGP 라우터가 이 IP 주소에 대한 여러 개의 경로 알림 메시지를 받으면 이를 동일한 물리적 위치로의 서로 다른 경로에 대한 정보를 제공받고 있는 것으로 생각하고 해당 IP 주소로의 최적의 경로를 선택한다.

사용자가 비디오를 요청하면 CDN은 사용자가 어디에 있든 상관없이 지리적으로 분산되어 있는 서버들이 공통적으로 사용하는 IP 주소를 사용자에게 돌려준다.

실제로는 BGP 라우팅이 변경되면 하나의 TCP 연결에 속한 패킷들이 서로 다른 복제 웹 서버로 도착할 수 있기 때문에 CDN은 위의 예처럼 IP 애니캐스트를 사용하지 않으며, DNS 시스템에서는 DNS 질의를 가장 가까운 루트 DNS 서버로 전달하기 위해 IP 애니캐스트를 광범위하게 사용된다.

라우팅 정책

AS 라우팅 정책은 최단 AS-PATH나 뜨거운 감자 라우팅 등 다른 모든 고려사항보다 우선시 된다.

여기서 A, B, C, W, X, Y 6개의 AS가 서로 연결되어 있다.

• W, X, Y는 사용자 접속 ISP
• A, B, C는 백본 제공자 네트워크
• ISP 접속 네트워크로 들어오는 모든 트래픽은 그 네트워크를 목적지로 해야만 함
• ISP 접속 네트워크에서 나가는 트래픽은 그 네트워크 안에서 생성된 것이어야만 함

→ W, Y는 접속 ISP이고, X는 두 제공자를 통해 네트워크의 다른 부분들과 연결되어 있으므로 다중 홈 접속 ISP라고 한다.

그러나 W나 Y처럼 X도 자신에게 들어오고 나가는 모든 트래픽의 목적지 또는 출발지여야 한다. 이는 BGP 경로의 알림 방식을 제어함으로써 해결된다. X는 자기 자신을 제외하고는 다른 어떤 목적지로도 경로가 없다고 알림으로써 접속 ISP 네트워크의 역할을 하게 된다. 즉 X가 Y까지 가는 XCY라는 경로를 알고 있더라도 이 경로를 B에게 알리지 않는다.

서비스 제공자 B는 A가 W까지의 경로 AW를 알게 되었다고 가정하자. B는 경로 AW를 자신의 라우팅 정보 테이블에 기록하고 자신의 고객인 X가 B를 통해 W로 갈 수 있음을 알게 하기 위해 경로 BAW를 X에게 알리길 인할 것이다. 그런데 이때 B가 C에게 BAW 경로를 알리면 C는 해당 경로를 통해 W까지 트래픽을 보낼 수 있는데, C→A→W로 보내면 되는데 C→B→A→W로 가므로 트래픽을 전달하는 짐을 지게 된다. 따라서 현재 백본 ISP들 사이의 경로를 결정하는 방법에 대한 공식적인 표준은 없지만 상업적 ISP들이 따르는 대략적인 규칙은 ISP 백본 네트워크를 통해 흐르는 트래픽은 해당 ISP의 고객 네트워크를 출발지로 하거나 목적지로 해야 한다는 것이다.

조각 맞추기 : 인터넷 존재 확인하기

우리가 작은 회사를 설립했고 회사에는 우리 회사의 서비스를 설명하는 공개 웹 서버, 직원들이 email을 받을 수 있는 메일 서버, DNS 서버 등 많은 서버가 있다고 가정하자. 우리는 전 세계 사람들이 우리 사이트를 방문하도록 하고 싶어 한다. 어떻게 존재를 알릴 수 있을까?

1. 먼저 지역 ISP와 계약하여 인터넷 연결을 해야 한다. 우리 회사는 게이트웨이 라우터를 갖게 될 텐데, 이는 지역 ISP의 라우터에 연결된다.
2. 지역 ISP는 특정 범위의 IP 주소를 제공하고 우리는 웹 서버, 메일 서버, DNS 서버, 게이트웨이 라우터와 다른 서버 및 네트워킹 장치들에 IP 주소를 할당한다.
3. 우리는 도메인 네임도 얻고 싶다. 다른 사람이 서버의 IP 주소를 얻기 위해 우리의 DNS 서버에 접속하기를 원할 것이므로 DNS 서버의 IP 주소를 등록 기관에 제공한다.
4. 그러면 등록 기관은. com 최상위 도메인 서버에 우리 DNS 서버(도메인네임과 IP주소)를 추가한다.
5. 사람들이 우리 서버의 IP 주소를 검색할 수 있도록 우리 DNS 서버에 호스트 네임(`www.xxx.com`)과 IP 주소의 매핑 항목을 포함시킨다.
6. 우리 웹 서버의 IP 주소를 알아낸 사람이 그 IP 주소로 IP 데이터그램을 보낼 때 데이터그램은 인터넷을 통해 라우팅 되어 여러 AS의 라우터들을 거친 후 웹 서버에 도착한다.
7. 라우터들 각각이 이 데이터그램을 수신하면 어느 출력 포트로 내보내야 하는지 결정하기 위해 자신의 포워딩 테이블에서 해당 엔트리를 찾는다. 그리고 이 과정이 BGP를 통해서 이루어진다
8. 즉 회사가 지역 ISP와 계약하고 주소 프리킥스를 할당받을 때 지역 ISP는 BGP를 사용하여 자신과 연결되어 있는 ISP들에게 회사의 주소 프리픽스를 알린다
9. 연결된 ISP들 역시 BGP를 활용하여 이 알림 정보를 전파한다.