Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL
Help

CHAPTER 12 Packet Classification > 12.8 USING DIVIDE-AND-CONQUER - Pg. 288

288 CHAPTER 12 Packet Classification Any 2D search algorithm for finding all matches for a pair (S, D) (S 1 , D 1 ) . . . (S p , D p ) . . . (S t , D t ) R 5 R 6 R 2 R 4 R 8 R 3 R 7 R 1 F I G U R E 12.10 Extending two-dimensional schemes. rule R precomputes its matching directive to be that of R if R is the lower cost of the two rules. This allows the traversal through the grid of tries to safely skip rule R when encountering rule R . While this works correctly with two-field rules, it requires some further modifications to handle the general case. One solution, equivalent to precomputing rule costs, is to precompute the list for R to include all the list elements for R. Unfortunately, this approach can increase storage because each rule is no longer represented exactly once. A more sophisticated solution, called the extended grid of tries (EGT) and described in Baboescu et al. [BSV03], is based on extra traversals beyond the standard grid of tries. The performance of EGT can be described as follows. Assumption: The extension of two-dimensional schemes depends critically on observation O5. Performance: The scheme takes at least one grid-of-tries traversal plus the time to linearly search c rules, where c is the constant embodied in observation O5. Assuming linear storage, the search performance can increase [BSV03] by an additive factor representing the time to search for less specific rules. The addition of a new rule R requires only rebuilding of the individual two-dimensional structure of which R is a part. Thus rule update should be fairly fast. 12.8 USING DIVIDE-AND-CONQUER The next three schemes (bit vector linear search, on-demand cross-producting, and equiva- lenced cross-producting) all exploit the simple algorithmic idea (P15) of divide-and-conquer. Divide-and-conquer refers to dividing a problem into simpler pieces and then efficiently com- bining the answers to the pieces. We briefly motivate a skeletal framework of this approach in this section. The next three sections will flesh out specific instantiations of this framework.