Packet classification via dynamic point location

21^st March 2019, 12:10
Konstantinos Tsakalidis

Abstract

Packet classification rules in IP routing can be implemented as an orthogonal planar subdivision of the sender/receiver address-space. Resolving the rules for a given packet corresponds to a point location query that reports the orthogonal region containing the packet's (sender, receiver) query point. Variants of orthogonal point location, such as vertical ray shooting, orthogonal line segment intersection, vertical ray stabbing and vertical stabbing-max can be used to model various classification schemes.

In a dynamic setting, the rules can be modified with update operations. We present dynamic data structures in the word-RAM model that support all the query variants in optimal query time and also support updates in significantly sublogarithmic O(log^{1/2+?} n) time (amortized, for any constant ?>0), provided that the x-coordinates are integers bounded polynomially in n, the subdivision size. Previous results achieved no less than logarithmic update time: [Mortensen, SODA 2003], [Agarwal, Arge and Yi, SODA 2005], [Giyora and Kaplan, SODA 2007], [Blelloch, SODA 2008], (Nekrich, 2010), [Nekrich, ISAAC 2011], (Tao, TALG 2014).