Address lookup algorithms for IPv6

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal

10 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)909-918
Journal / PublicationIEE Proceedings: Communications
Volume153
Issue number6
Publication statusPublished - 2006

Abstract

Previously published address lookup algorithms are mainly tailored for IPv4. The lookup operation is optimised based on the prefix distribution patterns found in IPv4 routing tables. The introduction of IPv6 with increased address length and very different prefix length distribution poses new challenges to the lookup algorithms. Major refinements to the address lookup algorithms are necessary when applied to IPv6. In this paper, we study three well-known approaches for IPv6 address lookup, namely the trie-based approach, the range search approach, and the hash-based approach. We extend the address lookup methods with incremental update capability and evaluate their lookup rate, update rate and memory requirement. Theoretically, the hash-based method has good scalability. However, it is found that the hash-based method has the slowest lookup rate and the worst memory efficiency. The trie-based method has the fastest lookup rate but the slowest update rate. The range search approach has the best update rate and memory efficiency. The update rate of the trie-based method can be improved by combining with the hash-based method.

Citation Format(s)

Address lookup algorithms for IPv6. / Li, Y. K.; Pao, D.

In: IEE Proceedings: Communications, Vol. 153, No. 6, 2006, p. 909-918.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal