[Network] 하향식 접근 네트워크 - 4. Network Layer - (5) Routing in the Internet

이 글은 이화여자대학교 이미정 교수님의 2014년 2학기 컴퓨터 네트워크 강의를 기반으로 재구성한 것입니다. 삽화는 링크를 출처로, 저작권은 J.F Kurose and K.W. Ross에게 있다는 것을 밝힙니다.

 network layer에서는 다음과 같은 내용들을 살펴본다.

1. network layer principles
2. virtual circuit, datagram network
3. router의 내부
4. IP
   • datagram format
   • IPv4 addressing
   • ICMP
   • IPv6
5. routing algorithm
   • link state
   • distance vector
   • hierarchical routing
6. routing in the internet
   • RIP
   • OSPF
   • BGP
7. broadcast, multicast

 

 

 

 지난 포스팅의 hierarchical routing에서 inter AS routing, intra AS routing 2가지에 대해 살펴봤었다. 이 글에서는 hiearchical routing의 좀 더 자세한 동작과 실제 internet에서 사용하는 routing들을 살펴본다.

 intra AS routing은 RIP와 OSPF, inter AS routing은 BGP가 있다.

 

RIP, Routing Information Protocol

 RIP는 intra AS routing protocol로, distance vector algorithm을 사용한다.

 특징으로는 매우 작은 network에서 사용한다.

• 모든 link cost를 1로 설정하기에 distance metric은 path가 거치는 router 개수(hop count)가 된다. 이 때 max hop을 15로 설정하고, 16부터는 INF를 의미한다. 따라서 path에 15개 이상의 router가 들어올 수 없기 작은 network에서만 사용할 수 있다.
• distance vector의 경우 각 router가 가지고 있는 distance vector를 다른 router에게 알리는 과정을 거치는데, RIP는 이 과정을 30에 한 번씩 진행한다. 이 때 distance vector는 최대 25개의 destination subnet의 정보를 가질 수 있기 때문에 마찬가지로 매우 작은 network에서만 쓸 수 있다.

가지고 있는 정보를 다른 router에게 알리는 과정을 advertise라고 한다.

 

Link Failure, Recovery

 만약 어떤 link에 문제가 생기면, 해당 link로 이어진 두 router는 advertise message를 교환할 수 없다. 바로 위에서 RIP는 distance vector는 30초에 한 번씩 교환한다고 했는데, link에 문제가 생기면 advertise message가 교환할 수 없게 된다. 만약 이러한 상태가 180초까지 진행되면 link에 문제가 생겼다는 것을 파악하고, 해당 router를 next hop으로 저장하고 있는 모든 route를 invalidate한다. (poisoned reverse) 그러면 distance vector algorithm에 의해 가지고 있는 모든 route가 재계산되고 neighbor에게 distance vector를 재전송한다.

• 이전 포스팅에서 설명했듯 posioned reverse를 사용하지만 count to infininty 문제를 100% 해결할 수는 없다.
• RIP의 경우 INF가 16이므로 cost가 이 값이 될 때까지 계산하다.

 

RIP Table Processing

RIP : application level process

 routing protocol은 network layer에 있지만 RIP는 route daemon으로 불리는 application level process이며 OS의 background에서 계속 실행되고 있다. 30초마다 실행되는 RIP는 application layer에 위치하기에, 30초마다 application message를 만들어 neighbor에게 보냄과 동시에 forwarding table을 갱신한다.

 이 때 일반적인 application message가 destination에 도착하듯 application message가 UDP - IP - link - physical layer를 거쳐 encapsulate되고 destination에서는 physical - link - IP - UDP를 거쳐 decapsulate된다. 

 

 

 

OSPF, Open Shortest Path First

 RIP의 경우 network 규모가 작은 경우에만 사용할 수 있었기 때문에 이를 해결하기 위해 OSPF가 고안되었다.

 OSPF는 intra AS routing protocol로, link state algorithm을 사용한다. 특징으로는 아래와 같다.

• public available : RFC에 공개되어 있다.
• link state 기반이다. : 각 router는 link state packet을 뿌린다. 그러면 모든 router는 network topology map을 그리게 되고, 결과적으로 모든 router가 전체 graph를 알게 된다. 이후 자신을 source로 하는 dijkstra를 적용해 routing table을 작성한다.
• RIP의 경우 routing table entry가 subnet별로 있었다면, OSPF는 neighbor별로 cost가 있다. 때문에 router 각각이 가지고 있는 정보는 작지만 advertise packet이 network 전체에 broadcast된다.
• IP layer의 위에 구현되어 있다 : OSPF는 IP layer 바로 위에 구현되어 있기 때문에 UDP나 TCP encapsulate랄 하지 않고, IP packet으로 바로 보낸다.

 

 OSPF는 RIP가 제공하지 않는 기능들도 제공한다.

• scale : RIP는 사용할 수 있는 network size가 작았지만 OSPF는 큰 size의 network에도 사용할 수 있다. (만약 너무 크면 후술할 hierarchical OSPF를 사용한다.)
• dynamic link cost : RIP는 link cost를 보통 1로 static하게 사용했다. 반면 OSPF의 경우 delay, bandwidth, cost 등 지표를 반영한 link cost를 사용할 수 있다.
  • 이 경우 link state가 여러개이므로 각 link state에 대해 routing table을 다르게 만든다. 즉, multiple cost metric을 사용한다.
• MOSPF : Multicast OSPF. OSPF가 모은 정보를 바탕으로 여러 router에게 message를 동시에 보낼 수 있는 기능을 지원한다.
• tie : 만약 같은 cost를 가진 경로가 2개 이상 있는 경우, RIP는 하나만 선택해 저장했다. 반면 OSPF는 두 path 모두 저장한다.

 

 

Hierarchical OSPF

 OSPF는 link state이기 때문에 아주 큰 규모의 autonomous system에 적용될 경우 vertex, edge size가 매우 커지게 되어 link state algorithm의 계산 시간이 커질 뿐만 아니라 link state packet을 교환하는데도 많은 시간이 걸린다. (link state의 경우 network 전체에 link state가 전파되어야 하기 때문이다.) 이러한 단점을 개선하기 위해 OSPF의 layer를 만들고 사용하는 방식이 Hierarchical OSPF이다.

 

hierarchical OSPF

 구체적으로는 network size를 제한한 여러 개의 area와, area를 연결하는 backbone으로 나눈다.

 area 내부에서는 link state broadcast와 OSPF를 돌린다. area는 size가 제한되어 있으므로 짧은 시간 내에 algorithm을 돌릴 수 있고 link state packet 양도 제한된다. 그러나 각각의 area가 독립이기 때문에 다른 area로 가는 path는 모른다.

 이를 해결하기 위해 border router 하나와 area를 연결하며, 이 border router들이 모여 backbone을 이룬다. 그러면 하나의 area border router는 해당 area에 reachable하게 된다.

area border router를 gateway router라고도 부른다.

 

 이후에는 backbone의 모든 router들도 link state broadcast와 OSPF를 돌려 backbone의 모든 area border router들이 서로에게 가는 route를 계산한다. 그러면 backbone의 모든 router는 destination subnet으로 가기 위해 어떤 router로 가야 하는지 알게 된다.

 이렇게 hierarchical OSPF가 구성되면 한 area에서 다른 area로 packet을 보낼 때 backbone을 거쳐 packet을 전송한다.

hierarchical OSPF는 AS들끼리 routing하는 것과 유사하다.

 

 요약하면 hierarchical OSPF는 area와 backbone 2개의 layer로 나눈다. area border router는 해당 area의 subnet 정보를 교환하고, 이 정보를 바탕으로 area와 backbone 각각이 OSPF routing을 실행함으로써 [area-area, area-외부]의 모든 route를 계산할 수 있다.

 

 

 

BGP, Border Gateway Protocol

 BGP는 inter AS routing protocol이다. 이전 포스팅에서 AS 사이에는 아래 2가지가 일어난다고 했는데, 이 둘 모두 BGP가 제공하는 기능이다.

1. eBGP : inter AS routing protocol을 사용해 autonomous system의 gateway들끼리 통신하고, 서로의 reachable subnet을 공유한다. (다른 AS의 reachable subnet 정보를 받아온다.)
2. iBGP : reachable subnet을 autonomous system의 내부에 알린다. (propagation)
3. 추가로 good path routing : policy를 우선하는 route를 계산한다.

 

 

BGP Session

 두 AS의 인접한 router들, 그러니까 gateway router들은 BGP message를 이용해 반영구적인 TCP session을 맺고, 이를 통해 advertise를 교환한다.

BGP에서 advertise는 "내가 x로 보낼 수 있다"의 의미는 "x로 보내는 packet 나한테 주면 내가 대신 운반해줄게"에 대한 약속이다.

 

 이 때 AS끼리는 eBGP session으로 연결하고 AS 내부는 iBGP session으로 연결한다.

 

 

예시

BGP 예시

 3a와 1c는 AS의 gateway router이다. 이 둘이 TCP session으로 연결한다. 이후에는 아래와 같은 과정이 일어난다.

1. 3a가 1c에게 eBGP를 사용해 subnet 경로 정보를 알린다.
2. 1c는 iBGP를 사용해 AS1 내부에 그 정보를 모두 알린다.
3. 1b가 해당 정보를 받으면 1b는 2a에게 eBGP를 사용해 subnet 경로 정보를 알린다.

 실제로는 policy에 따라 다른 gateway router에게 정보를 알릴지 말지 결정한다.

 

 

BGP Message

 앞서 autonomous system들의 gateway router끼리는 TCP session을 만들고 정보를 교환한다고 했다. 이는 BGP message를 사용해 수행한다.

• OPEN : neighbor BGP에게 이 message를 보내면 TCP session을 생성한다.
• KEEPALIVE: OPEN에 대한 ACK, 또는 ping을 위해 사용한다.
  • TCP session이 생성된 후로 아무것도 하지 않으면 session이 끊어지기 때문에 이 message를 날려 서로의 상태를 확인한다.
• UPDATE : gateway router가 가지고 있는 정보가 변경된 경우 이 message를 날려 advertise한다.
• NOTOFICATION : error report, 또는 session close를 위해 사용한다.

 

Advertise Message

 BGP가 전송하는 advertise message는 prefix와 attribute로 구성되며, attribute는 AS-PATH와 NEXT-HOP로 이루어진다.

• prefix : 목적지 subnet IP address prefix
• attribute
  • AS-PATH : 목적지 subnet까지 도착하기 위해 거쳐야 하는 autonomous system list.
  • NEXT-HOP : 첫 번째 autonomous system의 gateway router. autonomous system들끼리 gateway 2개 이상으로 연결되어 있을 수도 있기 때문에 도착 gateway를 식별하기 위해 사용한다.

AS-PATH가 있기 때문에 새로운 link state를 계산할 때 cycle이 발생하는지 감지할 수 있으므로 count to infinity 문제가 발생하지 않는다.

 

 

Route Selection

 특정 subnet으로 가는 route가 여러 개일 때, 다음과 같은 우선순위로 결정한다.

1. policy decision : policy에 따라 good route만 고른다.
2. shortest AS-PATH : 더 적은 autonomous system을 거치는 route를 선택한다.
3. hot potato routing : autonomous system 내부에서 OSPF를 사용해 cost가 작은 route를 선택한다.
4. 이후로는 구현에 따라 달라진다.

 

 

Policy Decision

 드디어 inter AS routing에서 policy가 무엇인지 살펴본다.

 import policy는 advertise message를 수신했을 때 그 정보를 쓸지 말지 결정하는 정책이다. 다르게 표현하면, 다른 autonomous system에게 이 정보를 뿌릴지 말지 판단하는 근거이다.

 

 아니, autonomous system들끼리 모든 packet 교환하는 게 더 좋지 않냐? 라는 의문이 생길 수도 있다. 그러나 autonomous system들의 관리자, ISP들은 사업가들이다! 자신이 계약한 customer의 packet이 아닌데 굳이 옮겨 주어야 하나? 아니다. 또, customer들이 packet을 옮겨 주어야 할까? 그것도 아니다! 아래 예시를 보자.

 

policy decision 예시

 A, B, C는 provider network이고 A는 w와, B는 x와, C는 y와 계약했다고 하자.

 x는 B, C와 계약했으므로 둘 다에게 가는 route를 안다. 그러나 x는 B, C에게 자신이 알고 있는 route 정보를 알려주지 않는다. BGP advertise는 해당 목적지로 가는 packet을 자신이 옮겨주겠다는 뜻이기 때문이다. x는 B와 C의 provider가 아니기 때문에 굳이 옮겨줄 이유가 없다.

 

 비슷한 예시 하나를 더 보자. w로 가는 route를 알려주는 상황이라고 하자.

• A는 B에게 Aw route를 알려준다. - A는 w의 provider이기 때문에 w로 가는 packet을 옮겨 주어야 한다.
• B는 x에게 BAw route를 알려준다. - B는 x의 provider이기 때문에 x에서 나오는 packet을 옮겨 주어야 한다.
• B는 C에게 BAw route를 알려주지 않는다 - w는 B의 customer가 아니고, C도 B의 customer가 아니기 때문이다.

 

 

 

 

요약 : BGP + OSPF가 forwarding table을 만드는 과정

1. autonomous system들의 gateway router들끼리 BGP message를 사용해 TCP session을 생성한다.
2. gateway router들끼리 advertise message를 날린다. 그 결과 각각의 autonomous system이 담당하는 subnet IP address prefix를 찾게 된다.
3. route selection한다.
   1. policy에 따라 선택한다.
   2. 더 적은 autonomous system을 거치는 route를 선택한다.
   3. hot potato routing을 선택한다. : advertise message에 있는 NEXT-HOP(첫 autonomous system의 첫 router)까지 OSPF를 사용해 경로를 찾는다.

 위 과정을 통해 route를 찾으면, forwarding table에 destination subnet IP address prefix에 대한 entry를 작성할 수 있다.

• subnet IP address prefix / route를 읽고 output port 작성

 

 

Intra AS routing vs Inter AS routing

 총 3가지 측면에서 비교할 수 있다.

1. policy
   • inter AS routing의 경우 traffic이 어떤 route를 타는지, 어떤 traffic이 나의 autonomous system을 타는지 정보를 알아야 하고, 계약관계이므로 policy가 중요하다.
   • intra AS routing의 경우 admin이 하나이므로 least cost로 가는 것이 제일 좋다.
2. scale
   • inter AS, intra AS routing 둘 다 scalability가 중요하다. advertise message를 보낼 때, prefix aggregation을 통해 prefix를 합칠 수 있다. 이를 통해 routing table의 entry 개수를 줄일 수 있고, advertise message traffic도 줄일 수 있다.
3. performance
   • intra AS routing의 경우 성능이 1순위로 중요하다.
   • inter AS routing의 경우 policy가 1순위로 중요하다.

 

 

 

참고 : Forwarding Table vs Routing Table

 forwarding table은 router의 data plane에 있고, 들어온 packet이 나갈 port를 mapping한다.

 routing table은 router의 control plane에 있고, IP address prefix와 어떤 router로 가야 하는지에 대한 정보가 있다.

 

 

 

 

 

잘못된 내용이나 오탈자에 대한 지적, 질문 등은 언제나 환영합니다.