Routing Protocols : (RIP, OSPF / BGP)

Routing algorithms in the Internet

Intra-AS Routing

also known as interior gateway protocols (IGP)

• RIP: Routing Information Protocol
• OSPF: Open Shortest Path First (IS-IS protocol essentially same as OSPF)
• IS-IS : Intermediate-System to Intermediate-System; standardized by the ISO(International Organization for Standardization) in 1992

• IGRP: Interior Gateway Routing Protocol (Cisco proprietary for decades, until 2016)

저기서 Path Vector는 Distance Vector

 

---

 RIP : Routing Information Protocol - 초기 internet

application-level로 구현

UDP packet 형태로 보내고 받는 것을 주기적으로 함

초기 internet에서 사용된 만큼 단순함.

단순한 distance match를 지원하고 소규모 네트워크에서 사용

 

최대 hop은 15로

16 이상이면 무한대로 간주하여 갈 수 없다고 표시

15 hop 이내의 작은 route여야 RIP 적용 가능

 

(소규모 scale, 단순한 metric - hop 수로 판단)

 

Distance Vector을

이웃과 매 30초마다 주기적으로 주고받음.

변화가 생겼을 때 주고받는 것이 아니라.

주기적으로 보내면서 나 살아있다, drop 여부를 아는 등 여러 장점이 있긴 함

 

destination subnet 개수가

최대 25개까지 지원 (IP address)

???

 

---

OSPF - Link state Algorithm 

최단 경로 우선 프로토콜(영어: Open Shortest Path First, OSPF)은

인터넷 프로토콜(IP) 네트워크를 위한 Link State Routing Protocol 

 

LS를 사용하기에

동일한 global topology map을

모든 router의 AS에 가지고 있어야 함

"다익스트라 알고리즘"

 

OSPF는 이러한 한계점을 극복하기위해 다양한 metric을 사용:

  bandwidth, minimum delay(RTT), max throughput, reliability를 제공

 

RIP의 한계점을 보완 :

한계점은 단순한 4 count라는 metric를 사용하고 host-to-host뿐이라 단순한 네트워크만 가능하다는 점

 

 

<Two-level hierarchy>

AS를 경우에 따라 여러 개의 area로 나눔 : 확장성의 문제 해결

Link-state advertisement (LSA)가 flooded 되는 것을 방지

area border router를 두어

목적지 subnet으로의  distance을 요약하여

다른  area border router와 교환

RIP는 UDP 위에 올라가는 application으로 제공되었지만.

 

backbone area는 backbone router를 이용하여

Area border router 간 연결 지원

backbone area와 각 area는

그 내부에서만 link state advertisement는 flooding,

그 안에서는 바로 서로 router를 통해 소통하지만 

자신의 area 외의 곳에는

area border router로 packet을 보내고

backbone이 어느 area로 가야할 지 알려주는 식으로 진행

AS boundary router는 다른 AS와 연결시켜주는 역할을 담당

OSPF에서 목적지가 다른 area에 속해 있다면,

최소한 2개의 라우터를 경유해야 목적지 호스트에 전달될 수 있다.

 

 

---

Routing algorithms in ISP

Inter-AS routing

packet의 목적지가 AS 내에 있지 않을 때 어느 AS로 보내야할지 결정하기 위해

1. reachable dest에 대해서 알고 있어야함
2. 자신의 AS 내 모든 router에 그 정보를 알림

---

 

BGP (Border Gateway Protocol)

Internet의 inter-AS routing 또는 inter-domain routing protocol은

각 internet을 연결시킴.

가장 넓게 퍼진 internet backbone.

가장 상위이므로 (?)

모든 router가 동등한 입장이기에

minimum cost path을 중요시함

 

그런데 AS 간 routing은

min cost보다 policy-based routing을 하여 control traffic flow.

그러므로 BGP는 path vector를 이용한 routing protocol을 사용

distance vector에서는 intra-AS에서 쓰였고

cost 최소화가 가장 중요했기에 cost만 명시해서 보냈지만

여기선 policy가 중요해서 어떤 AS를 거쳤는지 알아야 했음.

그래서 거쳐야하는 모든 AS의 번호를 쭉 나열

 

Classless inter domain routing (CIDR)

routing table에 목적지를 적을 때 subnet도 적음

 

Incremental Update

BGP 경로에 변화가 생겼을 때만 update. 

이렇게 되면 한 번 보낸 정보가

진정으로 도착했는지 알기 어려울 수 있기에

TCP로 reliability를 증명하여 손실을 막음

 

BGP: peering

BGP 메시지를 주고받는 두 router

• External BGP peering (eBGP) : 서로 다른 AS끼리
  • 이들은 직접적인 link로 연결됨
  • routing policy는 여기서.
• Internal BGP peering (iBGP) : 같은 AS 내에서. (같은 AS 번호를 가짐).
  • 직접 연결되지 않아도 몇 hop을 건너서 서로 주고 받을 수 있음.
  • fully meshed를 사용. 그래서 IGP((Internal Gateway routing Protocol)를 이용하여 닿을 수 있어야 함
• 이 길은  OSPF에 의해서 결정된다

네트워크의 집합을 몇개의 그룹으로 나누었을 때
동일 그룹 내에서 라우팅 정보를 교환할 때
사용하는 프로토콜을 IGP 라고 합니다.
쉽게 말해 IGP는 내부 경로 설정을 하는 Protocol

 

1c :&nbsp; gateway routers run both eBGP and iBGP protocols

 

 

BGP : basics

BGP session : 두 BGP routers는 semi-permanent TCP를 통해 BGP 메시지를 교환하는데,

메시지에는 different network prefix와 path가 들어있다. ( “path vector”)

 

BGP : inter-AS routing

eBGP : learn neighbor AS info

iBGP : propagate info to all routers in own AS

이 때 반드시 자신이 배워온 정보만 prefix로 두고 보냄

아래 사진에서 1c는 AS3만 알리고 1b는 AS2만 알림

 

최종적으로 목적지까지 가는 제일 좋은 경로를 선택

 

BGP : message (for TCP & path)

• OPEN : TCP connection 열고, 상대방에 대해 authenticate
• UPDATE : advertise new path ( or withdraw old path)
• KEEPALIVE : keep connection alive -  UPDATE가 없더라도! 서로 살아있는지 확인. Update의 ACK으로도 이용
• NOTIFICATION : reports error, close connection

BGP는 incremental update만을 수행하므로 
routing 을 위한 information update가 reliabl하게 전송되어야 한다.

 

이러한 type은 BGP header의 1 byte Type field에 기록

 

Path attributes and BGP routes

BGP route = 목적지의 prefix + 목적지까지의 path attribute

 

attribute = AS-PATH + NEXT-HOP _ …

• AS-PATH : prefix로 delivery되기 위해 거쳐야하는 모든 AS의 번호 목록을 여기에 적음
  • update msg를 통과할 때마다 다음 번 eBGP peer에게 BGP msg를 넘기기 전에 
  • 자신의 AS-PATH 앞에 자신의 AS 번호를 붙임.
• NEXT-HOP :  두 AS가 여러 개의 link로 연결되어 있을 때 어느 link를 타고 할 지를 정함
  • 바로 그 다음의 HOP의 BGP router 의 주소를 알고 있어야 하는 것

 

BGP의 route 정보는 경유하게 되는 AS들의 list로 구성되지만
next hop AS로 연결하는 internal BGP router의 주소도 필요하다.
next hop AS로 연결하는 BGP 라우터가 여러 개 일 수 있으므로 
그 중 어떤 것인지를 명시해 주어야 함.

 

 

 

BGP Path attributes: policy (policy-based routing)

<Enforcing various policies> - eBGP

import policy : 이 경로로 온 걸 받을 거냐 말 거냐 (AS Y를 절대 경유하지 않겠다 등)

export policy : 알고 있는 path를 다른 AS에게 advertise 할 것이냐 말 것이냐

 

AS는 특정 AS만 원하도록 설정할 수 있다는 것

 

 

 

 

BGP path advertisement

 

1)

2)

BGP: achieving policy via advertisements

 

ISP는 자신이 서비스하는 customer만 지나가기를 원하지,

transit traffic은 거쳐가지 않기 바람

 

A는 w에 provide하는 주체이고, Aw path를 B와 C에게 advertise를 함

w로 가는 traffic을 자신이 delivery를 하기위해 Aw를 남에게 알림

 

그런데 B의 입장에서 보면

B는 Aw path를 C에게 알리지 않음.

B의 입장에서는 C에 BAw로 알리면 B를 거쳐가야하기 때문에.

덕분에 C는 Aw만 알게 되어서 B를 거치지 않고 갈 수 있음

 

x처럼 두 network에 붙어있는 것을

dual-homed라고 하는데

x는 B와 C끼리 통신하는데

자신을 거치는 것을 원하지 않기에

B에게 xC path를 알리지 않음

 

 

Hot Potato routing : determining the best routes

AS2의 2d는 

2a로부터 AS1,AS3,X 경로를

2c로부터 AS3,X 경로를 알게 된다

 

hot potato routing은 자신의 AS2에서 최저 cost의 경로로 탈출하는 방법이다.

즉 least intra-domain cost를 가지는 local gateway로 보내려고 하는 것

2d에서 2a로는 201의 OSPF link weight를,

2d에서 2c로는 263의 OSPF link weight가 필요하기에,

AS3,X 경로가 적게 경유하지만 2a를 통해 보내게 된다

 

BGP는 shortest AS path가 두 개 이상일 때, hot potato routing을 적용한다.

 

BGP route selection based on …

tie를 이룰 수록 그 아래 단계를 적용하여 선택

1. local preference value attribute : policy decision
2. shortest AS-PATH  >>> num of router hops
3. closest NEXT-HOP router ~ 같은 거리라면 hot potato routing 적용
4. additional criteria (BGP ID)

BGP는 policy를 우선적으로 적용한다
그 다음으로 최단 거리 경로를 선택한다

 

 

EX 1

1. 1c는 3a로부터 eBGP를 통해 BGP message를 받음.
   1. 메시지 속 route(경로) =  목적지의 prefix + attribute(AS-PATH, NEXT-HOP)
   2. 예) prefix:138.16.64/22,   AS-PATH: AS3,AS131,AS201  NEXT-HOP:201.44.13.125(3a) 
2. 동일한 목적지에 대해 또다른 path를 받았다면 (1b로부터 받음)
   1. 목적지 prefix는 동일할 수 밖에 없지만 지나온 경로와 직전 gateway router가 다름
   2. 예) prefix:138.16.64/22,  AS-PATH: AS2,AS17   NEXT-HOP:202.43.12.12(2a) 
   3. 이 경로가 더 짧은 AS-PATH를 갖기에 새로운 경로가 최종 경로로 선택됨

 

EX 2

이 경우 policy->AS-PATH->NEXT-HOP까지 거쳐와야 결정할 수 있었음

2d는 iBGP를 통해 X로 가는데

2a와 2c의 경로가 있다는 것을 알게 됨

이 때 hot potato routing에 의해 weight가 적은 쪽을 선택하게 됨

그래서 AS-PATH: AS1,AS4 , NEXT-HOP:1c 로 결론남

 

 

왜 intra-, inter-AS routing을 구분하여 사용하나?

<policy> - inter-AS : admin이 전체 traffic 통제하려고

<performance> : intra-AS

<scale> - inter/intra 간 hierarchical routing 설정 (table size, reduced update traffic)

 

---

고로 forwarding table entry를 결정하는 방법을 정리하자면...

routing은 forwarding table의 entry를 결정하는 방법은...

목적지가 AS 내에 있는 internal dest를 가진다면 intra-AS에 의해 entry 값이 결정됨

목적지가 AS 밖에 있는 경우라면 inter-AS(learn)와 intra-AS(propagate)가 협력하여 entry 값을 결정 

 

AS 내에 존재하는 목적지 subnet에 대한 라우팅 테이블 엔트리는 
intra AS routing에 의해 결정되고,
다른 AS에 위치한 목적지 subnet들에 대한 routing entry 결정에도 
external AS routing과 더불어 internal  AS routing 적용이 필요하다

 

Ex: router 1d 속에 forwarding table 세팅하기

<iBGP>

AS1은 inter-AS protocol을 통하여 

subnet x가 AS3(gateway 1c)를 통과하여 닿을 수 있지만 

AS2를 통과하면 닿을 수 없음을 알게 됨

 

이런 식으로 inter-AS protocol은 path info를 모든 internal router에게 전파

 

 

<eBGP>

router 1d는 intra-AS routing info를 통해

1c로 가기위한 interface가 if0 interface임을 알게됨

 

그렇게 forwarding table entry에

x로 가려면 if0 interface를 거쳐야한다는 정보인

(x,if0)를 적음

 

 

종합 : BGP, OSPF, forwarding table entries

<intra AS로 OSPF가 사용되는 경우...>

BGP에 의해

1c가 목적지 x로 가려면

AS3,X 또는 AS2,AS3,X로 가야함

 

이를 eBGP를 담당하는 1c가 알고 있기에

그 경로에 대해 1b, 1a, 1d에게 iBGP를 통해 알림

덕분에 X로 가려면 1c로 내보내야한다는 것을 알게 됨

그럼 1d가 X로 보내기 위해선 OSPF intra-domain routing을 통해 1d에서 1c gateway로 먼저 가기 위해 interface1로 forwarding

1a가 X로 보내기 위해선 OSPF intra-domain routing을 통해 1d에서 1c gateway로 먼저 가기 위해 interface2로 forwarding

 

Ex)

Q) x에 대해 1d가 알려면

어떤 (x,?) entry를 forwarding table에 넣어야 할까요?

1d가 x에 대해서 알 수 있었던 건

1c를 거쳐왔기에 1c를 통해 AS1을 탈출할 수 있음을 앎

그러니 1d가 1c로 먼저 가려면 l1 interface로 가야함

(x, l1)

 

Q) 만약 AS2-AS4 사이 길이 놓인다면

1d는 x로 가기 위해 AS3를 거치는 l1을 선택할까

아니면 AS2를 거치는 l2를 선택할까?

둘 다 동일한 AS-PATH를 가지지만

l2가 더 가까운 NEXT-HOP router를 가지고 있기 때문에

l2 선택

 

Q) AS2-AS4 사이에 AS5가 있다고 한다면

1d는 AS2,AS5,AS4로 가는 l1과

AS3,AS4로 가는 l2 중 무엇을 선택할까?

l1. 얘가 더 짧은 AS-PATH를 가지기 때문

---

+) BGP에서 path 속 loop를 어떻게 감지하나?

path == AS number list

이미 자신의 AS number가 list 에 있다면 loop가 발생했음을 알 수 있음

1. How does router 3c learn x? : eBGP
2. 3a가 x를 발견하는 건? 
3. …