PUMA
Istituto di Informatica e Telematica     
Pellegrini M., Fusco G., Vecchiocattivi G. Adaptive Stratified Search Trees for IP Table Lookup. Technical report, 2002.
 
 
Abstract
(English)
The IP Table Lookup mechanism is a key component of a router in a packet network (such as Internet). A router in the network holds a table where each entry specifies a prefix (at most 32 bits long) and a next hop exit line. When a packet comes to the router the destination address in the header of the packet is read,the longest prefix in the table matching the destination is sought, and the packet is sent to the corresponding next hop exit line. In this paper we propose a data structure, called Adaptive Stratified Tree (AST) to solve the IP Table Lookup problem. For a table of n prefixes of length at most w the AST is built in O(n log n logw) time, uses storage O(n)and allows searching in time O (log n).The algorithm has been implemented in C and compared to a state of the art software solution, notably the Level-Compressed Trie of S.Nilsson and G.Karlson. For several large benchmark tables and for different traffic profiles we significantly reduce the storage of the search structure (up to a factor 10) and significantly reduce the search time (up to a factor 2).Interestingly, even for the largest test tables (about 75,000 entries) we could build small search trees having depth three.
Subject IP table lookup
Network routing
68M10
68P05


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional