Move Fast

▶ 인터넷에서의 라우팅

- 이전까지 알아본 라우팅 기법은 모두 이상적인 환경을 가정하고 있었는데, 이상적인 환경이란 “모든 라우터가 동일”하며, “하나의 네트워크”임을 의미한다.

- 현실에서는 아래와 같은 문제점을 가지게 된다.

• 규모의 확장(Scale) : 억 단위의 목적지(호스트)로 인해 모든 목적지를 라우팅 테이블에 저장할 수 없다는 것과 라우팅 테이블 정보의 교환은 링크의 대역폭을 고갈시킨다는 문제가 발생한다.

• 관리 자치권(Administrative autonomy) : 인터넷은 여러 네트워크의 집합으로 거대한 하나의 네트워크인데, 각 네트워크 관리자는 자신의 네트워크에서 라우팅을 제어하길 원한다는 문제가 발생한다.

▶ 자치 시스템(Autonomous System, AS)

- 라우터들을 영역으로 그룹화한 것으로 확장성(Scale) 문제를 해결한다.

(자치 시스템 외에 도메인으로도 확장성 문제를 해결 할 수 있다.)

- 인트라 AS 라우팅(intra-AS routing)

• 같은 자치 시스템(AS) 내부에 호스트와 라우터들 간의 라우팅 방식이다.

• AS 내의 모든 라우터들은 같은 인트라 도메인 프로토콜(intra domain protocol)을 수행한다.

• 다른 AS의 라우터들은 다른 인트라 도메인 프로토콜을 수행한다.

• 게이트웨이 라우터(Gateway Router) : 자신의 AS 내에서 가장자리에 있는 라우터로, 다른 AS의 라우터와 연결한다.

• ex) OSPE, RIP

- 인터 AS 라우팅(inter-AS routing)

• 서로 다른 자치 시스템(AS) 간의 라우팅 방식이다.

• 게이트웨이 라우터가 인트라 도메인 라우팅뿐만 아니라 인터 도메인 라우팅(inter domain routing)도 수행한다.

• ex) BGP

▶ Interconnected AS

- 포워딩 테이블은 인트라 AS & 인터 AS 라우팅 알고리즘에 의해 설정된다.

- 인트라 AS 라우팅은 해당 AS 내부에 목적지들에 대한 포워딩 테이블의 명부(Entry)를 설정한다.

- 인터 AS와 인트라 AS 라우팅 둘다 외부 목적지에 대한 포워딩 테이블의 명부(Entry)를 설정한다.

- 인터 AS의 작업 : AS1 안의 임의의 라우터가 AS1 밖으로 나가려는 데이터그램을 수신한다면, 해당 라우터는 게이트웨이 라우터로 패킷을 전달한다. 이 때, 여러 게이트웨이 라우터들 중 하나의 게이트웨이 라우터를 선택하는 방식이 필요한데 이는 “인터-AS 라우팅의 핵심 역할“이라고 볼 수 있다.

• 다른 AS를 경유하여 도달할 수 있는 목적지들을 학습한다.

• 이 도달 정보(라우팅 정보)를 AS1 내부의 모든 라우터들에게 전파한다.

- 인트라 AS 라우팅(Intra-AS Routing)

• 내부 게이트웨이 프로토콜(Interior Gateway Protocol, IGP)이라고도 한다.

• 대부분 흔히 인트라 AS 라우팅 프로토콜을 사용한다.

• 라우팅 정보 프로토콜(Routing Information Protocol, RIP) : 거리벡터 알고리즘이 구현되어 매 30초마다 거리벡터 값(DV)을 알린다.

• 개방형 최단경로 우선 프로토콜(Open Shortest Path First, OSPF) : IS-IS 라우팅 프로토콜과 본질적으로 유사하다.

• 내부 게이트웨이 라우팅 프로토콜(Interior Gateway Routing Protocol, IGRP) : 시스코(Cisco) 독점 프로토콜

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

- 개방형으로 라우팅 프로토콜이 공용으로 이용할 수 있다.

- RIP는 주로 하위 계층 ISP나 기업 네트워크 구축에 사용되는 반면, OSPF는 상위 계층 ISP들이 사용한다.

- 링크 상태 알고리즘(Link State Algorithm)을 사용한다.

• 다익스트라 알고리즘을 이용하여 최소 비용 경로를 계산한다.

• 링크 상태 패킷 정보를 전파한다.

• 각 노드에게 전체 AS의 토폴로지 맵이 주어진다.

- 라우터는 AS의 모든 라우터에게 OSPF 링크 상태 알림(라우팅 정보)을 브로드캐스트한다.

• 링크 상태 정보를 Flooding

• TCP, UDP가 아닌 IP를 통해 OSPF 메시지를 직접 전달한다. IP 데이터그램에 OSPF 메시지가 헤더가 아닌 data(페이로드)에 들어 있다.

- 보안(Security) : 모든 OSPF 메시지는 인증되어야 하므로, 아무나 라우팅 정보를 보낼 수 없다.

- 다수의 동일 비용 경로 허용 : 한 목적지까지 동일한 비용의 여러 경로가 존재할 때, 여러 경로를 사용할 수 있다. 

(RIP에서는 한 경로만 존재한다.)

- 각 링크에 다른 서비스 유형(Type Of Service, TOS)에 대해 동일 비용의 여러 경로(Equal Cost Multi Path, ECMP)의 측정값을 매긴다. 예를 들어 위성 링크의 비용을 최선(best-effort)의 경우 낮게 측정하고, 실시간(real-time)인 경우는 높게 측정한다. 즉, 위성 링크는 상황에 따라 비용(cost)이 바뀔 수 있다.

- 유니캐스트(Unicast)와 멀티캐스트(Multicast)를 통합 지원한다.

(Multicast OSPF(MOSPF)는 OSPF와 같은 토폴로지 데이터베이스를 사용한다.)

- 넓은 도메인 영역에서는 “계층적 OSPF”를 지원한다.

[ 파란색은 backbone area(백본 영역)이고, 점선 영역은 local area(지역 영역)이다. ]

- AS가 크면, Flooding 할 때 오버헤드가 증가한다. 이에 따라 제어 메시지(control message)가 증가하는데 이를 방지하기 위해 계층적으로 영역을 나눈다.

- 2계층 구조 : 지역 영역(local area)와 백본 영역(backbone area)

• 한 영역 내에서만 링크 상태를 광고하며, 바깥 노드는 축약된 정보만 받는다.

• 각 노드들은 상세한 영역 토폴로지를 가진다.

• 다른 영역의 네트워크에 대해서는 최단 경로의 방향만 알고 있다.

• AS(자치 시스템, 하나의 네트워크 관리자)에서 하나의 OSPF 영역만을 백본 영역으로 설정한다.

• boundary router : 트래픽 양을 줄이기 위해 계속해서 축약된 정보를 backbone 영역의 라우터들에게 전파한다. 다른 AS에 속한 라우터들과 연결한다.

• backbone router : 백본 내에서 OSPF 라우팅을 수행하는 비경계 라우터이다.

• area border router : 하나의 영역에서 네트워크에 거리를 요악하여 다른 영역 경계 라우터(area border router)들에게 알린다. 즉, 외부 영역으로 패킷 라우팅을 책임진다.

▶ 경계 게이트웨이 프로토콜(BGP)

- 사실상 “인터 AS 라우팅 프로토콜“을 의미한다.

- exterior BGP(eBGP) : 이웃 AS로부터 목적지 도달하기 위해 필요한 정보(서브넷 도달성 정보)를 얻는다. 라우터 간의 TCP기반의 통신이다.

- interior BGP(iBGP) : 모든 AS 내부의 라우터에게 도달성 정보를 전파한다. 즉 AS 내부에서 라우팅 정보를 주고받는다.

- 도달성 정보와 AS 정책을 기반으로 다른 네트워크에 “좋은 경로"를 결정한다.

- 서브넷이 자신의 존재를 외부 네트워크에게 알리도록 한다. 광고를 통해 그쪽으로 정보 전달이 가능하다.

[ 번개 모양의 꺾은 부분이 있는 선은 eBGP 연결이며, 구름 영역 내부의 직선은 모두 iBGP 연결이다. ]

- BGP 세션(session) : 두 개의 BGP 라우터(peer)가 반영구적 TCP 연결을 통해 BGP 메시지(라우팅 정보)를 교환한다.

- 다른 목적지 네트워크 프리픽스(prefixes)의 경로를 광고한다.  → 경로 벡터 알고리즘(Path Vector Algorithm)

- AS3의 게이트웨이 라우터가 경로 (AS3, X)를 AS2 게이트웨이 라우터에게 광고한다고 하면, AS3는 AS2에게 X로 향하는 데이터그램을 전달하겠다고 약속한다.

• (AS3, X) : X는 AS3를 거쳐옴을 의미한다.

- 경로 속성과 BGP route

• 광고된 네트워크 프리픽스(prefix)는 BGP 속성을 포함한다.

• 프리픽스(prefix) + 속성(attribute) = 루트(route)

• AS-PATH : 프리픽스 광고가 거쳐간 AS를 포함하는 리스트로 어딜 거쳐왔는지에 대한 라우팅 정보가 포함된다.

• NEXT_HOP : 다음 hop의 AS로 가기 위해 거쳐야하는 특정 내부 AS 라우터를 표시한다.

- 루트 광고를 수신하는 게이트웨이 라우터는 중요한 정책(important policy)을 통해 해당 광고의 수락 및 거절을 결정한다.

- 중요한 정책이란 여러 정보 중 우선순위를 결정하거나 정보의 수락 및 거절, 다른 이웃 AS들에게 경로를 알릴지 등을 결정하는 정책을 말한다.

- 경로 벡터(path verctor)의 전달 과정

1. AS2의 라우터 2c가 경로 광고(AS3, X)를 eBGP를 통해서 AS3의 라우터 3a로부터 수신한다.

2. AS2 정책을 기반으로, AS2 라우터 2c는 경로 정보(AS3, X)를 받아들이고, iBGP를 통해서 모든 AS2 내부 라우터들에게 전파한다.

3. AS2 정책을 기반으로, AS2 라우터 2a가 eBGP를 통해서 경로 정보 (AS2, AS3, X)를 AS1 라우터 1c에게 알린다.

- 게이트웨이 라우터는 목적지까지 다수의 경로에 대해 알 수 있다.

예를 들어, 위의 과정에서 AS3 라우터 3a가 바로 AS1 라우터 1c에게 경로정보 (AS3, X)를 전파할 수도 있다. 그 때는 AS1 라우터 1c가 AS2로부터 온 정보와 AS3로부터 온 정보 중 하나를 선택할 수 있다. 이후 iBGP를 통해 AS1 내부의 모든 라우터들에게 경로 정보를 알린다.

- BGP 메시지 : TCP 연결 상의 peer들 사이에서 교환되는 메시지로 아래와 같은 네 가지가 있다.

• OPEN : 다른 BGP 피어와의 연결, TCP 연결을 시작하고, 송신측 BGP 피어의 인증을 거친다.

• UPDATE : 새로운 경로정보를 광고하고, 오래된 정보는 철회한다.

• KEEPALIVE : 업데이트가 없어도 연결을 유지하며, OPEN 요청에 대한 ACK를 한다.

• NOTIFICATION : 이전의 메시지에 대한 에러를 보고하며, 연결 종료에도 사용된다.

▶ 포워딩 테이블 엔트리

- 라우터의 포워딩 테이블 엔트리에 프리픽스를 저장하는 방법 : AS 내에 특정 라우터가 수신하면 내부에 모든 다른 라우터들에게 경로 정보를 알린다.

예를 들어 라우터 a, b, c, d가 있다고 가정하자. c가 eBGP를 통해 경로 정보를 수신했다면, a, b, d에게 해당 정보를 알리고, a, b, d는 iBGP를 통해 c로부터 전달받은 목적지 X까지의 경로를 학습한다. 라우터 a는 OSPF 인트라 도메인 라우팅을 사용하여 c에 도달하는 출력 로컬 인터페이스 중 하나로 포워딩한다. 나머지 라우터 b와 d도 같은 행동을 수행한다. 그 때 목적지 X와 인터페이스 정보를 포워딩 테이블의 하나의 엔트리로 저장한다.

▶ BGP 경로 설정

- 라우터는 목적지 AS로 가는 다수의 라우팅 정보에 대해 배울 수 있고, 아래의 속성을 통해 하나의 정보를 선택한다.

- 지역 선호 값 속성(local preference value attribute)이 제일 높은 선호도 값의 루트를 선택, 이 속성은 정책에 의해 결정된다.

- 최단 AS-PATH : 똑같은 정보 중 최단 경로를 선택한다.

- 가장 가까운 NEXT-HOP 라우터를 갖는 경로를 선택한다. 즉, 경로의 비용이 최소인 라우터를 선택하는 방식으로 다음에 설명할 “핫 포테이토 라우팅” 방식이다.

- 위 세 개를 적용했음에도 여러 경로가 남아있다면 추가적인 기준을 사용한다.

▶ 핫 포테이토 라우팅(Hot Potato Routing)

- 언어적 의미는 뜨거운 감자를 만졌을 때 사람들이 뜨겁다며 빠르게 던지는 모습에서 따온 의미이다.

- 경로 정보를 가진 패킷이 왔을 때 큐가 짧은 쪽으로 빨리 보내는 라우팅 방식이다. 즉, AS 중에서는 짧은 경로의 AS로 빨리 내보낸다.

- 가장 작은 인트라 도메인 비용을 가진 로컬 게이트웨이 라우터를 선택한다.

예를 들어, 어떤 AS 내부에 라우터 a, b, c, d가 있다고 하고, d의 출력 인터페이스가 모든 라우터(a, b, c)와 연결되어 있다면 최저 비용을 가진 인터페이스로 패킷(경로 정보)을 전달한다. 이 때, 인터 도메인 비용은 고려하지 않는다.

▶ BGP 라우팅 정책

- ISP는 자신을 사용하는 네트워크(customer network)를 통해서만 트래픽(traffic)을 라우팅하기를 원한다. 다른 ISP 간의 트래픽이 전송되는 것을 방지하기 위함이다.

- A는 B와 C에게 경로 정보 Aw를 알린다. (Aw : A를 통해서 w로 정보 전달 가능하다라는 의미이다.)

- B는 C에게 경로 정보 BAw를 알릴지 말지 선택할 수 있다.

• B가 전송하지 않는다면, C는 w로 데이터를 전송할 때 절대로 B를 거치지 못한다. 대신 Aw를 받았기 때문에 A를 거쳐서 w로 데이터를 전송할 수 있다.

• B가 전송한다면 C는 B를 거쳐서 w로 데이터를 전송할 수 있다.

- C, A, w는 B의 customer network가 아니므로 CBAw 라우팅은 어떤 동작도 하지 않는다.

- C는 CBAw 경로를 학습하지 못한다.

- x는 두 provider network에 연결된 듀얼 홈 네트워크(dual-homed network)로, 두 ISP의 서비스를 받을 수 있다.

- x는 자신을 경유하여 B에서 C로 라우팅을 원하지 않는다. 따라서 X는 B에게 C로의 경로를 광고하지 않는다.

▶ 인터-AS & 인트라-AS 라우팅의 차이

- 정책(policy)

• 인트라-AS(내부AS) : 하나의 관리자가 제어하므로 정책 결정이 필요 없다.

• 인터-AS(외부AS) : 각 네트워크 관리자는 어떻게 트래픽이 라우팅되고, 누가 자신의 네트워크를 경유할 것인지를 제어한다.

- 확장성(scale) : 계층적 라우팅으로 인해 테이블 크기를 절약하고 업데이트 트래픽도 감소시킨다.

- 성능(performance)

• 인트라-AS : 성능에 초점을 맞춘다.

• 인터-AS : 성능보다 정책에 초점을 맞춘다. 최소 비용이 더 중요하기 때문이다.

▶ 인터넷 제어 메시지 프로토콜(ICMP)

- 네트워크 계층 정보를 통신하기 위해 호스트와 라우터들에 의해 이용되어진다.

- 오류 보고(error reporting)

목표 : 도달할 수 없는 호스트, 네트워크, 포트, 프로토콜 등을 보고하며, IP 데이터그램 전달 오류를 출발지 호스트에게 알리기

방법 : ping을 통해(like ping test) 에코 요청이나 응답을 한다.

- ICMP 메시지는 IP 데이터그램의 헤더가 아닌 데이터 영역(페이로드)에 저장되어 전송된다.

- ICMP 메시지 : 타입(type), 코드(code), 설명(description)으로 이루어진다. 에러 설명 부분은 8바이트이다.

- 아래는 ICMP 메시지 중 몇몇 설명에 대한 동작이다.

• source quench (congestion control – not used) -> 혼잡 상황을 라우터가 출발지에게 빨리 알려줌

• route advertisement -> 어떤 서브넷에 들어가면 ICMP 메시지를 통해 주기적으로 자신(라우터)을 광고한다.

• router discovery -> 내가 속한 서브넷의 라우터 정보를 받아온다.

• bad IP header -> 체크섬계산 오류시 전송되는 메시지 설명이다.

▶ Traceroute

- Traceroute 진단 프로그램 : 출발지와 목적지 사이의 라우터 이름과 주소를 추적하는 프로그램이다.

- ICMP 메시지를 이용한다.

- 지정된 목적지 경로에 따라 출발지에서 라우터까지 지연시간을 측정한다.

- 경로 상 모든 라우터의 동작 : 경로 상의 어떤 라우터 x에 대해 3개의 패킷을 송신한다면, 라우터 x는 송신자에게 패킷을 리턴한다. 그 다음, 송신자는 패킷 송신과 응답 사이 시간을 측정한다.

- Traceroute 원리

• 출발지는 목적지에 일련의 UDP 세그먼트를 보내고, 첫 번째 데이터그램의 TTL=1, 다음 hop을 거듭할수록 TTL=2, 3, 4, ... ,n 으로 계속 1씩 증가한다. UDP는 포트번호가 없다. (TTL 설정 방법)

• n번째 데이터그램이 n번째 라우터에 도착하면, 라우터는 데이터그램을 폐기한다.

• 출발지에 ICMP 메시지를 보낸다.(type:11, code:0)

• 메시지에 라우터의 이름과 IP주소가 포함된다.

• ICMP 메시지가 도착하면 출발지는 RTT를 계산한다.

- 표준 Traceroute 프로그램은 같은 TTL 값을 갖는 패킷을 3번 보낸다.

- 중단 조건(stopping criterion)

• UDP 세그먼트가 최종 목적지에 도착하고, 목적지가 ICMP port unreachable 패킷(type:3, code:3)을 반환하는데 여기서 UDP는 포트번호가 없으므로 오류를 반환한다.

• 그 다음 출발지가 이 ICMP 메시지를 받으면 traceroute를 중단한다.