네트워크 계층 함수
- forwarding (data plane)
라우터의 입력으로 들어온 패킷을 적절한 라우터 출력으로 이동시킨다.(HW)
- routing (control plane)
출발지에서 목적지까지 패킷의 경로를 지정해준다.(SW)
네트워크의 제어 영역을 구성하는 방법으로는 두 가지 접근방식이 존재한다,
1. per-router control (traditional)
2. logically centralized control (software defined networking)
Per-router control plane
위 알고리즘은 각 라우터마다 라우팅 알고리즘을 수행한다.
따라서 모든 라우터는 각각의 라우팅 알고리즘과 포워딩 테이블을 보유하고 있어 모두 직접 라우팅을 통해 경로를 찾으면 포워딩 테이블을 통해 포워딩을 수행한다.
또한 라우터끼리 서로 통신하여 정보를 교환하므로 자신의 포워딩 테이블을 지속적으로 업데이트한다.
Software-Defined Networking (SDN) control plane
SDN 알고리즘의 경우 모든 라우터에서 라우팅과 포워딩을 진행하는 것이 아니라,
원격 컨트롤러가 포워딩 테이블을 계산하여 각 라우터에 설치한다.
각각의 라우터들은 정보를 원격 컨트롤러에 전달하고, 원격 컨트롤러들 들어온 정보들을 통해 포워딩 테이블을 업데이트한다. 이 알고리즘은 전체적인 관점에서 경로를 찾을 수 있으므로 더 최적의 경로를 찾을 수 있다.
라우팅 프로토콜(Routing Protocol)
라우팅 프로토콜은 크게 두 가지로 나뉜다.
- link state: OSFP, IS-IS
- distance vector: RIP
라우팅 프로토콜은 최적의 경로를 계산하는 것이 목표이다.
즉, 목적지까지 가기 위해 중간에 들리는 라우터 수가 적고, 속도가 빠르며, 비용이 적게 들거나 대역폭이 큰 경로를 찾는 프로토콜이다.
라우팅은 일반적으로 사진과 같이 그래프틀 통해 수행된다.
이때, 그래프에서의 노드는 라우터를 의미하고, edge(엣지)는 라우터 사이의 연결인 엣지를 의미한다.
따라서 위와 같이 표기할 수 있다.
이때 각 엣지에 대해 숫자가 표기되어 있는데 이 숫자는 해당 링크를 통과하는 데에 필요한 비용이다.
보통은 모든 엣지에 대해 비용을 1로 표기하는데, 대역폭이나 혼잡도에 대해 반비례하여 표기하기도 한다.
라우팅 알고리즘 분류
라우팅 알고리즘은 크게 네 가지로 구분할 수 있다.
- global
모든 라우터에 대한 연결상태 및 링크의 비용을 알고 있는 상태에 사용할 수 있다.
'link state' 알고리즘이 여기에 해당하며 주로 다익스트라 알고리즘을 사용한다.
- decentralized
이웃과의 반복적인 정보 교환을 통해 반복적으로 계산하는 경우이다.
각 라우터는 인접한 라우터에 대한 링크의 비용을 알고 있으며 반복된 계산과 인접 노드와의 정보 교환을 통해 최적의 경로를 찾을 수 있다.
'distance vector' 알고리즘이 여기에 속하며 주로 Bellman-ford(벨만포드) 알고리즘을 사용한다.
- static
시간에 따른 경로의 변경이 느리고 라우팅 테이블에 경로를 수동으로 추가해야 한다.
- dynamic
경로의 변경이 더 빠르게 발생하고 주기적으로 업데이트를 하거나 링크의 비용에 대한 변화에 직접 응답을 준다. 다익스트라 알고리즘과 벨만포드 알고리즘은 보통 dynamic 라우팅을 위해 사용된다.
Dijkstra's algorithm
다익스트라 알고리즘은 중앙화를 통해 모든 네트워크의 토폴로지, 모든 링크의 비용을 알고 있으며 "link state broadcast"를 통해 수행된다. 이때 모든 노드는 동일한 정보를 가진다.
하나의 노드(보통 출발지)에 대해 다른 모든 노드까지의 최소 비용 경로를 찾은 후 해당 노드에 대한 포워딩 테이블을 전달한다. 이러한 과정을 k개만큼 반복하면 k개의 목적지까지의 최소비용을 알아낼 수 있다.
다익스트라 알고리즘에서 사용하는 표기법을 확인하자.
- Cx,y
x 노드에서부터 y 노드까지의 링크 비용이다. 연결이 되어 있지 않은 경우 무한으로 표기
- D(v)
현재까지 계산된, 출발지에서 목적지 v까지 가는 데에 필요한 최소 비용 경로
- p(v)
현재 라우터에서 목적지 v 도착하기 바로 직전의 노드에 대한 정보
- N'
현재까지 찾아낸 최소 비용 경로의 집합
다익스트라 알고리즘은 위와 같이 구현한다.
다익스트라 알고리즘을 통해 최소 비용 경로를 찾는 과정을 도식화한 것이다.
위 사진에서 출발지는 u이다.
표에서 볼 수 있듯이, 출발지에서 모든 노드에 대해 가장 짧은 경로를 구하는 것이다.
각 도달할 수 있는 모든 노드에 대해 비용을 구하면, 해당 비용들 중 가장 적은 값을 선택한다.
이때, 위의 예시에서 볼 수 있듯이 u에서 바로 v를 가는 비용은 u에서 x를 거쳐 v로 가는 비용에 비해 더 적으므로 더 적은 값을 계속해서 유지해준다. (2 < 3)
앞서 계산한 예시의 결과는 위 사진과 같다.
적은 비용이 드는 경로만 남겨놓은 그래프는 좌측과 같고, 계산의 결과값으로 인해 포워딩 테이블의 모습은 우측과 같다.
또 다른 예시는 위 사진과 같다.
이 다익스트라 알고리즘은 선행 노드를 추적하여 최소 비용 경로 트리를 구축할 수 있다.
이러한 경로에는 관계가 존재하는데, 이 관계는 끊어질 수 있다.
Discussion
- 알고리즘의 복잡성
n개의 노드가 있을 때 N이 아닌 모든 노드 w를 확인해야 한다.
n(n+1)/2번 비교해야 하므로 O(n^2)의 시간복잡도를 가진다.
더 효율적으로 구현하면 시간복잡도는 O(nlogn)까지로도 나타낼 수 있다.
- 메세지의 복잡성
각 라우터는 링크의 상태에 대한 정보를 다른 n개의 라우터에 대해 브로드캐스트(모든 네트워크에 대해 전파)해야 한다. 효율적이고 가장 흥미로운 브로드캐스트 알고리즘은 O(n)의 링크를 교차로 연결하여 하나의 출발지로부터 브로드캐스트 메세지를 전달한다.
각 라우터의 메세지는 O(n) 링크를 넘기 때문에 전체 메세지의 복잡도는 O(n^2)이 된다.
무슨 말일까.
oscillations possible(진동 가능성)
링크의 비용이 방향성 또는 트래픽 볼륨에 따라 달라지는 경우 경로가 진동할 수 있다.
즉, 링크의 비용이 바뀌면 가장 짧은 경로로 패킷이 몰리는 현상이다.
위 사진에서 C->A로 가는 최단 경로가 D로 바뀌면 패킷이 D에 몰리게 된다.
패킷이 몰리면 혼잡이 발생하여 링크의 비용이 상승하게 되고, 링크의 비용이 상승하면 B에 또 다시 패킷이 몰리게 된다.
이러한 현상이 반복되면 패킷은 혼잡의 저주에 빠져 나오지 못한다.
Distance Vector(DV)
Distance vector는 벨만포드 방정식에 기반한 알고리즘이다. (dynamic programming)
이때 dynamic programming이란 중앙 제어 없이 변화에 따라 인접 노드의 변화를 반영하여 경로를 변경하는 것이다.
벨만포드 방정식은 위 사진과 같다.
이때 Dx(y)는 노드 x에서 노드 y까지의 최단경로를 의미한다. 이때 v는 x와 인접한 모든 노드를 말한다.
예시를 통해 자세히 알아보자.
u에서 z까지의 최소 비용을 구하는 과정은 다음과 같다.
u에서 v의 비용 + v에서 z까지의 비용
u에서 x의 비용 + x에서 z까지의 비용
u에서 w의 비용 + w에서 z까지의 비용
위 세 가지를 모두 구하여 구한 값 중 최소값을 Du(z)라고 한다.
key idea
- 각 노드는 때때로 자신의 거리 벡터 추정치를 인접 노드에게 전송한다.
현재 라우터에서 몇 개의 라우터가 연결된지 모르기 때문에 주기적으로 정보를 받고, 계산한다.
이러한 과정을 수행하는 이유는 모든 네트워크는 죽었다가 살았다가를 반복하기 때문이다.
- 노드 x가 이웃으로부터 새로운 DV 추정치를 받으면 벨만포드 알고리즘을 사용하여 자체 DV를 업데이트한다.
모든 노드에 대해
(출발지부터 인접 노드까지의 비용 + 인접 노드에서 목적지까지의 비용)값을 사진과 같은 방법으로 반복하여 값을 업데이트한다.
각 노드들은 링크의 비용이 변하거나 인접 노드로부터 DV 업데이트 메세지를 수신할 때 비동기적으로 위의 과정을 반복한다. (그렇지만 보통 30초 주기로 시행한단다.)
각 노드들은 자체 DV가 업데이트 되어야 인접 노드에게 DV 업데이트 메세지를 발송하고, 아무런 메세지를 받지 못 했다면 아무런 조취도 취하지 않는, 분산적이고 self-stopping하는 특징을 갖고 있다.
위의 사진과 같이 DV 알고리즘은 상태 정보가 확산되면서 최적의 경로를 찾아간다.
DV 알고리즘에는 장단점이 존재한다.
장점
이웃 노드로부터 값을 받아 갱신하면 되기 때문에 구현이 간단하다.
단점
링크의 비용이 감소하는 경우 각 라우터의 값 업데이트에 시간이 오래 걸리기 때문에. count-to-infinity 문제가 발생한다.
good news(링크의 비용이 감소하는 경우)는 빠르게 전파된다.
위 사진과 같이 x에서 y로 가는 링크의 비용이 4에서 1로 줄었다고 하자.
t0
y는 링크의 비용 변화를 탐지하고 DV를 업데이트한 후 인접 노드에게 해당 사실을 알린다.
t1
업데이트 메세지를 받은 z는 거리 테이블을 수정하고 x로 향하는 비용을 계산한 후 마찬가지로 인접 노드에게 업데이트 메세지를 전송한다.
t2
y는 업데이트 메세지를 수신하는데 마찬가지로 거리 테이블을 계산하는데 이때 최단 거리(경로)에 대한 변화가 없으므로 인접 노드로 업데이트 메세지를 전송할 필요가 없다.
bad news: Count-to-infinity pronlem
(링크의 비용이 증가하는 경우)는 느리게 전파된다.
위 사진과 같이 x에서 y로 가는 링크의 비용이 4에서 60로 커진 경우를 가정하자.
비용이 변함에 따라 각 노드의 비용 테이블은 위 사진과 같이 변화한다.
각 라우터는 인접 노드에 대한 사실만 알고 있기 때문에 y와 z는 그리디 알고리즘처럼 서로의 링크만을 타고 왔다갔다하면서 비용을 증가시키다가 증가된 비용이 50을 초과했을 때에 z - x 링크를 사용할 수 있다.
다시 자세하게 풀어서 설명하자면,
y에서 DV 업데이트, 인접 노드에게 전파
-> z 비용 테이블 업데이트 시 y 테이블에서 더 작은 값인 6을 선택
-> z 비용 테이블에서 x로 향할 때 y를 거쳐감
-> 값 업데이트, 인접 노드에게 전파
-> y 또한 z를 거쳐 가야 하기 때문에 최소값 변화, 값 업데이트 및 전파
-> ...
의 과정을 거치게 된다.
(위 과정이 자세하게 이해가 가지 않는다면 DV 알고리즘을 직접 적용하여 디버깅하는 방법으로 구해보면 된다.)
poisoned reverse
위의 문제를 해결하기 위해 등장한 것이 poisoned reverse이다.
이 방식은 루프가 계속해서 발생하는 경우 y 노드에서 z 노드를 통해 x를 가면 무한대의 비용이 든다고 판단하여 y에서 x로 가는 경로가 최적으로 판단하게 하는 것이다.
따라서 y의 비용 테이블에서 z로 향하는 비용을 무한대로 설정하면 최소 비용은 y에서 x로 향하는 경로가 되어 테이블을 업데이트 한 후 주위에 전파하는 행동을 반복한다.
count-to-infinity 문제를 해결하기 위한 또 다른 방법으로는 건널 수 있는 라우터의 개수에 한계를 두는 TTL이 있다.
참고 및 출처
https://inyongs.tistory.com/72
https://gigibean.tistory.com/42
https://code-lab1.tistory.com/37
http://csmylov.blogspot.com/2017/08/network-layer-control-plane.html
https://seungjuitmemo.tistory.com/98
'Computer Science > 컴퓨터네트워크(ComNet)' 카테고리의 다른 글
| [컴네/CN] IP Routing: BGP (2) | 2023.12.07 |
|---|---|
| [컴네/CN] IP Routing: RIP, OSPF (2) | 2023.12.07 |
| [컴네/CN] NAT 공유기 개요 (0) | 2023.12.06 |
| [컴네/CN] 인터넷 잡학 (1) | 2023.12.06 |
| [컴네/CN] 네트워크 레이어의 라우터 큐 (1) | 2023.12.06 |