The Resource Building shape-shifting tries for fast IP lookup, by Mian Pan, (electronic resource)

Building shape-shifting tries for fast IP lookup, by Mian Pan, (electronic resource)

Label
Building shape-shifting tries for fast IP lookup
Title
Building shape-shifting tries for fast IP lookup
Statement of responsibility
by Mian Pan
Creator
Contributor
Thesis advisor
Subject
Genre
Language
eng
Summary
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 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(n2) 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
Cataloging source
MUU
http://library.link/vocab/creatorDate
1974-
http://library.link/vocab/creatorName
Pan, Mian
Degree
M.S.
Dissertation year
2010.
Granting institution
University of Missouri--Columbia
Illustrations
illustrations
Index
no index present
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
  • theses
http://library.link/vocab/relatedWorkOrContributorDate
1967-
http://library.link/vocab/relatedWorkOrContributorName
  • Lu, Haibin
  • Shang, Yi
http://library.link/vocab/subjectName
  • TCP/IP (Computer network protocol)
  • Computer networks
  • Routers (Computer networks)
  • Packet switching (Data transmission)
  • Computer algorithms
Target audience
specialized
Label
Building shape-shifting tries for fast IP lookup, by Mian Pan, (electronic resource)
Instantiates
Publication
Note
  • 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
Bibliography note
Includes bibliographical references
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Control code
650085670
Extent
1 online resource (ix, 34 pages)
Form of item
online
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Note
Access is limited to the campuses of the University of Missouri.
Other physical details
illustrations
Specific material designation
remote
System control number
(OCoLC)650085670
Label
Building shape-shifting tries for fast IP lookup, by Mian Pan, (electronic resource)
Publication
Note
  • 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
Bibliography note
Includes bibliographical references
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Control code
650085670
Extent
1 online resource (ix, 34 pages)
Form of item
online
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Note
Access is limited to the campuses of the University of Missouri.
Other physical details
illustrations
Specific material designation
remote
System control number
(OCoLC)650085670

Library Locations

    • UMKCBorrow it
      800 E 51st St, Kansas City, MO, 64110, US
      39.035061 -94.576518
    • Health Sciences LibraryBorrow it
      2411 Holmes St, Kansas City, Kansas City, MO, 64108, US
      39.083418 -94.575323
    • Leon E. Bloch Law LibraryBorrow it
      500 E. 52nd Street, Kansas City, MO, 64110, US
      39.032488 -94.581967
Processing Feedback ...