Various contents and multimedia services have been supplied to many people through WWW(World Wide Web) which is accessed conveniently by using any kind of web browsers. So, the Internet becomes really a necessary tool for the mass of people to gather information and to enjoy their cultural life. As the Internet gets popularity like this, the number of hosts connecting to it increases exponentially. The appearance of new multimedia services and increment of hosts and users mean that the amount of traffic passing the Internet becomes very large volume. Hence, the previous Inter-net infrastructure which supply low bandwidth for data service, has been much stressed. Also, quality of services is degraded because multimedia applications consume most of the network bandwidth.
Approaches enhancing quality of services for the Internet applications are classified into three directions. The first approach is to substitute trans-mission medium from copper wires to optical fibers which offer much higher bandwidth capacity. However, even if physical medium become very fast, their bandwidth would not be useful when a router's packet processing capacity is low. This is because routers are interconnecting nodes between a network and another network. In this case, routers become bottleneck points of high speed communications, and the overall performance of entire networks cannot be improved. If router's packet processing capacity increases to the degree fully utilizing the bandwidth supplied by transmission medium, various applications serviced on the Internet will be serviced much better than now. And this is the second approach to enhance quality of services of the Internet. The third approach is to change protocol from the pure IP (Internet Protocol) to the more sophisticated protocols which can supply quality of services. RSVP (Resource Reservation Protocol), IntServ (Integrated Service), and DiffServ (Differentiated Service) are the good examples of these protocols.
In this thesis, we will focus on the second problem above, that is, enhancement of router's packet processing capacity. Generally, a router ex-tracts many fields from an incoming packet's header, and guides the packet to reach its final destination rightly using the extracted information. The major functionality of a router can be divided largely into three parts. They are 1) IP address lookup which determines the output port of an incoming packet, 2) switching process which moves the packet from the input port to the proper output port, and 3) output buffer scheduling. For switching and output buffer scheduling schemes, much studies have been proceeded and the results are satisfactory. However, though much studies also have been performed for the low cost and high speed IP address lookup schemes, the results are not satisfactory. Hence, an IP address lookup process is considered as the bottle-neck point of the packet processing inside the router. To improve the overall performance of the Internet, we should raise the router's packet processing capacity. And to promote the router's packet processing capacity, we should speed up the IP address lookup process. Consequently, we can assert that an IP address lookup process is very important technology to improve the overall performance of the Internet.
An IP address lookup is one of the representative applications of 1-tuple packet classification. In this thesis, we study on the general packet classificalion problem as backgrounds and survey the architecture of the traditional and today's routers. We also study on the IP address lookup problem more closely. We survey many previously proposed IP address lookup schemes and classify them into a few categories. Then we compare the perfomances of these schemes. Also, we analyze the routing tables which are the snopshots of the real backbone routers' routing tables. This analysis give us hints in designing new IP address lookup solutions. Based on these studies, we propose new IP address lookup schemes that solve the LPM problem. The proposed IP address lookup solution can be implemented with simple hard-ware logic. It requires only two memory accesses to finish an IP address lookup in the worst case and consumes less memory space than the one that required by the previous hardware based lookup solutions.
인터넷을 이용하는 사용자들과 호스트의 수가 급증함에 따라서, 이제 인터넷은 공중 패킷 통신망의 사실상 표준으로 그 위상이 정립되어 가고 있다. 인터넷에 접속된 호스트의 수는 최근 2년 사이에 3배로 증가하였고, 서비스 제공을 수행하는 웹서버의 수는 평균 6개월 이내에 2배씩 증가하는 추세이다. 2002년 1월을 기준으로 볼 때, 약 147.3백만대의 호스트가 인터넷에 접속되어 있는 것으로 보고되고 있다. 사용자 및 호스트 수의 급증은 WWW(World Wide Web)을 통한 다양한 컨텐츠 및 멀티미디어 서비스에 기인한다고 볼 수 있다. 또 역으로 인터넷을 통한 다양한 서비스가 값싸게 제공됨으로 인해서 이를 이용하는 사용자들이 늘어난다고도 볼 수 있다. 수 많은 사용자들이 인터넷에 접속함에 따라서 인터넷 서비스 제공자들은 인터넷을 상업적인 기반로 사용하기 시작하였다. 각종 멀티미디어 및 컨텐츠 서비스가 유료화되기도 하고, 동영상 광고를 하기도 한다. 그리고 계속해서 사용자들의 요구에 부응하기 위하여 새로운 패러다임의 서비스를 창출하려고 노력하고 있다. 이와 같은 각종 서비스들은 기존의 텍스트 위주의 데이터 서비스로는 불가능하며 비디오 및 오디오를 기반으로 하는 멀티미디어 서비스를 통하여 제공될 수 있다.
사용자 및 호스트 수가 크게 증가하고, 멀티미디어를 기반으로 하는 새로운 인터넷 서비스가 제공됨으로 인해서 사용자들은 인터넷을 통하여 보다 나은 서비스들을 받을 수 있게 된 반면, 망 운영자 입장에서는 이러한 서비스들이 무리 없이 동작할 수 있는 환경을 제공해야 하는 부담을 가지게 되었다. 서비스의 향상 및 사용자들의 증가는 인터넷을 통과하는 트래픽 양의 증가를 의미한다. 또한 멀티미디어 서비스는 그 자체로 많은 트래픽을 유발시킬 뿐만 아니라, 일반 데이터 트래픽과는 다르게 일정 수준의 서비스 품질을 요구하기도 한다. 또한 ADSL(Asynchronous Digital Subscribe Line)과 같은 고속 통신망이 많은 가정에 보급됨에 따라서 사용자들이 인터넷에 접속하는 접근망의 평균 속도도 급격히 빨라지고 무선 통신이 인터넷과 접목됨으로써 계속해서 더 많은 인터넷 트래픽이 유발되고 있다.
이상과 같은 환경의 변화에 대처하기 위해서는 인터넷 하부구조의 방대한 성능 향상이 절실히 요구된다. 현재 인터넷의 성능 향상은 크게 세가지 방향에서 수행되고 있다. 그 첫번째는 구리선과 같은 기존의 전송 매체를 광섬유등과 같이 높은 대역폭을 제공하는 전송 매체로 교체하는 것이며, 두번째는 패킷들을 처리하는 라우터의 성능을 크게 향상시키는 것이다. 그리고 마지막으로 최선 서비스(best-effort) 서비스만을 제공하는 현재의 인터넷 프로토콜인 IP(Internet Protocol)를 대체하여, 사용자들에게 보다 나은 서비스를 제공할 수 있는 새로운 프로토콜을 개발하는 것이다. 현재의 인터넷은 인터넷 프로토콜인 IP Version 4를 사용한다. 하지만 인터넷을 이용하는 사람들과 호스트의 수가 증가하고 다양한 서비스가 제공됨으로 인해서 IP는 심각한 문제를 드러내게 되었다. 가장 대표적인 문제점은 각 호스트에게 할당되는 주소가 부족하게 되었다는 점이다. 이는 IP Version 4가 처음 개발될 당시, 인터넷 인기의 폭발적인 증가세를 예측하지 못했기 때문이다. IP version 6는 주소 공간을 IP Version 4의 32비트에서 128비트로 넓힘으로써 이 문제를 해결한다. 두번째 문제점은 IP Version 4에는 서비스 품질을 고려할 만한 어떠한 프로토콜 동작도 포함되지 않았다는 점이다. 따라서 최근 서비스 품질을 요구하는 다양한 멀티미디어 서비스들에 대해서 적절히 대처하지 못한다. 이 문제를 해결하기 위해서 RSVP(Resource Reservation Protocol), IntServ(Integrated Service), 그리고 DiffServ(Differentiated Service)와 같이 IP Version 4 망상에서 서비스 품질을 제공하기 위한 복잡하고 다양한 프로토콜들이 제안되기도 하였다. 그러나 이상의 고급 프로토콜들이 인터넷 망의 전체 성능을 향상시키기 위해서는 거의 모든 현재의 인터넷 라우터들이 서비스 품질 기능을 제공하는 새로운 라우터들로 교체되어야 하므로 망을 구축하는데에 있어서의 부담이 너무 커진다. 따라서 새로운 프로토콜들은 제대로 확산되지 못하고 있는 실정이다.
인터넷의 서비스 품질은 망의 패킷 전송률을 현저히 증가시키고, 전송지연을 현저히 줄임으로써 일정수준까지 끌어 올릴 수 있다. 패킷 전송률을 증가시키기 위해서는 전송 매체를 고속화하고 인터넷의 패킷 처리기인 라우터의 성능을 크게 향상시켜야 한다. 전송 매체의 고속화는 광섬유를 이용하는 광통신 기술의 발전으로 계속해서 발전하고 있다. 하지만 라우터의 성능은 광통신 기술이 제공하는 대역폭을 충분히 이용할 만큼 빠르게 발전하지 못하고 있다. 전송 매체가 제공하는 대역폭을 모두 사용하지 못할 정도로 느린 패킷 처리 능력 때문에 라우터는 고속 통신의 병목 구간이 되었다. 따라서 라우터의 성능을 향상시키지 않는 한 고속 인터넷 통신은 불가능하다. 다시 말해서 라우터가 인터넷 성능을 좌우하는 중요한 요소가 된 것이다.
라우터는 입력되는 패킷의 헤더로부터 여러가지 정보를 추출하고 처리한다. 또한 라우터는 해당 패킷의 목적지 주소에 따라 하나의 인터넷 망에서 다른 망으로 패킷을 전송하는 역할을 수행한다. 라우터는 크게 네가지 구성 요소로 이루어지는데, 그것들은 1) 라우터 프로세스와 2) 패킷이 들어오는 입력 링크, 패킷을 내보내는 출력 링크, 3) 입/출력 링크를 연결해주는 스위칭 회로, 그리고 4) 전송 엔진이 그것들이다. 전송 엔진은 패킷의 목적지 주소와 출력 링크를 대응시켜 주는 포워딩 테이블을 참조하여 패킷의 출력 링크를 결정한다. 이러한 작업을 IP 주소 검색이라고 하며 이는 1차원 패킷 분류의 대표적인 응용이다. IP 주소 검색은 입력된 패킷의 목적지 주소만을 이용하여 출력 링크를 결정하지만, 가상 사설망(VPN : Virtual Private Network)이나 방화벽과 같은 경우는 목적지 주소뿐만 아니라, 근원지 주소 및 상위 계층의 프로토콜 정보, 포트 정보등을 이용하여 출력 링크를 결정하기도 하는데 이러한 동작을 n차원 패킷 분류라고 한다. 상위 계층의 정보를 이용하여 출력 링크를 결정하기 위해서 라우터는 IP 계층 이상까지 처리해야 하므로 성능이 더 떨어질 것이다. 따라서 높은 처리 성능이 요구되는 인터넷 백본망에서는 IP 계층의 목적지 주소만을 이용해서 출력 링크를 결정하는 1차원 패킷 분류만을 주로 수행하고 n차원 패킷 분류는 백본망에 연결된 작은 망 내부에서의 라우터에서 수행될 수 있다.
라우터 내에서 입력 패킷의 출력 링크를 결정하기 위한 작업을 일반적으로 "패킷 분류"라고 한다. 입력 패킷에서 하나의 정보만을 이용하여 패킷을 분류하고 전송하는 대표적인 예가 IP 패킷의 포워딩이며 이미 언급했듯이 이는 1차원 패킷 분류의 대표적인 응용이라고 할 수 있다. IP 패킷 포워딩을 위해서 라우터가 수행해야 하는 일은 크게 보아 세가지로 나눌 수 있는데, 그것들은 1) 포워딩 테이블을 이용한 IP 주소 검색, 2) 스위칭 작업, 그리고 3) 출력 스케줄링들이 그것들이다. 스위칭 작업의 경우, 그 동안 많은 연구가 진행되어 왔으며 고속 버스, 크로스바 스위치와 같은 기술들이 ATM(Asynchronous Transfer Mode) 스위칭을 위해서 개발되었다. 출력 스케줄링 역시 많은 연구가 진행되었으며 공정 스케줄링 기술등이 스케줄링의 성능을 향상시키고 있다. 하지만 IP 주소 검색은 라우터의 성능에 있어서 아직까지 병목 구간으로 남아 있다. IP 주소 검색이 어려운 이유는 IP 패킷의 목적지 주소와 라우터 내부의 포워딩 테이블을 이용하여 해당 패킷의 출력 링크를 결정할 때, 최장 프리픽스 일치(Longest Prefix Match) 연산을 수행하기 때문이다. 다시 말해서 패킷의 목적지 주소와 일치하는 엔트리가 포워딩 테이블 내부에 여러개가 존재할 수 있고, 그 중에서 가장 길게 일치하는 프리픽스 엔트리의 출력 링크 정보를 이용해야만 해당 패킷이 올바른 목적지에 도달할 수 있는 것이다. 최장 프리픽스 일치 연산은 IP 주소 할당 정책이 기존의 클래스 기반에서 CIDR(ClasslessInter-Domain Routing)로 바뀌면서 나온 결과이며 이는 결국 IP Version 4의 문제점이라고 할 수 있다.
인터넷을 구성하는 전송 매체가 고속화됨에 따라서 상대적으로 느린 라우터가 인터넷 성능의 병목 구간이 되고 있다. 또한 라우터 내에서는 IP 주소 검색 작업이 전체 라우터 성능의 병목 구간이 되고 있음을 살펴보았다. 따라서 빠르고 비용이 적게 드는 IP 주소 검색 기법을 개발하는 일은 결국 인터넷의 전체 성능 향상에 커다란 영향을 미치는 매우 중요한 연구임에 틀림이 없다. 본 논문에서는 1차원 패킷 분류의 대표적인 응용이라고 할 수 있는 IP 주소 검색 기법에 대해서 연구한다. 빠르고 값싼 IP 주소 검색 기법은 인터넷을 보다 저렴한 비용으로 많은 대중들에게 보급하는데 있어서 매우 중요한 역할을 하게 될 것이다. 이상과 같은 기존의 연구를 바탕으로 본 논문에서는 라우터 성능을 높일 수 있는 IP 주소 검색 기법을 제안하다. 본 논문에서 제안하는 IP 주소 검색 기법은 실제 인터넷 백본망에 부착되어 있는 라우터의 라우팅 테이블을 분석한 이후, 현재의 라우팅 테이블의 특성을 이용하여 개발된 것이며, 하드웨어를 통하여 값싼 비용으로 쉽게 구현될 수 있다. 또한 제안되는 IP 주소 검색 기법은 기존에 제안된 어떠한 IP 주소 검색 기법이 요구하는 것보다 작은 메모리를 요구한다. 그리고 최악의 경우, 두번의 메모리 검색으로 한번의 IP 주소 검색을 끝낼 수 있고, 보통 단 한번의 메모리 검색으로 IP 주소 검색을 끝낼 수 있다. 포워딩 테이블을 저장하기 위해서 필요로 하는 메모리 양이 작다는 점과 하나의 IP 주소 검색을 끝내는데 필요한 메모리 접근 회수가 최악의 경우 두 번이기 때문에, 제안되는 IP 주소 검색 기법은 초고속 그리고 고성능 IP 라우터에 잘 적용될 수 있다.
