Efficient construction of variable-stride multibit tries for IP lookup

Author

Sahni, Sartaj ; Kim, Kun Suk

Author_Institution

Dept. of Comput. & Inf. Sci. & Eng., Florida Univ., Gainesville, FL, USA

fYear

2002

fDate

2002

Firstpage

220

Lastpage

227

Abstract

Srinivasan and Varghese (1999) have proposed the use of multibit tries to represent routing tables used for Internet (IP) address lookups. They propose an O(n _*W²_* k) dynamic programming algorithm to determine the strides for an optimal variable-stride trie that has at most k levels. Here, n is the number of prefixes in the routing table and W is the length of the longest prefix. We improve on this algorithm by providing an alternative dynamic programming formulation. The complexity of our algorithm is O(n_*W_*k), on real router data sets. This is an improvement by a factor of W over the corresponding algorithm of Srinivasan. Experiments conducted by us indicate that our variable-stride algorithm is between 2 and 17 times as fast for IPv4 routing table data

Keywords

Internet; computational complexity; dynamic programming; packet switching; telecommunication network routing; tree data structures; IP address lookups; Internet; complexity; controlled prefix expansion; dynamic programing; longest matching prefix; multibit tries; packet routing; routing tables; variable-stride trie; Communication system traffic control; Data structures; Dynamic programming; Heuristic algorithms; IP networks; Information science; Internet; Kernel; Routing; Table lookup;

fLanguage

English

Publisher

ieee

Conference_Titel

Applications and the Internet, 2002. (SAINT 2002). Proceedings. 2002 Symposium on

Conference_Location

Nara

Print_ISBN

0-7695-1447-2

Type

conf

DOI

10.1109/SAINT.2002.994482

Filename

994482