균형 이진 탐색 트리를 이용한 빠른 라우팅 테이블 검색 방법
A Fast Routing Table Lookup Method using AVL Tree
4
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
인터넷 망은 데이터를 목적지 주소로 전송할 때 라우터 별로 라우팅 테이블을 참조하여 데이터를 전송하므로 라우팅 테이블의 구성 방법에 따라 경로 탐색의 속도가 달라질 수 있다. 라우터에서 빠른 경로 검색은 라우터의 라우팅 성능에 큰 영향을 미치므로 라우팅 테이블을 구현하는 알고리즘이 중요한 역할을 한다. 속도 문제를 해결하기 위해 TCAM(Ternary Content Address Memory)과 같은 하드웨어를 이용한 방법이 많이 사용되고 있지만 라우팅 테이블의 규모가 커지면 하드웨어 비용이 증가하는 단점이 있다. 본 논문에서는 기존의 라우팅 테이블을 이용한 AVL 트리 구조로 IP 주소를 재배열하여 목적지 주소의 경로 탐색을 보다 빠르게 할 수 있는 라우팅 테이블 구성에 관한 알고리즘을 제안하여 경로 탐색 시간을 줄이고 소프트웨어로 라우터의 성능을 향상시키는 방안을 제시하고자 한다.
Abstract
When data are being delivered to the destination IP address over the Internet, the routing performance may be varied by routing table access algorithm since the path information of the network is acquired by accessing the routers’ routing tables. Therefore, the routing table access algorithm plays an important role in routing. In order to solve the speed problem and increase the routing performance, a kind of hardware solutions such as TCAM(Ternary Content Address Memory) are often used. However, there is a disadvantage of price increase as the size of routing tables become massive. This paper suggests a new routing table access algorithm which uses AVL(Adelson-Velskii and Landis) tree to rearrange IP addresses in order to decrease the time it takes to acquire path information for delivering data through a router.
참고문헌 (11)
- F. Baker, "Requirements for IPv4 Routers, RFC 1812", ~ (1995)
- C.D. Stormon, "A generalpurpose CMOS associative processor IC and system", IEEE Micro, 12(6), pp.68~78 (1992)
- Anthony J. McAuley, "Fast Routing Table Lookup Using CAMs", INFOCOM '93. Proceedings.Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies (1993)
- Tzi-cker Chiueh, "High-Performance IP Routing Table Lookup UsingCPU Caching", INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 3, pp.1421~1428 (1999)
- Robert Sedgewick, "chapter 15: Balanced Trees, In Algorithms", pp.199~ (1983), Addison-Wesley
- Donald Knuth, "Section 6.2.3: Balanced Trees, In The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition", pp.458~481 (1998), Addison-Wesley
- Donald Knuth, "Big Omicron and big Omega and big Theta", SIGACT News, pp.18~24 (1976)
- G. Adelson-Velskii, "An algorithm for the organization of information", Proceedings of the USSR Academy of Sciences, 3, pp.1259~1263 (1962)
- 유재형, "SDN", OpenFlow 기술동향 및전망, 2013, pp.15(2), ~
- Stefan Nilsson, "Fast address lookup for Internet routers", Proceedings of "Algorithms and Experiments", pp.9~18 (1998)
- M. Waldvogel, "Scalable high speed IP routing lookups", ACM Computer Communication Review, 27(4), pp.25~36 (1997)