Making Routing Scalable

scalable 하다는 것은 확장성(scalability)이 좋다는 것을 의미한다.
즉 시스템의 규모를 확장하는 것이 용이한지에 대한 지표이다.

전세계적으로 수많은 규모의 dest가 존재할 것이고 각각의 라우터들이 가지고 있는 routing table에 이 destination에 대한 forwarding 정보를 기록하고 있는 것은 불가능에 가깝다.

그래서 라우터는 autonomous systems(자율 시스템) (이하 AS) 이라는 영역으로 통합할 수 있다.

Intra-AS, Inter-AS

전체 네트워크를 여러 개의 AS로 나누었으면 이들 간에, 또 각각의 AS 내부에서 통신이 이루어져야 한다. 같은 AS 내부에서 이루어지는 라우팅을 Intra-AS, AS들 간의 라우팅을 Inter-AS 라 한다.

• Intra-AS(intra-domain)

• AS에 속하는 모든 라우터는 같은 intra-AS 프로토콜을 사용해야 한다.
• 각 AS의 edge 에 있는, 즉 다른 AS와 연결된 라우터를 gateway 라우터 라고 한다.

• Inter-AS(inter-domain)

• gateway 라우터(아까 언급한 각 AS edge)는 inter-AS 라우팅과 더불어, 다른 AS의 gateway 라우터와 inter-AS 라우팅을 수행한다.

Intra-AS Routing

• RIP (Routing Information Protocol) : 30초마다 distance vector를 교환하는 방식. 더 이상 잘 사용되지는 않는다. 홉 카운트가 15로 제한되어 있다.
• EIGRP (Enhanced Interior Gateway Routing Protocol) : Cisco 사가 개발한 프로토콜인 IGRP를 개선한 방식으로, Cisoco 전용 라우팅 프로토콜이다. Distance vector 알고리즘을 기반으로 동작한다.
• OSPF (Open Shortest Path First) : RIP, EIGRP와는 다르게 Link State 라우팅을 사용한다. 다익스트라 알고리즘을 통하여 구한 최단 경로를 바탕을 패킷을 전달해 준다.

OSPF (Open Shortest Path First) routing

각각의 라우터는 AS 내부의 모든 다른 라우터들에게 link state를 flood 한다.
각각의 라우터는 모든 link state 정보를 가지고 있으며 (full topology), 다익스트라 알고리즘을 통해 다른 모든 라우터들까지의 최적 경로를 탐색한다

OSPF는 홉 카운트 개수만을 고려하는 RIP와는 다르게 링크 비용의 개념을 도입한다. 즉, 다양한 변수를 기반으로 비용을 산정하여 최적의 경로를 구하기 때문에, 더 효율적이고 빠른 경로 산출이 가능하다.

Hierarchical OSPF

OSPF 네트워크를 더 작은 영역으로 나누어 관리할 수도 있다. 이를 위해 local area 영역과 backbone 영역을 둔다.

backbone 영역에 여러 라우터들이 있다. 이 영역에 속하지 않는 각각의 영역을 local 영역이라고 하는데 이 경계에 걸쳐 있는 라우터를 area border 라우터 라고 한다. 이 라우터들은 자기가 속한 local area의 대표자로 backbone 영역에 속해 있고, 자기가 속한 local area의 정보를 나머지 backbone 라우터들에게 알린다.

OSPF 프로토콜을 back bone 영역의 라우터들 간에만 수행하게 되면, 라우터의 개수가 줄어들 수 있어 관리에 용이해진다. 마치 subnet을 사용하는 것처럼 local area를 나누기 때문에 일종의 계층 구조라고 볼 수 있다.

local 영역에 속하고 있는 라우터들은 local 영역 내부적으로 link state 방식을 사용하며, area border 라우터를 통해 외부와 연결된다.

Inter-AS Routing

BGP (Border Gateway Protocol)이 사용된다.
BGP는 eBGP (external)와 iBGP (internal)가 있다.

• eBGP : 이웃 AS들로부터 reachability information 을 받아온다. AS의 위치, 갈 수 있는 destination의 종류와 경로 정보 등이 포함된다.
• iBGP : 받아온 reachability inforamtion을 AS 내부의 모든 라우터들에게 전파한다.

파란 부분은 각각의 AS이고 파란 점선으로 표시된 연결은 '논리적인' AS 내부의 연결이며 곧 iBGP 연결을 뜻한다. 빨간 점선은 AS 간의 연결, 즉 eBGP 연결을 의미한다.

BGP

AS의 gateway 라우터들은 서로 BGP 메시지를 교환한다. 이 메시지는 특정 destination으로 갈 수 있는 경로 정보를 담고 있다. destination network prefix(목적지 정보)가 있고, 이 목적지에 도달하기 위해 거쳐야 하는 AS 정보인 AS-PATH 속성과 다음 hop을 어느 라우터로 향해야 하는지에 대한 정보인 NEXT-HOP 속성이 있다.

정보를 받은 gateway 라우터들은 내부 정책을 통해 이 경로를 받아들일지(accpet) 혹은 거부할지(decline)를 선택한다. 정책을 따르기 때문에 BGP를 policy-based routing을 한다고 한다.

처음에는 라우터 X로 갈 수 있다라는 정보를 AS3이 AS2에게 전달한다. destination에다 자신을 앞에 붙여 AS3, X 라고 전달된다. 정보를 받은 2c 라우터는 AS 2 내부에 존재하는 모든 라우터들에게 이 정보를 flood 한다.

그 다음에 AS 1에게 X에 대한 경로 정보 AS2, AS3, X 를 전달한다.

AS 1은 AS 2 뿐만 아니라 AS 3에게서도 X에 대한 path 정보를 받게 된다. 정책에 따라 이 중 한 가지 경로를 선택하여 X로 가기 위한 경로를 결정한다.

BGP Message

BGP 메시지는 TCP 연결을 기반으로 이루어진다. BGP 메시지는 다음과 같다.

• OPEN : 다른 BGP 피어와 TCP 연결을 시도한다.
• UPDATE : 새로운 경로 정보를 받아 이를 통해 정보를 갱신한다.
• KEEPALIVE : 연결을 수립한 상대방의 연결이 유효한지, 또는 OPEN 메시지에 대한 ACK로써 사용된다.
• NOTIFICATION : 에러가 발생하였음을 알리거나 연결을 끊고자 할 때 사용된다.

Hot Potato Routing

뜨거운 감자 라우팅(?)이라는 말인데, 뜨거운 감자를 내가 잡고 있으면 빠르게 다음 사람에게 넘겨주려고 한다.
내가 가지고 있는 시간을 줄이고 최대한 빨리 넘겨주는 것이다.

AS는 현재 AS3으로 가는 두 가지 경로를 알고 있다.
2c -> 3a 경로가 있고, 2a -> 1c -> 3a 경로가 있다.

이 때 2d 라우터는 어떤 경로를 선택할 것인가? 정답은 intra-AS cost가 가장 작은 경로를 선택해야한다. 2d-2a 비용은 201이고, 2c로 가는 경로는 263이다. AS3으로 가기 위해 AS1을 거쳐야 하므로 inter-AS cost 까지 고려하면 2a -> 1c -> 3a 경로가 더 효율적이지 못하지만 내부 비용이 적기 떄문에 해당 경로를 선택한다.