Move Fast

▶ 네트워크 계층의 기능

- 포워딩(Forwarding) : 데이터 영역(Data Plane)의 기능으로, 포워딩 테이블을 탐색(look up)하여 라우터 입력 버퍼에서 출력 버퍼로 패킷을 전달한다.

-포워딩은 크게 (1)목적지 기반의 포워딩-전통적인 방식, (2)일반화된 포워딩-SDN 방식으로 두 가지가 있다.

- 라우팅(Routing) : 제어 영역(Control Plane)의 기능으로, 출발지에서 목적지까지 패킷의 헤더를 보고 전체 경로를 설정한다.

- 아래는 앞서 기술한 데이터 영역에 대한 정보(원리)가 포함되어 있다.

http://movefast.tistory.com/40

http://movefast.tistory.com/52

http://movefast.tistory.com/53

http://movefast.tistory.com/54

- 여기서는 제어 영역을 구성하는 정보를 알아볼 것이며, 우선 제어 영역의 구조에는 (1)라우터당 제어(분산적, 전통적 방식), (2)논리적으로 중앙 집중화된 제어(중앙 관리 방식, SDN) 방식으로 접근할 수 있다.

- 아래는 두 구조를 기반으로 포워딩 테이블을 계산하는 원리이다.

▶ 라우팅 프로토콜(Routing Protocol)

- 인터넷(Internet)은 Hop-by-Hop 라우팅 방식이라 하여 각 라우터는 다음 목적지까지만 안내한다.

- 이 때, 각 라우터마다 수신 호스트(최종 목적지)로 안내해주기 위해 각 라우터의 다음 목적지까지의 경로를 라우팅 프로토콜이 모두 결정한다.

- 송신 호스트(source host)에서 수신 호스트(destination host)로 네트워크의 라우터를 지나가는데 있어 “좋은 경로”를 결정하는 것을 목표로 한다.

- “좋은”은 “Good“을 직역한 것으로, 가장 빠르고 혼잡이 최소화되는 경로, 저렴한 비용 등 다른 일반적인 요소도 포함한다.

- “경로”는 “Path”를 직역한 것으로, 송신 호스트에서 수신 호스트로 가기 위해 지나갈 “라우터들의 순서”를 의미한다.

- Source Routing : 처음에 최종 목적지를 가기 위해 꼭 거쳐야 할 목적지(라우터)를 정해주는 기능이다.

- 아래는 네트워크의 경로를 그래프로 나타낸 것이다. 그래프 추상화는 네트워크 문맥 파악에 유용하게 사용된다.

[ 노란색은 라우터, 이어지는 선들은 경로이며, 숫자는 경로 비용(cost)이다. ]

• graph : G = (N, E) -> G는 그래프를 나타낸다.

• N : 라우터의 집합으로, 위의 그림은 N = { A, B, C, D, E, F, G } 이다.

• E : 링크의 집합으로, 위의 그림은 E = { (A, B), (A, D), (B, C), (B, E), (B, F), (D, F), (D, G), (E, F), (F, G) } 이다.

• c(x, y) : 라우터 x에서 라우터 y까지의 링크의 최소 비용으로, 비용이 적을수록 자료 전송율(bps)이 좋다. 혼잡이 많을수록 비용이 증가하며 이는 좋지 않다. 위의 그림에서 c(A, C) = 5 이다.

• Cost of Path (a, b, c, ... , z) = c(a, b) + c(b, c) + c(c, d) + ... + c(y, z) : 경로 비용이란 링크 비용의 합이다.

- 라우팅 알고리즘은 최소 비용의 경로를 찾는다. 추가로, 라우팅 경로 설정 시 정보 수집이 미리 이루어져야 하는데 위의 경우는 미리 정보가 주어진 경우이다. 소프트웨어적인 구현에 있어서 최단 경로를 찾는 자료구조가 활용된다.

▶ 라우팅 프로토콜의 분류(Classification)

- 포워딩 테이블을 계산하는 것은 “라우팅 알고리즘”의 일이다. 이 라우팅 알고리즘은 어떤 정보를 가지느냐에 따라 두 가지로 나뉜다.

- 링크 상태(Link State, LS) 알고리즘 : 모든 라우터들이 완벽한 토폴로지, 링크 비용 정보 등 각 라우터의 모든 정보(Global Info)를 가진다.

- 거리 벡터(Distance Vector, DV) 알고리즘 : 모든 라우터는 물리적으로 연결된 이웃 라우터의 링크 비용 정보만 가진다. 반복적인 계산과정과 이웃간의 정보 교환이 이루어진다.

- 처음에 송신 호스트와 수신 호스트가 정해지더라도, 라우터 간의 경로가 혼잡해지게 되어 비용이 증가하면, 최소 비용의 경로를 찾기 위해 “경로가 바뀌는“ 상황이 생긴다.

- 경로가 시간이 지남에 따라 느리게 변하거나 거의 일정한 것을 “Static”하다고 표현하며, 노드(링크)가 고정되어 있음을 의미한다. 링크 상태 알고리즘(LS)은 정적인 상태에서 경로를 설정한다.

- 경로가 빠르게, 많이 변하는 것을 “Dynamic”하다고 표현하며, 주기적으로 라우터끼리 정보를 주고받으며 링크 비용 변화에 대응한다. 거리 벡터 알고리즘(DV)은 동적인 상태에서 경로를 설정한다.

▶ 링크 상태(Link State, LS) 알고리즘

- 1단계, 정보수집 : Flooding 방식으로 망(net) 토폴로지, 링크 비용이 모든 노드에게 알려진다. 즉, 모든 노드들이 같은 정보를 가지게 된다.

- 2단계, 경로계산 : 출발지 노드에서 모든 다른 노드까지의 최소 경로 비용을 계산한다. 여기서 "다익스트라 알고리즘"(Dijkstra’s algorithm)이 사용된다.

- 3단계, 포워딩 테이블 생성 : 모든 라우터는 최단 경로 알고리즘(다익스트라)을 통해 생성된 “다음 hop에 대한 테이블”을 얻는다.

- Flooding 방식이란 “링크 상태 브로드캐스트”를 통해 홍수가 일어나듯 다른 라우터에서 받은 정보를 또 다른 라우터에게 알리는 방식이다. 중복된 정보가 수신되면 알아서 버린다.

- “링크 상태 브로드캐스트”는 라우터마다 자신의 로컬 링크 비용(link cost) 정보를 가지는데 다른 라우터와 이 정보를 주고받으면서 다른 라우팅 정보를 수집하는 것을 의미한다. Flooding 방식과 유사한 의미이다.

- 다익스트라 알고리즘에 사용되는 표기법

• c(x, y) : x에서 y까지의 링크 비용, 이웃 노드가 아닐 경우 무한대(∞)로 표시된다.

• D(v) : 출발지에서 목적지 v까지 경로의 현재 비용, 최소 비용을 발견하기까지의 비용을 현재 비용이라 한다. 현재 비용 중에 최소 비용을 찾는다.

• p(v) : 출발지에서 목적지 v까지의 경로에서 v 이전 노드(목적지, 라우터)

• N’ : 최소 비용 경로라고 명확하게 알려진 노드(목적지, 라우터)들의 집합

- 다익스트라 알고리즘의 코드

- 위의 이미지를 바탕으로, 출발지를 C라고 하고 목적지를 G라고 하였을 때의 C의 다익스트라 알고리즘 구현하기 

(실제로 위의 이미지 같은 자료는 라우팅 알고리즘에 제공되지 않습니다.)

• STEP 0 : C에서의 이웃 노드는 B밖에 없으므로, 나머지는 ∞로 표기합니다. B까지의 현재 비용은 그림과 같이 3입니다.

• STEP 1 : [step 0]에서 최소 비용이 되는 경로가 노드 B이므로 N’에 B가 추가도비니다. 이제 알고 있는 노드들(N‘의 원소)로 갈 수 있는 노드는 A, E, F로 세 경로가 있습니다. B는 이미 있으므로 계산하지 않아도 되고, D와 G는 지금까지 알고 있는 노드들과 이웃이 아니므로 ∞로 표기합니다.

C->B

• STEP 2 : [step 1]에서 현재 경로 중 최소 비용이 되는 경로는 노드 F이므로 N’에 F가 추가됩니다. 이제 알고 있는 노드들(N’의 원소)로 갈 수 있는 노드는 A, D, E, G로 네 경로가 있습니다. B와 F는 이미 추가한 노드이므로 표기하지 않습니다.

C->B

C->B->F

• STEP 3 : [step 2]에서 현재 경로 중 최소 비용이 되는 경로는 노드 A와 E가 있으므로 N’에 A와 E가 추가됩니다. 이제 알고 있는 노드들(N’의 원소)로 갈 수 있는 노드는 D, G로 두 경로가 있습니다. 나머지 노드는 이미 추가한 노드이므로 표기하지 않습니다.

C->B

C->B->F

C->B->A

C->B->E

• STEP 4 : [step 3]에서 현재 경로 중 최소 비용이 되는 경로는 노드 D가 있으므로 N’에 D가 추가됩니다. 이제 알고 있는 노드들(N’의 원소)로 갈 수 있는 노드는 G 하나만 있습니다. 나머지 노드는 이미 추가한 노드이므로 표기하지 않습니다.

C->B

C->B->F

C->B->A

C->B->E

C->B->F->D

• STEP 5 : [step 4]에서 현재 경로 중 최소 비용이 되는 경로는 노드 G가 있으므로 N’에 G가 추가됩니다. 모든 노드에 대하여 최소 비용 탐색이 끝났으므로 확장된 경로는 아래와 같습니다.

C->B

C->B->F

C->B->A

C->B->E

C->B->F->D

C->B->F->D->G

• 여기서 C에서 G까지의 최소 비용은 9가 되고, 아래는 C의 포워딩 테이블입니다.

• 어떤 목적지든 C에서는 다음 목적지가 B임을 알 수 있습니다.

- 다익스트라 알고리즘의 복잡도 : N‘에 없는 모든 노드들을 확인할 필요가 있으며, n개의 노드가 순서대로 살펴지기 때문에 n(n+1)/2 번의 비교횟수를 가진다. ->

- 더욱 효율적인 자료구조를 사용하여 복잡성을 감소할 수 있다. 위의 알고리즘 코드의 9번째 줄에서 w를 찾는데 "힙 자료구조"를 사용하는 것이다. 그 때의 복잡도는 O(nlogn) 가 된다.

▶ 거리 벡터(Distance Vector, DV) 알고리즘

- 벨만 포드 항등식(동적 프로그래밍에 자주 쓰임) : = min{c(x, v) +  }

• : x에서 y까지의 최소 비용 경로의 값

• c(x, v) : v는 x의 이웃노드이고, x와 v간의 경로 비용을 의미한다.

• : 모든 이웃 v에 대한 y까지의 거리

• min{ } : 괄호 안에 계산되어진 값들 중 최소값

• (이 때,  값은 v가 x에게 알려줌)

- 초기 상태에서 노드는 각 이웃들 간의 최소 거리 비용만 알고 있다.

-위의 그림에서 B에서 G까지의 거리를 벨만 포드 항등식을 사용하여 거리 벡터 알고리즘을 구현해보기

- B의 이웃노드는 A, E, F이므로(C는 G로 갈수 없으므로 제외한다.) 각 노드에서 G까지의 최소 비용 경로는 

 임을 노드 A, E, F는 알고 있다. 이 정보를 B에게 전달하면, B는 벨만 포드 항등식으로 계산한다.

node B :

-: x에서 네트워크 노드 중 임의의 노드 y까지의 최소 비용

- 거리벡터 값 (N : 네트워크 노드의 집합)

- 반복적, 비동기적 특성 : 로컬 링크 비용(c(x, v))이 변화가 생길 때마다 거리 벡터 값()이 갱신되며, 갱신된 노드는 이웃 노드에게 알리게 되고 따라서 다른 노드들도 거리 벡터 값을 갱신한다.(로컬 링크란 자신과 이웃간의 링크를 의미한다.)

- 분산적 특성 : 각 노드는 자신의 거리 벡터 값()의 변화가 있을 때만 이웃들에게 통지한다. 또는 이웃이 자신의 거리 벡터 값을 필요로 한다면 통지한다.

- 링크 비용 변화의 3단계

• 1단계 : 각 노드는 로컬 링크 비용의 변화(c(x, v))나 이웃(v)들로부터 통지( )를 받을 때까지 기다린다.

• 2단계 : 통지를 받으면 거리 벡터 값()을 다시 계산한다.

• 3단계 : 어떤 목적지에 대한 거리 벡터 값()이 변경되었다면 이웃에게 알린다. (단, 어디를 경유했는지는 없고, 비용에 대한 정보만 준다.)

- 링크 비용이 감소한 경우 해당 정보는 네트워크 전역에 빠르게 전파된다.

- 링크 비용이 증가한 경우 해당 정보는 네트워크 전역에 느리게 전파된다. 따라서 기존의 정보(이웃노드의 변화 전 거리벡터 값)를 유지한 채 다른 목적지까지의 거리벡터 값이 변경되면 기존의 정보가 적용되는 상황이 발생하고, 해당 노드는 이웃노드의 변화를 알 때까지 자신의 거리 벡터 값을 잘못 계산할 수 있다. 보통 정보 전달이 느리면 서로 잘못된 정보를 전달하게 되어 “무한 카운트 문제”가 발생한다.

- 무한 카운트 문제 예시) 노드 A와 노드 B간에 다른 노드로 보내야하는데 최소 경로로 서로가 지정되어 A->B,  B->A로 정보를 전달하게 되면 라우팅 루프가 발생한다.

- 포이즌 리버스(Poison Reverse) : 어떤 노드가 이웃노드에게 임의의 노드까지 가짜 거리벡터 값으로 ∞를 알려주는 것이다. 즉, 임의의 노드까지 가는데 자신을 거치지 말라는 의미이다. 이 방법은 무한 카운트 문제를 해결하기 위해 사용되나 세 개 이상의 이웃 노드를 포함한 루프인 경우 감지하지 못한다.

▶ 오동작 하는 경우(Robustness)

- 링크 상태(Link State, LS) 알고리즘 : 노드는 적절하지 못한 “링크 비용”을 알릴 수 있는데, 그럴 때 각 노드는 자신의 포워딩 테이블만 다시 계산한다.

- 거리 벡터(Distance Vector, DV) 알고리즘 : 노드는 적절하지 못한 “경로 비용”을 알릴 수 있는데, 그럴 때 각 노드의 테이블은 이웃 노드에게 이용되어지며 에러가 네트워크 전역에 전파된다.