The primary role of routers is to forward packets toward their final destinations. For this purpose, a router must decide for each incoming packet where to send it next. More exactly, the forwarding decision consists of finding the address of the next-hop router as well as the egress port through which the packet should be sent. This forwarding information is stored in a forwarding table that the router computes based on the information gathered by routing protocols. To consult to the forwarding table which port is proper for the packet to go out, the router uses the packet's destination address as a key; this operation is called address lookup. Once the forwarding information is retrieved, the router can transfer the packet from the incoming link to the appropriate outgoing link, in a process called switching.
The exponential growth of the Internet has stressed its routing system. While the data rates of links have kept pace with the increasing traffic, it has been difficult for the packet processing capacity of routers to keep up with these increased data rates. Specifically, the address lookup operation is a major bottleneck in the forwarding performance of today's routers.
This paper starts with a survey of the algorithms for efficient IP address lookup. And, we propose several new address lookup scheme enhancing the performance. We start by tracing the evolution of the IP addressing architecture. The addressing architecture is of fundamental importance to the routing architecture, and reviewing it helps us to understand the address lookup problem. Then, we propose and explain the basic approach to the address lookup. The basic idea is distributed lookup of address. Also, we modified the basic scheme into the realistic scheme by changing some parameters and lookup method partially. Moreover, we propose the necessity of small size memory and the method to save memory.
네트워크 라우터는 최종목적지까지 패킷을 포워딩하는 역할을 담당한다. 이를 위해 각 라우터는 어느 포트를 통해 패킷을 전달할지 결정을 하여, 다음 라우터나 노드의 MAC주소를 붙여 내보내는데, 이러한 일련의 과정을 포워딩이라 한다. 출력포트의 결정은 라우팅 프로토콜에 의한 라우팅 테이블을 참조하여 이루어지게 되는데, 적절한 라우팅 정보를 찾기위해 포워딩 테이블을 검색한다. 이 과정을 IP주소 검색이라 한다.
인터넷 트래픽의 증가는 이러한 라우팅 시스템의 고속화를 유도하였고, 이로 인하여 링크속도의 증가, 고속 스위칭 구조, 빠른 주소검색을 필요로 했다. 특히 주소검색은 이러한 전송패스에서 병목지점이 되어, 많은 연구가 진행중에 있다.
본 논문은 기존의 IP 주소검색 방법을 검토하고, 이러한 방법에 한계가 있음을 인지한 후에, 우선 기존 주소검색 방법 및 접근방법에 대한 성능 비교를 수행하고, 기존의 방법들에 대한 문제점과 주소 검색에 대한 새로운 접근을 시도한다. 기존 문제점을 극복하기 위하여 하드웨어 기반의 병렬처리를 이용한 새로운 IP 주소 검색 방법을 제안하였고, 이 방법이 적절하게 동작함을 보인다. 또한, 실제 라우터에 적용했을 때, 이에 대한 성능분석 및 시뮬레이션을 수행한다. 마지막으로 기본적으로 제안된 IP 주소 검색 방법은 검색 속도만을 고려 하여 설계하였기 때문에, 중복된 메모리를 사용하여 메모리 낭비가 심한데 이를 줄이기 위한 개선방법을 제안하고, 이에 대한 성능을 평가한다.
