디스턴스 벡터/링크 스테이트

[광고 누르면 오늘의 행운 상승!!]

라우팅 프로토콜은 '스태틱 라우팅 프로토콜'과 '다이내믹 라우팅 프로토콜'로 나누어 볼 수 있다. 즉 사용자가 라우터에 목적지에 대한 경로를 직접 넣어주는 방식인 스태틱 라우팅 프로토콜과 라우터가 자동으로 가장 빠른 경로를 찾는 다이내믹 라우팅 프로토콜로 나누어진다.

다이내믹 라우팅 프로토콜도 역시AS(Autonomous System) 안에서 사용되는 IGP(Interior Gateway Protocol)와 AS간에 사용되는 EGP(Exterior Gateway Protocol)가 있다고 말했다. AS는 하나의 네트워크 관리 지침을 따르는 라우터들의 집합이고 AS내부에서 경로 정보를 주고받는 라우팅 프로토콜을 IGP라고 말하는데 RIP, IGRP, OSPF, EIGRP등이 여기 속한다. 또 AS와 AS간에 라우팅을 해줄 때 주로 사용되는 EGP 라우팅 프로토콜에는 BGP가 있다.

또 하나의 라우팅 프로토콜에 대한 분류가 바로 이번에 배우실 디스턴스 벡터 알고리즘(Distance Vector Algorithm)과 링크 스테이트 알고리즘(Link State Algorithm)이다. 즉 라우팅 테이블을 어떤 식으로 관리하는가에 따른 분류라고 생각하면 된다.

먼저 디스턴스 벡터 알고리즘은 말 그대로 디스턴스(Distance, 거리) 와 벡터(Vector, 방향)만 을 위주로 만들어진 라우팅 알고리즘이다. 따라서 라우터는 목적지까지의 모든 경로를 자신의 라우팅 테이블 안에 저장하는 것이 아니라 목적지까지의 거리(홉 카운트 등)와 그 목적지까지 가려면 어떤 인접 라우터(Neighbor Router)를 거쳐서 가야 하는지에 대한 방향만을 저장한다.

따라서 인접 라우터들과 주기적(예를 들면 RIP의 경우 30초에 한 번)으로 라우팅 테이블을 교환해서 자신의 정보에 변화가 생기지 않았는지를 확인하고 관리한다.

이러한 디스턴스 벡터 알고리즘은 한 라우터가 모든 라우팅 정보를 가지고 있을 필요가 없기 때문에 라우팅 테이블을 줄일 수 있어서 메모리를 절약하고, 또 라우팅의 구성 자체가 간단하며, 여러 곳에서 표준으로 사용되고 있다는 장점을 가지고 있다. 반면에 라우팅 테이블에 아무런 변화가 없더라도 정해진 시간마다 한 번씩 꼭 라우팅 테이블의 업테이트가 일어나기 때문에 트래픽을 쓸데없이 낭비하고, 라우팅 테이블에 변화가 생길 경우 이 변화를 모든 라우터가 알 때까지 걸리는 시간(이 시간을 네트워크에서는 Convergence Time 이라고 한다.) 이 너무 느리다. 그림에서처럼 라우팅 테이블의 변화가 생기면 이웃 라우터와 전달, 전달, 전달, 이렇게 일어나기 때문에 라우팅 테이블의 변화를 알아채는 데 걸리는 시간이 길어진다. 뿐만 아니라 이렇게 느린 업데이트 때문에 RIP의 경우는 최대 홉 카운트가 15를 넘지 못하게 되어 있다. 즉 라우터 15개를 넘어서 있는 네트워크는 인식을 하지 못 하는 것이다.

이와 같은 여러 가지 단점 때문에 디스턴스 벡터 알고리즘은 커다란 네트워크에는 적용하지 않는다. 담나 작은 규모의 네트워크에 적용할 경우에는 구성의 편리와 메모리 절약 등의 장점을 살릴 수 있다. 대표적인 디스턴스 벡터 알고리즘은 RIP(Routing Information Protocol)와 IGRP(Interior Gateway Routing Protocol)가 있다. 링크 스테이트(Link State) 알고리즘은 조금 다르다. 즉 이 알고리즘은 한 라우터가 목적지까지의 모든 경로 정보를 다 알고 있다고 생각하면 된다. 그림에서처럼 링크 스테이트 알고리즘은 먼저 링크에 대한 정보(어디에 어떤 네트워크가 있고, 거기까지 가려면 어떤 라우터를 통해야 한다는 정보)를 토폴러지 데이터베이스로 만들게 된다.

이렇게 만들어진 토폴러지 데이터베이스를 가지고 라우터는 SPF(Shortest Path First)라는 알고리즘을 계산하게 된다. SPF는 말 그대로 어디로 가야 가장 빨리갈 수 있는가를 계산하는 것이다. 이 계산 결과를 가지고 라워를 SPF 트리를 만들게 된다. SPF 트리란, 출발지에서 목적지까지를 마치 나뭇가지처럼 펼쳐놓은 후 가장 빠른 경로를 찾아가는 방식이다. 이렇게 트리가 만들어지면 라우터는 그 트리 정보를 이용해서 라우팅 테이블을 만들게 된다.

링크 스테이트 알고리즘은 한 라우터에서 목적지까지의 모든 경로를 알고 있기 때문에 중간에 링크의 변화가 생겨도 이를 알아내는 데 걸리는 시간이 짧다. 또한 이웃 라우터들과 라우팅 테이블을 교환하는 과정에서도 모든 라우팅 테이블을 교환하는 디스턴스 벡터 방식과는 달리 라우팅 테이블의 교환이 자주 발생하지 않고, 또 교환이 일어나는 경우에도 테이블에 변화가 있는 것만들 교환하기 때문에 트래픽 발생을 줄여줄 수 있다.

하지만 링크 스테이트 방식의 경우 라우터가 모든 라우팅 정보를 관리해야 하기 때문에 메모리를 많이 소모하게 되고, 또 SPF 계산 등 여러 가지 계산을 해야 하기 때문에 라우터 CPU가 일을 많이 해야 한다. 따라서 링크 스테이트 알고리즘은 커다란 네트워크에 설치되는 고용량 라우터에 적용하는 것이 바람직하다. 대표적인 링크 스테이트 알고리즘에는 OSPF(Open Shortest Path First)라우팅 프로토콜이 있다.

요약.

라우팅 테이블을 유지 관리하는 방식은 크게 2가지로 나눌 수 있는데, 하나는 디스턴스 벡터이고, 또 하나는 링크 스테이트 방식이다. 디스턴스 벡터는 거리와 방향만 유지하며 라우터는 이웃 라우터와 주기적으로 라우팅 테이블을 교환한다. 이 방식은 메모리가 적게 들고 구성이 쉽지만 링크 변동 시 인식 시간이 길고 네트워크 크기(홉카운트)에 제한이 있다. 링크 스테이트는 라우터가 목적지까지의 모든 경로를 알기 때문에 링크 변동에 따른 인식이 빠르고, 라우팅 테이블의 교환 주기가 길며, 교환 시에도 링크 변동이 일어난 라우팅 테이블만 교환하기 때문에 트래픽이 적다. 또한 대형 네트워크에 적합하다. 하지만 메모리의 소모가 많고 CPU의 로드가 많다.