Free Trial

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

Share this Page URL


12.7 Extending Two-Dimensional Schemes 287 O4: The number of disjoint classification regions is small. This is perhaps the most interesting observation. Harking back to the geometric view, the lower bounds in Chazelle [Cha90a] depend partly on the worst-case possibility of creating N K classification regions using N rules. Such rules require either N K space or a large search time. However, Gupta and McKeown [GM99b], after an extensive survey of 8000 rule databases, show that the number of classification regions is much smaller than the worst case. Instead of being exponential in the number of dimensions, the number of classification regions is linear in N, with a small constant. O5: Source­Destination matching: In Singh et al. [BSV03], several core router classifiers used by real ISPs are analyzed and the following interesting observation is made. Almost all packets match at most five distinct source­destination values found in the classifier. No packet matched more than 20 distinct source­destination pairs. This is a somewhat more refined observation than O4 because it says that the number of classification regions is small, even when projected only to the source and destination fields. By "small," we mean that the number of regions grows much more slowly than N, the size of the classifier. 12.7 EXTENDING TWO-DIMENSIONAL SCHEMES The simplest general scheme uses observation O5 to trivially extend any efficient 2D scheme to multiple dimensions. A number of algorithms simply use linear search to search through all possible rules. This scales well in storage but poorly in time. The source­destination matching observation leads to a very simple idea depicted in Figure 12.10. Use source­ destination address matching to reduce linear searching to just the rules corresponding to source­destination prefix pairs in the database that match the given packet header. By observation O5, at most 20 rules match any packet when considering only the source and destination fields. Thus pruning based on source­destination fields will reduce the number of rules to be searched to less than 20, compared to searching the entire database. For example,