Hierarchical Routing
계층적 라우팅
- Core Network(Backbone)의 라우터부터 Local Network의 라우터까지, 각 라우터마다의 라우팅 테이블에 계층적 구조를 적용한 모델을 말한다.
- 각각의 라우터에서는 하위 계층 네트워크의 세부 사항을 고려하지 않음으로써, 라우팅 테이블의 엔트리 수를 줄여 처리 속도를 높인다.
- Regional ISP에서 Small ISP의 Customer까지에 이르는 계층적 라우팅 형태를 도식화한 것이다.
- Regional ISP는 120.14.64.0/18 주소(\(2^{14}\)개 주소)를 할당받아 4개의 Block으로 Subnetting한다.
(4개의 Block으로 Subnetting했으므로, 네트워크 필드에 2Bit가 추가된다.)
- Local ISP는 할당받은 주소를 다시 8개의 Block으로 Subnetting하여 Host(Customer)들에게 제공한다.
(8개의 Block으로 Subnetting했으므로, 네트워크 필드에 3BBit가 추가된다.)
- Small ISP들의 라우팅 엔트리 개수 = 128개의 호스트 + Default Router = 129개의 엔트리
- Local ISP1의 라우팅 엔트리 개수 = 8개의 Small ISP + Default Router = 9개의 엔트리
- Local ISP2의 라우팅 엔트리 개수 = 4개의 대형 기관 + Default Router = 5개의 엔트리
- Local ISP3의 라우팅 엔트리 개수 = 16개의 소형 기관 + Default Router = 17개의 엔트리
- Regional ISP = 3개의 Local ISPs + Default Router = 4개의 엔트리 (사용되지 않는 주소는 고려하지 않는다.)
- 수 단계의 계층을 거쳐도 라우팅 테이블의 엔트리 개수가 그리 많지 않음을 확인할 수 있다.
- 상위 계층의 라우터에서는 하위 계층의 네트워크의 많은 주소들을 하나로 간주하는 Aggregation을 수행하기 때문에 처리 속도를 높일 수 있다.
- 라우팅 테이블에서 패킷의 주솟값을 보고 적절한 라우팅 엔트리에 매칭시키는 대표적인 방법으로는 Longest Match Algorithm(가장 긴 부합 알고리즘)이 있다.
- 하지만, Longest Match Algorithm은 Mask를 기준으로 정렬되어 있는 엔트리를 Sequential Searching 하는데 평균적으로 \({n \over 2}\) 시간이 걸려, 실행 시간 측면에서 불리하다.
- 실제 라우터의 라우팅 테이블에서 주소와 엔트리를 매칭시키는 알고리즘은 검색과 더불어 엔트리 삽입/삭제 연산에도 용이한 형태로 복잡하게 구현되어 있다.
(실제 라우팅 테이블은 엔트리 삽입/삭제에 용이하도록 Mask를 기준으로 정렬하지 않는다. 정렬을 해놓을 시, 삽입/삭제에 소요되는 시간이 커지기 때문이다.)
Reference: TCP/IP Protocol Suite 4th Edition
(Behrouz A. Forouzan 저, McGraw-Hill, 2010)
Reference: Data Communications and Networking 5th Edition
(Behrouz A. Forouzan 저, McGraw-Hill, 2012)
