| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 449596 | Computer Communications | 2007 | 9 Pages |
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(n2) 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Networks and Communications
Authors
Mian Pan, Haibin Lu,