Building shape-shifting tries for fast IP lookup

[ACCESS RESTRICTED TO THE UNIVERSITY OF MISSOURI AT AUTHOR'S REQUEST.] The Internet Protocol (IP) is a protocol used to communicate data over packet-switched internet works. The currently deployed version of the Internet Protocol is IPv4. It provides a 32-bit address space which can at most address four billion nodes. IPv6, the new version of the Internet Protocol, provides a 128-bit address space which can at most address 3.4 x 10[superscript 38] nodes. An Internet router can forward incoming Internet packets by looking up their IP destination address in a routing table which then determines the output link on which the packet is sent. To achieve a competitive advantage, many routers today choose to do additional processing for a specific subset of packets, which requires that routers are able to classify packets based on packet header into corresponding classes or so-called flows. A router doing packet classification maintains a database containing rules one of which is for a certain type of flows. When a packet arrives at a router, the router look up the rule database and find a rule that matches the incoming packet headers and take corresponding actions associated to this rule. 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 minimumheight SST. Breadth-First Pruning (BFP) algorithm takes O(n[superscript 2]) time to construct a minimumheight SST, where n is the number of nodes in the binary trie corresponding to the routing table. In this thesis, 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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer science (MU)

Grantor dc:publisher

University of Missouri--Columbia

Year dc:date.issued

2010

Author dc:creator

• Pan, Mian, 1974-

Advisors dc:contributor.advisor

• Lu, Haibin
• Shang, Yi, 1967-

Statement dc:rights

• Access to files is limited to the campuses of the University of Missouri with SSO login.

Language dc:language.iso

eng, English

DOI

https://doi.org/10.32469/10355/8146

OAI identifier oai:identifier

oai:mospace.umsystem.edu:10355/8146