computer network - control plane(2)
network layer - control plane
저번 글에서, network layer의 control plane에서는 라우팅에 대한 Overview를 살펴봤습니다. 이번 글에서는 라우팅에 대해 전반적으로 이야기를 해보도록 하겠습니다.
routing protocol
라우팅이 길을 찾는 과정임은 이해했습니다. 그렇다면 무엇이 좋은 라우팅일까요?
보통 네트워크 상황을 현실의 교통 상황에 많이 비유합니다. 라우팅은 어떤 도로로 갈지 찾는 과정과 mappimg이 되겠네요. 차를 타고 목적지로 갈 때, 무엇이 좋은 길인가요?
정답은 “빠르고 쾌적하고, 경우에 따라서는 톨게이트 비용을 덜 내는, 기름값을 덜 내도 되는 길”입니다.
뭐 다른 대답을 해도 되지만, 대략 비슷한 맥락일 것입니다. 즉, 소모되는 비용을 최소화하는 길이 좋은 길입니다.
네트워크 상황에도 마찬가지겠네요. 즉 routing protocol의 목표는 최대한 비용을 덜 소모하는 쪽이 됩니다.
graph abstraction : cost
이러한 네트워크 상황을 하나의 point로 추상화 가능합니다.
이런 형태로 말이죠.
각 점(node, vertex) 사이 link 위 써져있는 숫자는, 어떤 점에서 이어진 점까지 필요한 비용이라고 생각하면 됩니다. 뭐 거리, 시간 등등이 될 수 있겠네요. 아무튼 핵심은 이러한 비용을 숫자로 추상화했다는 것입니다. 이렇게 추상화가 가능하다면, 훨씬 편하게 라우팅이 가능할 것입니다.
앞으로 우린, 네트워크 상황을 알고 있고, 각 node에서 다른 node로 가는 비용을 알고 있다고 가정할 것입니다!
점 z를 기준으로 생각해보겠습니다.
점 z와 w 사이 비용은 5입니다. 하지만 z에서 u사이 비용은 바로 갈 수 없으므로 무한대로 일단은 표기합니다. 하지만 우린 z와 u 사이 비용은 2+1+1=4임을 직관적으로 알 수 있습니다. 이러한 방식으로 후에, 비용을 계산하고 경로를 결정할 수 있습니다.
라우팅 알고리즘의 분류
위에서 설명했던 그래프를 가지고 라우팅을 합니다. 이러한 라우팅을 분류를 할 수 있습니다.
중앙 집중형 라우팅 알고리즘과, 분산 라우팅 알고리즘으로 나뉩니다.
중앙 집중형 라우팅 알고리즘과 분산 라우팅 알고리즘
중앙 집중형 라우팅 알고리즘은 아는 모든 정보를 가지고 라우팅을 하는 알고리즘입니다. 즉 일부를 보는 것이 아닌, 어느 지역 내의 모든 교통 상황을 고려하여, 한 번에 routing table을 만드는 것이죠. 어느 지역 내의 라우터들은 이 테이블을 공유하게 됩니다. 또한, 이렇게 전체 상태 정보를 갖는 라우팅 알고리즘을 link- state algorithm이라고 합니다. 약간 동기적(synchronous)인 느낌도 드네요.
분산 라우팅 알고리즘은 이름부터 직관적입니다. 어느 지역 내부 라우터들이 하나의 테이블을 공유하는 것이 아닌, 분산된 라우터들을 기준으로 라우팅을 계산하는 알고리즘인 것이죠. 즉, 어느 라우터들은 나와 연결된 라우터와 교류를 한다는 것입니다. 점점 퍼져나가서 하나의 net을 만드는 알고리즘인 것이죠. 이러한 분산 라우팅 알고리즘을 distance vector 알고리즘이라고도 부릅니다. 왜냐하면 어떤 라우터를 기준으로 거리와 방향으로 라우팅을 하기 때문입니다. 이는 비동기적(asynchronous)인 느낌이 듭니다.
정적과 동적 라우팅 알고리즘
또한 하나 더 분류를 할 수가 있습니다. 바로 동, 정적 라우팅 알고리즘으로 말이죠. 정적 라우팅 알고리즘은 이름부터 정적입니다. 잘 움직이지 않는다는 의미인 것이죠. 그러면 동적 라우팅 알고리즘은 동적인, 즉 상황에 맞추어 시시각각 바뀌는 알고리즘임을 직관적으로 알 수가 있겠네요.
뭔가 중앙 집중형 - 정적 -link state와 분산형 - 동적 - distance vector로 나뉠 듯한 기분이 듭니다.
link state - djikstra algorithm
이때까지 그래프와 최단 경로 이야기를 했습니다. 전공자들이라면 머릿속에 하나가 떠오르실듯 합니다. 바로 이름부터 유명한 “다익스트라 알고리즘 (djikstra algorithm)”입니다. 어떤 시작 노드에서, 모든 노드끼리의 최단 경로를 알 수 있는 알고리즘입니다.
네트워크 상황에서 이동하는데 비용은 음수가 될 수 없다고 직관적으로 알 수 있습니다. 다익스트라 알고리즘의 약점인 음수 cost는 고려하지 않아도 되는 장점이 있습니다.
다익스트라 알고리즘에 대해 간략하게 이야기해봅시다.
하나의 점을 기준으로 하나씩 확장해가며, 최솟값을 갱신하는 알고리즘이라고 알고 계시면 편할 것 같습니다.
해석해 볼까요?
일단 2차원 배열을 초기화합니다. 이름을 cost라고 하겠습니다. cost[i][j]는 i에서 j까지 가는 비용입니다. 일단 초기 정보를 가지고, 바로 알 수 있는 정보를 초기화합니다. 시작 노드를 s라고 하겠습니다.
이후, 방문하지 않은 노드 집합 중 비용이 최소인 노드를 찾습니다. 이름을 w라고 하겠습니다. w 기준으로 s부터 모든 w의 이웃한 노드의 거리를 찾습니다.
cost[s][neighborhood_node] = min (cost[s][neighborhood_node] , cost[s][w] + cost [w][neighborhood_node])
이 과정을 모든 정점을 방문할 때 까지 하면, s를 기준으로 모든 노드에 대한 최단 거리를 알 수가 있게 되겠네요!
하지만 총 노드의 수를 n개, 방문한 노드 기준 이웃한 노드의 평균 수를 m이라고 하면 이는 O(nm)의 시간 복잡도가 필요한 상황이죠. n은 보통 m과 유사하기에, O(nn)의 시간 복잡도가 필요한 것이죠. 뭐 우선순위 큐를 사용하면 최솟값을 찾는데 logn의 시간이 걸릴 것이므로, O(nlogn)의 시간이 걸릴 수 있지만 네트워크 상에선 보통 O(n*n)이 걸린다고 볼 수 있습니다. 매우 좋지 않은 상황이죠.
이러한 단점도 있고, 또한 진동 문제가 일어날 수가 있다는 것입니다.
oscillation problem
진동 문제가 뭘까요?
현재, traffic을 보고 라우팅을 한다고 가정하겠습니다. 초기 상태에서 (traffic=0), d와 c와 b에 각각 1 , e(e<1) , 1의 traffic이 들어왔다고 가정해봅시다. d -> a로 가는 경로의 traffic은 1이고 c -> b로 가는 경로의 traffic은 e고, b -> a로 가는 경로의 traffic은 1+e가 될 것입니다. 왜냐하면 이 경로는 c에서 출발한 traffic과 b에서 출발한 traffic을 포함하니까요.
이렇게 바뀌겠네요.
그럼 또 현재 상황을 기준으로 라우팅을 합니다. d와 c와 b에 각각 1 , e(e<1) , 1의 traffic이 들어왔다고 가정해봅시다. b는 반시계방향으로 a에 도달하는데 1+e의 traffic이 있음을 압니다. 하지만 시계방향으로 간다면 0+0+1 = 1의 traffic이 있음을 깨닫고, 시계 방향으로 노선을 꺾습니다.
이러한 상황이 계속 반복되는 것이죠.
이를 진동 문제라고 합니다. 현재 traffic 상황에 맞추어서 라우팅을 하다 보니, 진동 문제를 겪을 수 밖에 없는 것이죠.
마무리하며
이제 다음 글에서, link state가 아닌 distance vector 알고리즘에 대해 다뤄보도록 하겠습니다.