[Network Layer 03] Control Plane

이전 단원에서 routing table을 참조해서 forwarding 하는 과정에 대해 배웠다.

이번 단원에는 routing table을 어떤 방식으로 만드는지 알아보겠다. 

 

라우팅 테이블을 생성하는 주요 방식은 다음과 같은 2 가지이다.

1. 전통적인 라우팅 프로토콜
   • Link state 프로토콜(OSPF): 네트워크 토폴로지 정보를 교환하여 최단 경로 계산
   • Distance Vector 프로토콜(RIP): 이웃 라우터의 거리 정보를 교환하여 경로 결정
   • 이 경우 router마다 네트워크 상황을 다르게 해석할 수 있다. 
   • 전통적인 프로토콜에서 각 라우터는 독립적으로 네트워크 상황을 판단하고 경로를 결정한다. 이때 ISP(인터넷 서비스 제공자)마다 다른 방식으로 최적 경로의 비용(cost)을 계산할 수 있다. 비용 계산에 고려되는 요소로는 목적지까지 가는 대역폭, 거치는 라우터의 수, 전파 지연 시간(propagation delay)가 있다. 
2. SDN(Software-Defined Networking) 컨트롤러
   • 중앙 집중식 컨트롤러가 네트워크 정보를 수집하고 라우팅 경로를 계산하여 라우터에 전달

 

한편, 라우터는 일반적으로 최소 두 개의 라우팅 프로토콜을 사용한다

• Intra-ISP routing : 동일 ISP(Internet Service Provider) 내 라우터 간 연결을 위한 내부 프로토콜 (OSPF)
• routing amoung ISPs: 서로 다른 ISP 간 연결을 위한 외부 프로토콜 (BGP)

네트워크 layer에서 해줘야하는 역할은 2가지이다. control plane에서 경로를 어떻게 설정할지 routing을 하여 만들어진 table로 data plane에서 forwarding하는 것이다. 

 

네트워크 Control plane을 구현하는 2가지 방식이 존재한다. 위에 라우팅 테이블을 생성하는 주요 방식 2가지와 비슷한 이야기이다. 

 

1. router마다 각자 계산을 해서 공유하여 control을 생성하는 방법

    이 방법의 경우 router마다 network 상황을 다르게 해석할 수도 있다. 

2. SDN에 기반하여 중앙 집권식 컨트롤러가 존재하여 control을 생성하는 방법이다. 이렇게 될 경우 확실하게 consistency가 보장이 되며, 단일한 view를 전달할 수 있다. 

 

 

전통적인 라우팅 프로토콜

라우팅 프로토콜은 네트워크 통신에서 매우 중요한 역할을 한다. 이것은 송신 호스트에서 수신 호스트까지 패킷이 이동하는 경로, 즉 '최적의 길'을 결정한다. 여기서 '최적의 길'이란 비용이 적게 들거나, 가장 빠르거나, 네트워크 혼잡이 최소화되는 경로를 말합니다. 만약 모든 Path에 대한 cost가 1이면 hop을 가장 적게 거치는 min hop을 찾아갈 것이다. 

패킷이 라우터를 거치며 이동하는 전체 경로를 결정하는 것은 네트워크 분야에서 가장 어려운 과제 중 하나이다. 왜냐하면 네트워크 토폴로지, 트래픽 패턴, 대역폭 등 다양한 요소를 고려해야 하기 때문이다. 효율적인 라우팅 프로토콜을 설계하고 구현하는 것은 네트워크 엔지니어들에게 큰 과제이다. 

 

Routing 알고리즘은 크게 2가지로 나뉜다.

1. Link state algorithm

Link state algorithm은 global한 알고리즘으로 모든 라우터들이 완전한 topology,즉 link cost 정보를 가지고 있다. 이가 가장 많이 사용된다. 다익스트라 알고리즘을 사용하여 각 라우터가 독립적으로 최단 경로를 계산하여 공통된 정보를 가지게 되는 시점은 모든 노드가 다를 수 있다. Link state알고리즘을 따르는 대표적인 프로토콜에는 OSPF가 있다. 

모든 노드가 다른 노드들로 부터 정보를 받아서 전체 네트워크를 그린다. 다른 노드들에게 전달하는 정보를 link state라고 하며, 라우터들은 자신의 인접 링크 상태 정보를 broadcast하여 네트워크 전체에 홍보합니다. 이것을 링크 상태 광고(Link State Advertisement, LSA)라고 한다. 하나의 source 노드로부터 모든 다른 노드들까지의 최소 비용 경로를 계산하는 것이 주 목적이다. k개의 destination이 있는 경우 k번 반복후에 최소 비용 경로를 알 수 있다. 다익스트라에서 cost가 똑같은 노드라면 아무거나 선택해도 괜찮다. 

 

다익스트라 알고리즘에서는 n개의 노드가 있을때, Time Complexity(알고리즘 복잡도)는 O(n^2)이지만 우선순위큐를 사용하면 O(nlogn)이다. 메시지 복잡도 (Message Complexity)를 구해보면, link state 알고리즘에서 각 노드는 자신의 링크 상태 정보를 네트워크 전체에 홍보(Flood)해야 한다. 효율적인 브로드캐스트 알고리즘을 사용하면 하나의 소스에서 브로드캐스트 메시지를 전파하는 데 O(n) 링크 교차만 필요하다. 각 라우터의 메시지는 O(n) 링크를 통과하므로 전체 메시지 복잡도는 O(n^2)이다.

 

oscillations possible

Oscillations은 라우팅 프로토콜에서 라우팅 테이블이 계속해서 변경되는 현상을 의미한다. 이는 네트워크 토폴로지나 링크 비용이 자주 변경될 때 발생할 수 있다.

다익스트라 알고리즘 자체는 정적 네트워크 환경에서 실행되며, 최단 경로를 정확히 계산한다. 하지만 실제 네트워크에서 다익스트라 알고리즘을 주기적으로 재실행할 때 oscillations이 발생할 수 있다. 이런 oscillations은 link state algorithm방식에서만 발생한다. 

 

2. Distance vector algorithm

Distance vector algorithm은 분산화된 알고리즘으로 router가 직접 cost를 처음부터 계산하지 않고 이웃들이 알려주는 정보에 의존하여 계산을 한다. 이때 벨만포드 알고리즘을 사용한다. 예를 들어, 서울에서 부산을 가야하는데 내 이웃에 있는 대구와 대전이 부산을 가는데까지의 cost 정보가 있을때, 나는 min (서울에서 대구까지 가는 cost + 대구에서 부산까지 가는 cost, 서울에서 대전까지 가는 cost + 대전에서 부산까지 가는 cost)로 서울에서 부산까지 가는 cost를 구한다는 말이다. 

각 경로 계산이 distribution에 의존해 계산을 한다. 또 이렇게 계산한 나의 값이 최소로 업데이트되었을 경우 자신의 이웃들에게 전달해줘야한다. 

이렇게 Distance vector algorithm을 사용했을때 이웃으로부터 정보를 받아 독자적으로 계산을 하다보니 노드마다 시점이 다 다를 것이다. (asynchronous)

 

Bad news travels slow

Distance Vector 방식에서는 네트워크의 각 노드가 자신의 라우팅 테이블을 이웃 노드들에게 주기적으로 전송합니다. 이 라우팅 테이블은 네트워크의 다른 모든 노드까지의 최소 비용 경로를 나타냅니다. 각 노드는 이웃 노드들로부터 받은 정보를 사용해 자신의 라우팅 테이블을 업데이트합니다.

문제는, 노드 사이의 비용이 큰 값으로 변경될 때 발생합니다. 예를 들어, A와 B 사이의 비용이 갑자기 커졌다고 가정해보겠습니다. 이 경우, A와 B는 자신의 라우팅 테이블을 업데이트해야 하는데, 이 정보가 네트워크의 모든 노드에 전파되기까지 시간이 많이 걸릴 수 있습니다. 이는 특히 네트워크가 클 경우 심각한 지연을 초래할 수 있습니다.

이 문제를 해결하기 위해 Distance Vector 방식에서는 다음과 같은 규칙을 적용합니다

- 최소 비용 경로의 노드를 경유하는 경우: 만약 어떤 노드가 자신에게 도달하는 최소 비용 경로에 있는 다른 노드로부터 정보를 받을 때, 해당 경로를 무한대로 설정합니다. 이는 그 노드를 거쳐가는 경로를 사용하지 않도록 하기 위함입니다.

이 규칙을 적용하면 특정 경로의 비용이 크게 증가하는 경우, 네트워크 전체에 그 정보가 빠르게 전파되지 않고 특정 경로를 우회하는 다른 경로가 선택될 수 있게 됩니다.

좀 더 구체적으로 설명하자면, 예를 들어 노드 A에서 B로 가는 최소 비용 경로가 A -> C -> B 라고 가정해 봅시다. 이때 A가 B에 대한 정보를 업데이트할 때 C를 통해 전달받은 정보를 사용하지 않도록 설정하는 것입니다. 이렇게 하면 A는 B로 가는 다른 경로를 탐색하게 되고, 그 결과 네트워크 전체에 걸리는 지연 시간이 줄어들게 됩니다.

 

Link State 알고리즘과 Distance Vector 알고리즘의 Robust 비교

 

Link State가 더 견고하다.

 

특정 노드에서 잘못된 링크 비용 정보를 전파하더라도, 다른 노드들은 여전히 전체 토폴로지 정보를 바탕으로 최단 경로를 계산할 수 있습니다.따라서 일부 경로에만 영향을 미치고, 전체 네트워크 라우팅 테이블이 잘못되는 것을 방지할 수 있다.

 

악의적인 노드가 자신을 목적지까지 최소 비용 노드로 거짓 정보를 전파하면, 다른 노드들이 이를 신뢰하여 해당 노드를 다음 홉으로 선택한다. 결과적으로 네트워크 전체 트래픽이 악의적 노드를 경유하게 되어 전체 네트워크 라우팅이 잘못될 수 있다.