Internet packet filter management and rectangle geometry

David Eppstein; S. Muthukrishnan

Internet packet filter management and rectangle geometry

David Eppstein, S. Muthukrishnan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider rule sets for internet packet routing and filtering, where each rule consists of a range of source addresses, a range of destination addresses, a priority, and an action. A given packet should be handled by the action from the maximum priority rule that matches its source and destination. We describe new data structures for quickly finding the rule matching an incoming packet, in near-linear space, and a new algorithm for determining whether a rule set contains any conflicts, in time &Ogr; (n ^3/2).

Original language	English (US)
Title of host publication	Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	827-835
Number of pages	9
State	Published - 2001
Event	2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States Duration: Apr 30 2001 → May 1 2001

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other	2001 Operating Section Proceedings, American Gas Association
Country/Territory	United States
City	Dallas, TX
Period	4/30/01 → 5/1/01

Keywords

Algorithms
Management
Theory
Verification

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@inproceedings{4698c7ffae2f47999dd84f6e7f3a4727,

title = "Internet packet filter management and rectangle geometry",

abstract = "We consider rule sets for internet packet routing and filtering, where each rule consists of a range of source addresses, a range of destination addresses, a priority, and an action. A given packet should be handled by the action from the maximum priority rule that matches its source and destination. We describe new data structures for quickly finding the rule matching an incoming packet, in near-linear space, and a new algorithm for determining whether a rule set contains any conflicts, in time &Ogr; (n 3/2).",

keywords = "Algorithms, Management, Theory, Verification",

author = "David Eppstein and S. Muthukrishnan",

year = "2001",

language = "English (US)",

isbn = "0898714907",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

pages = "827--835",

booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "2001 Operating Section Proceedings, American Gas Association ; Conference date: 30-04-2001 Through 01-05-2001",

}

TY - GEN

T1 - Internet packet filter management and rectangle geometry

AU - Eppstein, David

AU - Muthukrishnan, S.

PY - 2001

Y1 - 2001

N2 - We consider rule sets for internet packet routing and filtering, where each rule consists of a range of source addresses, a range of destination addresses, a priority, and an action. A given packet should be handled by the action from the maximum priority rule that matches its source and destination. We describe new data structures for quickly finding the rule matching an incoming packet, in near-linear space, and a new algorithm for determining whether a rule set contains any conflicts, in time &Ogr; (n 3/2).

AB - We consider rule sets for internet packet routing and filtering, where each rule consists of a range of source addresses, a range of destination addresses, a priority, and an action. A given packet should be handled by the action from the maximum priority rule that matches its source and destination. We describe new data structures for quickly finding the rule matching an incoming packet, in near-linear space, and a new algorithm for determining whether a rule set contains any conflicts, in time &Ogr; (n 3/2).

KW - Algorithms

KW - Management

KW - Theory

KW - Verification

UR - http://www.scopus.com/inward/record.url?scp=65549164282&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=65549164282&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:65549164282

SN - 0898714907

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 827

EP - 835

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 2001 Operating Section Proceedings, American Gas Association

Y2 - 30 April 2001 through 1 May 2001

ER -

Internet packet filter management and rectangle geometry

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this