{"id":{"repo_id":"missouri","oai_identifier":"oai:mospace.umsystem.edu:10355/8146"},"canonical_url":"https://search.dev.ndltd.org/etd/missouri/oai:mospace.umsystem.edu:10355/8146","repository":{"repo_id":"missouri","name":"University of Missouri","base_url":"https://mospace.umsystem.edu/oai/request"},"display":{"title":"Building shape-shifting tries for fast IP lookup","abstract":"[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.","abstract_html":"[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.","abstract_has_math":false,"creators":["Pan, Mian, 1974-"],"institution":"University of Missouri--Columbia","degree_name":"M.S.","degree_level":"Masters","degree_discipline":"Computer science (MU)","degree_department":null,"school":null,"contributors":[],"advisors":["Lu, Haibin","Shang, Yi, 1967-"],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010","date_published":"2010","updated_at":"2026-07-24T03:08:20Z","subjects":[],"languages":["eng","English"],"rights":["Access to files is limited to the campuses of the University of Missouri with SSO login."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.32469/10355/8146"],"render_values":[{"text":"https://doi.org/10.32469/10355/8146","href":"https://doi.org/10.32469/10355/8146","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10355/8146","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Lu, Haibin","Shang, Yi, 1967-"]},{"key":"dc:creator","label":"Author","values":["Pan, Mian, 1974-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2010-08-03T19:29:14Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2010-08-03T19:29:14Z"]},{"key":"dc:date.issued","label":"Date","values":["2010"]},{"key":"dc:publisher","label":"Institution","values":["University of Missouri--Columbia"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer science (MU)"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Missouri--Columbia"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Access to files is limited to the campuses of the University of Missouri with SSO login."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.32469/10355/8146"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10355/8146"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Title from PDF of title page (University of Missouri--Columbia, viewed on June 25, 2010).","The entire thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file; a non-technical public abstract appears in the public.pdf file.","Thesis advisor: Dr. Haibin Lu, and Dr. Yi Shang.","M.S. University of Missouri--Columbia 2010."]},{"key":"dc:description.abstract","label":"Abstract","values":["[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."]},{"key":"dc:title","label":"Title","values":["Building shape-shifting tries for fast IP lookup"]}]}],"canonical_facts":{"dc:contributor.advisor":["Lu, Haibin","Shang, Yi, 1967-"],"dc:creator":["Pan, Mian, 1974-"],"dc:date.accessioned":["2010-08-03T19:29:14Z"],"dc:date.available":["2010-08-03T19:29:14Z"],"dc:date.issued":["2010"],"dc:description":["Title from PDF of title page (University of Missouri--Columbia, viewed on June 25, 2010).","The entire thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file; a non-technical public abstract appears in the public.pdf file.","Thesis advisor: Dr. Haibin Lu, and Dr. Yi Shang.","M.S. University of Missouri--Columbia 2010."],"dc:description.abstract":["[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."],"dc:identifier.doi":["https://doi.org/10.32469/10355/8146"],"dc:identifier.uri":["https://hdl.handle.net/10355/8146"],"dc:language":["English"],"dc:language.iso":["eng"],"dc:publisher":["University of Missouri--Columbia"],"dc:rights":["Access to files is limited to the campuses of the University of Missouri with SSO login."],"dc:title":["Building shape-shifting tries for fast IP lookup"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer science (MU)"],"thesis:degree_level":["Masters"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Missouri--Columbia"]},"updated_at":"2026-07-24T03:08:20Z"}