Free Trial

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

Share this Page URL

CHAPTER 12 Packet Classification > 12.1 WHY PACKET CLASSIFICATION? - Pg. 271

12.1 Why Packet Classification? 271 Num P12 P2a P15 P2a P15 P12,2a P11 P4a P11 Principle Add marker state Precompute filter info Use Dest and SRC tries Precompute switch pointers Divide-and-conquer by first doing field lookups Lookup Technique Rectangle and tuple search Grid of tries Bit vector, pruned tuple, cross-producting Multiple 2D planes Bit vector scheme Pruned tuple On-demand cross-product Equivalent cross-producting Exploit lack of general ranges Exploit bitmap memory locality Exploit small number of prefixes that match any field P11a,4a Exploit crossproduct locality P1 Avoid redundant crossproducts F I G U R E 12.1 chapter. Summary of the principles used in the classification algorithms described in this This chapter will continue to exhibit the set of principles introduced in Chapter 3, as summarized in Figure 12.1. The chapter will also illustrate three general problem-solving strategies: solving simpler problems first before solving a complex problem, collecting different viewpoints, and exploiting the structure of input data sets.