=== Border Gateway Protocols (BGP) ===

inter-domain routing에서 사용되는 BGP 에 대해서 알아보자

1. Flat vs. Hierarchical Networks

네트워크가 전체적으로 Flat 하기 보다는 계층적인 구조로 되어 있다.
• Flat
– No hierarchy
– Not scalable

• Hierarchical
– Network divided into “areas”
– Scalable

• Internet is hierarchical

Autonomous System(AS)

같은 라우팅 policy가 적용되는 라우터의 집합 혹은 망이다.
• Collection of networks with same routing policy
• Single routing protocol
• Single administrative control

Hierarchical Structure

• Tiers
– Tier 1 AS: global reachability
– Tier 2 AS: regional/country
– Tier 3 AS: local

AS들이 모두 연결되어 있는데 열결되어 있는 형태는 총 두가지가 존재한다.
• AS relationships
– provider/customer : 한쪽이 서비스를 제공해주는 형태
– peers : 동등한 수준의 망끼리 서로 연결되어 라우팅할 수 있도록 계약을 맺어놓은 것 이것을 peer 관계라고 이야기 한다.

Business Model

• Customer pays provider for service
• Peers: mutual cooperation
• Multi-homing
– An AS may have multiple providers

AS간의 계층이 다르다면 provider-customer관계이고 같은 관계라면 peer이라고 이야기 한다.
이때 customer가 여러 provider로 부터 패킷을 받는 형탤르 보고 multihoming이라고 부른다.

2. Routing

• Intra-domain (inside a single AS)
– RIP (Distance Vector)
– OSPF (Link State)

• RIP/OSPF do not scale well : 전세계에 대해서 RIP/OSPF를 쓰면 안되나? 하지만 scale 문제가 생긴다.
– Count-to-infinity problem (RIP) : Count-to-infinity 문제가 생길 수 있다.
– Routing information flooded to all nodes (OSPF) : 노드수가 너무 많아지면 flooding을 하는 packet이 많아져서 overhead가 커지는 문제가 생긴다.

• Inter-domain needs a different routing scheme
– BGP (Border Gateway Protocol) : 망과 망 사이를 연결해주는 것은 BGP 프로토콜을 사용하게 된다.

BGP

• Routing between "border" routers : border 라우터들간의 routing을 담당하는 프로토콜이다.
• Border routers
– Routers that have links to other AS : 다른 AS로 연결이 되어 있는 라우터들

• eBGP (E-BGP, external BGP) : 서로 다른 도메인의 border router간의 라우팅을 담당한다.
– Routing between border routers of different domains

• iBGP (I-BGP, internal BGP) : 같은 domain안에서(같은 AS) border router까지의 routing을 담당한다.
– Routing between border routers of the same domain

BGP routing

• Distance vector with paths (Path vector routing) : Distance vector(목적지, 거리 cost, path)

• BGP routing table

이것도 망이 너무 커지면 전달해줄것이 많아진다. 그래서 위의 테이블을 보면 똑같은 주소에 대해서 경로가 다른 것을 확인할 수 있다.

• BGP routers (also called BGP speakers) send route advertisements to other BGP routers : 다른 BGP 라우터에게 route advertisement(routing table같은거)을 전달해 주면된다.
– Same as distance vector routing

그러면 AS 400을 보면 180.10.0.0/16을 가기 위해서는 AS300->AS200->AS100으로 가게된다는 것을 알 수 있다.

• Using path information, loop is detected

나(AS500)로부터 목적지까지(AS100) 가는데 routing table안에 들어간 AS100이 들어간 것에 대해서는 AS100에게 바로 전달해주면 안된다. 왜냐하면 그것을 주었을 때 routing loop가 생길 수 있기 때문이다.

iBGP

• Same as eBGP : eBGP 와 동작은 비슷하다.
• Routes learned from eBGP can be advertised to iBGP neighbors
• Routes learned from iBGP neighbor cannot be advertised to other iBGP neighbors
– Avoid loops
– AS-path information not carried inside an AS

• All iBGP routers inside an AS must be fully connected : Border 라우터끼리는 직접 iBGP의 정보를 받아야 하지 다른 Border Router을 거치어 받아서는 안된다. 그래야만 라우팅 loop이 생기기 때문이다. 이것이 원칙이다.

• R3 can tell R1 and R2 routes from R4 : R3가 R4로 부터 받은 데이터를 R1, R2에게로 알려준다.
• R3 can tell R4 routes from R1 and R2 : R3가 R4쪽으로 R1, R2의 정보를 포함해서 보내준다. 이것은 eBGP의 일이다.
• R3 cannot tell R2 routes from R1 : R3가 R2에게 R1의 정보를 알려주지 못하게 하는 것이 iBGP가 하는 일이다.
– R2 must directly hear routes from R1 (not through R3) : 그래서 R1이 직접 R2에게 직접 알려주어어야 한다.
– iBGP routers must be fully connected : 그래서 이러한 것을 보고 fully connected라고 부른다.

3. Policies

• In BGP, shortest path is often not the best path : shortest path 보다는 다른 것이 보다 최우선 선택지가 될 수 있다.
– Money involved

• Path selected based on policies
– customer > peer > provider : path를 결정할때 이와 같은 순서로 보낼 수가 있다.

• Policies on transit traffic
– Transit traffic: traffic that does not go to my customers : 트래픽이 나의 customer쪽으로 가지 않는 traffic을 transit traffic이라고 부른다. 그래서 이 트래픽을 받아줄 것인지를 결정해야 한다.
– Providers accept transit traffic : provider가 transit traffic을 받는것이다.
– Customers and Peers do not accept transit traffic : Customer이나 peer은 transit traffic을 보통 받지 않는다.

• Other policies may apply

보통 정책에 의해서 라우팅이 결정된다.

Policies affect routing

• Green: valid routes
• Red: invalid routes
• Summary: traffics go up and then down

빨강생이 privider-customer관계이고 노란색은 peer-to-peer관계이다. 그래서 위와 같이 데이터를 전달하는 것은 valid한 route이다. 왜냐하면 provider로 보내서 peer에게 보내는 것이기 때문이다.

하지만 위와 같은 경로는 불가능하다.

위와 같은 라우팅역시 불가능하다.

이를 통해서 보면 어떤 경로는 허용되지 않는지 알 수 있게 된다.

Route advertisements

• To customer link : customer쪽으로는 모든 route에 대한 정보를 주어야 한다.
– Advertise all routes

• To provider link : provider쪽으로는 나의 router정보만 준다.
– Advertise customers only

• To peer link : customer관련 정보만 주는 거다.
– Advertise customers only

Local Preference

• Multi-homed AS : 하나의 customer가 여러개의 provider와 연련되어 있는 경우이다.
– Has multiple providers
– Preference on which provider to use
– Higher local preference value wins

위에서는 목적지와 값이 나오는데 값은 local preference이다. 선호도를 이야기 한다. 그래서 선호도가 높은쪽으로 트래픽을 보내게 된다.

Multi-Exit Discriminator (MED)

• AS201 wants traffic from AS200 to be directed to B rather than A
• B advertises smaller MED compared to A
• Smaller MED win

A,B모두 C와 연결되어 있는 Case이다. AS200에서 오는 패킷이 B로 왔으면 좋겠다고 하는 것이다. MED value가 있어서 이 것을 A,B 모두 C에 전달해 주는 것이다. 이때 전달은 smaller MED 쪽으로 보내게 된다.