iently, and the scalable capability flexibly handling large tables that continuously evolve in size. In some cases, some algorithms trade lookup performance for the time needed to build the table. If this is an appropriate trade-off, then the systems designer is always looking for ways to decrease this preprocessing time. DEEP PACKET CLASSIFICATION We mentioned earlier that when classification must be performed based on the lookup on multiple fields, as is the case with deep packet classification, we create flows. We then assign packets to indi- vidual flows. The flow is a new concept that can be compared in granularity and conceptual impor- tance with the datagram. As a result, routers (which from now on must become flow aware as opposed to being exclusively packet aware) treat different flows differently. However, when unrelated packets 12. Radia Perlman, Interconnections: Bridges, Routers, Switches, and Internetworking Protocols, 2nd ed. (Reading, Massachusetts: Addison-Wesley, 2000). Downloaded from Digital Engineering Library @ McGraw-Hill (www.digitalengineeringlibrary.com) Copyright © 2004 The McGraw-Hill Companies. All rights reserved. Any use is subject to the Terms of Use as given at the website. CLASSIFICATION PROCESSORS 248 NETWORK PROCESSORS (iii) FIGURE 13.5 A geometrical visualization of a two-dimensional classification problem into multiple regions: (i) three regions, (ii) four regions, (iii) five regions, and (iv) six regions. The principle can be eas- ily understood in three-dimensional and higher spaces. are assigned to the same flow, they will all be treated in the same way. A flow is a virtual object that is created to better manage the performance of the network gear. As a result, it may not even have a concrete physical substance, yet it is important to monitor and process properly. What does a flow look like? A flow can be a pair of source addresses and destination addresses, or it can take the form of an ordered list, such as the destination address, the type of protocol and SO on. The li