Basic Security/_Networks2008.01.25 13:51
라우팅 알고리즘(Routing Algorithm)


라우팅 알고리즘은 네트워크를 통해 정보 이동 시, 최적의 경로를 결정하기 위한 방식이다. 즉, 정보를 목적지까지 전송하기 위해서 인접한 라우터들의 네트워크 정보와 메트릭 값을 받아 최적의 경로를 설정하는 과정이다. 메트릭(Metric)은 라우터는 인접한 라우터로부터 전달받은 경로정보로 비용을 계산하여 최적의 경로를 결정하는데, 이 비용계산에 영향을 미치는 요소들을 의미한다. 홉수(Hop Count), 대역폭(Bandwidth), 지연(Delay), 신뢰도(Reliability), 부하(Load) 등이 있다.

라우팅 알고리즘에는 다음과 같은 요구사항이 필요하다.
  • 정확성(correctness)
  • 단순성(simplicity)
  • 견고성(robustness)
  • 안정성(stability)
  • 공정성(fairness)
  • 최적성(optimality)
이러한 라우팅 알고리즘으로 구현되는 라우팅 프로토콜에는 일반적으로 거리벡터(Distance Vector) 알고리즘의 RIP, IGRP, EIGRP 등과, 링크상태(Link State) 알고리즘의 OSPF, NLSP 등이 있다.


테이블 관리 방법에 따른 분류
라우팅 테이블 관리 방법에 따라 정적 라우팅(Static Routing)과 동적 라우팅(Dynamic Routing)으로 나눌 수 있다.

정적 라우팅은 네트워크 관리자가 직접 목적지 별로 네트워크 경로를 지정하는 방식이다. 관리자가 변경하지 않을 경우 테이블의 내용은 변하지 않는다. 정적 라우팅즘은 상대적으로 네트웍 설계가 간단하고 네트웍 트래픽 예측이 쉬운 환경에 적절하다. 그러나 네트웍의 상황이 변하였을 경우 관리자는 다시 적당한 환경을 설정해야 하므로 네트워크 변화가 심할 경우나 큰 네트워크에서는 부적합하다. 그리고 네트워크의 한 노드가 동작하지 않을 경우 우회경로를 이용하지 못한다.

동적 라우팅은 네트워크의 변동된 정보를 라우터간에 자동으로 교환하여 업데이트 하는 방식이다. 자동으로 정보를 전달 받으므로 어떠한 네트워크의 장애가 발생하더라도 능동적으로 대처가 가능하다. 동적 라우팅은 정적 라우팅 보다 설정 방법은 매우 간단하지만 정적 라우팅보다 대역폭 및 라우터 리소스를 더 많이 소모하게 된다. 동적 라우팅 프로토콜은 RIP, IGRP, EIGRP, OSPF, ISIS 등이 있다.  


범위에 따른 구분
네트워크 집합간의 관리와 연결에 따라 내부(Interior) 라우팅 프로토콜과 외부(Exterior) 라우팅 프로토콜로 구분한다.

사용자 삽입 이미지

  1. AS(Autonomous System)
    독자적인 관리체계와 동일한 운영 정책을 가지는 네트워크의 집합이다. (e.g. ISP)
  2. IGP(Interior Gateway Protocol)
    하나의 AS 내에서 라우팅 정보를 교환하는데 사용되는 프로토콜이다. (e.g. RIP, IGRP, EIGRP, OSPF, IS-IS)
  3. EGP(Exterior Gateway Protocol)
    AS와 AS 간에 라우팅 정보를 교환하는데 사용되는 프로토콜이다. (e.g. BGP4)


프로토콜 지원 수에 따른 분류
사용할 수 있는 네트워크 프로토콜의 수에 따라 단일(Single) 라우팅 프로토콜과 다중(Multi) 라우팅 프로토콜로 분류할 수 있다.

단일 라우팅 프로토콜은 네트워크 프로토콜(IP, IPX, Appletalk) 중에서 하나의 네트워크 프로토콜만 지원하는 라우팅 프로토콜이다. (e.g. RIP, IGRP/EIGRP, OSPF, BGP)

다중 라우팅 프로토콜은 네트워크 프로토콜(IP, IPX, Appletalk) 중에서 두 개 이상의 네트워크 프로토콜을 지원하는 라우팅 프로토콜이다. (e.g. EIGRP)


정보 교환 방법에 따른 분류
정보 교환 방법에 따라 거리 벡터(Distance Vector) 라우팅 프로토콜과 연결 상태(Link State) 라우팅 프로토콜로 분류할 수 있다.

거리 벡터 라우팅 프로토콜은 일정 시간마다 이웃에 위치한 라우터와 경로 정보(Hop Count)를 교환하여 최적 경로를 설정하는 방식이다. 교환되는 정보는 라우팅의 모든 정보를 교환하며, 이웃 라우터의 정보와 자신의 정보를 비교하여 적은 값으로 라우팅 테이블을 갱신한다. 알고리즘은 간단하지만 일정 시간이 링크 상태의 변화보다 느릴 경우 링크 상태의 변화에 적절히 대응하기 어렵다. 또한 많은 량의 정보가 브로드캐스트 되어 이동하므로 대규모 네트워크에 부적합하다. (e.g. RIP, IGRP)

링크 상태 라우팅 프로토콜은 홉수는 물론 지연, 속도, 네트워크 위상 등의 다양한 변수를 고려하여 링크 상태가 변할 때마다 모든 정보를 고려하여 최적의 경로를 계산, 전송하여 트래픽을 줄이고 거리 벡터 방식의 단점을 극복하기 위해 개발된 프로토콜이다. 최단 거리 알고리즘을 사용하여 라우터에 대한 비용을 직접 계산한다. (e.g. OSPF, NLSP)

Posted by Proneer

댓글을 달아 주세요