DocumentCode :
2715806
Title :
Fast IP Table Lookup Construction Using Lexicographic Prefix Ordering
Author :
Hiryanto, Lely ; Soh, Sieteng ; Rai, Suresh ; Gopalan, Raj
Author_Institution :
Dept. of Comput., Curtin Univ. of Technol., WA
fYear :
2005
fDate :
5-5 Oct. 2005
Firstpage :
324
Lastpage :
328
Abstract :
Crescenzi et al. have proposed a fast full-expansion-compression (FEC) technique that requires exactly three memory accesses for each IP lookup. However, prefix updates on their FEC scheme require the forwarding table data structure to be rebuilt from scratch. Therefore, fast table reconstruction is important to make the scheme effective for use in a dynamic environment. In this paper, we propose an efficient technique to reduce the FEC table construction time. Our approach generates the RLE sequences for the forwarding table directly from a list of decreasing lexicographic ordered prefixes to avoid the expansion step of the previous technique. We also propose an improved unification technique to construct the FEC tables more efficiently. Our approach has been implemented in C, and several experiments using six databases from some real IPv4 router show that our proposed technique runs 4 to 29 times faster than the previous technique
Keywords :
IP networks; table lookup; telecommunication network routing; IP table lookup construction; IPv4 router; data structure; full-expansion-compression; lexicographic prefix ordering; Data structures; Databases; Internet; Routing protocols; Scalability; Spine; Table lookup; Time measurement;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Communications, 2005 Asia-Pacific Conference on
Conference_Location :
Perth, WA
Print_ISBN :
0-7803-9132-2
Type :
conf
DOI :
10.1109/APCC.2005.1554073
Filename :
1554073
Link To Document :
بازگشت