and good search-engine-based table man- agement on the network behavior, consider the following scenario. In the previous paragraph, we men- tioned that four operations are needed each time a table entry is moved to a new location. However, in cases like CIDR routing, the segments are created according to the prefix length and some empty slots are left in each segment to accommodate new entries. If a segment is suddenly filled up, the table must be taken offline to reshuffle the entries. This is an annoying situation. 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. SEARCH ENGINES 230 NETWORK PROCESSORS The worst-case scenario is when all segments except one are full. 5 From that point, any new entries will require 31 move operations. Each move requires four commands (with one clock cycle per com- mand) to the CAM-both reads and writes. This brings us to at least 4X31 = 124 clock cycles per move operation. This is conservative, because occasionally supervisory code must be executed to cal- culate the boundaries of entire segments. However, we will ignore this for now in order to make a point. Approximately 3,000 route updates occur per second (if not 4,000 by the time this book is pub- lished) in a typical core/edge router. This means that 3,000X124 = 372,000 cycles per second must be spent on activities that update and maintain the table entries. If the packet-processing engine in the router is clocked at 100 MHz, the corresponding cycle time is 10 nanoseconds (10x10-9) seconds). This means that the 372,000 cycles spent on table updating and maintenance consume the following: 372,000 cycles X 10 nanoseconds per cycle = 3,720,000 nanoseconds = 3.72 X 106 = 3.72 10-3 = 3.72 milliseconds In the case of OC-192 links, which are typically characterized by aggregate flows of around 20 to 30 million packets per second (Mpps), this means that 3.72 thou