Scalable Best Matching Prefix Lookups

Cite This

Files in this item

Checksum: MD5:8c8b851b7bd218664d24bc73de5f8071

WALDVOGEL, Marcel, George VARGHESE, Jonathan TURNER, Bernhard PLATTNER, 1998. Scalable Best Matching Prefix Lookups. The seventeenth annual ACM symposium. Puerto Vallarta, Mexico, Jun 28, 1998 - Jul 2, 1998. In: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing - PODC '98. New York, New York, USA:ACM Press, pp. 312. ISBN 0-89791-977-7. Available under: doi: 10.1145/277697.277765

@inproceedings{Waldvogel1998Scala-6211, title={Scalable Best Matching Prefix Lookups}, year={1998}, doi={10.1145/277697.277765}, isbn={0-89791-977-7}, address={New York, New York, USA}, publisher={ACM Press}, booktitle={Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing - PODC '98}, author={Waldvogel, Marcel and Varghese, George and Turner, Jonathan and Plattner, Bernhard} }

All global routing protocols use hierarchies to allow scaling to a world wide community while keeping the routing database size manageable. Databases of variable length prefixes are a powerful tool for providing this in a flexible manner, but require a Longest Prefix Matching algorithm. In this paper, we report a fundamentally new solution that is both algorithmically interesting and practical.<br /><br />Our scheme is based on doing binary search on hash tables organized by prefix lengths, and scales very well as address and routing table sizes increase: independent of the table size, it requires a worst case time of log2(address bits) hash lookups. With the current Internet Protocol, which uses 32 bit addresses, at most 5 hash lookups are needed; for the upcoming 128 bit addresses of the next generation Internet Protocol (IPv6), 7 lookups suffice. Several refinements, including specializing the Binary Search with every match, considerably reduce the average number of hash search steps to less than 2. terms-of-use Scalable Best Matching Prefix Lookups Turner, Jonathan 2011-03-24T16:10:14Z application/pdf 2011-03-24T16:10:14Z eng 1998 Varghese, George Turner, Jonathan Plattner, Bernhard Varghese, George Waldvogel, Marcel Plattner, Bernhard Waldvogel, Marcel First publ in: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, Puerto Vallarta, México, 1998, p. 312

Downloads since Oct 1, 2014 (Information about access statistics)

scalable_best_matching_prefix_lookups.pdf 123

This item appears in the following Collection(s)

terms-of-use Except where otherwise noted, this item's license is described as terms-of-use

Search KOPS


My Account