A fast IPv6 route lookup algorithm with hash compression

Author

Xingrniao Yao ; Lemin Li ; Guangming Hu

Author_Institution

Key Lab. of Broadband Opt. Fiber ´Transmission & Commun. Networks, Univ. of Electron. Sci. & Technol. of China, Chengdu, China

Volume

1

fYear

2004

Firstpage

674

Abstract

To solve the problem of the LLCAT algorithm (P.A. Yilmaz et al., IEEE GLOBECOM´00, vol.1, p.593-8, 2000) that needs large memory space for IPv6 route lookup, the paper proposes a fast IPv6 route lookup algorithm with hash compression. In order to save space, hash compression is used when a node´s table includes some prefixes that are less than or equal to a predefined value. After being compressed, the algorithm´s time and update complexity do not change much under the worst condition. Simulation results show that our average lookup time and memory consumed are all efficient compared to those of the LLCAT algorithm.

Keywords

Internet; computational complexity; data compression; protocols; table lookup; telecommunication network routing; tree data structures; Internet; fast IPv6 route lookup algorithm; hash compression; memory space; multibit trie; time complexity; update complexity; Commercialization; Communication networks; Compression algorithms; IP networks; Laboratories; Optical fibers; Protocols; Security; Space technology; Web and internet services;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, Circuits and Systems, 2004. ICCCAS 2004. 2004 International Conference on

Conference_Location

Chengdu

Print_ISBN

0-7803-8647-7

Type

conf

DOI

10.1109/ICCCAS.2004.1346255

Filename

1346255