[Network] 네트워크 계층 : 라우팅(Link-State Routing)

라우팅 알고리즘의 목표는 송신자로부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로를 결정하는 것이다.

일반적으로 좋은 '경로'란 최소 비용 경로를 의미한다. 그러나 현실적으로는 네트워크 정책('Y'기관에 속해있는 라우터 x는 'Z'기관이 보낸 패킷을 전달해서는 안된다.)과 같은 실제 문제가 고려된다.

 

---

라우팅 알고리즘을 분류하는 일반적인 방법

1. 중앙 집중형 vs 분산형

중앙 집중형

네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산하는 알고리즘이다. 이러한 정보는 알고리즘이 실제로 계산을 수행하기 전에 어떠한 방법을 통해서라도 얻어야 한다. 계산 자체는 한 장소에서 수행하거나 각각의 라우팅 모듈로 복사될 수 있다.

이 알고리즘의 핵심은 연결과 링크 비용에 대한 완전한 정보를 가진다는 점이다. 전체 상태 정보를 가지는 알고리즘을 링크 상태(Link-State, LS)알고리즘이라고 한다.

 

분산형

최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다. 어떤 노드도 모든 링크의 비용에 대한 완전한 정보를 갖고 있지 않다. 대신 각 노드는 자신에게 직접 연결된 링크에 대한 비용 정보만을 가지고 시작한다. 이후 반복된 계산과 이웃 노드와의 정보 교환을 통해 노드는 점차적으로 목적지 또는 목적지 집합까지의 최소 비용 경로를 계산한다.

이러한 방식으로 최소 비용을 결정하는 알고리즘을 거리 벡터(Distance-Vector)알고리즘이라고 부른다.

 

---

2. 정적 vs 동적 

정적 라우팅 알고리즘

경로가 아주 느리게 변하는 경우이다. 종종 사람이 개입(직접 링크 비용을 수정)한 결과로 그렇게 된다.

 

동적 라우팅 알고리즘

네트워크 그래픽 부하나 위상 변화에 따라 라우팅 경로를 바꾼다. 동적 알고리즘은 주기적으로, 혹은 토폴로지나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행된다.

 

---

3. 부하에 민감하다 vs 부하에 민감하지 않다

부하에 민감한 알고리즘

링크 비용은 해당 링크의 현재 혼잡 수준을 나타내기 위해 동적으로 변한다.

 

부하에 민감하지 않은 알고리즘

오늘날의 인터넷 라우팅 알고리즘(RIP, OSPF, BGP)은 링크 비용이 현재의 혼잡을 반영하지 않는다.

 

 

---

링크 상태(LS) 라우팅 알고리즘

라우터는 전체 네트워크 상태에 대한 정보가 필요하다. 따라서 라우터들은 자신이 알고있는 정보들을 다른 라우터들과 교환하려고 한다.

정보를 교환하기 위한 패킷을 LSA(Link-State-Advertisement)라고 한다.

 

LSA(Link-State-Advertisement)

기본적으로 2가지 정보가 들어간다.

1. 현재 링크들의 연결 상태(끊어짐/안끊어짐)

2. 지연시간 or 현재 남아있는 용량

 

라우터들은 자신의 이웃이 바뀌었을때, 새로운 라우터가 연결 되었을 때 등의 상황에 LSA를 생성한다.

만들어진 LSA는 자신이 속한 네트워크에 있는 모든 라우터들한테 전송된다.

그렇게 LSA를 라우터들 끼리 공유하게 되고,  전체 네트워크 상태를 구성할 수 있게 된다.

 

전체 네트워크 상태를 알고 있다면, 최소 비용 경로를 구하기 위해서 대표적으로 다익스트라(Dijkstra)알고리즘을 사용한다.

 

---

다익스트라 알고리즘을 사용해 경로를 구하는 과정

U -> Z 까지 가는 최소 비용 경로

 

		D(v)	D(w)	D(x)	D(y)	D(z)
Step	N'	p(v)	p(w)	p(x)	p(y)	p(z)
0	u	7, u	3, u	5, u	INF	INF
1	uw	6, w		5, u	11, w	INF
2	uwx				11, w	14,x
3	uwxv				10, v	14, x
4	uwxvy					12, y
5	uwxvyz

 

1. step0 : 시작점 U와 연결된 라우터만 살펴보고 해당 라우터까지의 최소 비용을 갱신해준다. 직접적으로 갈 수 없는 경우에는 INF 값으로 설정한다. 예를 들어 U에서 V로 가는 경우에 7의 비용이 들고, V로 가기 직전의 노드는 U이므로 7, u로 설정해준다.
2. step1 : step0에서 가장 적은 비용이 드는 노드는 비용이 3인 w이므로, 다음 경로는 w로 선택하고 모든 경로의 비용을 갱신해준다.
3. step2 : step1에서 아직 방문하지 않았으면서 가장 비용 적게 드는 노드는 5인 x이므로, 다음 경로는 x로 선택하고 모든 경로의 비용을 갱신해준다.
4. step3 : step2에서 아직 방문하지 않았으면서 가장 비용 적게 드는 노드는 6인 v이므로, 다음 경로는 v로 선택하고 모든 경로의 비용을 갱신해준다.
5. step4 : step3에서 아직 방문하지 않았으면서 가장 비용 적게 드는 노드는 10인 y이므로, 다음 경로는 y로 선택하고 모든 경로의 비용을 갱신해준다.
6. step5 : step4에서 아직 방문하지 않았으면서 가장 비용 적게 드는 노드는 5인 x이므로, 다음 경로는 x로 선택하고 모든 경로의 비용을 갱신해준다.

 

---

거리 벡터(Distance Vector) 라우팅 알고리즘

링크 상태 알고리즘이 네트워크 전체 정보를 이용하는 알고리즘인 반면에, 거리 벡터 알고리즘은 반복적이고 비동기적이며 분산적이다.

 

각 노드는 하나나 그 이상의 직접 연결된 이웃으로부터 정보를 받고, 계산을 수행하며, 계산된 결과를 다시 그 이웃들에게 배포한다는 점에서 분산적이다.

 

이웃끼리 더이상 정보를 교환하지 않을 때까지 프로세스가 지속된다는 점에서는 반복적이다.

 

 

위 그림은 거리 벡터 알고리즘의 직관적인 동작과정을 나타낸 그림이다.

 

각 행의 1번째 열은 각 노드가 초기에 가지고 있는 연결 정보를 테이블로 나타낸 것이다.

 

(x 노드를 기준으로 설명) 

2열에서 노드 y와 z가 가진 테이블의 초기 값(1열) 정보를 받는다. x는 x, y, z의 초기 연결 정보를 모두 갖게 되고, 이를 토대로 자신의 라우팅 테이블을 최적화 한다.

기존에 x -> z로 가는 비용은 '7'이었지만 y에서 z로 가는데 '1'의 비용이 든다는 정보를 통해서 x -> y -> z 로 가게되면 비용이 3임을 깨닫고 비용을 갱신하게 된다.

 

3열도 위 과정과 마찬가지로,

각 노드의 2열의 값을 받고 비용을 최적화해서 갱신한다.

 

---

거리 벡터 알고리즘의 무한 계수 문제(Count-to-Infinity Problem)

1. 링크 x-y의 비용이 변경되기 전에 D(y-x)=4, D(y-z)=1, D(z-x)=5 이다. 

   시각 t0에 y가 링크 비용 변화를 감지하고 (비용이 4 -> 60으로 변함) 노드 x까지 다음의 비용을 갖는 새로운 최소 비용 경로를 계산한다.

D(y-x) = min(D(y-x) + D(x-x), D(y-z) + D(z-x)) = (60 + 0, 1 + 5) = 6

D(x-z)의 비용은 링크 x-y의 비용이 변경되기 전의 값인 D(y-x)=4에 의존하고 있었다.

하지만 아직 D(x-z)의 비용이 갱신되기 전에 D(y-x)의 비용이 갱신되는 바람에 D(y-x)는 잘못된 정보를 가지고 최소 비용을 갱신하게 된다.

 

2. 노드 y는 x까지의 새로운 최소 비용을 계산했으므로 z에게 새로운 거리 벡터를 알려준다.

 

3. z는 y의 새로운 거리벡터를 받고, y에서 x로의 최소 비용이 6이라는 것을 알게 된다. z는 y에 도달하기위해 1의 비용이 든다는 사실을 알고있으므로 D(z-x)의 새로운 최소비용 (1 + 6) = 7을 계산한다.

 

4. 비슷하게 y는 z의 새로운 거리 벡터를 받는다. y에서 z까지의 비용이 1이고, D(z-y)값이 7임을 받았으므로 D(y-x)=8로 결정하고 다시 z에게 새로운 거리벡터를 알려준다. 이렇게 프로세스가 반복된다.

 

언제까지 반복될까?

z의 y를 통한 경로 비용 값이 50보다 커질 때까지 루프를 반복할 것이다.

만약 링크 비용 D(y-x)가 10000으로 바뀌고, D(z-x)가 9999였다면 엄청난 반복을 하게 될 것이다.

 

---

포이즌 리버스(Poison Reverse)

위에서 설명한 무한 루프를 해결할 수 있는 방법이다.

만약 z가 y를 통해서 x로 가려고 하는 경로 설정을 했다면, z는 y에게 x까지의 거리가 무한대라고 알린다.
즉, z는 y에게 D(z-x)=INF 라고 말한다.

 

1. D(y-x)의 비용이 60으로 변하면 D(z-x)가 INF이므로 D(y-x)의 값은 60이 되고, z노드에게 벡터를 알려준다.

2. z노드는 D(z-x)=50이 D(y-x)=60보다 작기 때문에 D(z-x) 벡터를 y노드에게 알려준다.

3. y노드는 x노드로 가기위해서 z노드를 거쳐가야 함을 바로 알게되고, D(y-x) = 51로 갱신할 수 있다.

4. 그리고 z를 통과하는 경로이기 때문에 z에게는 D(y-x) = INF라고 알려준다.

 

포이즌 리버스는 단순히 직접 이웃한 두 개의 노드가 아니라 세 개 이상의 노드를 포함한 루프는 감지할 수 없다.