2001 · 139 citations · 10 references
ComputingComputer ScienceAlgorithmsComputer NetworksData StructuresData Structure AlgorithmsInternet RoutingPacket FilteringPacket SwitchingRoutingRouting AlgorithmsPacket ProcessingPacket RoutingRule Conflict DetectionTraffic Filtering
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 O(n 3/2 ). 1 Introduction The working of the current Internet and its posited evolution depend on efficient packet filtering mechanisms: databases of rules, maintained at various parts of the network, which use patterns to filter out sets of IP packets and specify actions to be performed on those sets. Typical filter patterns are based on packet header information such as the source or destination IP addresses. The actions to be performed depend on where the packet filtering is performed i...
10
Multidimensional binary search trees used for associative searching
Jon Bentley · Communications of the ACM · 1975 · 7.5K citations · Full text
Tradeoffs for packet classification
A. Feldman, S. Muthukrishnan · 2002 · 268 citations
Detecting and resolving packet filter conflicts
Subhash Suri, Gurudatta M. Parulkar · 2002 · 247 citations
New Upper Bounds in Klee’s Measure Problem
Mark H. Overmars, Chee-Keng Yap · SIAM Journal on Computing · 1991 · 135 citations