[Ch5] Hierarchical routing, RIP, OSPF, BGP

Hierarchical Routing

Autonomous Systems (AS)

Autonomous Systems (1 AS ~= 1 ISP ~= domain)

• collection of networks with same routing policy, under single ownership
• identified by a unique 32-bit integer AS number (ASN)
  • ASN is managed by the Internet Assigned Numbers Authority (IANA)
• routers in the same AS run same routing protocol: intra-AS routing protocol (OSPF, RIP..)
• Gateway router: locates at "edge" of an AS and has a link to router in another AS
  • gateway routers run inter-AS routing protocol (BGP..)
  • ASBR(Autonomous System Border Router)
  • gateway routers perform IGP + EGP
• Trasnsit AS: 여러 AS를 경유하는 트래픽들이 통과
• Stub AS: 하나의 ISP하고만 연결되어 있으며, 해당 AS로 도착 혹은 출발하는 트래픽만 존재 (departing & arriving only)

 

하나의 AS에서 어떤 라우터가 IGP 라우팅 프로토콜로 OSPF를 사용한다면, 해당 AS 안의 나머지 모든 라우터들도 OSPF를 사용해야 한다.

Internet approach to scalable routing

Intra-AS Routing (IGP)

• Interior Gateway Protocol (IGP)
• routing among hosts, routers in same AS
  • all routers in AS must run same intra-domain protocol
• RIP, OSPF, IS-IS, IGRP ...

Inter-AS Routing (EGP)

• Exterior Gateway Protocol (EGP)
• routing among AS'es

Interconnected ASes

• forwarding table configured by both Intra-AS(IGP) and Inter-AS(EGP) routing algorithm
• inter-AS & intra-AS determine entries for external destinations

각 라우터가 다른 AS로 가는 경로를 설정하기 위해서는 intra-AS(IGP)와 inter-AS(EGP) 모두 필요

---

Intra-AS Routing

RIP(Routing Information Protocol)

RIP(Routing Information Protocol)

• L5 protocol: RIP routing tables managed by application-level process called "routed"
• advertisements sent in UDP packets, periodically repeated
• Distance-Vector (DV) algorithm (B-F algorithm)
  • Metric = hop counter(max = 15 hops), each link has cost
  • routes with a hop count > 15 are unreachable
  • DVs (a.k.a. advertisement) are exchanged with neighbors every 30 sec
  • each advertisement contains up to 25 destination subnets (IP address)
• Slow convergence problem: Count-to-Infinity -> Solution: Split horizons, Split horizons with poison reverse

RIP에서 DV 테이블의 엔트리 중 특정 destination subnet으로 가기 위한 output port가 0인 엔트리의 정보는 output port 0에 연결된 이웃 라우터에게는 전달하지 않아야 그 두 라우터 간의 count-to-infinity를 막을 수 있다.

 

OSPF(Open Shortest Path First)

OSPF(Open Shortest Path First)

• Link State (LS) algorithm
  • Metric = based on type of service (BW, minimum delay, throughput, reliability, etc.)
  • every router in an AS has the same global topology map
  • computing uses Dijkstra's algorithm
• Two-level hierarchy
  • AS is divided into areas: local areas, one backbone area
  • LS advertisement (LSA) flooded to only in area: carried directly over IP

• ABR(Area Border Router): summarize, advertise to other ABR
• Backbone router: run OSPF routing limited to backbone (using DV)
• ASBR(AS Boundary Router): connect to other AS's (OSPF + BGP)
• Backbone area: DV 사용, count-to-infinity 발생 가능 -> loop-free topology should be guaranteed -> vulnerable to routing loop

• OSPF를 운영하는 AS에서 backbone area에 해당하는 area 0는 DV를 사용하므로 count-to-infinity가 발생할 수 있다. 따라서 area 0에서 loop-free topology를 유지하는 것이 망 운영자가 할 일이다.
• area 간의 통신은 반드시 area 0 안의 loop-free topology로 구성된 backbone router를 통해서 이루어진다.
• 인접하여 연결된 서로 다른 ISP가 동일한 OSPF를 사용해도, 각 ISP에서 사용하는 policy는 독립적이기 때문에 같은 파라미터를 link cost로 사용할 필요는 없다.

RIP vs. OSPF

OSPF	RIP	BGP
	UDP	TCP
IP

• Max. Hop Count: 망의 크기 - RIP = 15 < OSPF = no limit
• Convergence: 계산 속도 - RIP = slow < OSPF = fast
• Routing updates: RIP = full table every 30 sec / OSPF = LSA generated upon any routing change
• BW usage: RIP = use more BW per link / OSPF = use less BW per link
• Areas/Boundaries: 계층 - RIP = No / OSPF = Yes

• RIP는 path selection 계산 시 hop count를 사용하나, OSPF는 다양한 파라미터를 이용할 수 있다.
• path가 여러 개인 경우 RIP는 단 하나의 경로만 찾을 수 있으나 OSPF는 다양한 경로를 찾는 것이 가능하다.

---

BGP

BGP (Border Gateway Protocol)

Inter-AS routing protocol

• 여러 ISP를 거쳐 가는 경로 계산
• EGP와 BGP가 있는데 현재는 인터넷에 연결된 모든 라우터들 BGP 이용

BGP (Border Gateway Protocol)

• inter-AS routing or inter-domain routing protocol
  • widely used for Internet backbone (core NW)
• policy-based routing
  • determine good routes based on policy and allow AS to control traffic flow
• path vector routing protocol: advertise a list of the full path of ASNs to reach a destination subnet
  • to avoid a routing loop
• Classless Inter Domain Routing (CIDR)
• Incremental updates: after establishing a TCP connection and exchanging all candidate BGP routes, only the change or difference from the previious updates are advertised

 

BGP: Peering

• Peering: exchanging routing information and traffic for no fee
• BGP Peers (neighbors): two routers which exchange BGP msgs
• External BGP Peering (eBGP) btw different AS's
  • eBGP peers have the different ASNs
  • eBGP implements routing policy
  • they should be directly connected (physically connected)
• Internal BGP Peering (iBGP) within the same AS
  • iBGP peers have the same ASN
  • they must be fully meshed (not necessarily directly connected) - iBGP peers must reachable usually by using an IGP
• gateway routers run both eBGP and iBGP protocols

 

BGP: session

• two BGP routers(peers) exchange BGP msgs over semi-permanent TCP connection
  • advertising paths to different dest. network prefixes (BGP = path vector protocol)
• eBGP: learns subnet reachability information from neighboring ASs
• iBGP: propagates prefixed learned frou outside the AS to all AS-internal routers
  • iBGP doesn't pass on prefixes learned from other iBGP
• determine good routes to other networks based on reachability information and policy

• ASBR은 다른 AS에 속한 라우터와는 eBGP TCP session을 맺고, 같은 AS에 속한 라우터들과는 iBGP TCP session을 맺는다.
• ASBR 라우터는 자신이 속한 AS 안의 모든 라우터에게 point-to-point TCP 연결을 맺고 외부 라우팅 정보를 직접 전달한다.
• ASBR A에서 동작하는 BGP가 eBGP로 B로부터 learn한 라우팅 정보를 내 AS 안의 라우터들에게 advertise 한다는 것은, 향후 해당 라우팅 정보에 포함된 subnet으로 향하는(destined) 패킷이 A에게 오면 B로 forward 해주겠다는 의미이다.

 

BGP: messages

• OPEN: open TCP connection to remote BGP peer and authenticates sending BGP peer
  • ASN 주고 받음
• UPDATE: advertise new path (or withdraws old)
• KEEPALIVE: keeps connection alive in absense of UPDATEs; also ACKs OPEN request
  • TCP 세션 유지
• NOTIFICATION: reports errors in previous msgs; close connection
• Marker: BGP 시작을 구별하기 위해 두 BGP 프로세스 사이에 약속한 특정 pattern으로 BGP msg 시작할 때 들어감, BGP가 L4 프로토콜로 TCP를 사용하며 TCP는 byte-stream 방식으로 데이터를 전송하기 때문에 필요

BGP: routes

• advertise prefix includes BGP path attributes
• BGP route = (dest. prefix + path. attributes to the dest.)
• BGP Path attributes
  • AS-PATH: list of ASN to reach a dest. subnet
  • NEXT-HOP: IP address of eBGP peer of next-hop AS
• if eBGP receives route information whose AS-PATH includes my own ASN, drop it to avoid loop

BGP: policy-based routing

• import policy: gateway receiving route advertisement using import policy to accept/decline path
  • controlling outgoing traffic
  • 외부 AS에서 얻은 라우터 정보를 내부 AS로 전달 여부 결정 (advertise)
• export policy: determine wheter to advertise path to other neighboring ASes
  • controlling incoming traffic
  • 내부 AS(혹은 다른 AS)의 라우터 정보를 이웃 AS에 알려줄지 말지 결정 (propagate)

• ASBR은 다른 ASBR이 알려준 모든 inter-AS 경로 정보를 iBGP 세션으로 전달한다? (X) 👉 policy에 기반하여 선택된 경로 정보만 전달
• BGP는 ISP의 망 운영 독립성을 보장하면서 DV의 단점인 loop 생성을 막기 위해 path vector를 사용하여 loop를 포함한 경로를 구별한다.

BGP Route Selction

Hot Potato Routing

• 외부 AS에 연결된 destination으로 가는 경로 중 나의 AS를 가장 빨리 벗어나는 즉, 나의 AS 내부 비용이 가장 적은 라우트를 선택하는 알고리즘
• choose local gateway that has least intra-domain cost
• don't worry about inter-domain cost

BGP route selection

• router may learn about more than one route to destination AS, selects route based on
  1. policy-based routing
  2. shortest AS-PATH rather than the number of router hops
  3. closest NEXT-HOP router: hot potato routing
  4. additional criteria (BGP ID)

---

Summary

How different Intra-, Inter-AS routing?

• Policy
  • inter-AS: admin wants control over how its traffic routed, who routes through its network
  • intra-AS: single admin, so no policy decisions needed
• scale
  • hierarchical routing saves table size, reduced update traffic
• performance
  • intra-AS: can focus on performance (OSPF, RIP)
  • inter-AS: policy may dominate over performance (BGP)