BGP

상위 문서: Network Layer

개요

BGP(Border Gateway protocol)은 수많은 AS들을 하나로 연결하는 역할을 하는 inter-AS 라우팅 프로토콜의 사실상의 표준이다.

역할

BGP의 역할을 이해하기 위해 하나의 AS와 그 안에 있는 임의의 라우터를 가정하자. 각 라우터는 forwarding table을 가지고 있으며, 이 테이블은 도착한 패킷을 어떤 출력 링크로 전송할지 결정하는 역할을 한다. 이때, 어떤 패킷의 출발지와 목적지가 동일한 AS 내에 속해 있다면, 해당 테이블의 항목은 AS 내부의 경로를 결정하는 intra-AS 라우팅 프로토콜에 의해 결정된다. 목적지가 반대로 AS 외부에 있다면, 이 경우에 BGP가 사용된다.

BGP에서는 패킷이 특정 목적지 주소로 라우팅되는 것이 아니라, CIDR prefix로 라우팅된다. 이때 각 CIDR prefix는 하나 이상의 subnet을 나타낸다. 예를 들어 임의의 패킷의 CIDR prefix는 138.16.68/22일 수 있으며, 이 경우 1024개의 인터페이스에 대한 IP 주소를 포함한다. 따라서, 라우터의 forwarding table의 각 항목은 (x, I)와 같이 구성되며, 이는 prefix x로 향하는 각 패킷은 인터페이스 I로 forwarding한다는 뜻이다. 이때 I는 다음 AS의 게이트웨이 라우터가 아니라, 경로에 연결되어 있는 다음 라우터의 인터페이스에 해당한다.

BGP 프로토콜은 각 라우터에게 다음과 같은 기능을 제공한다:

• prefix reachability에 대한 정보를 이웃 AS로부터 얻는다.
  • BGP는 각각의 subnet이 자신의 존재를 인터넷 전역에 "광고(advertise)"할 수 있도록 한다. 예를 들어 하나의 subnet이 "나는 여기 있어요!"라고 외치면, BGP는 인터넷 상의 모든 라우터가 이를 알게 한다.
  • eBGP: 다른 AS와 연결된 라우터들 간에 각 subnet의 reachability 정보를 교환하는데 사용되는 BGP 운용 방식이다.
  • iBGP: 동일한 AS 내의 라우터들 사이에서 eBGP로부터 얻은 정보를 공유하는데 사용되는 BGP 운용 방식이다.
  • 만약 BGP가 없다면, 각 subnet은 고립된 섬처럼 존재하며, 인터넷의 나머지와 연결되지 않는다.
• 어떤 prefix에 대한 최적의 경로를 설정한다.
  • 하나의 라우터는 특정 prefix가 가리키는 subnet으로 가는 경로를 여러 개 가질 수 있다. 이 경우, 라우터는 이웃의 라우터들로부터 얻은 reachability에 대한 정보를 BGP 프로토콜을 통해 활용하여 자체적으로 최적의 경로를 설정한다.
  • 이 경우, 최적의 경로를 결정하는 것은 단순히 shortest path 뿐만 아니라, 정치 역학으로부터도 영향을 받는다. 예를 들어, 한국에서 미국으로 향하는 패킷이 단순히 짧은 경로라고 해서 북한을 거쳐 간다는 것은 상상도 할 수 없다.

Advertising BGP Route Information

Figure 1. AS3 includes a subnet with prefix x

Figure 1과 같이 세 개의 AS인 AS1, AS2, AS3로 구성되어 있는 네트워크를 생각해보자. 모든 라우터들은 내부(internel) 라우터이거나, 게이트웨이(gateway) 라우터이며, AS1에는 1a, AS2에는 2a, 2c, AS3에는 3a가 게이트웨이 라우터이다. 이때, prefix x에 대한 정보를 모든 라우터에게 광고하는 과정을 고수준(higher-level)에서 살피면 다음과 같다:

1. AS3이 AS2에 BGP 메시지를 보내며, 이 메시지는 "x는 AS3에 있다"(AS3 x)는 내용을 담는다.
2. AS2는 AS1에 "x는 존재하며, AS2를 거쳐 AS3로 가면 된다"(AS2 AS3 x)는 메시지를 보낸다.

이런 방식을 통해 각 AS는 x의 존재와, x까지 이어지는 AS 경로(BGP 경로)도 알게 된다. 이때 AS 경로는 다음과 같은 속성들을 포함한다:

1. AS-PATH: 이 경로가 지나온 AS 목록이다.
2. NEXT-HOP: AS-PATH를 따르기 위해 거쳐야 하는 다음 AS의 게이트웨이 라우터이다. 이는 보통 해당 라우터가 위치한 AS에 BGP 경로를 광고한 라우터이다.

하지만, 이는 너무 단순화되어 있는 설명이며, 실제로는 각 AS 사이에서가 아니라, 라우터 수준에서 메시지가 송수신된다.

Figure 2. eBGP and iBGP connections

BGP에서는 라우터 쌍이 TCP 연결을 통해서 라우팅 정보를 교환되며, 교환되는 BGP 메시지이 사용하는 TCP 연결들을 통틀어 BGP 연결(connection)이라고 한다. 이때 두 AS에 걸친 BGP 연결은 eBGP 연결이라 하고, 동일 AS 내에서 이루어지는 BGP 연결은 iBGP라고 한다. 이는 figure 2에 잘 나타나 있다. 보통 서로 다른 AS의 게이트웨이 라우터를 직접 연결하는 링크마다 하나의 eBGP 연결이 존재하며, figure 2에는 c와 2a 사이, 그리고 2c와 3a 사이에 eBGP 연결이 존재한다. 또한 figure 2는 AS 내부의 모든 라우터 쌍마다 BGP 연결이 이루어진 일반적인 형태를 보여준다. 이를 통해 prefix x에 대한 reachability에 대한 정보를 광고하는 과정을 아래와 같이 더 자세히 살펴볼 수 있다:

1. 게이트웨이 라우터 3a가 eBGP 메시지 "AS3 x"를 게이트웨이 라우터 2c에 보낸다.
2. 2c는 그 정보를 iBGP를 통해 AS2의 다른 모든 라우터들(2a 포함)에게 전달한다.
3. 2a는 "AS2 AS3 x"라는 eBGP 메시지를 게이트웨이 라우터 1c에 보낸다.
4. 1c는 iBGP를 통해 AS1 내의 모든 라우터에게 "AS2 AS3 x" 메시지를 전달한다.

이러한 과정을 통해 AS1과 AS2 내에 있는 모든 라우터는 x의 존재와, x로 가는 AS 경로를 알게 된다.

BGP Route-Selection

HOT Potato Routing

Figure3. Network augmented with peering link between AS1 and AS3

실제 네트워크에서는, 어떤 라우터에서 특정 목적지로 가는 여러 경로가 있을 수 있다. Figure 3는 기존 Figure 1에 1d에서 3d로 가는 물리적인 링크를 추가한 것이다. 이 경우 AS1에서 x로 가는 두 가지 경로가 존재한다. 하나는 1c를 통해 "AS2 AS3 x" 경로이고, 다른 하나는 1d를 통해 바로 "AS3 x" 경로이다. 예를 들어, Figure 3에서 라우터 1b는 prefix x로 향하는 두 개의 BGP 경로가 존재한다는 것을 광고받는다. 이러한 상황에서 사용되는 가장 간단한 알고리즘이 hot potato routing 알고리즘이다.

Hot potato routing에서는 가능한 모든 경로 중에서, 다음 라우터인 NEXT-HOP 라우터까지의 비용이 가장 적은 경로를 선택한다. Figure 3에서는 라우터 1b는 intra-AS 라우팅 정보를 참고하여 NEXT-HOP 라우터인 2a까지의 최소 비용 경로와 NEXT-HOP 라우터인 3d까지의 최소 비용 경로를 확인한 후, 이들 중 더 적은 비용의 경로를 선택한다. 예를 들어, 비용이 경유하는 링크 수로 정의된다면, 라우터 1b에서 라우터 2a까지의 최소 비용은 2이고, 라우터 3d까지의 최소 비용은 3이므로 라우터 2a가 선택된다. 라우터 1b는 intra-AS 알고리즘에 의해 구성된 forwarding table을 조회하여 라우터 2a까지 최소 비용 경로에 있는 인터페이스 I를 찾는다. 그런 다음 (x, I)를 forwarding table에 추가한다. 이때, 외부 AS의 prefix를 forwarding table에 추가하기 위해서는 inter-AS 라우팅 프토콜(BGP)와 intra-AS 라우팅 프로토콜(OSPF 등)이 모두 사용된다. 이는 BGP 연결을 통해 전달된 정보가 어떤 AS에 해당 prefix가 가리키는 subnet이 위치하는지 만을 알려줄 뿐, 구체적으로 패킷이 어떻게 전달되어야 하는지는 알려주지 않기 때문이다. 즉, 라우터는 어떤 인터페이스(I)로 보낼지를 알기 위해서, OSPF와 같은 intra-AS 프로토콜을 이용해 NEXT-HOP BGP 라우터까지의 최단 경로를 계산하고 이를 forwarding table에 반영한다.

Hot potato routing의 개념은 각각의 라우터가 패킷을 최대한 빨리 자신의 AS에서 내보내도록 하는 것이다. 즉, 목적지까지의 경로 중 자기 AS 외부의 나머지 비용은 신경 쓰지 않는다. 비유하자면 패킷은 손에 들고 있으면 뜨거운 감자와 같으며, 가능한 한 빨리 다른 사람(즉, 다른 AS)에게 넘기는 알고리즘이다. 따라서 Hot potato routing은 이기적인 알고리즘이라고 할 수 있다. 이로 인해 Hot potato routing에서는 같은 AS에 있는 두 라우터가 같은 prefix에 대해 서로 다른 AS 경로를 선택할 수도 있다.

Route-Selection Algorithm

실제로 BGP는 hot potato routing을 일부 포함하지만, 그보다는 조금 더 복잡한 알고리즘을 사용한다. 어떤 목적지 prefix에 대해 BGP의 경로 선택 알고리즘에 입력으로 사용되는 것은 해당 prefix에 대해 라우터가 입력받은 경로들의 집합이다. 이때 경로가 하나만 존재한다면 BGP는 당연히 그 경로를 선택하지만, 같은 prefix에 대해 둘 이상의 경로가 존재한다면, BGP는 다음의 제거 규칙을 순차적으로 적용하여 하나의 경로만 남을 때까지 반복한다:

1. 각 경로는 local preference 값을 속성 중 하나로 가지고 있다. 이 local preference 값은 라우터가 설정할 수도 있고, 같은 AS 내의 다른 라우터로부터 전달 받을 수도 있다. 이때, 가장 높은 local preference 값을 가진 경로들이 선택된다.
2. 남은 경로들 중에서는 AS-PATH가 가장 짧은 경로가 선택된다. 만약 이 규칙만으로 경로를 선택한다면, BGP는 AS의 hop 수를 값으로 사용하는 DV 알고리즘이 된다고 할 수 있다.
3. 남은 경로들 중에서는 hot potato routing이 적용되어, NEXT-HOP 라우터까지의 거리가 가장 짧은 경로가 선택된다.
4. 여전히 둘 이상의 경로가 남는다면, 라우터는 BGP identifier를 사용하여 경로를 선택한다.

예를 들어, 다시 figure 3를 기준으로 라우터 1b를 다시 생각한다면, prefix x로 향하는 BGP 경로는 정확히 두 개 있으며, 하나는 AS2를 경유하고, 다른 하나는 AS2를 우회한다. 해당 알고리즘을 적용한다면 결과적으로 AS2를 경유하는 hot potato routing과는 다르게, 더 짧은 AS-PATH를 가지는 경로, 즉 AS2를 거치지 않고 곧장 prefix x로 도달하는 경로를 선택한다. 따라서 해당 알고리즘을 사용하는 BGP는 이기적인 알고리즘이라고 할 수 없다. end-to-end 지연을 줄이기 위해 짧은 AS-PATH를 우선적으로 고려하기 때문이다.

IP-Anycast

Figure 4. Using IP-anycast to bring users to the closest CDN server

BGP 라우팅 프로토콜은 inter-AS 라우팅 프로토콜이라는 기본적인 역학 외에도, IP-anycast 서비스를 구현하는데 사용된다. IP-anycast는 동일한 콘텐츠를 여러개의 서로 다른 곳에 위치한 서버에 복제하고, 각 사용자가 해당 콘텐츠를 가장 가까운 서버로부터 접근하게 하고 싶은 경우에 종종 사용된다. 예를들어, CDN은 여러 콘텐츠들을 서로 다른 국가에 위치한 서버들에 복제하여 저장하고, DNS 시스템은 동일한 매핑 정보를 전세계에 있는 DNS 서버들에 복제하여 저장한다. 사용자들이 이들 콘텐츠에 접근할 때, 사용자에게 해당 콘텐츠를 가지는 가장 "가까운" 서버를 알려주는 것이 바람직하며, BGP의 경로 선택 알고리즘은 이것을 수행할 수 있는 메커니즘을 제공한다.

IP-Anycast의 작동 방식을 CDN의 예시를 통해 설명해보자. FIgure 4와 같이, IP-anycast 설정 단계에서 CDN 회사는 각 서버에 동일한 IP 주소를 할당하고, 각 서버에서 표준 BGP를 사용해 이 IP 주소를 광고한다. BGP 라우터가 이 IP 주소에 대한 여러 개의 경로를 전달 받으면, 해당 라우터는 이들 광고를 하나의 물리적 위치로 가는 서로 다른 경로로 간주한다. 각 라우터들이 라우팅 테이블을 설정할 때, 라우터는 경로 선택 알고리즘을 사용하여 해당 IP 주소에 대해 "가장 좋은" 경로를 선택한다.
이러한 초기 설정 단계들이 끝난 후, CDN은 본래의 목적, 즉 콘텐츠 배포를 수행할 수 있다. 클라이언트가 비디오를 요청할 때, CDN은 전 세계 여러 위치에 분산된 서버들이 공통으로 사용하는 IP 주소를 클라이언트에게 반환한다. 클라이언트가 이 IP 주소로 요청을 보내면, 인터넷의 라우터들은 BGP 경로 선택 알고리즘이 정의한 대로 가장 “가까운” 서버로 요청 패킷을 전달하게 된다.

이러한 IP-anycast는 실제로는 CDN에서는 잘 사용되지 않으며, DNS 시스템에서 광범위하게 사용된다.

Routing Policy

라우터가 어떤 목적지에 대한 경로를 선택할 때, AS의 라우팅 정책이 가장 중요한 기준이 될 수 있으며, 이는 AS 경로의 길이나 hot potato routing 같은 다른 모든 고려사항을 무시할 수 있다. 실제로 BGP의 경로 선택 알고리즘에서는 경로가 먼저 local-preference 속성에 따라 선택되는데, 이 속성 값은 해당 AS의 라우팅 정책에 의해 결정된다.

Figure 5. A simple BGP policy scenario

BGP 라우팅 정책의 기본적인 개념을 간단한 예제를 통해 살펴보자. Figure 5는 여섯 개의 AS(A, B, C, W, X, Y)가 서로 연결된 구조를 보여준다. W, X, Y는 액세스 ISP (access ISP)이고, A, B, C는 백본 제공자 네트워크(backbone provider network)이다. A, B, C는 서로 직접 트래픽을 주고받으며, 각자 자신의 고객 네트워크에게 전체 BGP 정보를 제공한다고 가정하자. 이때, 액세스 ISP에 대해 중요한 제약 사항이 두가지 존재한다:

• 액세스 ISP로 들어오는 모든 트래픽은 반드시 해당 액세스 ISP가 목적지로 해야 한다.
• 액세스 ISP에서 나가는 트래픽은 반드시 그 네트워크에서 시작한 것이다.

위의 제약 사항은 액세스 X, Y에 대해 명확하게 지켜진다. 하지만 X는 두 개의 다른 제공자에게 연결되어 있으므로 multi-homed 액세스 ISP이다. 그러나 W, Y처럼 X 자체도 그 안에서 시작되거나 끝나는 트래픽만을 전송해야 한다. 이러한 제약 사항은 BGP 경로의 광고를 제어하여 간단히 충족시킬 수 있다. 해당 예시에서 X가 액세스 ISP로 동작하게 하려면, 이웃인 B와 C에게 "자신 이외의 어떤 목적지도 갈 수 없다"고 광고하면 된다. 이를 통해 B는 X가 Y로 가는 경로를 알고 있다는 사실조차 알지 못하게 된다. 따라서 B는 X를 통해 Y나 C로 트래픽을 보내지 않는다. 이는 C에 대해서도 마찬가지이다.