Hierarchical routing

실제 네트워크의 규모는 매우 방대하기 때문에 Distance Vector 또는 Link State 알고리즘을 바로 적용하기에는 무리가 힜다.

Distance Vector의 경우 링크 하나라도 변경되면 이를 안정화시키고 또 반영하는데 시간이 오래 걸린다.

Link State의 경우 네트워크를 구성하는 노드가 너무 많아서 포워딩 테이블을 구성하는데 시간이 오래 걸린다.

따라서 네트워크를 계층화하여 관리하는 것이 필요하며 이를 Hierarchical routing (계층적 라우팅) 이라고 한다.

Interconnected ASes

AS (Autonomous System)

계층적 라우팅을 통해 나눠놓은 독립적인 네트워크 영역을 각각 AS (Autonomous System)이라고 한다.

우리나라의 LG U+, SK, KT 등이 AS의 예시이다.

AS는 하나의 라우팅 도메인에 대한 자치권을 갖고 있는 시스템이다.

각각의 AS 내부에서는 Link State 또는 Distance Vector를 사용하여 라우팅을 실시한다. 따라서 Link State, Distance Vector 알고리즘을 Intra-AS Routing algorithm이라고 한다.

이때 Link State 알고리즘으로 구현한 프로토콜을 OSPF 프로토콜 (Open Shortest Path Fast) 이라고 한다.
또한 Distance Vector 알고리즘으로 구현한 프로토콜을 RIP 프로토콜 (Routing Information Protocol) 이라고 한다.

각각의 Intra-AS는 고유의 숫자를 가지고 있으며 이를 ASN이라고 한다.

반면 네트워크끼리 사용하는 라우팅 알고리즘은 Inter-AS Routing algorithm이라고 한다. Inter-AS 라우팅은 계층적 라우팅으로 구현한 BGP 프로토콜 (Border Gateway Protocol)을 사용한다.

Interconnected ASes

라우터의 포워딩 테이블은 Intra-AS와 Inter-AS 알고리즘에 의해 생성된다.

또한 각각의 AS의 가장자리 (Edge)에 위치한 Gateway router는 다른 AS와 링크로 연결되어있는 라우터이다.

AS 간에는 사용자 (Customers)와 제공자 (Providers)가 존재한다. 이 관계는 상대적인 것으로 경우에 따라 달라진다.

네트워크를 제공하는 KT, SK 같은 AS를 제공자라고 하고, 이 네트워크를 비용을 지불하고 제공받는 가정집, 대학교 등등을 사용자라고 한다.

세상에는 60,000개 이상의 AS가 존재하는데, 이 AS 간에도 급이 나눠져있다.
이때 같은 급 끼리의 관계는 Peering Relationship이라고 한다.

AS는 AS 간에 트래픽이 네트워크 사이를 이동할 수 있도록 하는 피어링(Peering) 계약을 맺는다.

Peering 관계 끼리는 자유롭게 네트워크 트래픽을 주고받으며, 사용자/제공자 관계에서는 일종의 계약을 통해 트래픽을 주고받는다.

이처럼 Peering 관계가 모여서 파랑색 traffic allowed 처럼 트래픽 제공이 가능해진다.

BGP (Border Gateway Protocol)

BGP는 AS들의 경계에 있는 게이트웨이 라우터들 사이의 라우팅을 결정하는 프로토콜이다. (Inter-AS)

BGP는 비용의 최적화가 목적이 아니라 AS간의 정책에 따라서 좌우되는 프로토콜이다.

BGP Path Attribute (BGP 경로 속성)

BGP 경로 속성이란 어떤 도착 가능한 목적지 AS까지의 라우트 경로에 관련된 정보들을 나타내는 일종의 매개변수 (속성)을 의미한다.

AS-Path Attribute

AS-Path 속성은 자기 자신의 ASN과 그 전에 거쳐왔던 AS의 ASN이다. 즉, 목적지의 AS까지 이동할 때 경유하는 AS의 ASN들이다.

선택할 수 있는 경로는 많다. 실제 경로 상의 이동 비용이 제일 적은 경로보다는, 비용은 좀 더 들더라도 내가 갑의 관계가 될 수 있는 경로를 선택할 수도 있다.

만약 해당 그림처럼 University에서 AS1으로 가는 경로를 정해야한다고 할때, AS4 또는 AS5를 거쳐가는 것이 더 효율이 좋을 수 있다.

Local Preference

하지만 Provider보다는 Customer를 거쳐가는 것이 University 입장에서 더 이익이 크기 때문에 좀 더 돌아서 가더라도 AS3, AS2를 거쳐갈 수 있다.

Intra-AS의 목적은 최단 경로 선택이지만 Inter-AS의 목적은 Policy-based이다. 즉, AS 내부에서는 최단 경로를 통해 이동하지만 AS 사이에서의 경로는 최단 경로가 아니라 제일 경제적인 (제일 돈을 많이 벌 수 있는) 경로를 선택한다.