rldnd
rldnd
5.4 인터넷 서비스 제공업자(ISP) 간의 라우팅: BGF - Computer Network

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

생성일
Jun 12, 2024 06:40 AM
Description
ISP 간의 라우팅, BGF 에 대해 알아봅니다.
Tag
Computer Network
Computer Science Engineering
패킷이 여러 AS를 통과하도록 라우팅할 때,
(e.g., 한국에 있는 스마트폰이 실리콘 밸리에 있는 데이터 센터로 전송을 할 경우)
자율 시스템 간 라우팅 프로토콜(inter-autonomous system routing protocol)이 필요하다.
통신하는 AS들은 같은 AS 간 라우팅 프로토콜을 수행해야만 한다.
실제로 인터넷의 모든 AS는 경계 게이트웨이 프로토콜(Border GateWay Protocol, BGP)을 사용하며,
이는 거리 벡터 라우팅과 같은 줄기에서 나왔다고 볼 수 있는 분산형 비동기식 프로토콜이다.

5.4.1 BGP의 역할

같은 AS 내에 있는 목적지에 대해서는 라우터의 포워딩 테이블 엔트리들이 해당 AS의 AS 내부 라우팅 프로토콜에 의해 결정된다.
하지만 목적지가 AS 외부에 있는 경우, BGP가 필요하다.
BGP에서는 패킷이 CIDER(Classless Inter-Domain Routing) 형식으로 표현된, 주소의 앞쪽 프리픽스(prefix)를 향해 전달된다.
각 프리픽스는 서브넷이나 서브넷의 집합을 나타낸다. (e.g., 139.16.68/22)
라우터의 포워딩 테이블은 (x, I) 같은 형식의 엔트리들을 갖게 된다
  • x : 주소 프리픽스 (e.g., 139.16.68/22)
  • I : 라우터 인터페이스의 인터페이스 번호
AS 간 라우팅 프로토콜로서 BGP는 각 라우터에게 다음과 같은 수단을 제공한다.
  1. 이웃 AS를 통해 도달 가능한 서브넷 프리픽스 정보를 얻는다.
      • 특히 각 서브넷이 자신의 존재를 인터넷 전체에 알릴 수 있도록 한다.
  1. 서브넷 주소 프리픽스로의 가장 좋은 경로를 결정한다.
      • 라우터는 특정한 주소 프리픽스를 향한 2개 이상의 경로를 알 수도 있다.
      • 가장 좋은 경로를 결정하기 위해 라우터는 BGP의 경로 결정 프로시저를 수행한다.

5.4.2 BGP 경로 정보 알리기

아래의 단순한 네트워크는 3개의 자율 시스템 AS1, AS2, AS3를 가지며,
AS3는 주소 프리픽스가 x인 서브넷을 포함한다.
notion image
각 AS에서 각각의 라우터들은 게이트웨이 라우터(gateway router) 또는 내부 라우터(internal router)다.

게이트웨이 라우터(gateway router)

  • AS의 경계에 있는 라우터
  • 다른 AS들에 있는 하나 또는 여러 개의 라우터와 직접 연결된다.
  • e.g., AS1의 라우터 1c

내부 라우터(internal router)

  • 자신의 AS 내에 있는 호스트 및 라우터와만 연결된다.
  • e.g., AS1의 라우터 1a, 1b, 1d
자율 시스템은 서로 메시지를 보내지 않고 라우터가 보낸다.

BGP 연결(BGP connection)

  • BGP에서 라우터의 쌍들은 포트 번호가 179이고 반영구적인 TCP 연결을 통해 라우팅 정보를 교환한다.
  • 이 TCP 연결을 통해 모든 BGP 메시지가 전송된다.

외부 BGP(external BCP, eBGP) 연결

  • 2개의 AS를 연결하는 BGP 연결

내부 BGP(internal BGP, iBGP) 연결

  • 같은 AS 내의 라우터를 연결하는 BGP 연결
보통 각기 다른 AS에 속하는 게이트웨이 라우터들을 직접 연결하는 링크에는 eBGP 연결이 존재한다.
각 AS 내부 라우터 간에는 iBGP 연결도 존재하며,
아래 그림은 한 AS 내 모든 라우터의 쌍 각각에 대해 하나씩의 BGP 연결을 두는 일반적인 설정 모습을 보인다.
iBGP 연결은 물리적인 링크와 항상 일치하지는 않는다.
notion image
위 예시에서 프리픽스 x에 대한 도달 가능성 정보를 AS1과 AS2의 모든 라우터에게 알리는 작업을 생각해보자.
아래의 과정이 완료되면 AS1과 AS2의 각 라우터들은 x의 존재와 x로 향하는 AS 경로를 알게 된다.
  1. 먼저 게이트웨이 라우터 3a는 게이트웨이 라우터 2c에게 ‘AS3 x’라는 eBGP 메시지를 보낸다.
      2. (’x가 존재하고 AS3 내에 있다’는 의미)
  1. 게이트웨이 라우터 2c는 iBGP 메시지 ‘AS3 x’를 게이트웨이 라우터 2a를 포함한 AS2 내부의 모든 라우터에게 전송한다.
  1. 게이트웨이 라우터 2a는 eBGP 메시지 ‘AS2 AS3 x’를 게이트웨이 라우터 1c에게 보낸다.
      2. (’x가 존재하고 x에 도달하기 위해서는 먼저 AS2를 통과하고 그 후 AS3으로 갈 수 있다’는 의미)
  1. 마지막으로, 게이트웨이 라우터 1c는 iBGP를 사용하여 AS1 내의 모든 라우터에게 메시지 ‘AS2 AS3 x’를 전달한다.
실제 네트워크에서는 주어진 라우터에서 특정 목적지까지 다른 많은 경로가 존재할 수 있고, 심지어 각기 다른 일련의 AS들을 통과하기도 한다.
아래 그림은 라우터 1d에서 3d로 연결되는 물리적인 링크를 추가한 것이다.
notion image
이 경우에 AS1에서 x로는 2개의 경로가 존재한다.
  1. 라우터 1c를 통과하는 경로 ‘AS2 AS3 x’
  1. 라우터 1d를 통과하는 새로운 경로 ‘AS3 x’

5.4.3 최고의 경로 결정

주어진 라우터에서 목적지 서브넷까지는 많은 경로가 있을 수 있는데,
이런 경로들 중에서 라우터는 어떻게 선택을 할까? 그리고 어떻게 그에 따라 포워딩 테이블을 설정할까?

BGP 관련 용어들

라우터가 BGP 연결을 통해 주소 프리픽스를 알릴 때 몇몇 BGP 속성(attribute)을 함께 포함한다.
BGP의 용어로는 프리픽스와 그것의 속성을 경로(route)라고 한다.

AS-PATH

  • 알림 메시지가 통과하는 AS들의 리스트를 담는다.
      1. 프리픽스가 어떤 AS에 전달되었을 때
      1. 그 AS는 자신의 ASN을 AS-PATH 내 현재 리스트에 추가한다.
  • 메시지의 루프를 감지하고 방지하기 위해 활용한다.
      1. 어떤 라우터가 자신의 AS가 경로 리스트에 포함되어 있는 것을 발견하면
      1. 그 알림 메시지를 버린다.

NEXT-HOP

  • AS-PATH가 시작되는 라우터 인터페이스의 IP 주소
e.g.,
notion image
AS1에서 AS2를 통과하여 x로 가는 ‘AS2 AS3 x’ 경로의 NEXT-HOP 속성은 라우터 2a의 왼쪽 인터페이스의 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 속성은 AS1에 속하지 않는 라우터의 IP 주소이다.
그러나 이 IP 주소를 포함하는 서브넷이 AS1에 직접적으로 연결된다.

뜨거운 감자 라우팅(hot potato routing)

💡 가능한 모든 경로 중, 경로 각각의 시작점인 NEXT-HOP 라우터까지의 경로 비용이 최소가 되는 경로를 선택한다.
  1. 여러 게이트웨이를 통해 서브넷 x에 도달할 수 있다는 사실을 AS 간 프로토콜로부터 알게 된다.
  1. 각 게이트웨이까지의 최소 비용 경로를 정하기 위해 AS 내부 프로토콜을 통해 얻은 라우팅 정보를 이용한다.
  1. 뜨거운 감자 라우팅: 가장 적은 비용의 게이트웨이를 선택한다.
  1. 포워딩 테이블로부터 최소 비용 게이트웨이로의 인터페이스 I를 결정한 후 포워딩 테이블에 (x, I)를 추가한다.
포워딩 테이블에 AS 외부의 목적지를 추가할 때
AS 간 라우팅 프로토콜(BGP)과 AS 내부 라우팅 프로토콜(e.g., OSPF) 둘 다가 사용된다.
e.g.,
notion image
  1. 라우터 1b는 주소가 x로 시작하는 서브넷으로 가는 2개의 BGP 경로를 안다.
  1. NEXT-HOP 라우터 2a와 3d 각각에 대해 최소 비용을 가진 AS 내부 경로를 찾기 위해 AS 내부 라우팅 정보를 조사한다.
  1. 이들 최소 비용 경로 중에서도 가장 적은 비용을 가진 경로를 선택한다.
      2. 비용을 거쳐가야 하는 링크의 수로 정의하면,
      • 라우터 1b에서 라우터 2a까지의 최소 비용 : 2
      • 라우터 1b에서 라우터 3d까지의 최소 비용 : 3
      따라서 라우터 2a가 선택된다.
  1. 라우터 1b는 자신의 (AS 내부 알고리즘에 의해 설정된) 포워딩 테이블을 관찰하여 라우터 2a로 가기 위한 인터페이스 I를 찾아내고,
      2. 엔트리 (x, I)를 자신의 포워딩 테이블에 추가한다.
💡 기본 아이디어
라우터가 목적지까지의 경로 중 자신의 AS 바깥에 있는 부분에 대한 비용은 신경 쓰지 않고
최대한 신속하게(가능한 한 최소의 비용으로) 패킷을 자신의 AS 밖으로 내보내는 것이다.
즉, 뜨거운 감자 라우팅은 오로지 자신의 경로 중에서 자기 AS 내부 비용만 줄이려는 이기적인 알고리즘이다.
이를 사용하면 한 AS 내 2개의 라우터가 동일한 목적지 주소에 대해 각기 다른 AS 경로를 선택할 수도 있다.
e.g.,
위의 예시에서 라우터 1b는 AS2를 통해 서브넷 x로 패킷을 보냈지만, 라우터 1d는 바로 AS3으로 보내 서브넷 x에 도달한다.

경로 선택 알고리즘

실제로 BGP는 뜨거운 감자 라우팅을 포함하는 더 복잡한 알고리즘을 사용한다.
목적지 주소의 프리픽스가 주어지면, 지금까지 라우터가 알아낸 해당 목적지까지의 모든 경로가 BGP의 경로 선택 알고리즘에 입력으로 주어진다.
💡 하나의 목적지에 대해 2개 이상의 경로가 존재한다면 BGP는 하나의 경로가 남을 때까지 다음의 제거 규칙을 계속 수행한다.
여기서 뜨거운 감자 라우팅에서 추가된 것은 속성 중의 하나로서 지역 선호도(local preference)가 경로에 할당되었다는 것이다.
한 경로의 지역 선호도는 라우터에 의해 설정되었거나 같은 AS 내부의 다른 라우터로부터 학습된 것이다.
  1. 최고 지역 선호 값을 가진 경로가 선택된다.
  1. 최고 지역 선호 값을 가진 경로가 여러 개 있다면 이들 중에서 최단 AS-PATH를 가진 경로가 선택된다.
      • 만약 이 규칙이 경로 선택을 위한 유일한 규칙이라면, BGP는 경로 결정을 위해 DV 알고리즘을 사용할 것이다.
      • 여기서 거릿값으로는 AS 홉 수를 사용한다.
  1. (같은 최고 지역 선호 값 및 같은 AS-PATH 길이를 가진) 모든 남은 경로들에 대해 뜨거운 감자 라우팅을 수행한다.
  1. 만일 아직도 하나보다 많은 경로가 남아 있다면 라우터는 BGP 식별자를 사용하여 경로를 선택한다.
e.g.,
notion image
라우터 1b에서 서브넷 x로 가는 BGP 경로는 2가지가 존재했고(AS2를 통과 또는 우회),
뜨거운 감자 라우팅이 바로 사용된다면 BGP는 AS2를 통과하는 경로로 패킷을 보내야 한다.
하지만 위의 경로 선택 알고리즘에서 규칙 2가 규칙 3보다 먼저 적용되므로, 더 짧은 AS-PATH를 가진 AS2 우회 경로가 선택된다.
따라서 이는 더이상 이기적인 알고리즘이 아니며, 결과적으로 종단 간 지연 시간이 줄어들 것이다.

5.4.4 IP 애니캐스트

BGP는 IP 애니캐스트(anycast) 서비스를 구현하는 데도 활용된다.
[참고] 애니캐스트(anycast) : 송신노드가 네트워크에 연결된 수신 가능한 노드 중에서 가장 가까운 한 노드에만 데이터를 전송한다. (IPv6 기반으로 작동)
많은 애플리케이션에서 (1) 같은 콘텐츠를 지리적으로 분산된 다른 많은 서버에 복제하고,
(2) 각 사용자를 가장 가까운 서버의 콘텐츠로 접근하게 하려고 하는 경우를 생각해보자.
e.g., CDN은 비디오 등을 각기 다른 나라의 서버들에 복제해두며, DNS 시스템도 DNS 정보를 전 세계 DNS 서버에 복제할 수 있다.
이 경우, BGP의 경로 선택 알고리즘을 사용할 수 있다.
아래 그림은 사용자를 가장 가까운 CDN 서버로 보내기 위한 IP 애니캐스트의 활용을 보여주는 그림이다.
notion image
  1. IP 애니캐스트 설정 단계에서
      2. (1) CDN 사업자가 자신의 서버 여러 대에 동일한 IP 주소를 할당하고
      (2) 표준 BGP를 활용하여 이 주소를 서버 각각으로부터 알린다.
      • 라우터가 이 IP 주소에 대한 복수 개의 경로 알림 메시지를 받으면이를 동일한 물리적 위치로의 서로 다른 경로에 대한 정보를 제공받고 있는 것으로 생각한다.
      • 실제로는 서로 다른 물리적 위치로 가는 서로 다른 경로다.
  1. 각 라우터는 라우팅 테이블을 설정하면서 BGP 경로 선택 알고리즘을 수행하여 해당 IP 주소로의 최고의 경로를 골라낸다.
이러한 최초의 BGP 주소 알림 단계 이후에 CDN는 콘텐츠 배포를 할 수 있다.
  1. 사용자가 비디오를 요청하면 CDN은 사용자가 어디에 위치해 있든 상관없이
      2. 지리적으로 분산되어 있는 서버들이 공통적으로 사용하는 IP 주소를 사용자에게 돌려준다.
  1. 사용자가 그 주소로 요청을 보내면 인터넷 라우터는 그 요청 패킷을 BGP 경로 선택 알고리즘이 정의한 가장 ‘가까운’ 서버로 전달한다.
실제로는 BGP 라우팅이 변경되면 하나의 TCP 연결에 속한 패킷들이 서로 다른 복제 웹 서버로 도착될 수 있기 때문에
CDN은 위의 예처럼 IP 애니 캐스트를 사용하지 않으며,
DNS 시스템에서는 DNS 질의를 가장 가까운 루트 DNS 서버로 전달하기 위해 IP 애니캐스트를 광범위하게 사용된다.

5.4.5 라우팅 정책

라우터가 목적지까지의 경로를 선택하려고 할 때
AS 라우팅 정책은 최단 AS-PATH나 뜨거운 감자 라우팅 등의 다른 모든 고려사항보다 우선시된다.
아래 그림에서는 A, B, C, W, X, Y 이렇게 6개의 자율 시스템(AS)이 서로 연결되어 있다.
  • W, X, Y는 사용자 접속 ISP
  • A, B, C는 백본 제공자 네트워크
    • 트래픽을 서로에게 직접 보낸다.
    • 그들의 사용자 네트워크에 완전한 BGP 정보를 제공한다.
notion image
ISP 접속 네트워크로 들어오는 모든 트래픽은 그 네트워크를 목적지로 해야만 하고,
ISP 접속 네트워크에서 나가는 트래픽은 그 네트워크 안에서 생성된 것이어야만 한다.
  • W와 Y는 명백히 접속 ISP다.
  • X는 각기 다른 두 제공자를 통해 네트워크의 다른 부분들과 연결되어 있으므로 다중 홈 접속 ISP(multi-homed access ISP)라고 한다.
X도 W나 Y처럼 자신에게 들어오고 나가는 모든 트래픽의 목적지 또는 출발지여야 한다.
이 접속 네트워크의 동작을 구현하고 강제하며, X가 B와 C간 트래픽을 전달하는 것을 방지하는 것은
BGP 경로의 알림 방식을 제어하는 것으로 가능하다.
즉, X는 이웃인 B와 C에게 자기 자신을 제외하고는 다른 어떤 목적지로도 경로가 없다고 알리는 것이다.
(X가 Y까지 가는 XCY라는 경로를 알고 있더라도 이 경로를 B에게 알리지 않음)
따라서 B는 X가 Y로의 경로를 갖고 있음을 모르기 때문에 C 또는 Y로 가야 하는 트래픽을 X에게 절대 전달하지 않을 것이다.
서비스 제공자 네트워크 B는 (A로부터) A가 W까지의 경로 AW를 갖고 있음을 알게 되었다고 가정하자.
그러면 B는 경로 AW를 자신의 라우팅 정보 테이블에 기록하고,
자신의 고객인 X가 B를 통해 W로 갈 수 있음을 알게 하기 위해 경로 BAW를 X에게 알리길 원할 것이다.
하지만 B는 C에게도 BAW 경로를 알려야 할까?
만약 그렇게 한다면, C는 해당 경로를 통해 W까지 트래픽을 보낼 수 있게 되는데,
A, B, C가 모두 백본 제공자라면 B는 당연히 A와 C 사이의 트래픽을 전달하는 짐을 져서는 안 된다고 생각할 것이다.
현재는 백본 ISP들 사이의 경로를 결정하는 방법에 대한 공식적인 표준은 없지만,
상업적 ISP들이 따르는 대략적인 규칙은
ISP 백본 네트워크를 통해 흐르는 트래픽은 해당 ISP의 고객 네트워크를 출발지로 하거나 목적지로 해야 한다는 것이다(또는 둘 다).
개별적인 상호 협정은 전통적으로 두 ISP 간에 협상되고 종종 기밀사항이다.

왜 AS 간 라우팅과 AS 내부 라우팅 프로토콜이 다를까?

이는 AS 내부 라우팅과 AS 간 라우팅의 목적의 차이에 있다.

정책

AS 간 라우팅은 정책 이슈가 지배한다.
특정 AS에서 시작된 트래픽이 다른 특정 AS를 통과할 수 없다는 것은 중요할 수 있으며,
특정 AS가 다른 AS들 사이에서 어떤 트래픽을 전달할지 결장할 수 있기를 원하는 것 역시 당연하다.
반면, 하나의 AS 안에서는 모든 것이 동일한 관리 통제하에 있으므로 정책 문제는 경로 선택에 그리 중요하지 않다.

확장성

AS 간 라우팅에서 수많은 네트워크로, 또는 네트워크 간 경로 설정을 처리하기 위한 라우팅 알고리즘과 자료 구조의 능력은 매우 중요한 문제다.
반면, 한 AS 내에서는 확장성이 중요하지 않다.
하나의 ISP가 너무 커지면 이를 2개의 AS로 분리하고, 이 새로운 두 AS 사이에서 AS 간 라우팅을 수행할 수 있다.
(OSPF가 하나의 AS를 여러 영역으로 나눔으로써 계층을 만드는 것을 허용함)

성능

AS 간 라우팅은 정책 지향형이므로 사용하는 라우터의 품질(e.g., 성능)은 부수적인 관심사에 지나지 않는다.
단일 AS에서는 이러한 정책의 고려가 중요하지 않으므로, 경로의 성능 수준에 좀 더 초점을 두고 라우팅을 한다.

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

이 절은 본질적으로 BGP에 관한 내용은 아니지만,
IP 주소체계, DNS, BGP를 포함하여 지금까지 살펴본 많은 프로토콜과 개념을 한데 모은다.
작은 회사를 설립했다고 가정하다.
회사에는 회사의 제품과 서비스를 설명하는 공개 웹 서버, 메일 서버, DNS 서버를 포함한 많은 서버가 있다.
  1. 먼저 지역 ISP와 계약하여 인터넷 연결을 해야 한다.
      • 회사는 게이트웨이 라우터를 갖게 될 텐데, 이는 지역 ISP의 라우터에 연결될 것이다.
      • 지역 ISP는 특정 범위의 IP 주소를 제공한다. (e.g., 256개의 주소를 포함하는 /24 주소 범위)
      • 물리적 연결과 IP 주소 범위를 가지면회사의 웹 서버, 메일 서버, DNS 서버, 게이트웨이 라우터와 다른 서버 및 네트워킹 장치들에 IP 주소(주소 범위에서)를 할당해야 한다.
  1. 회사의 도메인 이름(e.g., xanadu.com)을 얻기 위해 인터넷 등록 기관과 계약을 해야 하며, DNS 시스템에 등록해야 한다.
      • 회사의 DNS 서버의 IP 주소를 등록 기관에 제공해야 한다.
      • 그러면 등록 기관은 .com 최상위 도메인 서버에 회사의 DNS 서버(도메인 이름과 해당 IP 주소)를 추가한다.
  1. 사람들이 회사의 웹 서버 IP 주소를 검색할 수 있도록
      2. 회사의 DNS 서버에 웹 서버의 호스트 이름(e.g., www.xanadu.com)과 IP 주소의 사상 항목을 포함시켜야 한다.
      (메일 서버를 포함하여 회사의 공개적으로 사용 가능한 다른 서버들에 대해서도 유사한 항목들을 가져야 한다.)
      • 만일 앨리스라는 사람이 회사의 웹 서버를 방문하기를 원하는 경우,
          1. DNS 시스템은 회사의 DNS 서버에 접촉하여 웹 서버의 IP 주소를 알아낸 후
          1. 이를 앨리스에게 제공한다.
      • 이제 앨리스는 회사의 웹 서버에 직접적으로 TCP 연결을 설립할 수 있다.
  1. 전 세계의 외부인이 회사의 웹 서버에 접근할 수 있도록 하기 위해서는라우터가 회사 주소 범위에 해당하는 IP 주소 프리픽스 24비트(또는 다른 길이의 엔트리)의 존재를 알고 있어야 한다.
      • 예시 상황
          1. 회사의 웹 서버의 IP 주소를 알아낸 앨리스가 그 IP 주소로 IP 데이터그램(e.g., TCP SYN 세그먼트)을 보낸다.
          1. 이 데이터그램은 인터넷을 통해 라우팅되어 여러 자율 시스템의 라우터들을 연속적으로 거친 후 마침내 웹 서버에 도착하게 된다.
              • 라우터들 각각은 이 데이터 그램을 수신하면,어느 출력 포트로 내보내야 하는지 결정하기 위해 자신의 포워딩 테이블에서 해당 엔트리를 찾는다.
      • 이는 BGP를 통해서 이루어지게 된다.
        • 회사가 지역 ISP와 계약하고 주소 프리픽스(즉, 주소 범위)를 할당 받을 때,지역 ISP는 BGP를 사용하여 자신과 연결되어 있는 ISP들에게 회사의 주소 프리픽스를 알린다.
        • 연결된 ISP들 역시 BGP를 활용하여 이 알림 정보를 전파한다.
Copyright 2023 rldnd