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).

REFERENCES

• 1: H. Adiseshu, S. Suri, and G. Parulkar. Detecting and resolving packet filter conflicts. In Proc. INFOCOM, volume 3, pages 1203-1212. IEEE, March 2000.
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Stephen Alstrup , Jens Peter Secher , Maz Spork, Optimal on-line decremental connectivity in trees, Information Processing Letters, v.64 n.4, p.161-164, Nov. 28, 1997 [doi>10.1016/S0020-0190(97)00170-1]
• 4: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.295-304, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301323]
• 5: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 6: Dan Decasper , Zubin Dittia , Guru Parulkar , Bernhard Plattner, Router plugins: a software architecture for next-generation routers, IEEE/ACM Transactions on Networking (TON), v.8 n.1, p.2-15, Feb. 2000 [doi>10.1109/90.836474]
• 7: A. Feldmann and S. Muthukrishnan. Tradeoffs for packet classification. In Proc. INFOCOM, volume 3, pages 1193- 1202. IEEE, March 2000.
• 8: Paolo Ferragina , S. Muthukrishnan , Mark de Berg, Multi-method dispatching: a geometric approach with applications to string matching problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.483-491, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301378]
• 9: H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. J. Comput. Sys. Sci., 30(2):209-221, April 1985.
• 10: V. King. A simpler minimum spanning tree verification algorithm. Algorithmica, 18(2):263-270, June 1997.
• 11: Mark H. Overmars , Chee-Keng Yap, New upper bounds in Klee's measure problem, SIAM Journal on Computing, v.20 n.6, p.1034-1045, Dec. 1991 [doi>10.1137/0220065]
• 12: Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications

          Nouns: Internet

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Algorithms, Management, Theory, Verification