본문 바로가기

Information Network

Network Layer : Routing Protocols(라우팅 프로토콜)-Unicast Routing Protocols-Distance vector routing

라우팅 프로토콜에는 유니캐스트 라우팅 프로토콜과 멀티캐스트 라우팅 프로토콜이 있다.

이번 포스트에서는 유니캐스트 라우팅 프로토콜의 거리 벡터 라우팅에 대해서 알아보자.

유니캐스트 라우팅 프로토콜에 대해서 알아본 후에 멀티캐스트 라우팅 프로토콜에 대해서 알아보자!





Unicast Routing Protocols


라우팅 테이블은 정적이거나 동적일 수 있다. 정적 테이블은 수동으로 작업해야하지만, 동적 테이블은 인터넷의 어딘가에 변경이 발생하면 자동적으로 갱신할 수 있다.때문에 거대한 요즘의 인터넷망에는 동적 라우팅 테이블을 사용한다. 

라우팅 프로토콜은 동적 라우팅 테이블에 대한 요구에 반응하기위해 만들어졌다. 즉, 라우팅 프로토콜은 인터넷에 있는 라우터들이 서로의 변경사항을 알릴 수 있는 규칙과 절차들의 조합이라고 할 수 있다. 





Optimization


라우터는 네트워크로부터 패킷을 수신하고 이 패킷을 다른 네트워크로 전달하는 역할을 한다.

그렇다면 수신한 패킷을 어떤 네트워크가 전달하게 될까?
이 결정은 최적화를 기본으로 한다. 그렇다면 어떤 경로가 최적의 경로이고, 또 최적이란 용어의 정의는 무엇일까!

하나의 접근법은 네트워크 경로에 대한 cost를 할당하는 것이다.

우리는 이 cost를 metric이라 부른다. 한편 각 네트워크가 할당된 metric은 protocol의 유형에 따라 다르다.

RIP
와 같은 몇몇 간단한 protocol은 모든 네트워크를 동일하게 간주하여, 하나의 네트워크를 통해 전달되는 cost는 1hop으로 동일하다. 그래서 만약 패킷이 10개의 네트워크를 통해 목적지에 도달하면 전체 cost는 10hop이 된다.  

OSPF
와 같은 protocol들은 필요로 하는 서비스 유형에 근거하여 네트워크를 통해 전달되는 cost를 관리자가 할당할 수 있게 한다. 하나의 네트워크를 통한 경로는 서로 다른 cost(metric)을 가질 수 있다.

예를 들어, 최대 처리량이 원하는 서비스 유형일 때 위성 링크가 광케이블보다 더 낮은 metric을 갖는다. 반면에 최소 지연이 원하는 서비스 유형이면 광케이블이 위성 링크보다 더 낮은 metric을 갖게 된다.  

BGP
에서 판단을 위한 척도는 관리자에 의해 정의되는 정책이된다. 이 정책은 어떤 경로가 선택되어야 하는가를 정의한다.







Autonomous System(AS, 자율 시스템)


오늘날 인터넷은 매우 거대해져서 하나의 라우팅 프로토콜이 모든 라우터의 라우팅 테이블의 갱신 작업을 처리할 수 없다. 때문에 인터넷은 AS(자율시스템)로 나누어지는데, AS는 단일한 관리권에 있는 네트워크와 라우터들의 그룹으로 구성된다. 

AS내에서의 라우팅은 intradomain routing(도메인 내 라우팅),
AS간의 라우팅은 interdomain routing(도메인 간 라우팅)이라고 한다.
 
각각의 AS는 AS내에 있는 라우팅을 처리하기 위해 하나 이상의 intradomain routing protocol을 채택할 수 있다. 그러나 AS간의 라우팅 처리를 위해서는 오직 하나의 interdomain routing protocol을 사용해야 한다.



실상 intradomain routing & interdomain routing table에는 여러 종류가 있지만, 그 중에 가장 많이 사용되는 몇가지에 대해서만 알아보자.(아래 그림 참조)

 




Distance Vector Routing

distance vector routing에서 임의의 두 node 사이의 최소 cost 경로는 최소 거리 경로이다. 이름에서 의미하듯 이 protocol에서 각 node는 모든 node에 대한 최소 거리 벡터 테이블을 관리한다. 또한 각 노드의 테이블은 경로상의 다음 정거장을 보여줌으로써 요구된 노드로 패킷을 안내한다. (Next-hot routing)

예를 들면, 노드를 어느 지역의 도시로, 선을 각 도시를 연결하는 도로로 생각해보자. 그렇다면 테이블은 각 도시 간의 최소 거리를 여행자에게 보여줄 수 있다.

아래 그림은 다섯 개의 노드와 해당 테이블을 갖는 시스템을 보여준다.


위 테이블에서 A 노드는 노드 E로 가기 위한 최소 cost는 6으로써 노드 C를 경유해서 간다는 것을 의미한다.


Initialization
위 그림의 각 노드는 다른 노드로 가는 방법과 비용을 알고 있는 안정된 상태이다. 그러나 위 그림은 초기상태는 아니며, 초기상태에서의 각 노드는 오직 자기 자신과 직접적으로 연결된 immediate neighbors에 대한 거리만 알 수 있다.

그 순간 각 노드는 neighbors에게 메시지를 전달할 수 있고 자신과 인접 이웃 간의 거리를 찾을 수 있다고 가정한다. 이때 자신의 neighbors이 아닌 경우는 일단 cost값을 ∞로 설정한다. 
 
초기상태는 다음과 같다.
 



Sharing
초기 상태에서 각 노드들은 자신의 테이블을 업데이트 시키기 위하여 자신의 라우팅 테이블을 immediate neighbors과 주기적이고 변경사항이 있을 때 공유를 통한 방법을 이용한다.

이때 Network의 크기(hop number)에 따라서 Update에 완료되는 시간이 달라진다. 노드가 많다면 그만큼 라우팅 테이블을 완성하는데 오랜 시간이 걸리게 되는 것이다.

그렇다면 sharing은 언제 수행되는 것일까?

일단 주기적으로 수행이 되는 경우는 매 30초마다 한 번씩 수행이 되며, 이와는 다르게 neighbors의 라우팅 테이블이 변경되었다던가, neighbors중 link가 끊어진 곳이 발생할 경우에는 즉시 sharing이 수행(triggered update)된다.


Two-Node Loop Instability
distance vector routing의 문제점은 불안정성이다.  이는 해당 프로토콜을 사용하는 네트워크는 불안정해질 수 있다는 것이다.

다음과 같은 시나리오를 살펴보자.



위와 같은 상황(우회 경로가 없음에도 불구하고 서로간에 우회경로가 있다고 생각하고 loop가 생성되는 문제)이 발생한다면 몇가지의 해결책이 존재한다.

그중에 하나는 무한대 정의(Defining infinity)이다. 무한대를 더 작은 수로 재정의 함으로써 loop의 depth를 줄이는 것이다. 사실 대부분의 distance vector routing protocol의 응용은 각 노드 사이의 거리를 1로, 무한대를 16으로 정의한다. 이로 인하여 distance vector routing을 큰 시스템에서는 사용할 수 없다.

또 수평분할(Split Horizon)을 이용하는 방법이 있다. 각 인터페이스를 통해 테이블을 flooding하는 대신, 각 노드는 각 인터페이스를 통해 자신의 테이블의 일부분만 전송한다.

수평분할 전략을 사용하는 것은 하나의 단점을 갖고 있다. 때문에 포이즌 리버스(Poison reverse)전략과 함께 사용하기도 한다.

포이즌 리버스란 라우트 포이즈닝(특정 네트워크가 다운 되면 해당 네트워크의 metric 값을 16으로 설정하여 인접 라우터에게 광고함으로써 그 네트워크가 다운 되었다는 것을 알림)을 수신한 라우터는 자신에게 다운된 네트워크에 대한 대체경로가 있는지 계산한 후 대체 경로가 없을 시 라우트 포이즈닝을 보내온 라우터에 metric 값을 16으로 포이즌 리버스를 보낸다. 포이즌 리버스를 수신한 라우터는 즉시해당 경로를 삭제하게 된다.



Three-Node Loop Instability 
2-노드 불안정은 수평분할 전략과 포이즌 리버스를 조합하여 피할 수 있지만 3개의 노드사이에 불안정하면 안정성을 보장받지 못한다.




RIP
라우팅 정보 프로토콜(Routing Information Protocol)은 자율 시스템 내에서 사용되는 도메인내 라우팅 프로토콜이다. 이는 거리벡터 라우팅에 기반한 매우 간단한 프로토콜로써, 다음과 같은 특징을 갖는다.

RIP의 metric은 목적지에 도달하기 위한 링크수로 정의된다. 이러한 이유로 metric은 hop count라고 불린다.

16으로 무한대를 정의하여 RIP를 사용하는 자율 시스템에서 어떤 경로도 15hop을 넘을 수 없다.

next hop 열은 패킷이 목적지에 도달하기 위해 전달되어야 할 라우터의 주소를 정의한다.