5-1-(1) Hierarchical routing(BGP) & (2)

5-1. Traditional routing algorithms(per-router control)

(1) Routing algorithm classification

- Link state routing algorithm: Dijkstra's algorithm(OSPF)

- Distance vector algorithm: Bellman-Ford algorithm

- Hierarchical routing(BGP)

(2) Routing protocols

- RIP, OSPF/BGP

 

5-2. SDN controllers(logically centralized control)

ㄴ OpenFlow, ODL, ONOS controllers

(1) Network management, configuration

- Internet Control Message Protocol(ICMP)

- SNMP, YANG/NETCONF

 

 

Making routing scalable

 

여태까지는 모든 router들이 모두 동일한 계급을 가진다는 가정 하에 생각해 왔지만

지금부터는 현실을 반영하여 생각해볼 거다.

 

실제로는 모든 destination을 routing table에 저장할 수도 없을 뿐더러

저장하더라도 routing table 교환할 때 link가 꼬일 수 있다.(scale)

 

또한 자신의 내부 네트워크 내용을 외부에 알리고 싶지 않아 한다. (administrative autonomy)

 

Hierarchical routing: Autonomous Systems(AS)

 

같은 routing policy를 제공하는 네트워크 집합

=> 네트워크 내에서 관리자는 한 명이기 때문에 link state를 알릴 때 외부에 알려야 한다는 부담이 없다.

 

AS number

 

- 고유한 32-bit 정수

- ICANN에 의해 관리

* ICANN 안의 Internet Assigned Numbers Authority가 관리

* ICANN은 DNS의 root name server, Internet address 주소 block 할당 등 총괄

 

- transit AS: 다른 AS로부터 들어오는 routing 정보 알려주는 AS

- stub AS: 한 AS 내 routing 정보 알려주는 AS

 

Internet approach to scalable routing

 

서로 다른 AS 간 routing이 이루어질 때

일단 한 AS 내에서 entry를 결정하기 위해 intra-AS routing이,

외부 목적지로의 entry 결정하기 위해 inter-AS & intra-AS가 사용된다.

 

 

- unicast: (1:1)

- multicast: (1:N) unicast로 하나씩 보내는 것보다 효율적이기 때문에 수행

- broadcast: (1:불특정다수)

이중 unicast를 중심으로 볼 거다.

 

intra-AS routing(각 AS가 다른 프로토콜 사용 가능)

 

: 같은 AS에 속한 host/router 사이의 routing

- gateway router을 포함한 AS 내 모든 router들은 같은 protocol(OSPF, RIP, ...) 사용함

* gateway router(border router): 물리적으로 다른 AS의 router들과 물리적으로 연결돼있음

- interior gateway protocols(IGP)라고도 불림

- 대표 종류

* RIP: Routing Information Protocol => 과거에 널리 사용. 지금은 사용 안 함

* EIGRP: Enhanced Interior Gateway Routing Protocol => Cisco 소유의 프로토콜이었지만 현재는 오픈됨

* OSPF: Open Shortest Path First => 현재 널리 사용

* IS-IS protocol: ISO가 제시한 표준안. 근본적으로는 OSPF와 동일.

 

 

Classful->Classless->IPv6로 변해가면서 버전도 바뀌고 있다.

모든 종류를 보긴 어려우므로 대표적으로 RIP, OSPF, BGP만 살펴볼 거다.

 

 

<"RIP"(Routing Information Protocol)>

: metric = hop count(최대 15개), 각 link들 cost=1

=> network diameter<=15 인 네트워크에서만 RIP 적용 가능

: 30초마다 이웃에게 자신의 DV 알려줌(변화가 없어도 생존신고식으로)

: DV algorithm 사용하기 때문에 각 목적지 subnet 별로(subnet 최대 25개) distance를 적어야 함

hop count 혹은 destination subnet 개수로 인해 network size 고정됨

: RIP는 network 계층의 forwarding table을 세팅하기 위한 프로토콜

=> "route demon"이라는 app 계층의 프로그램으로 동작하므로 UDP/TCP, IP에서 encapsulate되어 옴

 

 

 

<"OSPF"(Open Shortest Path First)>

: LS algorithm 사용

=> IP 계층의 프로토콜이므로 TCP/UDP에서는 encapsulate되지 않고 바로 IP datagram으로 encapsulate돼 전달

=> bandwidth, minimum delay(RTT), maximum throughput, reliability 등 link cost metrics 여러 개 가능 (AS 별로 다를 수 있음)

* 한 AS 내에서 여러 cost metrics 사용한다면 routing table 여러 개 둬야 함

=> 결과적으로 AS 내의 모든 router들은 동일한 topology map을 가짐(link-state advertisement의 broadcasting)

=> Dijkstra's algorithm 사용해 route 계산해 forwarding table 작성

: security

=> 모든 OSPF msg들은 authenticate 된 상태

: two-level hierarchy

=> OSPF가 크다면 area로 나누고, local area들은 하나의 backbone area로 연결됨

=> Link-state advertisement 는 하나의 area에서만 효력

- AS boundary router(ASBR)

: backbone의 최상위 router(gateway/border) => 다른 AS와 연결해줌

 

- ABR(Area Border Routers)

: area 내 어떤 destination subnet이 있고, distance는 각 얼마인지 요약해 backbone 내에 advertise

=> 각 ABR들은 자신의 목적지에 해당하는 ABR을 찾아 보낼 수 있음

: backbone 영역에만 국한된 OSPF 사용

 

- local or internal routers

: 한 local area 내의 router들

=> local area에 국한된 LS

=> 다른 area로 forward하기 위해서는 ABR을 거쳐야 함

 

	RIPv2	OSPFv2
Routing updates	30초마다 entire routing table 업데이트	routing에 변화가 있을 때만 업데이트
Metric	hop count(<=15) delay나 link cost에 대한 개념 없음 그저 hop count 가장 적은 것이 선호됨	cost (Bandwidth, Minimum delay=RTT, maximum throughput, reliability, 등)

 

 

inter-AS routing(모든 AS 같은 프로토콜)

: 서로 다른 AS 간 routing

gateway router들만 참여

전세계가 공통 protocol(BGP) 사용함

 

<"BGP"(Border Gateway Protocol)>

AS1 내의 router가 다른 AS의 destination으로 보내고자 할 때

AS1의 어떤 router가 gateway router(나갈 때 거쳐야 하는 router)가 될 것인가? 에 대한 것.

 

1. 우선 그 목적지로 가기 위해서는 AS2, AS3 중 어디로 가야 할 것인가(eBGP)

2. 그 정보를 AS1 내 모든 router들에게 BGP를 통해 propagate(iBGP)

 

- 이러한 과정을 통해 internet이 하나로 통합됨

- backbone을 위해 사용

- gateway router: "나 여기 있는데, 나를 통해서 갈 수 있는 destination에는 이런 게 있고, 이렇게 가면 돼" 라는 msg 서로 주고받음

- BGP 종류

* eBGP: gateway router가 이웃 AS들로부터 정보 얻음(어떤 destination에 가기 위해서는 어떤 AS로 가야 하는지 알게 됨)

* iBGP: 자신의 AS 내에 알림 => iBGP끼리는 논리적 연결

- policy-based(path vector) routing

* cost보다는 policy가 더 중요 => policy를 통해 각 AS는 자신을 드나드는 traffic 종류 정해둘 수 있음

 

 

iBGP/eBGP가 만들어지려면 우선 BGP session이 만들어져야 함

BGP session은 TCP connection을 맺어 peer 관계를 형성한 두 개의 BGP router 간에 이루어짐

BGP는 routing protocol인데, TCP의 application program으로 실행되는 것이다.

 

=> next hop이 아닌, "path"(거쳐야 하는 모든 AS 목록)를 advertise

 

따라서 BGP는 "path vector" protocol

 

AS3의 gateway router인 3a는 AS2의 gateway router인 2c에게, destination X로 가는 path를 advertise

=> "advertise한다" = "destination으로의 forwarding을 약속해준다."

 

 

gateway router가 eBGP를 통해 배워온 정보가 iBGP를 통해 AS 내 모든 router에게 알려짐(inter-AS routing)

단,, 자신이 배운 정보만을 알려주고, AS 내 다른 router에게 전해들은 정보는 알려주지 않는다 !!

 

예컨대 1a는 AS3과 연결되는 gateway router, 1b는 AS2와 연결되는 gateway router이다.

1a는 1b로부터 AS2에 대한 정보를 들을 수 있지만, 이걸 다른 router에게 알려줄 수는 없고,

오직 자신이 직접 얻은 AS3에 대한 정보만 알려줄 수 있다. 그래서 가능한 경우는 다음과 같다.

- 1c는 3a로부터 얻은(eBGP) 정보를 1a로 전달할 수 있음(iBGP)

- 1c는 1b로부터 얻은(iBGP) 정보를 3a로 전달할 수 있음(eBGP)

좋은 route를 결정하려면 얻은 정보 및 policy에 기반해야 한다.

 

BGP message 종류

 

- OPEN: BGP peer & TCP connection을 시작하기 위해 쓰는 msg

- UPDATE: open된 TCP connection을 통해 새로운 경로 advertise하거나, 기존 경로 withdraw하기 위해

- KEEPALIVE: UPDATE가 일정 기간 동안 없어도 TCP connection이 닫히지 않게 하기 위해, 혹은 OPEN msg에 대한 ACK으로도 사용

* TCP connection은 일정 기간 동안 업데이트 없으면 알아서 닫음..

- NOTIFICATION: 이전에 보냈던 BGP msg의 오류를 report하기 위해, 혹은 현재 오픈돼 있는 TCP를 끊기 위해(peer 끊기 위해)

 

TCP는 msg의 바운더리 인식 못해 아무렇게나 자름

BGP는 TCP의 application이므로 하나의 BGP가 토막나 들어오거나, 이전BGP와 다음BGP가 섞일 수도 있음

=> Length field로 바운더리 구분할 수 있음

but, length field에 오류가 있으면 다른 BGP msg가 섞일 수도 있는데

=> Marker field 모든 byte=1로 설정하면 length field에 오류가 있어도 peer 간 섞임 현상 방지

(Marker field=1이면 다음 msg가 시작됐음을 알 수 있음)

 

 

BGP route: path attributes

BGP는 path vector routing protocol => 목적지 subnet 별로 full path의 목록을 AS number로 제시

이때 제공되는 route는 

 

NLRI: 목적지 network IP의 prefix

Path Attributes: 목적지 IP prefix로 가기 위한 path 알려줌

BGP update는 incremental함 => 모두 보내는 게 아니라, 추가적으로 업데이트된 부분만을 보냄

 

- "AS-PATH": 목적지 subnet으로 가기 위한 AS number들의 list

advertise가 이웃 AS로 이루어질 때마다 자신의 AS number를 list 가장 앞에 붙임

ex. AS 500 입장에서, 목적지가 AS 100일 때는 AS 300->200->100 순서로 가기 때문에 180.10.0.0/16 300 200 100

목적지가 200일 때는 AS 300->200 순서로 가기 때문에 170.10.0.0/16 300 200

- "NEXT-HOP": next hop router가 이웃 AS에 있을 때, 구체적으로 어느 inter-AS router인지 특정

다른 AS와 연결된 link가 여러 개 있어 inter-AS-router가 여러 개일 수 있기 때문

 

BGP는 다양한 policy가 포함되도록 route advertise함

- import policy: 받은 advertisement를 AS 내 router들에게 알려줄 건지

* 자신의 AS로부터 나가는 outgoing traffic들이 거치는 AS를 통제 가능 => 보안상/가격상 문제 방지

- export policy: 어떤 path 정보를 알아도 이웃 AS에게 export 할 것인지

* incoming traffic 통제 가능 => 도움이 되는 traffic만 자신을 거칠 수 있게 함

** path 정보 알려주지 않음 => 이웃들은 그 path 정보 모르기 때문에 이웃들이 자신을 거칠 수 없음

 

 

예컨대 다음과 같은 상황에서

 

<policy1> "ISP들이 오직 customer network에게만 route traffic 정보 알려주고 싶을 때"

A는 B,C에게 목적지 A로 갈 수 있다고 advertise

=> B는 x에게 w로 가는 방법 알려주지만, C에게는 알려주지 않음

* x는 자신의 customer network이지만, C는 아니기 때문

=> C는 w로 갈 때 C->A->w

 

<policy2> "x는 provider network의 traffic이 자신을 지나는 것을 원하지 않을 때"

x는 B랑도, C랑도 연결되어 있지만, provider network의 traffic이 자신을 지나는 것을 원하지 않기 때문에

B에게는 C->x->B route가 있다는 사실을, C에게는 B->x->C route가 있다는 사실을 알리지 않는다.

 

BGP route selection

 

router들은 목적지 AS로 가는 route를 여러 개 배울 수 있다고 할 때

어느 route로 갈지 선택해야 한다.

선택 기준은 다음과 같고 번호가 작을수록 우선순위가 높다.

1. policy decision: 자신이 정한 policy 내용(비용/보안 등..)에 맞는 것을 선택

2. AS-PATH: AS-PATH list의 길이가 짧은 것 선택

3. NEXT-HOP: 가장 가까운 inter AS router 고름(hot potato routing)

4. 다른 기준(BGP ID 등..)

 

* hot potato routing: 2d는 X로 갈 수 있는 경로를 2a와 2c를 통해 두 개 얻게 되는데, 그중 cost가 가장 적은 2a를 거치는 route 선택

 

 

BGP path advertisement: example

 

(ex1)

AS2 안의 2c가 AS3의 3a로부터 X로의 경로(AS3, X) 받으면

AS2 policy에 의해 

- 2c가 AS2 전체에 알림

- 2a가 1c에게 (AS2, AS3, X) 알림

 

(ex2)

gateway router가 여러 개의 path 정보를 배울 수 있는 상황에서

1c가 2a와 3a로부터 route 정보를 받았고, AS2와 AS3 모두 policy상 괜찮은 AS라면,

더 짧은 AS-PATH를 가진 (AS3, X) 경로를 선택한다.

이때 AS1 내에서 X로 가려는 router들은 1c로부터 정보를 얻었기 때문에 1c(gateway)로 우선 보낸다.

 

 

정리하자면

Forwarding table에는 목적지 subnet prefix들에 대해 next hop 정보가 표시돼있어야 함

그러기 위해서는 intra-AS routing algorithm과 inter-AS routing algorithm이 모두 필요하다.

- 한 AS 내 gateway router로 가기 위해 => intra-AS

- 외부의 destination으로 가기 위해 => inter&intra-AS

 

Setting forwarding table by BGP, OSPF

 

(ex1)

<BGP:inter>

1a, 1b, 1d는 목적지 X로 가려면 1c를 통해 가야 한다는 것을 1c로부터 배움

=> <OSPF: intra>

- 1d: 1c로 가기 위해서 자신의 인터페이스 중 1로 내보냄

- 1a: 1c로 가기 위해서 1d를 거쳐야 하므로 자신의 인터페이스 2로 내보냄

 

 

 

(ex2)

<BGP:inter>

AS1의 gateway router 2a는 x로 가려면 AS3를 거쳐야 함을 배워 AS1 내 다른 router들에게 전달

=> <OSPF:intra>

- 1d: 1c로 가기 위해서 인터페이스 if0로 내보냄

 

 

(ex3)

1. router가 prefix를 알게 됨

=> BGP msg는 route정보(prefix&attributes) 포함 => "AS-PATH", "NEXT-HOP"

* prefix: 138.16.64/22

* AS-PATH: AS3 AS131 AS201 AS500 (목적지로 갈수록 앞에)

* NEXT-HOP: 201.44.13.125(3a)

 

2. 같은 목적지 prefix에 대한 route가 여러 개일 수 있음

* 1c가 3a로부터 받는 것

=> Prefix: 138.16.64/22; AS-PATH: AS3 AS131 AS201 AS500; NEXT-HOP: 201.44.13.125(3a)

* 1b가 2a로부터 받는 것

=> Prefix: 138.16.64/22; AS-PATH: AS2 AS17 AS500; NEXT-HOP: 202.44.12.12(2a)

 

3. 2에서 나온 여러 개의 route 중 최적의 BGP route 선택

(Policy->AS-PATH->NEXT-HOP-> ..)

2개 중 AS-PATH가 더 짧은 후자 선택

AS-PATH: AS2 AS17 AS500; NEXT-HOP: 202.43.12.12(2a)

AS2로 내보내려면 1b로 보내야 하므로 output port=4

 

 

왜 Intra-AS routing과 Inter-AS routing에 다른 프로토콜을 적용할까?

정답은, 두 가지가 있다.

 

A1: "Intra-AS routing에서는 performance가 중요하지만, Inter-AS routing에서는 policy가 중요하기 때문"

- Intra-AS routing

: 적은 resource로 빨리 전달하는 게 중요하기 때문에 performance 중요

: single admin이므로 policy 결정할 필요 없음(중요x)

 

- Inter-AS routing

: traffic이 어떻게 route되는지, 누가 route하는지 통제하므로 policy 중요

: performance는 중요x

 

A2: "scalability 때문"

hierarchical하지 않다면 routing table size도 커지고 update traffic도 너무 많아질 수 있음

=> hierarchical하게 Intra와 Inter에서 각각 다른 프로토콜 적용

 

 

두 개 사이에서 loop가 일어나면 split 어쩌구를 통해 해결 가능하지만 

세 개 이상일 경우 count to infinity 문제가 발생

=> BGP에서는 거치게 되는 list 전체가 나오기 때문에 AS-PATH에 자기 이름이 있으면,

자신이 반복적으로 호출되는 loop가 발생하고 있다고 알 수 있음

 

 

a. eBGP(4c를 통해 x로 가는 route "AS4, x" 알게 되기 때문)

b. iBGP(AS2에서 AS4로 가는 방법은 없으므로 AS3->AS4 route로 가는 수밖에)

c. eBGP(1c는 3a로부터 알게 됨)

d. iBGP

 

I1로 가려면, 1d->1a->1c 

I2로 가려면, 1d->1b->1a->1c

=> 더 짧은 경로인 I1 선택

 

 

(AS1->AS3->AS4)나 (AS1->AS2->AS4)는 AS-PATH가 같기 때문에 

AS1 내부에서 더 짧은 거리인 (1d->1a->1c) 선택

=> I1 선택

 

 

1b의 AS-PATH: (AS2 AS5 AS4 x)

 

1c의 AS-PATH: (AS3 AS4 x)