Name
Abstract | ||
|---|---|---|
Most data structures for packet forwarding are optimized for IPv4, and less capable of handling IPv6 routing tables. Shape-Shifting Trie (SST) is specifically designed to be scalable to IPv6. To reduce the worst-case lookup time that is proportional to the height of SST, it is desirable to construct a minimum-height SST. Breadth-First Pruning (BFP) algorithm takes O(n^2) time to construct a minimum-height SST, where n is the number of nodes in the binary trie corresponding to the routing table. In this paper, we propose a Post-Order Minimum-Height Pruning (POMHP) algorithm that takes only O(n) time to construct a minimum-height SST. We further propose nodes merging algorithm to cut down SST size without affecting SST height. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.comcom.2007.09.006 | Computer Communications |
Keywords | Field | DocType |
IP lookup,Packet forwarding,Shape-Shifting Trie,Binary trie | IPv6,Internet Protocol,Data structure,Computer science,Computer network,Algorithm,Routing table,Trie,Packet forwarding,Binary number,Scalability | Journal |
Volume | Issue | ISSN |
30 | 18 | Computer Communications |
Citations | PageRank | References |
1 | 0.37 | 20 |
Authors | ||
2 | ||