5.1 개요
포워딩 테이블이나 플로우 테이블이 어떻게 만들어지고 유지, 설치되었는가?
① 라우터별 제어
: 개별 라우팅 알고리즘이 제어 평면에서 상호작용
- 라우팅 알고리즘들이 모든 라우터 각각에서 동작하는 경우
- 개별 라우터에는 포워딩과 라우팅 기능이 모두 포함
- 각 라우터는 다른 라우터의 라우팅 구성요소와 통신하여 자신의 포워딩 테이블을 계산하는 라우팅 구성요소를 가진다.
ex, OSPF, BGP 프로토콜(5.3, 5.4절)
② 논리적으로 중앙 집중된 제어
: 별개의, 일반적으로 원격에 위치한 컨트롤러가 지역의 제어 에이전트(CA)와 상호작용
- 논리적으로 집중된 컨트롤러가 포워딩 테이블을 작성하고 이를 모든 개별 라우터가 사용할 수 있도록 분포한 경우
- 마치 하나의 중앙 서비스 지점에 있는 것처럼 서비스에 접근한다.
- 부하분산, 방화벽 및 NAT뿐만 아니라 전통적인 IP포워딩 수행
ex, SDN
- 컨트롤러 : 각 라우터의 제어 에이전트(CA)와 상호작용하여 라우터의 플로우 테이블 구성 및 관리
- CA : 컨트롤러와 통신하고 컨트롤러의 명령을 수행하는 최소한의 기능만 가짐
| 라우터별 제어 | 논리적으로 중앙 집중된 제어 |
| 라우터가 직접 테이블을 생성하고 동작 | CA는 서로 직접 상호작용하지 않으며 포워딩 테이블을 계산하는데에도 적극적으로 참여하지 않는다. |
5.2 라우팅 알고리즘
목표 : 송신자로부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로(루트)를 결정하는 것
좋은 경로 = 최소 비용 경로
네트워크 제어 평면이 방식 상관없이 패킷이 전송 호스트에서 수신 호스트로 이동하기 위한 잘 정의된 일련의 라우터가 항상 존재해야한다.
라우팅 문제는 그래프를 사용한다.
그래프 : G = (N, E)
N(node의 집합, 라우터의 집합) : 패킷 포워딩 결정하는 라우터
E(edge의 집합, 링크의 집합) : 하나의 에지는 집합N에 속하는 한 쌍의 노드로 표시, 라우터들 간의 물리 링크
[그림 5.3]
집합 E에 포함된 어떤 에지(x, y)에 대하여
c(x, y) : 노드 x, y간의 비용
에지(x, y)가 집합 E에 속한경우 : 노드 y는 노드 x의 이웃이라한다.
최소비용경로는 하나일 수도 있고 여러개일 수도 있다.
그래프의 모든 에지가 같은 비용을 갖는다면 최소비용 경로는 최단경로가 될 것이다.
첫번째 분류. 라우팅 알고리즘은 중앙집중형과 분산형으로 분류한다.
| 중앙집중형 라우팅 알고리즘 | 분산형 라우팅 알고리즘 |
| - 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산 - 모든 노드 사이의 연결 상태와 링크 비용을 입력값으로 한다. - 연결과 링크 비용에 대한 완전한 정보를 가진다 - 링크 상태 알고리즘(LS) : 전체 상태 정보(링크비용) 를 가지는 알고리즘 |
- 라우터들에 의해 반복적이고 분산된 방식으로 최소비용 계산 - 각 노드는 자신에 직접 연결된 링크에 대한 비용정보만 가짐 - 거리벡터 알고리즘(DV) : 각 노드가 네트 워크 내 모든 다른 노드까지 비용(거리)의 추정값을 벡터 형태로 유지 |
두번째 분류. 라우팅 알고리즘은 정적 알고리즘과 동적 알고리즘으로 분류한다.
| 정적 라우팅 알고리즘 | 동적 라우팅 알고리즘 |
| - 관리자가 네트워크에 대한 정보를 직접 지정하여 라우팅하는 방법 - 아주 느리게 변환 |
- 대규모 네트워크에서 라우터 간 동일한 라우팅 프로토콜 설정하여 변경정보를 자동으로 교환하여 라우팅하는 방법 - 네트워크 변화에 빠르게 대응 - 경로의 루프(loop)나 경로진동에 취약 |
세번째 분류. 라우팅 알고리즘이 부하에 민감한지 아닌지 분류한다.
| 부하에 민감한 알고리즘 | 부하에 민감하지않은 알고리즘 |
| - 링크 비용은 해당 링크의 현재 혼잡 수준을 나타내기 위해 동적으로 변환 - 현재 혼잡한 링크에 높은 비용을 부과하면 혼잡한 링크를 우회하는 경로 선택 ex, ARPAnet |
-링크 비용이 현재의 혼잡을 반영하지 않아 부하에 민감하지 않다. ex, 인터넷 라우팅 알고리즘(RIP, OSPF, BGP) |
5.2,1 링크상태(LS) 라우팅 알고리즘
링크 상태(LS) 라우팅 알고리즘
- 링크 상태 알고리즘의 입력값으로 사용이 가능
Why? 각 노드가 자신과 연결된 링크의 식별자와 비용을 포함하는 링크 상태 패킷을 네트워크 상의 모든 다른 노드로 브로드캐스팅 하게 함으로써 가능하다.
- 링크 상태 브로드캐스트 알고리즘(ex, OSPF)에 의해 수행
- 노드들의 브로드캐스트를 통해 모든 노드는 네트워크에 대한 동일하고 완벽한 관점(view)를 갖게 된다.
링크 상태 알고리즘에는 다익스트라 알고리즘(Dijkstra's algorithm)과 프림 알고리즘(Prim's algorithm)이 있다.
다익스트라 알고리즘
- 하나의 노드(출발지, u)에서 네트워크 내 모든 다른 노드로의 최소 비용 경로를 계산
- k번째 반복 이후에는 k개의 목적지 노드에 대해 최소비용경로를 알 수 있다.
기호
C(x, y) : x에서 y까지 직접적 링크 비용
D(v) : 알고리즘의 현재 반복 시점에서 출발지 노드부터 목적지 v까지의 최소 비용 경로의 비용
p(v) : 출발지에서 v까지의 현재 최소 비용 경로에서 v의 직전 노드(v의 이웃)
N' : 노드의 집합. 출발지에서 v까지의 최소 비용 경로가 명확히 알려져 있다면, v는 N'에 포함된다.
[그림 5.3 네트워크에서 링크 상태 알고리즘을 수행한 결과] - 시험
| 단계 | N' | D(v),p(v) | D(w),p(w) | D(x),p(x) | D(y),p(y) | D(z),p(z) |
| 0 | u | u, 2 | u, 5 | u, 1 | ∞ | ∞ |
| 1 | ux | u, 2 | x, 4 | u, 2 | ∞ | |
| 2 | uxy | u, 2 | y, 3 | y, 4 | ||
| 3 | uxyv | y, 3 | y, 4 | |||
| 4 | uxyvw | y, 4 | ||||
| 5 | uxyvwz |
[그림 5.3 최소 비용 경로의 결과와 네트워크에 대한 u의 포워딩 테이블
노드의 총 수 : n(n+1) / 2
링크 상태 알고리즘의 최악의 경우 : O(n^2)
링크 상태 알고리즘의 효율적인 경우 : O(nlogn)
링크 상태 알고리즘의 문제점
- 링크 비용은 링크상에 전송중인 부하와 같고 이는 패킷이 겪을 수 있는 지연시간을 반영한다.
- 링크 비용은 대칭적이지 않다(경로 진동이 발생)
초기 라우팅 : 노드 d와 노드 b는 a를 목적지로 하는 1단위의 트래픽을 생성하고 노드 c는 e단위의 트래픽을 a에게 보낸다.
다시 수행한 라우팅 : 노드 c는 a로 가는 시계방향의 경로 비용이 1인 반면, (지금까지 사용했던) 경로 비용은 e+1이므로 c에서 a로 가는 최소비용 경로는 시계방향이 된다.
다시 수행한 라우팅 : 노드 b, c, d가 모두 a로 가는 시계 반대 방향의 경로 비용이 0임을 알게 되고 모든 트래픽을 시계 반대 방향으로 보낸다.
다시 수행한 라우팅 : b, c, d가 모두 시계방향으로 트래픽 전송
다음과 같은 진동 문제를 방지하기 위한 방법
1. 링크 비용이 해당 링크가 전달하는 트래픽 양에 의존하지 않게 한다.
매우 혼잡한 링크를 회피하는 것이므로 어려움
2. 모든 라우터가 동시에 링크 상태 알고리즘을 실행하지 못하도록 한다.
시간이 지날 수록 라우터는 서로 동기화한다.
5.2.2 거리 벡터(Distance-Vector, DV) 라우팅 알고리즘
거리 벡터 알고리즘
- 반복적이고 비동기적이며 분산적이다.
분산적(distributed) : 각 노드는 하나나 그 이상의 직접 연결된 이웃으로부터 정보를 받고 계산을 수행하며 계산된 결과를 다시 그 이웃들에게 배포한다.
반복적(iterative) : 이웃끼리 더 이상 정보를 교환하지 않을 때까지 프로세스가 지속된다.
비동기적(asynchronous) : 모든 노드가 서로 정확히 맞물려 동작할 필요가 없다.
- 벨만-포트(Bellman-Ford)식을 통해 다음과 같이 나타낸다.
- dx(y) : 노드 x부터 y까지 최소 비용 경로의 비용
dx(y) = minv{c(x, y) + dv(y)}
x에서 v로 이동한 후 , v에서 y까지의 최소 비용 경로 : c(x, y) + dv(y)
반드시 v를 가는 것부터 시작하므로 minv{c(x, y) + dv(y)} 가 된다.
1. 가장 왼쪽 열 세 개는 x, y, z의 최초 라우팅 테이블 모습이다.
- 각 노드의 라우팅 테이블은 자신과 이웃들의 거리 벡터를 갖는다.
ex, 노드x의 초기 라우팅 테이블의 첫 번째 행 : Dx = [Dx(x), Dy(y), Dx(z)] = [0, 2, 7]
- 최초에는 노드 x가 y와 z로부터 받은 게 아무것도 없으므로 ∞로 초기화한다.
2. 각 노드는 자신의 두 이웃 각각에게 자신의 거리 벡터를 보낸다.
ex, 노드 x는 자신의 거리벡터 Dx=[0, 2, 7]을 노드 y와 노드 z에게 보낸다.
3. 업데이트 수신후 각 노드는 자신의 거리 벡터를 재계산한다.
ex, 노드 x는 다음과 같다.
Dx(x) = 0
Dx(y) = min{c(x, y) + Dy(y), c(x, z) + Dy(z)} = min{2 + 0, 7 +1} = 2
Dx(z) = min{c(x, y) + Dy(z), c(x, z) + Dz(z)} = min{2 + 1, 7 + 0} = 3
Dx = [0, 2, 3]으로 변경되었다.
4. 변화된 거리 벡터를 다시 이웃들에게 보낸다.
- 만약 거리 벡터가 변하지 않았다면 벡터 정보를 보내지 않는다.
ex, 노드 y는 거리 벡터가 변하지 않았으므로 노드 y는 거리 벡터 정보를 보내지않는다.
5. 더 이상의 갱신 메시지가 없을 때 까지 반복한다. 메시지가 없으면 알고리즘은 정지 상태로 대기한다.
거리벡터(DV) 알고리즘: 링크 비용 변경과 링크 고장
[그림 5.7 링크 비용의 변경 - 감소하는 경우]
그림 5.7에서 y에서 x로의 링크 비용이 4에서 1로 감소한 상황이다.
① 시각t0에 y가 4에서 1로 변함을 감지하고 자신의 거리 벡터를 업데이트 후 이웃에게 알림
② 시각t1에 z는 y로부터 업데이트 정보를 받고 자신의 테이블을 갱신한다.
z는 x까지의 새로운 최소 비용을 계산하여 (5에서 2로 변경) 이웃에게 자신의 새로운 거리 벡터를 알림
[그림 5.7 링크 비용의 변경 - 증가하는 경우]
그림 5.7에서 y에서 x로의 링크 비용이 4에서 60으로 증가한 상황이다.
① 링크 비용이 변경되기 전 Dy(x) = 4, Dy(z) = 1, Dz(y) = 1, Dz(x) = 5이다.
시각t0에 y가 비용이 4에서 60로 변함을 감지하고 노드x까지 다음의 비용을 갖는 새로운 최소 비용 경로를 계산
Dy(x) = min{c(y, x) + Dx(x), c(y, z) + Dz(x)} = min{60 + 0, 1+5} = 6
y는 z가 비용 5로 x에 도달할 수 있다고 예상하고 z을 통해 x로 도달하는 잘못된 경로를 지정해준다.
시각t1에 x로 가기 위해 y는 z로 경로를 설정하고 z는 y로 경로 설정을 하는 라우팅 루프가 발생한다.
(y에서 x로가기에 y는 z(1)로 가는게 더 빨라서 z로 왔는데, z는 z→y→x로 가는게 빨라서 다시 y로 감)
② 노드 y는 x까지의 새로운 최소 비용을 계산하므로 t1시각에 z에게 새로운 거리 벡터(y→z(1))을 알린다.
③ z는 y의 새로운 거리 벡터(y→z)를 받고 y에서 x로의 최소 비용(y→z→y→x)이 6이라는 것을 알게 된다.
z는 y에 도달하기 위해 비용 1이 필요한 것을 알 고 있으므로 x로의 새로운 최소 비용을 계산한다.
Dz(x) = min{50+0, 1+6} = 7
x까지의 z의 최소 비용이 증가했으므로 t2 시각에 새로운 거리 벡터를 y에게 알린다.
④ 다음과 같은 방법이 계속 반복되어 Dy(x) = 8을 결정하고 Dz(x) = 9를 결정하며 50보다 커질 때 z는 x와의 직접 연결이
x로의 최소 비용 경로로 결정하게 된다.
거리벡터 알고리즘 : 포이즌 리버스 추가
포이즌 리버스 방법을 통해 라우팅 루프를 피할 수 있다.
z가 y를 통해서 목적지 x로 가는 경로를 설정했다면, z는 y에게 x까지의 거리가 ∞라고 알린다.
[예제, 그림 5.7 링크 비용의 변경 - 증가하는 경우]
① z는 y에게 Dz(x) = ∞라고 말한다. (실제로 z가 Dz(x) = 5임을 알더라도)
② y→ z→ x 경로가 없다고 믿으므로 z→ y→ x로 가는 경로를 사용하는 동안 y→ z→ x 경로를 시도하지 않게 된다.
③ t0시각에 링크 (x, y)의 비용이 4에서 60으로 증가하면 y는 테이블을 갱신하고 x로 직접 라우팅하며 z에게 x로의 새로운 비용 Dy(x) = 60을 알린다.
④ t1시각에 업데이트 정보를 받은 뒤 z는 즉시 x로의 경로를 비용이 50인 직접 연결 (z, x)로 바꾼다. 이 경로는 x로의 새로운 최소 비용 경로이므로 더이상 y를 통과하지 않는다.
⑤ z는 t2 시각에 Dz(x) = 50을 y에게 알린다. y는 업데이트 정보를 받고 거리 테이블을 Dy(x) = 51로 갱신한다.
⑥ z →y→x 최소비용경로 상에 있으므로 t3시각에 Dy(x) = ∞라고 (실제 Dy(x) = 51) z에게 알리면서 z → x 역경로 차단
세 개 이상의 노드를 포함한 루프는 포이즌 리버스로 감지 x
링크 상태 알고리즘과 거리 벡터 라우팅 알고리즘의 비교
| 링크상태 알고리즘(LS) | 거리 벡터 라우팅 알고리즘(DV) | |
| 메시지 복잡성 | - 각 노드는 네트워크 내 각 링크 비용을 알아야한다. -O(|N| |E|)개의 메시지 전송 - 링크 비용이 변할 때마다 새로운 링크 비용이 모든 노드에게 전달 |
- 매번 반복마다 직접 연결된 이웃끼리 메시지 교환 - 알고리즘 결과 수렴하는데 걸리는 시간↑ - 변화된 링크 비용이 연결된 어떤 노드의 최소 비용경로에 변화를 준 경우에만 수정된 링크 비용 전파 |
| 수렴속도 | O(|N|)^2 | 천천히 수렴, 라우팅 루프 발생, 무한 계수 문제 |
| 견고성 (라우어 고장, 오작동, 파손될 경우) |
- 자신의 포워딩 테이블에 대해서만 계산 - 다른 노드들도 유사한 계산을 수행 - 경로 계산이 분산적 수행, 견고성 제공 |
- 라우터는 연결된 링크에 대해서 잘못된 비용 정보를 브로드 캐스트 할 수 있다. - 노드는 전송된 링크 상태 브로드캐스트 부분을 변질 시키거나 폐기 할 수 있다. - 한 노드의 잘못된 계산은 전체로 확산될 수 있다. |
'컴퓨터 네트워크' 카테고리의 다른 글
| 5단원 네트워크 계층: 제어평면-3 (0) | 2022.10.10 |
|---|---|
| 5단원 네트워크 계층: 제어평면 -2 (0) | 2022.10.10 |
| 4단원 네트워크 계층: 데이터 평면 (0) | 2022.10.09 |