Shared more. Cited more. Safe forever.
    • advanced search
    • submit works
    • about
    • help
    • contact us
    • login
    View Item 
    •   MOspace Home
    • University of Missouri-Columbia
    • Graduate School - MU Theses and Dissertations (MU)
    • Theses and Dissertations (MU)
    • Theses (MU)
    • 2010 Theses (MU)
    • 2010 MU theses - Access restricted to UM
    • View Item
    •   MOspace Home
    • University of Missouri-Columbia
    • Graduate School - MU Theses and Dissertations (MU)
    • Theses and Dissertations (MU)
    • Theses (MU)
    • 2010 Theses (MU)
    • 2010 MU theses - Access restricted to UM
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    advanced searchsubmit worksabouthelpcontact us

    Browse

    All of MOspaceCommunities & CollectionsDate IssuedAuthor/ContributorTitleIdentifierThesis DepartmentThesis AdvisorThesis SemesterThis CollectionDate IssuedAuthor/ContributorTitleIdentifierThesis DepartmentThesis AdvisorThesis Semester

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular AuthorsStatistics by Referrer

    Building shape-shifting tries for fast IP lookup

    Pan, Mian, 1974-
    View/Open
    [PDF] public.pdf (2.083Kb)
    [PDF] short.pdf (41.02Kb)
    [PDF] research.pdf (260.1Kb)
    Date
    2010
    Format
    Thesis
    Metadata
    [+] Show full item record
    Abstract
    [ACCESS RESTRICTED TO THE UNIVERSITY OF MISSOURI AT REQUEST OF AUTHOR.] 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.
    URI
    https://hdl.handle.net/10355/8146
    https://doi.org/10.32469/10355/8146
    Degree
    M.S.
    Thesis Department
    Computer science (MU)
    Rights
    Access is limited to the campuses of the University of Missouri.
    Collections
    • Computer Science electronic theses and dissertations (MU)
    • 2010 MU theses - Access restricted to UM

    Send Feedback
    hosted by University of Missouri Library Systems
     

     


    Send Feedback
    hosted by University of Missouri Library Systems