IP Lookup Using the Novel Idea of Scalar Prefix Search with Fast Table Updates

Mohammad BEHDADFAR  Hossein SAIDI  Masoud-Reza HASHEMI  Ali GHIASIAN  Hamid ALAEI  

IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.11   pp.2932-2943
Publication Date: 2010/11/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.2932
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Architectures, Protocols, and Applications for the Future Internet)
scalar prefix,  LPM,  LMP,  SP-BT,  search,  update,  

Full Text: PDF>>
Buy this Article

Recently, we have proposed a new prefix lookup algorithm which would use the prefixes as scalar numbers. This algorithm could be applied to different tree structures such as Binary Search Tree and some other balanced trees like RB-tree, AVL-tree and B-tree with minor modifications in the search, insert and/or delete procedures to make them capable of finding the prefixes of an incoming string e.g. an IP address. As a result, the search procedure complexity would be O(log n) where n is the number of prefixes stored in the tree. More important, the search complexity would not depend on the address length w i.e. 32 for IPv4 and 128 for IPv6. Here, it is assumed that interface to memory is wide enough to access the prefix and some simple operations like comparison can be done in O(1) even for the word length w. Moreover, insertion and deletion procedures of this algorithm are much simpler and faster than its competitors. In what follows, we report the software implementation results of this algorithm and compare it with other solutions for both IPv4 and IPv6. It also reports on a simple hardware implementation of the algorithm for IPv4. Comparison results show better lookup and update performances or superior storage requirements for Scalar Prefix Search in both average and worst cases.