Routing algorithms - Hierarchical routing

---

Inter-AS

지금까지 다룬 routing algorithm들은 모든 router를 flat한 network에 있고 identical하다고 가정한 이상적인 상황에서 사용가능한 알고리즘이다. 그러나 현실에서는 전세계 모든 router를 identify하는것은 불가능하기 때문에 hierachical한 구조를 이용한다. 이때 특정 범위 예를들어 'XX대학교 서버'를 Autonomous System(AS)라고 한다. AS가 하나의 계층이라고 볼 수 있는 것이다. 지금까지 AS내부에서의 routing algorithm은 intra-AS routing protocol이라고 부르고 AS간의 네트워크 algorithm을 결정하는 protocol이 inter-AS routing protocol이 되는 것이다.

위와 같이 AS1, AS2, AS3가 있을때 각 AS간의 네트워크를 결정하는 protocol이 inter-AS, AS내부의 routing algorithm이 intra-AS인 것이다.

inter-AS routing에서 AS1은 다른 두 AS(AS2, AS3)를 통해 도달할 수 있는 목적지를 학습하고, 그 정보를 AS1 내의 모든 라우터에 전파해야 한다는 의무를 가지고 있다.

한 AS로 가려는데 ASx를 거쳐도 되고 ASy를 거쳐도 될때 보통 hot potato routing이라는 규칙에 따라 방향이 선택된다. 이는 뜨거운 감자를 얼른 놓아버리라는 의미인데 이후의 상황은 신경쓰지 않고 무조건 빠르게 내보낼 수 있는 방향을 선택하는 것이다.

---

Routing in the Internet

실제로 internet에서 쓰이는 routing protocol은 다양하게 있다.

Distance Vector를 이용하는 RIP, Link State를 이용하는 OSPF, inter-AS routing algorithm인 BGP등 다양하게 존재한다. 이들에 대해서 하나씩 간단하게 알아보도록 하자.

---

RIP

RIP는 Routing Information Protocol의 약자로 대표적인 intra-AS Routing의 예시이다. RIP는 distance vector algorithm을 이용하는데 이때 distance metirc을 굉장히 단순하게 가져간다. 최대가 15인 hops라는 단위를 이용하고 모든 link의 cost를 1로 통일하여 하나의 link를 넘어갈때마다 hops를 늘려가며 algorithm 계산을 하는 것이다. 또한 distance vector는 매 30초마다 이웃 노드들과 교환을 하고 이는 advertisement라고 불린다. 또한 각 advertisement는 최대 25개의 destination subnets만 포함할 수 있다. 다시말해 RIP는 작은 사이즈의 AS에서 이용되는 간단한 routing protocol이다.

만약 180초 동안 아무런 advertisement가 오지 않는 neighbor와 link는 dead라고 정의한다.

또한 ping-pong loops를 막기 위해 앞에서 사용했던 poison reverse를 마찬가지로 이용하는데 이때 infiite distance로 표현한다고 했던 부분을 16hops로 저장해둔다. 이는 어짜피 최대가 15hops이니 16hops도 연결하지 말라는 의미를 충분히 전달할 수 있기 때문이다.

Routing table들은 application-level process에서 관리된다. 그러나 RIP는 여전히 네트워크 계층에서 동작하는 프로토콜이다.

---

OSPF

OSPF는 Open Shortest Path First의 약자로 이름에도 나와있듯 open되어있어서 공개되어있는 프로토콜이다. 누구든지 이용할 수 있는 것이다. OSPF는 각 라우터가 전체 네트워크의 링크 상태 정보를 수집하고, 이 정보를 바탕으로 최단 경로 트리를 계산하는 link state algorithm을 이용한다.

Hierarchical OSPF는 위와 같이 계층화되어 효율적으로 networking을 할 수 있도록 한다.

OSPF는 복잡한 네트워크와 대규모 환경에서 효율적인 routing을 가능하게 하는 강력한 protocol이다. 하지만 구성이 복잡하고 메모리 및 CPU 자원을 상대적으로 많이 사용하기 때문에, 소규모 네트워크나 자원이 제한된 환경에서는 다른 라우팅 프로토콜이 더 적합할 수 있다.

---

BGP

BGP는 Border Gateway Protocol의 약자로 인터넷의 핵심 inter-AS routing protocol이다.

이때 eBGP는 subnet 접근 가능 여부에 대한 정보를 이웃 AS를 통해 얻어오는 세션을 말하고 iBGP는 얻어온 정보를 AS내부의 router들에게 propagate하는 세션이다.

이때 BGP는 매우 중요한 AS간의 연결을 결정하는 정보를 전달하기 때문에 Application layer에서 작동하여 TCP를 통해 reliable data를 제공한다. 따라서 BGP message라고 부른다.

BGP에서의 핵심 속성인 AS-PATH와 NEXT-HOP은 경로 선택과정에서 매우 중요하다.

AS-PATH는 BGP 광고가 경유한 AS(자율 시스템)의 순서를 기록하는 속성이다. 이 리스트는 BGP 경로 광고가 네트워크를 통해 전파될 때, 각 AS 번호가 순차적으로 추가되면서 구성된다. AS-PATH는 루프 방지에도 사용된다. BGP 라우터는 자신의 AS 번호가 AS-PATH에 이미 존재하는 경로 광고를 수신하면, 그 광고를 무시함으로써 라우팅 루프를 방지한다. 또한 경로 선택에서 AS-PATH는 가장 짧은 경로를 선호하는 메트릭으로 사용된다.

NEXT-HOP은 BGP 경로 광고를 수신한 라우터가 패킷을 보내야 하는 다음 점프의 IP 주소를 지정하는 속성이다. 간단히 말해, 다음 목적지 라우터로 가는 인터페이스의 주소이다. 이 속성은 특히 여러 네트워크를 거쳐 연결되는 복잡한 BGP 환경에서 중요하다. 라우터는 NEXT-HOP을 통해 BGP 경로 정보를 전파받은 후, 그 경로를 통해 패킷을 어디로 전송해야 하는지를 알 수 있다.

---

Routing policy

아무리 protocol의 규칙이 있다고 해도 각 AS가 정해둔 policy를 앞서서 네트워킹을 결정하지는 않는다. 실제로 네트워크가 연결되고 정보를 전송할때 그 방향은 각 AS들이 사전에 결정해둔 policy대로 작동하는 경우가 굉장히 많다. 예를 통해 살펴보자.

위와 같은 네트워크 상황에서 X라는 고객은 B와 C provider 모두와 계약을 하여 보다 쾌적한 환경에서 네트워킹을 하고자 한다. 이때 실제로는 w에서 y로 데이터를 전송할때 w-A-B-x-C-y라는 동선이 가능하다. 하지만 x 고객은 본인이 징검다리 역할을 하기 위해 돈을 더 지불한 것이 아니기 때문에 C와 이웃이지만 본인이 B와 연결되어있다는 사실을 알려주지 않고 마찬가지로 B에게도 본인이 C와 연결되있다는 사실을 알려주지 않아서 남좋은 일을 해주지 않는다.

똑같은 상황에서 이번에는 A가 AW라는 path를 B에게 advertise를 하고 B가 BAW라는 path를 x에게 advertise를 했다. 이때 원래대로라면 B는 BAW라는 path를 C에게도 알려야하지만 C는 본인의 경쟁 provider이고 C에게 BAW path를 알려서 본인의 고객에게 이득이 가는 것이 없기 때문에 정보를 보내주지 않는다.

---