TY - JOUR
T1 - Simple and fast IP lookups using binomial spanning trees
AU - Chang, Yeim Kuan
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2005/3/23
Y1 - 2005/3/23
N2 - High performance Internet routers require an efficient IP lookup algorithm to forward millions of packets per second. Various binary trie data structures are normally used in software-based routers. Binary trie based lookup algorithms are simple not only for searching for the longest prefix match but also for updating the routing table. In this paper, we propose a new IP lookup algorithm based on binomial spanning trees. The proposed algorithm has the same advantages of simple search and update processes as the ones based on binary trie. However, the performance of the proposed algorithm in terms of memory requirement and the lookup time is better than the schemes based on binary tries, such as path-compression and level-compression.
AB - High performance Internet routers require an efficient IP lookup algorithm to forward millions of packets per second. Various binary trie data structures are normally used in software-based routers. Binary trie based lookup algorithms are simple not only for searching for the longest prefix match but also for updating the routing table. In this paper, we propose a new IP lookup algorithm based on binomial spanning trees. The proposed algorithm has the same advantages of simple search and update processes as the ones based on binary trie. However, the performance of the proposed algorithm in terms of memory requirement and the lookup time is better than the schemes based on binary tries, such as path-compression and level-compression.
UR - http://www.scopus.com/inward/record.url?scp=15544374876&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=15544374876&partnerID=8YFLogxK
U2 - 10.1016/j.comcom.2004.10.014
DO - 10.1016/j.comcom.2004.10.014
M3 - Article
AN - SCOPUS:15544374876
VL - 28
SP - 529
EP - 539
JO - Computer Communications
JF - Computer Communications
SN - 0140-3664
IS - 5
ER -