Multi-dimensional Prefix Matching Using Line Search


Marcel Waldvogel: Multi-Dimensional Prefix Matching Using Line Search. In: Proceedings of IEEE Local Computer Networks, pp. 200-207, Tampa, FL, USA, 2000.


Abstract

With the increasing popularity of firewalls, virtual private networks (VPNs) and Quality of Service (QoS) routing, packet classification becomes increasingly important in the Internet. The high-performance solutions known so far strongly rely on certain properties of the filter database to match against, such as a small number of distinct prefixes or the absence of conflicts. In this paper, we present Line Search as a two-dimensional generalization of the one-dimensional binary search on prefix lengths, exploiting the advantage given by the different approach therein. This algorithm also works best on the filter databases that are expected to occur most often, but degrades gracefully when these assumptions no longer hold. We also show how to efficiently extend the algorithm to a complete five-dimensional Internet Protocol (IP) and transport header match.

BibTeX (Download)

@inproceedings{Waldvogel2000Multi-Dimensional,
title = {Multi-Dimensional Prefix Matching Using Line Search},
author = {Marcel Waldvogel},
url = {https://netfuture.ch/wp-content/uploads/2000/waldvogel00multidimensional.pdf},
year  = {2000},
date = {2000-11-01},
urldate = {1000-01-01},
booktitle = {Proceedings of IEEE Local Computer Networks},
pages = {200-207},
address = {Tampa, FL, USA},
abstract = {With the increasing popularity of firewalls, virtual private networks (VPNs) and Quality of Service (QoS) routing, packet classification becomes increasingly important in the Internet. The high-performance solutions known so far strongly rely on certain properties of the filter database to match against, such as a small number of distinct prefixes or the absence of conflicts. In this paper, we present Line Search as a two-dimensional generalization of the one-dimensional binary search on prefix lengths, exploiting the advantage given by the different approach therein. This algorithm also works best on the filter databases that are expected to occur most often, but degrades gracefully when these assumptions no longer hold. We also show how to efficiently extend the algorithm to a complete five-dimensional Internet Protocol (IP) and transport header match.},
keywords = {Fast Routers, Hash Tables, Quality of Service},
pubstate = {published},
tppubtype = {inproceedings}
}

Let’s stay in touch!

Receive a mail whenever I publish a new post.

About 1-2 Mails per month, no Spam.

Follow me on the Fediverse

Web apps


Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.