네트워크 프로그래밍 - Unicast Routing Protocols, Distance vector routing

Unicast Routing Protocols

router가 routing table을 만드는 과정에 대해서 알아보자.

 

Autonomous systems

인터넷에서 네트워크와 네트워크가 하나로 묶이는 단위를 AS라고 한다. 

AS간에도 경로설정이 가능하다.

 

Intradomain은 domain안에서의 경로설정에 관련된 일로 경로설정과 관련된 방법 Distance vector와 Link state 두 가지가 있고, 각각의 개념을 이용한 RIP, OSPF 프로토콜이 있다.

 

Interdomain은 domain끼리의 경로설정에 관련된 일로 Path vector를 이용한 BGP라는 프로토콜이 있다.

 

Intradomain은 위 Autonomous systems 그림에서 AS에서 다른 AS로 연결되는 router, 즉 게이트웨이까지의 최단경로를 구하는 역할을 한다. 

 

AS 그림을 다시보면,

위 그림에서 AS끼리 이동하는 경우 예를 들어 R1에서 R3로 갈 때, R1에서 R2를 거쳐 R3로 가는 경우가 있는데, 

AS내의 경로를 설정하는 Intradomain의 경우 최단경로를 기준으로 routing table을 작성하지만,

Interdomain의 경우 특정 rule을 base로 경로를 설정한다. rule은 전달하는 패킷 수나 혼잡 등 여러가지 기준을 통해서 설정된다.

 

The fact behind Bellman-Ford algorithm

bellman-ford 알고리즘은 Intradomain의 Distance vector에 사용되는 알고리즘이다.

 

위 그림에서 i에서 j까지의 최단경로를 알아보자. 

c_in과 D_nj는 알고있는 값이라고 하였을 때, 각 경로들의 c + D 거리들 중 최소값이 i에서 j까지의 최단거리인 것이다. 

 

이를 Pseudo code로 나타낸 것은 다음과 같다.

 

Distance vector routing tables

위 그림에서 A table을 보자.

A, B, C, D는 경유없이 바로 갈수 있는 경우이고, E로 가는 데 C를 경유하는 방법이 최단거리임을 알고 있다. 

각각의 노드로 가는 경로에 대해 최단거리 cost가 적혀있다. 

위 table들이 만들어지는 과정을 알아보자.

 

Initialization of tables in distance vector routing 

위 그림은 아직 직접적으로 연결되어있는 것 끼리만 table에 표시하고 나머지는 cost를 무한으로 설정해놓은 상태이다. 

B의 경우 D로 가는 경로가 결정되지 않았는데, A로부터 D로 가는 거리를 B에게 알려주면 B가 A를 경유한 경로로 저장하고, 다른 노드로부터 D로 가는 경로가 전달되더라도 B가 이미 가지고 있던 D로 가는 경로의 최단거리보다 크면 무시하면 된다. 

이러한 방식으로 노드끼리 정보를 주고받으면서 table을 완성한다.

 

Updating in distance vector routing

update하는 과정을 보자.

A는 C로부터 각각의 노드로 전달하는데 걸리는 cost들을 받고 임시로 C를 next로 설정해놓는다. 

한 줄 씩 비교해보아 A에서 C를 거쳐 각 노드로 이동하는 cost가 A의 old table의 cost보다 작으면 대입한다.

위 그림의 겨우 A의 old보다 A의 modified (C경유)에서 E를 가는 경우 C를 거쳐가는 경로가 더 cost가 적으므로 E에 대한 경로내용이 수정된 새 table을 만든다.

 

실제로 이 routing table들은 다음과 같이 구성된다.

 

 

example

A에서 B로 각각의 Net에 대한 정보를 전달한다.

Net1에 대한 정보를 B로 전달하면 B의 table에는 없는 정보이므로 다음과 같이 갱신한다.

 

A에서 Net2에 대한 정보를 B로 전달하면 cost가 더 낮은 경우가 아니므로 다음이 갱신하지 않는다.

 

A에서 Net4에 대한 정보를 B로 전달하면 B의 table에는 없는 정보이므로 다음과 같이 갱신한다.

 

A에서 Net5에 대한 정보를 B로 전달하면 B의 table에는 없는 정보이므로 다음과 같이 갱신한다.

 

즉 다음과 같이 B의 routing table이 변화하게 된다.

 

 

 

만약 위 그림과 같은 경우에서 C의 table이 수정되어 E로가는 cost가 4→7로 변경되었다고 가정하자.

그러면 A에서 C를 통해 E로 가는 cost는 9가되어 A의 new table의 기존 cost보다 높지만 갱신해야한다.

이미 table에서 next가 정해져있는 경로의 정보가 next node로부터 수정되어 전달되면 cost가 기존보다 높더라도 갱신해야한다. 

A의 new table의 next인 C로부터 E로가는 cost가 변경되어 A→C→E 경로의 cost가 9로 cost가 기존보다 높지만 갱신해야하는 이유이다.

전달된 정보의 next가 기존과 다른 경우에는 cost가 기존보다 낮은 경우에만 갱신한다.

 

Two-node instability

After failure

X에서 A로의 링크가 failure 즉 끊어졌을 때, A의 table에서는 X로의 cost가 무한대로 설정된다.

 

update가 되는 경우는 두 가지이다.

정보를 주기적으로 교환하거나, 수정이 될 경우 교환한다.

 

After A receives update from B

X에서 A로의 링크가 끊어졌을 때, B에게 정보를 알려주면 B의 table을 수정할 수 있지만, 그러기 전에 B로부터 A에게 먼저 정보를 전달하여 수정되면 문제가 발생한다. 

그림의 경우 B로부터 X로 가는 경로에 대한 정보를 받고 next다 다른데 cost가 더 작으므로 A의 table이 수정된다. 

 

After B receives update from A

A의 table이 수정되고 B로 정보를 전달하면, B에서는 A table의 정보를 받고, 같은 next이므로 cost가 4(3+1)로 더 크더라도 그림과 같이 table이 수정된다.

이와 같은 상황에서 B에서 A로 가기 위해 패킷을 전달하면 A와 B간에 loop가 발생한다. 

이와 같은 상황을 Two-node instability라고 한다.

 

Finally

loop에서 router에서 지정한 패킷의 cost만큼 이동을 거치다가 cost를 초과하여 detect되면 그때서야 잘못됨을 알 수 있다.

 

1. 이를 해결하기 위해 16을 무한대로 간주한다. 16이라는 숫자만큼 이동하는 것은 네트워크 상에서 매우 오래걸리는 것이므로 16을 무한대로 간주하여 16번 전송하게 되면 detect하게 된다.

 

2. 또는 split horizon이라는 방법을 사용한다.

위와 같은 two-node instability 상황은 B가 정보를 여러 노드들에 전달할 때 next에 해당하는 노드에는 해당 정보를 보내지 않는 것이다.

위 그림에서는 B가 A가 next인 정보를 제외한 정보만 A 노드에게 전달하는 것이다. 

 

3. split hozion & poison 방식은 B가 A에게 next가 A인 정보를 보내주되, cost를 무한대로 하여 보내는 방법이다. 

받는 A의 입장에서는 B가 무한대를 통해 자신을 next로 하였음을 알 수 있다.

 

Three-node instability

Before failure

B와 C는 A가 가르쳐준 정보를 통해 table을 update한 상태이다.

 

After A sends the route to B and C, but the packet to C is lost

X와 A사이의 링크가 끊어진 상황이다. A의 table이 update되었기 때문에 

A가 B,C에게 route를 전달하여 B는 X로의 cost가 무한대로 update되고 C로의 packet은 손실되었다. 

 

After C sends the route to B

이러한 상황에서 C가 B에게 route정보를 전달하면 X/3/C가 전달되는데, B는 next가 다르고 cost가 더 적으므로 X/3/C로 update하게된다. 

 

After B sends the route to A

B가 A에게 table 정보를 전달하면 X/4/B가 전달되고, A는 기존의 X/∞/- 와 next도 다르고 cost도 적으므로 X/4/B로 update하게 된다. 

이 상황에서 A로 패킷이 들어오면 A,B,C간에 loop가 일어날 것이다.