David Eppstein – Publications

Publications with S. Muthukrishnan

• Internet packet filter management and rectangle geometry.
  D. Eppstein and S. Muthukrishnan.
  arXiv:cs.CG/0010018.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 827–835.

  Rule sets for internet routers and firewalls can be represented as sets of prioritized rectangles; the rule to use for a packet is the maximum priority rectangle containing its (source,destination) address pair. We develop efficient data structures for performing these queries, and find an O(n^3/2) time algorithm for testing whether a rule set contains any ambiguities.

  (SODA paper)