Scalable Best Matching Prefix Lookups

Waldvogel, Marcel; Varghese, George; Turner, Jonathan; Plattner, Bernhard

doi:10.1145/277697.277765

Aufgrund von Vorbereitungen auf eine neue Version von KOPS, können kommenden Montag und Dienstag keine Publikationen eingereicht werden. (Due to preparations for a new version of KOPS, no publications can be submitted next Monday and Tuesday.)

Scalable Best Matching Prefix Lookups

Type of Publication:	Contribution to a conference collection
URI (citable link):	http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-24730
Author:	Waldvogel, Marcel; Varghese, George; Turner, Jonathan; Plattner, Bernhard
Year of publication:	1998
Conference:	The seventeenth annual ACM symposium, Jun 28, 1998 - Jul 2, 1998, Puerto Vallarta, Mexico
Published in:	Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing - PODC '98. - New York, New York, USA : ACM Press, 1998. - pp. 312. - ISBN 0-89791-977-7
DOI (citable link):	https://dx.doi.org/10.1145/277697.277765
Summary:	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. 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.
Subject (DDC):	004 Computer Science
Link to License:	Attribution-NonCommercial-NoDerivs 2.0 Generic

Cite This

Files in this item

Name: scalable_best_matching_prefix_looku ...

Size: 39.4 KiB

Format: PDF

View/Open

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. 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 Attribution-NonCommercial-NoDerivs 2.0 Generic First publ in: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, Puerto Vallarta, México, 1998, p. 312