A Fast IP Lookups using Dynamic Trie Compression


The KIPS Transactions:PartA, Vol. 10, No. 5, pp. 453-462, Oct. 2003
10.3745/KIPSTA.2003.10.5.453,   PDF Download:

Abstract

IP address lookup of router searches and decide proper output link using destination address of IP packet that arrive into router. The IP address lookup is essential part in the development of high-speed router needed to high-speed backbone network as one of bottleneck of router performance. This paper introduces DTC data structure that can support gigabit IP address lookup by dynamic trie compression technique that just uses small memory in conventional Pentium CPU. When make a forwarding table by trie compression, the DTC can dynamically select a size of data structure with considering correlation between table´s size and searching speed. Also, when compress the prefix trie, DTC makes IP address lookup on the forwarding table of a search on the high speed SRAM cache by minimizing the size of data structure reflecting the structure of the trie. In the experiment results, the DTC data structure recorded performance of maximum 12.5 x 10^6 LPS (lookup per second) in conventional Pentium CPU through a dynamic building of most suitable compression over variety of routing tables.


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]
O. S. Hyeon, "A Fast IP Lookups using Dynamic Trie Compression," The KIPS Transactions:PartA, vol. 10, no. 5, pp. 453-462, 2003. DOI: 10.3745/KIPSTA.2003.10.5.453.

[ACM Style]
O Seung Hyeon. 2003. A Fast IP Lookups using Dynamic Trie Compression. The KIPS Transactions:PartA, 10, 5, (2003), 453-462. DOI: 10.3745/KIPSTA.2003.10.5.453.