▶ 네트워크 계층의 기능
- 포워딩(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’ : 최소 비용 경로라고 명확하게 알려진 노드(목적지, 라우터)들의 집합
- 다익스트라 알고리즘의 코드
Initialization:
N’ = {u} //출발점이 u임을 의미.
for all nodes v //모든 노드 중 임의의 노드 v에 대하여
if v adjacent to u //노드 v가 노드 u에 이웃이라면,
then D(v) = c(u, v) //경로 계산
else D(v) = ∞ //이웃이 아니라면 무한대 표시
Loop //N’에 없는 노드 중 최소 비용의 노드 탐색
find w not in N’ such that D(w) is a minimum
add w to N’ //찾으면 N’에 추가
update D(v) for all v adjacent to w and not in N’ :
//찾은 노드의 이웃 노드들의 현재 비용을 갱신
D(v) = min(D(v), D(w) + c(w, v))
/* 노드 v에 대한 새로운 비용이 v에서 오래된 비용이거나 최단 경로로 알려진 비용이라면 노드 w에서 v까지의 비용을 추가한다. */
untill all nodes in N’ //N’을 채울 때까지 반복한다.
- 위의 이미지를 바탕으로, 출발지를 C라고 하고 목적지를 G라고 하였을 때의 C의 다익스트라 알고리즘 구현하기
(실제로 위의 이미지 같은 자료는 라우팅 알고리즘에 제공되지 않습니다.)
STEP 0 : C에서의 이웃 노드는 B밖에 없으므로, 나머지는 ∞로 표기합니다. B까지의 현재 비용은 그림과 같이 3입니다.
STEP |
N' |
D(A), p(A) |
D(B), p(B) |
D(D), p(D) |
D(E), p(E) |
D(F), p(F) | D(G), p(G) |
0 |
C |
∞ |
3, C |
∞ |
∞ |
∞ | ∞ |
STEP 1 : [step 0]에서 최소 비용이 되는 경로가 노드 B이므로 N’에 B가 추가도비니다. 이제 알고 있는 노드들(N‘의 원소)로 갈 수 있는 노드는 A, E, F로 세 경로가 있습니다. B는 이미 있으므로 계산하지 않아도 되고, D와 G는 지금까지 알고 있는 노드들과 이웃이 아니므로 ∞로 표기합니다.
STEP | N' | D(A), p(A) | D(B), p(B) | D(D), p(D) | D(E), p(E) | D(F), p(F) | D(G), p(G) |
0 | C | ∞ | 3, C | ∞ | ∞ | ∞ | ∞ |
1 | C, B | 5, B |
| ∞ | 5, B | 4, B | ∞ |
C->B
STEP 2 : [step 1]에서 현재 경로 중 최소 비용이 되는 경로는 노드 F이므로 N’에 F가 추가됩니다. 이제 알고 있는 노드들(N’의 원소)로 갈 수 있는 노드는 A, D, E, G로 네 경로가 있습니다. B와 F는 이미 추가한 노드이므로 표기하지 않습니다.
STEP | N' | D(A), p(A) | D(B), p(B) | D(D), p(D) | D(E), p(E) | D(F), p(F) | D(G), p(G) |
0 | C | ∞ | 3, C | ∞ | ∞ | ∞ | ∞ |
1 | C, B | 5, B |
| ∞ | 5, B | 4, B | ∞ |
2 | C, B, F | 5, B |
| 8, F | 5, B |
| 11, F |
C->B
C->B->F
STEP 3 : [step 2]에서 현재 경로 중 최소 비용이 되는 경로는 노드 A와 E가 있으므로 N’에 A와 E가 추가됩니다. 이제 알고 있는 노드들(N’의 원소)로 갈 수 있는 노드는 D, G로 두 경로가 있습니다. 나머지 노드는 이미 추가한 노드이므로 표기하지 않습니다.
STEP | N' | D(A), p(A) | D(B), p(B) | D(D), p(D) | D(E), p(E) | D(F), p(F) | D(G), p(G) |
0 | C | ∞ | 3, C | ∞ | ∞ | ∞ | ∞ |
1 | C, B | 5, B |
| ∞ | 5, B | 4, B | ∞ |
2 | C, B, F | 5, B |
| 8, F | 5, B |
| 11, F |
3 | C, B, F, A, E |
|
| 8, F |
|
| 11, F |
C->B
C->B->F
C->B->A
C->B->E
STEP 4 : [step 3]에서 현재 경로 중 최소 비용이 되는 경로는 노드 D가 있으므로 N’에 D가 추가됩니다. 이제 알고 있는 노드들(N’의 원소)로 갈 수 있는 노드는 G 하나만 있습니다. 나머지 노드는 이미 추가한 노드이므로 표기하지 않습니다.
STEP | N' | D(A), p(A) | D(B), p(B) | D(D), p(D) | D(E), p(E) | D(F), p(F) | D(G), p(G) |
0 | C | ∞ | 3, C | ∞ | ∞ | ∞ | ∞ |
1 | C, B | 5, B |
| ∞ | 5, B | 4, B | ∞ |
2 | C, B, F | 5, B |
| 8, F | 5, B |
| 11, F |
3 | C, B, F, A, E |
|
| 8, F |
|
| 11, F |
4 | C, B, F, A, E, D |
|
|
|
|
| 9, F |
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
STEP | N' | D(A), p(A) | D(B), p(B) | D(D), p(D) | D(E), p(E) | D(F), p(F) | D(G), p(G) |
0 | C | ∞ | 3, C | ∞ | ∞ | ∞ | ∞ |
1 | C, B | 5, B |
| ∞ | 5, B | 4, B | ∞ |
2 | C, B, F | 5, B |
| 8, F | 5, B |
| 11, F |
3 | C, B, F, A, E |
|
| 8, F |
|
| 11, F |
4 | C, B, F, A, E, D |
|
|
|
|
| 9, F |
5 | C,B, F, A, E, D, G |
|
|
|
|
|
|
여기서 C에서 G까지의 최소 비용은 9가 되고, 아래는 C의 포워딩 테이블입니다.
목적지 |
Link(Next hop) |
B |
(C, B) |
F |
(C, B) |
A |
(C, B) |
E |
(C, B) |
D |
(C, B) |
G |
(C, B) |
어떤 목적지든 C에서는 다음 목적지가 B임을 알 수 있습니다.
- 다익스트라 알고리즘의 복잡도 : N‘에 없는 모든 노드들을 확인할 필요가 있으며, n개의 노드가 순서대로 살펴지기 때문에 n(n+1)/2 번의 비교횟수를 가진다. ->
- 더욱 효율적인 자료구조를 사용하여 복잡성을 감소할 수 있다. 위의 알고리즘 코드의 9번째 줄에서 w를 찾는데 "힙 자료구조"를 사용하는 것이다. 그 때의 복잡도는 O(nlogn) 가 된다.
▶ 거리 벡터(Distance Vector, DV) 알고리즘
- 벨만 포드 항등식(동적 프로그래밍에 자주 쓰임) : 
c(x, v) : v는 x의 이웃노드이고, x와 v간의 경로 비용을 의미한다.
min{ } : 괄호 안에 계산되어진 값들 중 최소값
(이 때,
- 초기 상태에서 노드는 각 이웃들 간의 최소 거리 비용만 알고 있다.
-위의 그림에서 B에서 G까지의 거리를 벨만 포드 항등식을 사용하여 거리 벡터 알고리즘을 구현해보기
- B의 이웃노드는 A, E, F이므로(C는 G로 갈수 없으므로 제외한다.) 각 노드에서 G까지의 최소 비용 경로는
node B :
-
- 거리벡터 값 (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) 알고리즘 : 노드는 적절하지 못한 “경로 비용”을 알릴 수 있는데, 그럴 때 각 노드의 테이블은 이웃 노드에게 이용되어지며 에러가 네트워크 전역에 전파된다.
'Network > OSI 3-4 계층' 카테고리의 다른 글
| 14. Routing in Internet - 인터넷에서의 라우팅 (0) | 2017.06.11 |
|---|---|
| 12. Software Defined Networking, OpenFlow - 일반화된 포워딩 방식, SDN, 소프트웨어 정의 네트워킹 (0) | 2017.06.05 |
| 11. IPv6 and Tunneling - IPv6 주소 체계와 터널링 기법 (0) | 2017.06.04 |
| 10. Internet Protocol and IPv4 - 인터넷 프로토콜 and IP version 4 (1) | 2017.06.03 |
| 9. Network Layer and Router - 네트워크 계층과 라우터의 기능 (0) | 2017.04.22 |
