Routing in the Internet

Inter-AS task#

• AS2, 3와 같은 이웃 AS가 존재함
• AS1은 AS3를 통해서 도달할 수 있는 subnet을 발견할 수 있어야하고, 마찬가지로 AS2 를 통해서 도달할 수 있는 Subnet도 발견할 수 있어야 함

  • 이후 밖에 있는 Subnet 정보를 Gatway router들이 알아와서 네트워크 전체에 알려주게 됨
• inter-AS routing의 책임

  • 이웃한 AS로 부터 도달할 수 있는 서브넷이 뭐냐 = reachability information
  • 그리고 해당 reachability information을 AS 내에서 proagate한 역할을 해야함

포워드 테이블 셋팅 예시#

1. AS1은 Inter-AS routing protocol을 통해서 세상에 x라는 서브넷이 있고, AS3를 통해서 reach할 수 있다는 정보를 알아와야함

   1. 해당 역할은 AS3에 연결된 게이트웨이 1c가 해당 역할을 수행
   2. 1c는 AS전체에 정보를 propagetes 시킴

그런데 도달 방법이 multiple 하다면?#

• 1c는 AS3를 통해서 X에 도달할 수 있는 정보를 알아옴
• 1b도 AS2를 통해서 X에 도달할 수 있는 정보를 알아옴
• 그렇게 1c, 1b 모두 자신의 라우터 내에 해당 도달 정보를 퍼트리게 됨
• 그 경우 1d는 어떤 라우터를 골라갈 것이냐? ⇒ 이것도 Inter-AS 라우팅 프로토콜의 일임!
• hot potato routing

  • 1c와 1b중 더 가까운 라우터는 어딘지 확인

    • 그건 우째 파악할까? intra-AS routing protocol을 통해서 얻어진 정보로 확인이 가능
  • 더 가까운 라우터를 x로 나가는 인터페이스로 결정함

inter-AS routing protocol 정리#

1. inter-AS routing protocol을 통해서 외부의 subnet에 접근할 수 있는 정보를 알아 냄
2. 도달 정보가 multiple 하다면 내부 게이트웨이의 최단경로를 알아냄 (intra-AS 라우팅 사용)
3. 그 중에서 가장 가까운 라우터에게 x로가는 게이트웨이로 결정 (hot potato routing)
4. 게이트웨이가 결정됬다면 해당 게이트웨이로 가는 인터페이스는 intra-AS routing protocol을 통해서 알아낼 수 잇음

인터넷에서 이용되는 라우팅 프로토콜#

Intra-AS Routing#

• 가장 일반적인 intra-AS 프로토콜의 종류

  • RIP : Routiong Information Protocol
  • OSFP : Open Shortest Path First
  • IGRP : Interior Gateway Routiong Protocol (Cisco proprietary)

RIP#

• 인터넷 가장 초창기에 사용되던 프로토콜
• distance vector 알고리즘에 속함
• 1982년 BSD-UNIX 시스템 내장되어 distribution됨
• 소규모의 네트워크에서 적합함
• RIP는 모든 링크 코스트를 1로 잡음 ⇒ 매우 단순한 방법

  • 따라서 distance matric이 홉 카운트임
  • RIP에서 Maximum 홉 카운트는 15임

    • 16부터는 경로가 없다는걸 의미함
• Advertisement 메세지에 distance vector를 실어서 이웃과 교환

  • 실릴 수 있는 목적지의 갯수가 25개임
  • 매 30초마다 이웃과 교환함

예제#

• Z 목적지로 가는 엔트리를 수정함

  • 다음 라우터는 A로, 홉카운트는 5로 수정

link filure, recovery#

• 180초 동안 Advertisement가 오지 않을 경우 해당 link가 fail 되었다고 생각
• 해당 루트로 가는 라우팅 테이블을 모두 invalidated를 함
• 자신의 디스턴스 벡터를 새롭게 계산하여 새로운 Advertisement를 자신의 이웃들에게 보내주게 됨
• 이웃들 역시 새로운 디스턴스 백터를 계산해서 변경이 있다면 새로운 Advertisement를 보내줌
• ping-pong loops을 회피하기 위해서 poison reverse를 사용함

RIP table processing#

• RIP는 어플리케이션 레벨의 프로세스로 만들어짐

  • 프로세스의 이름은 route-d (deamon)

OSPF#

• Open = publicly available
• OSPF는 link state 알고리즘에 기반한 프로토콜임

  • 각 라우터는 LS packet을 네트워크 전체에 퍼트림
  • 모든 네트워크상의 라우터는 네트워크 토폴로지 맵을 그리게 됨
  • 토폴로지맵이 그래프로 모델링 됨
  • 해당 그래프를 모델로 다익스트라 알고리즘을 적용함으로서 라우트 테이블을 계산하게 됨
• OSPF의 Advertisement에는 각 엔트리가 이웃별로 있음
• OSPF 프로토콜은 IP바로 위에 구현이 되어있음

OSPF가 RIP에 비해서 향상된 점#

• 규모가 크다면 hierarchical(구조적인) OSPF를 사용함
• 링크 코스트를 다양하게 사용 가능

  • delay, bandwidth, money 등 다양한 링크코스트 사용 가능
  • 각자 LS Advertise가 필요함, 라우팅 테이블도 별도로 계산 필요
• OSPF의 메세지들은 authenticated됨 (보안 요소)
• 멀티케스트 라우팅을 지원함 = MOSPF
• 동일 경로의 비슷한 비용의 PATH가 존재할 경우 모든 경로를 활용할 수 있도록 허용함

hierarchical OSPF#

• AS의 규모가 커지면 node와 link가 많아짐
• 규모가 커질 수록 LS packet이 많아짐 때문에 AS의 규모가 제한됨

  • 때문에 AS를 다시 Area로 나누게 됨
  • 그리고 LS broadcasting은 해당 Area내에서만 이루어지게 됨
• 다른 Area가는 길을 알수가 없음

  • 때문에 Area border routers를 두게 됨
  • 자신에 Area내엔 어떤 목적지 Subet이 있는지 그리고 각 거리를 나타내는 summarize를 서로 교환하게 됨
• Area border router를 포함해서 backbone area가 구성이됨

  • Area 들을 붙혀주는 역할을 함
  • Backbone Area 내에서도 OSPF가 돌음
  • 때문에 Backbone Area내의 라우터들은 다른 라우터로 가는길을 정확히 알고있음
  • 그리고 해당 Area는 Boundary router를 통해서 다른 Area와 연결됨
• hierarchy는 local area와 backbone으로 구성되어 있음

Internet inter-AS routing: BGP#

• BGP는 역할에 따라 2가지로 나누어짐

  • eBGP : 서브넷 도달정보를 이웃 AS로 부터 알오는데 이용되는 프로토콜
  • iBGP : 그렇게 알아온 정보를 라우트 내부에 퍼트리는 역할을 하는 프로토콜
  • 좋은 경로는 선택하는데 있어서 BGP가 가장 중요시하는건 Policy(정책)

BGP Basics#

• semi-permanent TCP connections를 통해서 BGP advertis를 교환함

• AS3는 해당 새로운 경로로 보내는걸 약속해준다는 의미

기본적인 BGP 동작#

• 3a가 X에 대한 prefix reachability를 adversies할 경우
• 1c는 eBGP 세션을 통해서 해당 정보를 받음
• 1c는 iBGP 세션을 통해서 자신의 AS에 해당 정보를 알리게됨
• 1b는 X로 가는 경로를 2a에게 알리지 말지 결정할 수 있음

Path attributes and BGP routes#

• BGP 라우터들이 주고받는 경로 정보의 핵심적 내용은

  • 목적지 subnet의 prefix와 도달하기 위한 attributes로 구성됨
• 목적지 prefix의 구성

  • AS-PATH : subnet prefix로 가기위해 거쳐야 하는 AS의 리스트를 보여줌
  • NEXT-HOP : 다음 AS로 가기위한 라우터 정보

    • 왜냐하면 multiple 정보를 가지고 잇을 수 있기때문에 하나를 선택해서 보내줘야 함
• 받은 AS advertisement를 받은 후 우리의 AS 쓸것인지 말것인지를 결정하는 import policy를 적용함

BGP route selection#

1. policy decision을 함
2. shortest AS-PATH
3. hot potato routing
4. 추가적인 criteria

BGP message#

• OPEN : 세션을 오픈하기 위한 메세지 = 이웃간 TCP 커넥션이 연결됨
• UPDATE : 새로운 경로를 발견할 때마다 advertises를 하게됨 (혹은 중단 시킬대도 사용)
• KEEPALIVE : OPEN 메세지를 받은 BGP 클라이언트는 해당 메세지로 ACKs을 하게 됨

  • 혹은 TCP 커넥션의 중단을 막고, 서로 연결되어 있다는걸 알리기 위해서 사용
• NOTIFICATION : 이전 메세지에서 오류가 있다거나, BGP 세션을 종료하고 싶을때 이용