[전공 시리즈] 4. 라우팅 프로토콜(Routing Protocol)

[전공 시리즈] 3. IP(Internet Protocol)

🔰서론

좋은 경로를 찾자!

라우팅 프로토콜은 좋은 경로를 찾는 프로토콜이다. 여기서 좋은 경로란, 빠르고 덜 혼잡한 최소 비용이 드는 경로를 말한다.
비용(cost)에는 두 가지 종류가 있다. 먼저 고정된 요소엔 link length, hop count, speed, BW(band width), propagation delay 등이 있다. 변할 수 있는 요소는 average traffic, buffer occupancy(queueing), processing delay, error 등이 있다.
어떻게 하면 적절한 경로를 찾을까?

🍎 그래프 표현
이번 챕터는 그래프 용어를 알아야 이해하기 쉽다.
그래프는 G = (V, E)로 표현할 수 있다. V는 vertex(node, point)의 집합을 의미하고, E는 edge(link)의 집합을 의미한다. 이번 챕터에서 노드는 라우터, 엣지는 인접한 라우터를 잇는 링크를 말한다.
x노드부터 y노드까지 링크의 비용(cost)은 c(x, y)로 표현한다.

---

🔰라우팅 알고리즘 분류

Centralized(global) vs Decentralized

Centralized(Global)	Decentralized
모든 노드가 전체 그래프와 링크 비용을 모두 알고 있다(knows complete topology). source부터 destination까지 모든 경로를 계산해서 모든 라우터에게 알린다. 단점은 복잡도가 높고, 한 지점에서 오류가 있을 경우 문제가 있다는 것이다(single point of failure). 예를 들어, link state 알고리즘이 있다.	각각의 노드는 오직 자신과 인접한 노드들과의 경로와 링크 비용만을 알고 있다. 각각의 라우터는 라우팅 테이블이 변하지 않을 때까지 서로의 이웃과 경로와 비용에 관한 정보를 계속해서 공유한다(iterative process). 단점은 정보 공유가 지연됨으로써 발생할 수 있는 부분 최적화(sub-optimality)와 convergence 시간이 오래 걸릴 수 있다는 것이다(count-to-infinity problem). 예를 들어, distance vector 알고리즘이 있다.

Static vs Dynamic

Static	Dynamic
경로가 거의 고정된 것처럼 느리게 변한다.	주기적으로 경로가 갱신되거나, 특정 링크의 비용 변화로 인해 경로가 빠르게 변하는 것을 말한다.

---

🔰Link State Routing

link state broadcast를 통해 모든 노드가 전체 네트워크 topology와 링크 코스트를 알고, 같은 정보를 가지게 된다.
Dijkstra 알고리즘을 이용해 source 노드로부터 다른 모든 노드들까지의 최소 비용 경로를 계산한다. E개의 링크와 V개의 노드가 있다고 했을 때, 인접 리스트(adjacency list)와 우선순위큐(priority queue)로 효율적으로 구현한다면 O(ElogV)의 시간 복잡도를 가진다. 일반적으로 O(V^2)이다.

🍎 Dijkstra's algorithm
1. 초기화 단계
- V = {u}, u는 source 노드
- 모든 다른 노드 v에 대해 u와 v가 인접한 경우 d(v) = c(u, v), 그렇지 않으면 d(v) = ∞
2. 업데이트 단계
- V 집합에 속하지 않은 모든 노드 v에 대해 d(v)가 가장 작은 노드 w를 선택한다.
- V 집합의 원소로 w를 추가한다.
- w 노드와 인접한 노드이면서 V 집합에 속하지 않은 모든 노드 v의 d(v)를 다음과 같이 업데이트한다.
      d(v) = min(d(v), d(w) + c(w, v))
      값이 바뀐 경우, p(v) = w
      p(v)는 source 노드로부터 v까지 경로에서 v 바로 전에 거쳐온 노드를 말한다.
- 위 과정을 반복한다.
- 그래프의 모든 노드가 V에 속하면 반복을 멈춘다.

Dijkstra 알고리즘 적용 예시

source 노드로부터 다른 모든 노드까지 최단 거리를 구한 후, 이로부터 source 노드의 forwarding table을 얻을 수 있다. forwarding table이란, 현재 노드에서 특정 목적지까지 가기 위해 다음 홉이 무엇인지를 저장한 테이블을 말한다.

forwarding table 예시

oscillations가 발생할 수 있다. 예를 들어 링크 코스트가 해당 링크의 트래픽과 같을 때 발생한다.

oscillations 예시

---

🔰Distance Vector Routing

시간에 따라 각각의 노드들은 자신의 distance vector를 인접 노드에게 알린다.
인접한 링크 코스트가 바뀌었거나 새로운 ditance vector를 받았을 경우, Bellman-Ford 알고리즘을 이용해서 자신의 distance vector를 업데이트한다.

🍎 Bellman-Ford algorithm
x와 인접한 모든 노드 v에 대해, d[x][y] = min_v(c(x, v) + d[v][y])
d[x][y]는 x 노드부터 y노드까지의 최단 거리를 의미한다.
즉, d[x]는 x 노드의 distance vector다. d[x] = [d[x][y]: y ∈ V]

자신의 distance vector가 바뀌었을 경우, 새로운 distance vector를 인접 노드에 알린다.
distance vector가 수렴할 때까지 위 과정을 반복한다.

Bellman-Ford 적용 예시

결과적으로 distance table(distance vector)를 구하고, 이로부터 특정 목적지로 가기위한 다음 홉 노드가 무엇인지를 저장한 routing table을 얻는다.
보면 알겠지만, distance vector 라우팅은 iterative, asynchronous, distributed 특징이 있다. 변화가 있을 때까지 기다려야 하고 변화가 있으면 다시 계산해야 한다는 점에서 iterative, asynchronous하고, 각각의 노드가 distance vector가 바뀌었을 때 이웃에게만 알려서 업데이트된다는 점에서(모두가 업데이트되지 않는다.) distributed하다.

🍎 왜 synchronous하도록 구현하지 않는 걸까?
만약 synchronous 하다면, 각각의 노드가 distance vector를 업데이트하는 것이 parallel하고 '동시에(simultaneously)' 계산된다. 이 방식의 장점은 (노드 개수) - 1 번 안에 업데이트 과정이 끝난다는 것이다. 단점은 모든 노드의 업데이트 타이밍을 어떻게 동기화할 것인지, 업데이트 과정 중에 링크의 상태가 변하면 어떻게 중단하고 다시 업데이트 과정을 재개할 것인지를 정하는 것이 어렵다는 것이다.
asynchronous 하게 구현할 경우, 각 노드를 동기화할 필요가 없다. 그리고 일반적인 Bellman-Ford 알고리즘과 다르게 초기화 과정(다른 노드까지 거리를 ∞로 초기화)이 필요 없다. 또한, 재시작할 필요도 없다. 언젠가 Bellman-Ford 알고리즘을 실행하고, 그 결과를 인접 노드들에 알린다는 것만 보장하면 된다.

또 다른 특징은 좋은 변화는 빠르게 퍼지는데, 나쁜 변화는 느리게 퍼진다는 것이다(good new travels fast, bad news travels slow). 여기서 좋은 변화란 인접한 링크 코스트가 줄어든 것이고, 나쁜 변화는 링크 코스트가 늘어난 것을 말한다. 이런 특징으로 인해 count to infinity 문제가 발생할 수 있다.

count to infinity problem

극단적으로 한 링크가 끊겼을 경우를 생각해보자. 즉, 링크 코스트가 ∞으로 바뀐 것이다.

count to infinity problem 예시

위 그림의 상황이 계속된다면 distance vector가 수렴하지 않을 것이다. 이 상황에서 벗어나기 위해서는 최대 비용을 설정할 필요가 있다.
count to infinity 문제를 해결할 방법은 poisoned reverse가 있다. 만약 c 노드가 a 노드로 가기 위해 b 노드를 거쳐야 한다면, c 노드가 b 노드에게 "c가 a 노드까지 가는 길은 무한대 비용이라 b는 c를 통해 a로 갈 수 없다."라고 말하는 것이다. 그러나 이 방법도 노드의 개수가 3개 초과라면 문제를 해결할 수 없다.

---

🔰라우팅 알고리즘 비교

\	message complexity	speed of convergence	robustness(router malfunction)
link state routing	전체 그래프를 파악해야하기 때문에 O(VE)로 일반적으로 복잡도가 더 높다.	O(VE)의 메시지를 O(V^2) 복잡도의 알고리즘이 다룬다. 더 빠른 편이다. oscillations이 발생할 수 있다.	잘못된 링크 코스트를 알린다. 각각의 노드들은 자신의 테이블만 이용하기 때문에 전체 네트워크엔 큰 영향을 미치지 않는다.
distance vector routing	인접한 노드끼리만 정보를 주고받기 때문에 일반적으로 복잡도가 낮다. convergence 시간에 따라 다르다.	convergence 시간이 매번 다르다.  count to infinity 문제가 발생할 수 있다.	잘못된 경로(path) 코스트를 알린다. 각각의 노드들은 다른 노드의 테이블도 이용하기때문에 네트워크 전체에 오류가 영향을 미칠 수 있다.

---

🔰인터넷 라우팅 구조

앞선 챕터들에서 봤듯이 라우팅을 할 땐 네트워크를 먼저 찾고, 호스트를 찾는다. 이 라우팅의 단위가 되는 네트워크를 AS(Autonomous System)이라 한다.

인터넷 라우팅 2층 구조

인터넷 라우팅은 Intra-AS routing과 Inter-AS routing의 2층 구조로 되어 있다.

Intra-AS routing	Inter-AS routing
같은 AS 안에서 호스트 또는 라우터 간의 라우팅을 말한다. 같은 AS 안의 모든 라우터들은 같은 intra-domain 라우팅 프로토콜을 사용한다. 서로 다른 AS에 있는 라우터들은 서로 다른 intra-domain 라우팅 프로토콜을 사용할 수 있다. gateway router는 한 AS의 끝(edge)에 있는 라우터를 말하며, 다른 AS와 연결된 링크를 가지고 있다. IGP(interior gateway protocols)라고도 한다. 대표적인 프로토콜로 link state 알고리즘을 사용하는 OSPF가 있다. 성능(performance - least cost)에 따라 라우팅이 결정된다.	서로 다른 AS 간의 라우팅을 말한다. gateway router를 통해 inter-domain 라우팅 프로토콜을 수행한다. 다른 AS로 패킷을 보내기 위해 어떤 gateway router로 보낼지를 결정하고 현재 AS 내부의 모든 라우터에게 알린다. 프로토콜로 BGP가 있다. 이해관계에 의해 성능보다 policy에 의존해서 라우팅이 결정된다.

Intra-AS routing과 Inter-AS routing 모두 forwarding table을 만든다.
2층 구조로 나눠져 있는 이유는 scalability와 policy 때문이다. 인터넷은 거대한 규모를 가지고 있어 라우팅 테이블에 모든 목적지를 저장할 수 없다. 또한 네트워크(AS) 내부 topology가 변한다면 라우팅 계산을 감당하기 어렵다. 그리고 인터넷은 네트워크로 이뤄져 있는데, 각각의 네트워크 관리자들은 비용과 관련해서 자신의 네트워크 라우팅을 유리하게 컨트롤하고 싶어 한다. 그렇기 때문에 라우팅은 2층 구조로 나눠져 있다.

---

🔰정리

• 라우팅 프로토콜이란, 최적의 경로를 찾아 라우팅을 결정하는 프로토콜이다.
• 최단 경로를 찾는 라우팅 알고리즘에는 link state 알고리즘과 distance vector 알고리즘이 있다.
• link state 알고리즘은 전체 네트워크 그래프를 파악하여 dijkstra 알고리즘을 적용해 라우팅 테이블을 얻는다.
• distance vector 알고리즘은 인접 노드의 정보를 이용해 Bellman-Ford 알고리즘을 적용하여 라우팅 테이블을 얻는다.
• 인터넷 라우팅은 scalability와 policy 문제로 인해 2층 구조다. Intra-AS routing과 Inter-AS routing으로 나뉜다.