BGP (Border Gateway Protocol)

OSPF는 intra-AS routing protocol이다. 즉, OSPF는 같은 AS 내에서 패킷을 라우팅하는 프로토콜인 것이다. 그런 반면 BGP는 inter-AS routing protocol로, 패킷을 여러 개의 AS를 거쳐 라우팅할 때 쓰는 인터넷 프로토콜이다. 이때, 여러 개의 AS를 거친다는 것은 AS들이 소통해야 하는데 이를 위해선 AS들이 동일한 inter-AS routing protocol을 써야 한다. 그렇기에 현 인터넷에선 모든 AS들이 동일한 inter-AS routing protocol을 쓰고 있는데, 그것이 바로 BGP이다.

5.4.1 The Role of BGP

Forwarding Table Entry 설명

Forwarding table은 (x, l) 형태의 entry로 구성되어 있다. 이때, x는 목적지, l은 link(interface nubmer)를 의미한다. 즉, (x, l)은 패킷이 x라는 특정 목적지로 가려고 할 때, l link로 가야한다는 의미이다.

BGP와 Forwarding Table

OSPF이나 BGP 모두 라우팅 알고리즘으로써 라우터의 forwardig table을 결정한다. 특정 목적지로 가는 데 있어 최적의 경로를 파악하고, 그 경로를 바탕으로 다음에 어딜 가야하는지를 forwarding table에 작성한다. 이때, OSPF는 동일한 AS 내에 있는 목적지를 다루고 있기 때문에 forwarding table에는 구체적 목적지 주소를 적어놓는다. 그러나 BGP는 다른 AS에 있는 목적지로 패킷을 라우팅해야 하기 때문에 OSPF처럼 특정 목적지를 작성하지 않고 CIDR된 prefix를 작성한다. 각 prefix는 서브넷이나 서브넷 그룹을 가리킨다. 가령, BGP는 목적지를 138.16.68/22와 같은 형태로 작성하는데, 이는 1024개의 IP 주소를 가지고 있는 서브넷을 가리키고 있는 것이다. 그래서 BGP는 forwarding table에 (CIDR prefix, link) 형태의 entry를 작성한다.

BGP의 기능

BGP는 구체적으로 두 가지 기능을 제공하고 있다.
1. 주변 AS들의 prefix 정보 알아오기

• 더 구체적으로 말하자면 BGP는 각 서브넷이 그들의 존재를 인터넷 전체한테 알릴 수 있도록 한다. BGP는 인터넷에 있는 모든 라우터들이 서브넷들의 prefix 정보를 알아와서 모든 서브넷의 존재를 알 수 있도록 한다.

2. prefix 목적지로의 최적 경로 파악

• 라우터는 로컬로 BGP route-selection procedure를 돌린다. 주변 라우터들을 통해 얻은 prefix 정보를 바탕으로 알고리즘을 돌리고, 알고리즘의 정책과 정보를 기준으로 최적 경로르 파악한다.

5.4.2 Advertising BGP Route Information

BGP가 라우팅 정보를 전달하는 방식을 설명하기 앞서, AS에서의 라우터 종류와 BGP connection 종류에 대해 알 필요가 있다.

라우터 종류

AS에서 라우터는 두 종류로 나뉜다.

• gateway router:
  • AS 끝에 있는 라우터로 1개 이상의 다른 AS 라우터와 연결되어 있는 라우터를 의미한다.
  • 위 이미지에선 1c, 2a, 2c, 3a 가 gateway router이다
• internal router:
  • 이 라우터 종류는 본인 AS 내에 있는 라우터들과만 연결되어있는 라우터를 가리킨다.

BGP Connection 종류

한 쌍의 라우터들은 라우팅 정보를 TCP connection(port 179)을 통해 전달한다. 이 TCP connection을 통해 BGP 메시지도 보내는데, 이런 connection을 BGP connection이라고 부른다. 이런 BGP connection은 여러 개의 AS를 연결하는지에 따라 종류가 나뉜다.

• External BGP (eBGP):
  • BGP connection이 두 개의 AS 사이에서 이루어질 경우
• Internal BGP (iBGP):
  • BGP connection이 동일한 AS 내에서 이루어질 경우

서로 다른 AS를 연결하는 Gateway router들 사이에선 주로 한 개의 eBGP connection이 있으며, 위 이미지에선 1c-2a, 2c-3a 링크들에서 eBGP connection이 각각 있다고 생각하면 된다.

BGP Routing Information 전달 방식

그러면 실제로 BGP 정보(prefix)를 다른 AS에 있는 라우터들에게 어떻게 전달하는가? AS3는 prefix x를 쓰고, 이 x 정보를 AS1과 AS2에게 전달하려는 시나리오를 가정해보자. 그럼 3a gateway router는 2c gateway router에게 eBGP 세션을 이용해 “AS3 x” 메세지를 보낸다. AS3의 prefix는 x라는 의미의 메세지이다. 그럼 2c는 AS2에 있는 모든 라우터들에게 iBGP를 이용해 똑같은 “AS3 x”를 보낸다. 2a gateway router는 그 메세지를 받고 1c gateway router에게 "AS2 AS3 x"(AS3는 prefix x를 쓰고 AS3를 가기 위해선 AS2를 거쳐야 한다의 메세지)를 보낸다. 그러고 나서 1c는 AS1 내 모든 라우터들에게 "AS2 AS3 x"를 보낸다. 이젠 AS1와 AS2의 모든 라우터들이 AS3의 존재를 알게 된 것이다.

5.4.3 Determining the Best Routes

BGP에서 최적 경로를 결정하기 전 BGP 관련 용어들을 알 필요가 있다.

BGP 용어

• BGP attribute
  • prefix을 보낼 때 BGP attribute을 함께 보낸다. 대표적인 attribute으로는 AS-PATH와 NEXT-HOP이 있다.
  • AS-PATH: BGP advertisement가 지나간 AS를 담은 리스트
  • NEXT-HOP: AS-PATH를 시작하는 라우터 인터페이스의 IP 주소
    • 가령, “AS2 AS3 x”에서 AS-PATH는 [AS2, AS3]이고, NEXT-HOP은 1c와 2a를 연결하는 링크의 IP 주소일 것이다.
• BGP route
  • = prefix + attributes(AS-PATH, NEXT-HOP)
  • 'NEXT-HOP; AS-PATH; destination prefix' 형태로 표현된다
  • ex) IP address of leftmost interface for router 2a; AS2 AS3; x

Hot Potato Routing

BGP 용어들을 바탕으로 대표적인 BGP 라우팅 알고리즘인 hot potato routing 알고리즘에 대해 알아보겠다. 이 알고리즘은 현재 라우터에서 NEXT-HOP 라우터까지의 비용이 가장 적은 경로를 택한다. 즉 여러 개의 경로가 존재할 때, 경로 중 현재 라우터에서 NEXT-HOP 라우터까지의 비용이 가장 적은 경로를 최적의 경로라고 판단하는 것이다.

가령, 1b router에서 3d router로 간다고 했을 때, intra-AS routing 알고리즘을 바탕으로 3d까지 가는 경로 중 가장 가까운 NEXT-HOP 라우터(gateway 라우터)를 찾는다. 이때, 비용이 거쳐야 하는 링크 개수라 할 때, 1b에서 2a로 갈 것이다.

hot potato routing 알고리즘은 현재 라우터에서 다음 라우터까지의 최소 비용만 고려하기 때문에 그리디 알고리즘이라 할 수 있다.

BGP Routing Algorithm

BGP의 라우팅 알고리즘은 hot potato routing보다 복잡하지만 여전히 그 알고리즘 원리를 내포하고 있다. 만약 목적지까지의 경로가 하나면 BGP는 그 경로를 택하겠지만, 여러 개의 경로가 존재할 경우 다음과 같이 소거법으로 최적 경로를 결정한다.

1. local preference 설정하기:
   • 특정 attribute을 선호 기준으로 삼고, 이를 바탕으로 여러 경로를 정렬한다. 가장 선호도가 높은 경로들만 남기고 나머지는 버린다.
   • 이때, 선호 기준은 AS 네트워크 관리자가 설정한다.
2. Shortest AS-PATH 선택
   • 남은 경로들 중에서 AS-PATH가 가장 적은 것을 택한다.
3. Hot potato routing
   • 남은 경로들에는 hot potato routing을 적용한다.
   • 즉, 가장 가까운 NEXT-HOP 라우터를 가진 경로를 택한다.
4. BGP identifier
   • 여전히 여러 개의 경로가 남을 경우, 라우터는 BGP identifier 이용해 최적 경로를 택한다.

5.4.4 IP-Anycast

IP-Anycast이란?

IP-Anycast는 여러 서버에 같은 주소를 할당하는 기술이다. 이것은 동일한 기능을 하는 여러 서버를 가지고 있을 때, 패킷을 가장 가까운 서버로 전달하는 방식이다. 예를 들어, 여러 개의 DNS 서버가 같은 IP 주소를 가질 수 있다. 사용자가 DNS 쿼리를 보내면 가장 가까운 DNS 서버가 응답한다. 이런 IP-Anycast를 이용하면 서비스를 빠르고 안정적으로 제공할 수 있다.

BGP를 IP-Anycast에 적용할 수 있다!

• 여러 서버를 동일한 IP 주소로 설정하고, BGP를 통해 다른 라우터들에게 이 IP 주소를 알린다고 가정하다
• 라우터들은 이 IP 주소로 갈 수 있는 여러 경로를 전달받을 것인데, 라우터는 이 경로를 모두 동일한 지리적 위치의 IP주소로 가는 경로가 여러 개인 것으로 받아들일 것이다.
• 그리고 BGP routing 알고리즘을 활용하여 최적 경로를 파악함으로써 우리는 사용자에게 가장 가까운 서버를 사용할 수 있도록 하는 것이다.

Intra-AS vs Inter-AS routing protocol

• 정책(Policy):
  • AS 간 라우팅에서는 정책 문제가 지배적이다. 특정 AS에서 발생한 트래픽이 다른 특정 AS를 통과하지 못하도록 하는 것이 중요할 수 있다. 마찬가지로, 특정 AS는 다른 AS 간에 전달되는 트랜지트 트래픽을 제어하고 싶을 수 있다. BGP는 경로 속성을 전달하고 라우팅 정보의 제어된 분배를 제공하여 이러한 정책 기반 라우팅 결정을 가능하게 한다.
  • 반면, AS 내부에서는 모든 것이 기본적으로 동일한 관리적 통제 하에 있으므로 정책 문제가 라우트 선택에 훨씬 덜 중요한 역할을 한다.
• 규모(Scale):
  • 규모에 따라 라우팅 알고리즘과 데이터 구조가 확장되어야 할 수 있다. AS 간 라우팅에서는 대규모 네트워크를 처리할 수 있는 능력이 매우 중요하다.
  • 그러나 AS 내부에서는 이러한 확장성이 덜 중요하다. 하나의 이유는 단일 ISP가 너무 크면 항상 두 개의 AS로 분할하여 두 새로운 AS 간에 AS 간 라우팅을 수행할 수 있다. (OSPF는 AS를 영역으로 분할하여 이러한 계층 구조를 구축할 수 있도록 한다.)
• 성능(Performance):
  • AS 간 라우팅은 정책 중심적이기 때문에 사용되는 경로의 품질(예: 성능)은 종종 중요한 문제가 아니다. AS 간에는 경로의 비용 개념조차 없다.
  • 반면, 단일 AS 내에서는 이러한 정책 문제가 덜 중요하며, 라우팅은 더 많은 성능 수준에 집중할 수 있다.