Network layer: control plane

Routing protocols - link state

라우팅 프로토콜의 목표는 라우터들 사이에서 가장 '좋은 경로'를 찾는 것이다. 여기서 '좋은' 경로 란 적은 비용, 속도, 그리고 낮은 혼잡도를 의미한다. 

 이를 찾기 위해 각각의 라우터들을 노드로 먼저 그래프 추상화를 한다. 

그래프 추상화

이 중 이 글에서는 link state에서만 다룰 예정이다.

link state란, 모든 라우터들이 각자의 상태(state)를 공유하여 다익스트라 알고리즘을 통해 최적의 경로를 구하는 방법이다.

다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최소 경로를 계산하는 알고리즘으로 포워딩 테이블을 만드는데 사용된다.

Dijkstra's link-state routing algorithm

노테이션은 다음과 같다.

C는 x에서 y로 가는 비용을 뜻하며 직접 연결되어 있지 않으면 무한대 값을 갖는다.

D(v)는 특정 점에서 v로 가는 '현재'의 최소 비용을 뜻한다.

p(v)는 특정 점에서 v로 가는 경로의 바로 직전 노드이다. 이는 특정 노드에서 v까지의 경로를 알기 위해 필요하다.

N'은 최단 경로를 찾은 노드들의 집합이다.

다익스트라 알고리즘

다익스트라 알고리즘을 좀 더 자세히 살펴보자.

먼저 초기상태이다.

N'에는 u만 기술되어있다. 

그 다음 모든 v에 대하여 만약 v가 u에 인접해 있다면 v까지의 현재 경로 비용을 설정하고 그 외에는 무한대로 설정한다.

 

다음은 반복문이다. N'에 속해 있지 않은 w에 대해 D(w)가 최소인 경로 비용을 찾고, 이를 N'에 추가한다.

그리고 나서 N'에 속해 있지 않지만 v에 인접한 w에 대해 현재의 v까지의 최소비용 D(v)와 w를 거쳐 v로 가는 D(w)+ Cwv의 비용을 비교하여 더 작은 값을 N'에 update 해준다.

모든 노드에 대해 위 작업이 끝나면 반복문을 종료한다.

 

예시를 보자.

다익스트라 알고리즘 예시

 

알고리즘을 완료하면 이에 대한 포워딩 테이블이 생성된다.

 

포워딩 테이블

v만 u에서 직접 가고, 나머지 노드들은 전부 x를 경유한다.

 

다음 예제는 직접 풀어보자.

마찬가지로 u에서 출발한다고 가정한다.

 

다익스트라 알고리즘의 복잡도를 보자.

먼저 시간복잡도이다.

n개의 노드에 대해 모든 노드 중 하나를 골라 나머지 노드들과 계속 비교해야 하므로 시간복잡도는 O(n^2)라고 볼 수 있다.

이때 우선순위 큐를 사용하여 시간복잡도를 O(nlogn)까지 줄일 수 있다. (민힙?)

 

다음으로 공간복잡도이다. (message complexity)

link state는 기본적으로 모든 노드가 서로의 상태(state = msg)를 공유해야 하므로 1개의 노드가 n-1개의 링크가 필요할 것이고

이 작업을 모든 노드 n이 반복할 것이므로 n(n-1) 로 공간복잡도는 O(n^2)가 된다.

공간 복잡도 n^2

 

지금까지 배운 라우팅 프로토콜은 이상적인 상황에서의 설계이다. 하지만 실제는 다르다.

우선 노드 scale이 billion 단위라서 각 노드에 state와 라우팅 테이블을 저장할 수 없다. 이는 계산에 있어 복잡성이 너무 커진다.

또한 인터넷은 단일 네트워크가 아니다. 

>>따라서 인터넷 라우팅은 확장성(scalability)과 분산된 관리를 동시에 해야 한다.

 

여기서 라우터는 '영역' 단위로 관리를 하게 되는데 이를 'autonomous systems'라고 칭한다.

autonomous systems(AS)

라우터가 관리 가능한 주체적인 영역으로 하나의 단위이다.

여기서 AS 내부를 intra-AS, AS끼리를 inter-AS라고 한다.

Autonomous Systems(AS)

intra-AS

intra-AS는 AS 안에서의 라우팅을 말하는데 동일한 내부이기에 동일한 도메인 프로토콜을 사용한다.

하나의 AS 내에서는 다른 AS와 다른 프로토콜을 사용해도 된다.

이 때 서로 다른 프로토콜을 쓰는 AS끼리 통신하기 위해 서로 AS의 edge에 gateway router라는 것을 설정하여 통신한다.

inter-AS

AS 끼리의 라우팅을 뜻한다. AS의 edge인 gateway가 inter-domain routing을 수행한다.

 

다음과 같이 포워딩 테이블이 형성되는데 AS 내부에서의 목적지는 intra-AS routing 프로토콜이 AS 외부의 목적지는 inter-AS routing 프로토콜이 생성한다.

라우팅 프로토콜

intra-AS에는 다음과 같은 라우팅 프로토콜이 있다.

RIP - 현재 사용되지 않음

EIGRP - Cisco에서 만든 라우팅 프로토콜로 DV 방식에서 쓰인다.

OSPF(Open Shortest Path First) - 다익스트라 알고리즘을 사용하는 link state 방식의 프로토콜. IS-IS 프로토콜이 본질적으로 OSPF와 같다.

OSPF routing

전통적인 link-state 방식을 따른다.

각각의 라우터가 broadcast 방식으로 자신의 state를 flooding한다.(broadcasting 한다고 이해하면 됨)

local area, backbone 이라고 하는 두 계층으로 나뉜다.

inter-AS routing:BGP

intra-AS에서는 사용하지만 inter-AS에서는 더 이상 LS(link state)나 DV(distance vector) 방식은 잘 사용하지 않는다.

대신 새로운 알고리즘으로 de facto inter-domain 라우팅 프로토콜을 사용하는 BGP(Border Gateway Protocol)을 사용한다.

작동 방식은 단순하다. 한 subnet이 본인의 존재와 리치가 어디까지 닿는지의 정보를 주변에 쏜다.

"I'm here, here is who I can reach and how"

크게 두 가지가 있다.

eBGP: 이웃 AS들로부터 subnet이 도착 가능한 목적지 주소들을 받는 것

iBGP: AS 내부 라우터들에게 위에서 받은 정보들을 전파하는 것. 이 때, intra-AS 프로토콜을 사용하지 않는 이유는 intra-AS는

단순히 최적의 경로를 찾지만, iBGP는 policy-based routing이기 때문이다. 즉, 특정 정책을 넣어 경로가 최적이 아니여도 특정

경로를 경유하도록 할 수 있다.

ABC는 ISP, xwy는 고객이라고 하자.

이 때 x는 B와 C 두 제공자를 사용하고 있다. (dual-homed 라고 함)

B와 C가 서로가 아닌 오로지 customer network로의 경로만을 원한다면(어른들의 사정, real world policy라고 하자.)

B나 C가 서로를 통하지 않고 바로 x로 통신되게끔 설정할 수 있다.

 

ICMP(Internet Control Message Protocol)

host와 router 사이에 네트워크 레벨을 공유하는 프로토콜이다.