A Partitioned Compressed-Trie for Speeding up IP Address Lookups


The KIPS Transactions:PartC, Vol. 10, No. 5, pp. 641-646, Oct. 2003
10.3745/KIPSTC.2003.10.5.641,   PDF Download:

Abstract

Packet processing speed of routers as well as transmission speed of physical links gives a great effect on IP packet transfer rate in Internet. The router forwards a packet after determining the next hop to the packet's destination. IP address lookup is a main design issue for high performance routers. In this paper, we propose a partitioned compressed-trie for speeding-up IP address lookup algorithms based on trie data structure by exploiting path compression. In the proposed scheme, IP prefixes are divided into several compressed-tries and lookup is performed on only one partitioned compressed-trie. Memory access time for IP address lookup is lessen due to compression technique and memory required for maintaining partition does not increased.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
P. J. Hyeong, J. I. Hyeon, J. M. Yeong, W. Y. Gwan, "A Partitioned Compressed-Trie for Speeding up IP Address Lookups," The KIPS Transactions:PartC, vol. 10, no. 5, pp. 641-646, 2003. DOI: 10.3745/KIPSTC.2003.10.5.641.

[ACM Style]
Park Jae Hyeong, Jang Ig Hyeon, Jeong Min Yeong, and Won Yong Gwan. 2003. A Partitioned Compressed-Trie for Speeding up IP Address Lookups. The KIPS Transactions:PartC, 10, 5, (2003), 641-646. DOI: 10.3745/KIPSTC.2003.10.5.641.