라우팅 알고리즘과 프로토콜

본 포스팅은 이석복 교수님의 네트워크 수업과 성공과 실패를 결정하는 상위 1%의 네트워크 원리를 참고하여 작성한 포스팅입니다.

 

라우팅 알고리즘이란?

 

라우팅 알고리즘이란 출발 라우터에서 도착 라우터로 패킷을 보낼 때 최적의 비용으로 보낼 수 있는 라우팅 경로를 결정하는 알고리즘입니다. 네트워크를 아래 그림의 그래프로 추상화한다고 생각해볼 수 있습니다.

 

 

위 그림의 예에서, u라는 라우터에서 z라는 라우터까지 가는 경로를 결정해야하는 문제가 발생합니다. 이를 결정하는 알고리즘을 구체화하기 전에, 알고리즘의 분류를 먼저 생각해보겠습니다.

 

Q. Global(전역적인 공통의 정보를 이용) 알고리즘인가? 혹은 decentralized(각 지역의 정보를 종합) 알고리즘인가?

 

Global

• 모든 라우터가 전체 라우터의 topology와 비용 정보를 아는 상태
• Link State 알고리즘이 이에 해당됩니다.

Decentralized

• 라우터는 인접 라우터의 비용 정보만을 알고, 각 라우터는 이 정보를 인접 라우터에게 전파합니다.
• Distance Vector 알고리즘이 해당됩니다.

 

Link-State Routing Algorithm

 

Link-state 알고리즘은 네트워크의 topology를 모든 노드가 알고 있는 상황에서 적용할 수 있는 알고리즘입니다.

크게 아래 step으로 이루어진다고 볼 수 있습니다.

 

1.  각 노드는 자신의 인접 라우트에 대한 연결 정보를 broad-casting하여 전역으로 알립니다.
2.  각 노드는 broad-casting된 정보를 종합하여 네트워크의 topology를 구성합니다.
3.  각 노드는 다익스트라 알고리즘을 이용하여 최단 비용 경로를 찾아 라우팅 테이블을 완성합니다.

예시로 아래와 같은 그래프를 생각해보겠습니다.

 

 

Link-state 알고리즘은 아래와 같은 정보를 각 라우터가 broad-casting을 하여 모든 라우터가 위 예시의 그래프 정보를 인지한 상태가 됩니다. 다익스트라 알고리즘은 하나의 노드에서 다른 모든 노드로 가는 최단 경로를 얻을 수 있는 알고리즘입니다. 다익스트라 알고리즘에 대한 자세한 설명은 생략하겠습니다. 그리고 각 노드는 다익스트라 알고리즘으로 아래 그림의 과정을 거쳐 최단 비용의 라우팅 경로를 얻을 수 있습니다.

 

 

Link-state 방식의 문제점은 oscilations 문제가 발생할 수 있다는 것입니다. oscilation 문제란, 만약의 아래의 그림과 같은 토폴로지에서 각 연결 노드의 비용이 트래픽이라고 생각해보겠습니다. 트래픽은 그 경로를 많이 이용할수록 높아지므로 동적으로 변하는 값입니다. 그렇다면 아래 그림처럼 A 경로와 B 경로가 있다고 생각해보겠습니다.  A 경로를 이용하게 되면 A 경로에 트래픽이 몰리므로, 그래프를 갱신했을 때 B 경로를 이용하는 것이 최단 경로로 갱신되게 됩니다. 그리고 B 경로를 이용하면 다시 B 경로에 트래픽이 몰리므로 다음 갱신 때는 A 경로가 다시 최단 거리가 될 것입니다. 이러한 경로의 변경이 무한히 반복되는 형태가 oscilation 문제입니다.

 

 

Distance Vector Routing Algorithm

Distance Vector 알고리즘은 Bellman-Ford equation을 이용하는 방법입니다. 

 

위 예시에서, u노드에서 z노드로 가는 최단 거리는, u와 연결된 임의의 노드 a로 향하는 비용 c(u,a)와 노드 a에서 z로 향하는 최단 비용의 합 중 최소 값이 될 것입니다. 각 노드는 인접 노드에 대한 비용을 알고 있기 때문에 c(u,a)는 알고 있지만, 후자는 알지 못합니다. 이를 재귀적으로 반복하면서 후자의 값을 서로에게 전달해주는 알고리즘이 Distance Vector 알고리즘입니다.

 

각 노드 입장에서 흐름을 설명하면 아래와 같습니다.

 

1. 각 노드의 local link 비용이나 인접 노드로부터의 Distance Vector 정보가 변경될 때까지 기다립니다.
2. 변경된 정보를 받으면 재계산합니다.
3. DV가 만약 변경된다면, 인접 노드에게 이를 알려줍니다.

 

Distance Vector 알고리즘의 특징은, 재귀적으로, 비동기적으로 라우터 간 비용 정보의 교환이 발생한다는 것입니다. 그리고, 각 노드는 인접 노드에게만 DV가 변경될 때에만 정보를 알려주기 때문에 분산되어있습니다.

 

 

위 그림의 예시에서는, 시간의 변화에 따라 노드 간 DV 정보를 교환하며 모든 노드가 더 이상 업데이트되지 않고 수렴하는 지점까지 반복합니다. 

 

Distance Vector 알고리즘 : 링크 비용 변경 문제

DV 알고리즘에서 수렴 이후에 링크 비용이 변경되는 경우를 생각해보겠습니다.

 

 

알고리즘에서 링크 비용이 변경되는 두 가지 경우를 가정합니다.

두 경우 모두 동일하게 아래 순서에 따라 갱신이 발생합니다.

 

1. 노드는 local link 비용 변경을 감지합니다.
2. 라우팅 정보와 DV 정보를 갱신합니다.
3. DV 정보가 변경되었다면 이웃 노드에게 알립니다.

 

이 때, 링크의 비용이 낮아지는 (a)의 경우, 네트워크 전체에 빠르게 전파되지만, 비용이 높아지는 (b)의 경우는 매우 느리게 전파되는 count-to-inifinity 문제가 발생합니다. 이를 "good news travels fast, but bad news travels slow"라고 합니다.

왜 이런 현상이 발생하는지 살펴보겠습니다.

 

위의 예시에서는, 직접 계산해보면 44번의 iteration에 걸쳐 최종 결과에 수렴하게 됩니다. 이러한 현상이 발생하는 이유는 만약 최단 거리가 상대 경로를 다시 거쳐야하는 경우에, 서로 노드에게 DV를 알려줄 때, 상대 노드에게 상대 노드를 참조하는 최단 경로를 알려주기 때문에 갱신이 느리게 발생하는 문제입니다. Poisoned Reverse라고도 하는데요, 이를 해결하기 위해서는 DV를 알려줄 때 만약 상대 노드를 참조하는 최단 거리인 경우 이를 무한대로 설정하여 알려주는 방법입니다.

 

인터넷에서 라우팅

 

위에서 라우팅 알고리즘을 알아보았는데, 실제 네트워크에서 각 라우터가 모든 end-to-end 경우에 대해서 라우팅 정보를 가지고 있을 수 있을까요?

 

 

아마 불가능할 것입니다. 실제로 네트워크는 계층적 구조로 이루어져있습니다. 그리고 그 계층적 구조의 단위를 AS라고 합니다.

 

AS(Autonomous System)

AS란, 하나의 네트워크에 속하는 라우터들의 집합을 AS(Autonomous System)이라고 합니다. AS라고 부르는 이유는, 하나의 네트워크 내에서 라우터 간 라우팅 알고리즘을 자율적으로 정할 수 있는 시스템의 단위이기 때문입니다. 예를 들어서 라우터를 100개정도 가지고 있는 권역이라고 했을 때, 그 네트워크의 주인은 자유롭게 내부 라우터 간 통신 알고리즘을 선택할 수 있을 것입니다. 즉, 위에서 언급했던 라우팅 알고리즘이 적용된 프로토콜을 자율적으로 선택하여 사용할 수 있습니다. 위의 Link-state 알고리즘에 해당하는 프로토콜이 RIP, 그리고 Distance Vector에 해당하는 프로토콜이 OSPF입니다. 

 

그렇지만 AS들 간의 라우팅 프로토콜은 어떻게 정할 수 있을까요? 이는 조금 더 어려운 문제입니다. 이때까지 배웠던 라우팅 알고리즘이 비용을 최소화하는데 목적을 두었지만, 큰 규모의 네트워크에서는 각 네트워크의 관리자가 네트워크 패킷의 전송 경로를 컨트롤하고 싶을 수 있습니다. 예를들어 우리나라에서 북한을 거쳐서 패킷을 전송하기 보다는 경로가 더 멀더라도 다른 나라를 거쳐서 전송하는 경우가 있을 수 있겠습니다. 이런 정치적, 경제적 고려사항을 반영한 프로토콜이 바로 BGP 프로토콜입니다.

 

BGP 프로토콜(Border Gateway Protocol)

 

 

BGP 프로토콜의 가장 큰 특징은 Policy-based 프로토콜이라는 것입니다. 네트워크를 위와 같은 계층 관계를 이루는 AS의 집합으로 보고, Peer, Customer, Provider의 관계를 정의합니다. 이러한 관계의 경제적, 정치적 논리에 따라 원하는 루트를 선택할 수 있는 프로토콜이 BGP 프로토콜이라고 할 수 있습니다.

 

예를 들면,  아래처럼 AS1으로 가는 패킷을 보낼 때, Provider의 link를 거쳐 전송하면 비용을 지불해야합니다. (Provider에게 보내므로) 반대로, Customer Link로 패킷을 전송하는 경우 오히려 비용을 받을 수 있겠죠. BGP 프로토콜에는 이러한 Provider보다는 peer, peer보다는 customer를 선호하는 Local Preference가 반영되어있습니다.