http://www.cnr.it/ontology/cnr/individuo/prodotto/ID156697

Adaptive Stratified Search Trees for IP Table Lookup (Rapporti tecnici, manuali, carte geologiche e tematiche e prodotti multimediali)

Type

Label

Adaptive Stratified Search Trees for IP Table Lookup (Rapporti tecnici, manuali, carte geologiche e tematiche e prodotti multimediali) (literal)

Anno

Alternative label

Pellegrini M., Fusco G., Vecchiocattivi G. (2002)
Adaptive Stratified Search Trees for IP Table Lookup
(literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#descrizioneSinteticaDelProdotto

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. (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#supporto