정보처리기사 필기 - 제4과목 프로그래밍 언어 활용 (2020 개정)
라우터 프로토콜을 위한 자료구조의 분석 및 성능 평가 요 약 통신 및 네트워크 사용자의 중가와 실시간 처리를 요하는 멀티미디어 데이터 서비스의 중가로 인하여 네트워크 트래픽이 중가하고 서비스 품질 저하 및 접속 속도의 감소가 초래되고 있다. 이러한 문제를 해걸하기 위하여 라우터의 용량이 확장되고 있으나,라우터의 용량확장에 따른 테이블의 크기 중가는 경로 선택올 위한 검색 시간 중가를 초래하므로, 라우팅 태이블의 구성방식에 대한 연구가 필요하다. 본 논문은 TCP/IP 기반의 라우팅 프로토콜을 관리하는 Zebra 소프트웨어를 이용하여. 라우팅 테이블의 구조와 구성방식에 대하여 분■석하고, 비교 알고리즘을 제시하여 성능 비교 및 평가를 하고자 한다. 1. 서 론 최근 인터넷 사용이 기하급수적으로 증가하고 요구되는 어플리케이션 종류가 다양해짐 따라,멀티미디어 데이터의 이동량이 확산되고 있으며, 네트워크 트래픽 증가로 서비스 품질의 저하 및 접속 속도의 감소가 초래되고 있다. 이러한 제반적인 문제-!- 해결하기 위하여 서비스 제공자는 초고속 기간망올 구축해야만 되는 상황에 이르렀으며, 대용량 트래픽올 수용할 수 있는 보다 막강한 고성능 네트워크 장비가 필요하게 되었다. 이에 따라 네트워크에 사용되고 있는 기존의 스위치나 라우터를 이용하여 이 문제를 해결 하기에는 여러 가지 문제점 및 한계성이 존재하므로 기존의 라우터 보다 용량이 크면서 두 장비(스위치, 라우터)의 기능을 동시에 제공할 수 있는 장비 가 검토되 고 있다. 라우터는 동일한 전송 프로토콜을 사용하는 분리된 네트워크를 연결해주는 장치로 네트워크 계충간을 서로 연결하며. 다양한 네트워크 관리 기능을 수행한다. 또한 라우터나 기타 다른 인터-네트워킹 장치의 라우팅 테이블은 네트워크상 특정 목적지까지의 경로를 유지하여 여러 경로중 가장 효율적인 경로를 제공한다. 따라서 라우터의 용량확장은 라우팅 테이블의 크기 중가 및 효율적인 경로 선택을 위한 검색시간 중가를 초래하게 되므로, 라우팅 테이블의 구성 방식은 새로이 검토 되어야 할 필요성 이 있다. 본 논문은 프리 소프트웨어인 Zebra를 분석하여 기존 라우팅 테이블의 구조와 구성방식에 대하여 분석하고, 비교 알고리즘올 제시하여 성능 비교 및 평가를 하고자 한다. 본 는문은 제 1장 서론, 제 2장에서는 관련연구 동향 343 Copyright (C) 2005 NuriMedia Co., Ltd. 제3장은 라우터의 자료구조인 라우팅 테이블 분석. 제4장은 라우팅 테이볼 구성 알고리즘의 성능평가에 관하여 기술하고, 마지막으로 5장에서 결론을 맺는다. 2. 관련연구 Zebra 는 TCP/IP 를 기반으로 하는 라우팅 프로토콜을 관리하는 프리 소프트웨어로서, 하나의 프로토콜당 하나의 프로세스를 사용하며. BGPfflorder Gateway Protocol) 와 OSPF(Open Shortest Path First) 그리고 RIP(Routing Information Protocol)의 라우팅 프로토吾을 지원한다. 라우팅 프로토콜은 크게 기업의 근거리 통신망과 같은 자율 네트워크 내의 게이트웨이들 간의 라우팅 정보-i교환하는데 사용되는 프로토콜인 IGP(Interior Gateway Protocol)와 내부적으로 IGP틀 사용하여 도메인 간을 연결하는 인터넷 라우팅 프로토콜인 EGP (Exterior Gateway Protocol)로 나눌 수 있다. 작은 규모의 네트워크에 주로 사용되는 RIP와 대규모 계충적 구조에서 사용되는 OSPF가 IGP에 속하고, EGP로는 BGP를 에로 들 수 있다.[1,3,6,7! 그림 1은 Zebra의 구조로, 각 라우팅 프로토콜들은 Zebra라는 라우팅 메니저를 통하여 라우팅 테이블을 접근한다. 3. 라우팅 테 이블의 구조와 구성 라우팅 테이블의 구조는 Radix 알고리즘을 이용한 20이년도 한국정보과학회 가을 학술발표논문집 Vol. 28. No. 2 3.2 라우팅 테이블의 구성 라우팅 테이블은 2진 기수법올 사용하는 Radix 씻? 알고리즘을 적용하고 있으며. 비트값에 따라 분배한다. Kernel [그림 1] Zebra의 구조 이진 트리 형태를 이루고 있으며,여러 필드를 포함 하고 있는 노드들로 구성되어 있다. [그림 3] 라우팅 테이블의 구성 에 3.1 라우팅 테이블의 구조 라우팅 테이블올 이루고 있는 각 노드들온 라우팅에 필요한 정보들을 유지하고 있으며, 이는 그림 2에서 보는 것과 같이 크게 P, table, parent, link, lock, aggregate로 이루어져 있디.. ᅵ . . " ■ I # # 甲 纏 . ' ,, . . [그림 2] 라우팅 테이볼의 노드구조 P필드는 fami!y, safi, prefbden, padding, 니로 구성 되 어 있으며, table과 parent는 테이블과 부모를, link는 '0'과 M'의 값에 따라 좌촉과 우측 자식노드를 가리킨다. Jock필드는 각 노드의 히트 수晉 나타내며, lock이 '0'의 값욜 가지게 되면 노드를 삭제하게 된다. info 와 aggregate 필三는 패킷 전송에 관한 정보와 IP Address/IP Network Mask 로 정해진 범위 값을 가리킨다. ① family : IP 버전(AF_INET, AFᅳ INET6. AFJJNSPEC ) ② safi : unicast, multicast 지원에 관한 정보 ③ .prefixlen : prefix 길이 ④ padding : 패킷의 사이즈률 마쳐수기 위해 덧붙이는 padding 정보 ⑤ u : prefix, prefix4(AFJNET), prefix6(AF_lNET6), Ip(AFJJNSPEC), val 첫번째는 2 진 Radix 알고리즘을 적용하여 이진트리 344 Copyright (C) 2005 NuriMedia Co., Ltd. 그림 3은 라우팅 테이블의 간단한 구성 예로 이진 트리 형태를 이루고 있으며,라우팅 테이블은 prefix와 prefix iength에 의해 분배된다. 즉 추가하려는 노드의 prefix 중 이미 존재하는 노드의 prefix iength+1 의 위치의 비트가 기수 값이 되어 방일 때는 좌측 니'일 때는 우측으로 분배된다. 예를 들어, 그림 3의 prefix 값이 127.182.113.10°H prefix length가 32인 노드 A가 존재하지 않는다고 가정 할 때, 이 노드를 추가 시기는 과정은 다음과 같다. ① 루트 노드의 prefix length 값은 방 이 므로 A의 prefix 첫번째 비트에 의해 좌측노드로 이동하게 된다. ② 좌축 노드의 prefix length는 ' 8' 이므로 8비트,즉 1바이트를 A와 비교한다. ③ 1바이트가 1 127' 로 같고 A의 9비 S 값이 1이므로 우측 노드로 이동하게 된다. © 우측 노드의 prefix length가 ' 24' 이므로 3바이트를 A와 비교한다. © 3바이트가 127,182,113으로 같고 A의 25비트 값이 ' 0,이므로 좌측노드로 이동하게 되나 좌측노드가 존재하지 않으므로 이 위치에 노드를■추가하게 된다. 위의 결과 그림 3의 라우팅 테이볼을 얻을 수 있다. 그러나, 이며 위와 같이 구성된 라우팅 테이블에 다시 prefix 와 prefix length 가 127.182.133.2/32인 B를 또 다시 추가 하게 되면 A의 위치와 충돌하게 된다. 따라서 A와 B의 마지막 같은 비트값을 갖는 위치까지를 prefix length로 하는 부모노드를 생성하여 추가 시킨 다음 A와 B를 재배치 시켜야 한다. 즉 prefix와 prefix length가 127.182.133.0/27인 C 노드를 생성하여 A 와 B 의 부모노드로서 원래 A의 위치에 위치 시켜야 한디■. 3,3 라우팅 테이블의 구조와 구성 방식에 따른 문제점 라우팅 테이블이 Radix 알고리즘을 적용한 이진트리 형태를 구성됨에 따라 여러 문제점을 가지고 있다. 20이년도 한국정보과학회 가을 학술발표논문집 Vol. 28. No. 2 형태를 가지기 때문에 트리의 깊이가 길어진다. 즉, 추가, 삭채 등의 업데이트 과정에 었어서 보다 많은 트리의 노드를 순회하여야 하며, 보다 많은 비교 연산을 수행하여야 한다. 두 번째는 트리가 가지는 일반적인 문제점으로 균형성을 들 수 있다. 트리의 균형성이 깨져 한쪽 방향으로 경사를 이루게 되면 그 만晉의 평균 접근 시간이 중가한다. 세 번째 문제는 위에선 언급했던 추가적인 부모노■드의 생성이다. 이는 불필요한 노드의 생성에시 오는 기억공간의 낭비와 그로 인해 접근해야 하는 노드 수의 중가로 탐색속도의 증가를 초래하게 된디.. 따라서 보다 적합한 구조와 구성 알고리즘의 필요하다. 4. 라우팅 테이블 구성 알고리즘의 성능평가 본 논문에서는 Radix 알고리즘올 이용하여 구성된 이진트리 형태의 라우팅 테이블의 성능평가를 위하여 MLH{Modified Unear Hashing)을 비교 대상으로 선택 하였다. MU1 은 ᄂinear Hashing이 정적으로 메모리를 할당함에 따라 생기는 메모리 낭비를 줄이기 위해 동적으로 변형한 것으로, 검색 시 이진트리 탐색이 루트롤 경유해서 순차적으로 검색하는 반면에 MLH 은 해심함수에 의해서 직접 또는 찾는 값에 인접한 노드부터 검색을 수행하기 때문에 검색시간을 줄일 수 있으며,충돌이 없을 경우 이진트리에 비해 삽입 삭제할 노드의 위치를 빨리 찾을 수 있어 효율적이나,충돌이 발생했을 경우 충돌회비를 위헤서 추가연산이 필요하게 된다. [2,4,5] 4.1 성능평가 방법 알고리즘의 성능 평가틀 위하여 PTM(Performa:\ce Test Manager)이란 모델을 설계하였다. PTM은 라우팅 테이블을 접근 및 제어 할 수 있는 TC(Table Controller)와 임의의 '1P를 생성할 수 있는 PG(PreJix Generator) 를 가지고 있으며, 이를 이용하여 두 알고리즘으로 구성된 테이블을 제어하게 된다. 그림 4는 Radix 알고리즘과 MLH의 테이블의 노드 수와 시간과의 관계를 나타낸 것으로, 임의의 IP를 가지고 라우팅 테이블을 생성하는데 걸리는 시간과 생성된 테이블의 메모리를 해제하는데 걸리는 시간을 측정한 것이다. 그림 4에서 보는 것과 같이 MLH온 테이블에 15000개의 IP-f 추가하여 라우팅 테이블을 생성 할 때까지는 Radix 알고리즘에 비해 테이블의 생성 시간과 해제 시간이 직게 걸리나, 추가 하려는 IP의 수가 20000개 이상에는 Radix 알고리즘이 보다 적은 시간을 보여 주고 있다. 이는 MLH이 1P1: 추가 할 때 충돌이 발생하여 분할을 하는데 걸리는 시간이 증가하기 때문이다. MLH Radix [그림 4] 생성시간 과 추가 1P 수 임의의 내를 추가 했을 때 라우팅 테이블의 노드들의 수와 사용된 메모리를 측정한 결과,MLH은 추가적인 노드의 생성이 존재하지 않지만 Radix 알고리즘은 노드를 추가할 때 발 허수노드가 발생하여 추가하려 는 IP의 수가 ] 00000일때 약 30000개의 허수 노드가 발생하는 것을 볼 수 있다. 5. 결론 본 논문에서 Zebra라는 프리 소프트웨어를 이용하여 라우팅 테이블의 구조와 구성방식을 분석하였으며, 성능분석을 위하여 !^니4를 비교 알고리즘으로 선택하였고,PTM모델을 설계 하였다. 위에서 언급한 것과 같이 Radix 알고리즘은 MUH보다 많은 메모리의 낭비가 발생하나,탐색 시간은 Ml서보다 적게 걸리는 것을 발견할 수 있다. Radix 알고리즘을 적용한 라우팅 테이블의 문제점과 성능분석을 토대로 추후에 대체 알고리즘에 대한 연구가 필요하다. 참고문헌 [1] Kunihiro Ishiguro,“The GNU Zebra Manual,” internet-draft, July 2000. [2] Michael A. Harrison, James T.DeWolf, “Computer Algorithms introduction to Design and Analysis second edition,” p.83-89, August 1993, [3] C. Hedrick, “Routing Information Protocol/' RFC 1058, June 1988. [4] Per—Ake Larson, ^Performance Analysis of Linear Hashing with Partial Expansions,” ACM Transactions on Database System, Vol. 7, No. 4, December 1982. [5] Per-Ake Larson, “Dynamic Hash Tables,” Communications of the ACM, Vol. 31, No. 4, April 1988, [6] J. Moy, “OSPF Version 2,” RFC 1583,March 1994. [7] Y. Rekhter, 丁.J. Watson, T. Li, “A Border Gateway Protocol 4 (BGP-4X” RFC 1771, March 1995. 345 Copyright (C) 2005 NuriMedia Co., Ltd.