22 CHAPTER 2 Network Implementation Models the input bits. Logic minimization is often used to eliminate redundant gates and sometimes to increase speed. For example, if + denotes OR and · denotes AND, then the function O = I 1 · I 2 + I 1 · I 2 can be simplified to O = I 1 . Example 1. Quality of Service and Priority Encoders: Suppose we have a network router that maintains n output packet queues for a link, where queue i has higher priority than queue j if i < j. This problem comes under the category of providing quality of service (QOS), which is covered in Chapter 14. The transmit scheduler in the router must pick a packet from the first nonempty packet queue in priority order. Assume the scheduler maintains an N-bit vector (bitmap) I such that I[ j] = 1 if and only if queue j is nonempty. Then the scheduler can find the highest-priority nonempty queue by finding the smallest position in I in which a bit is set. Hardware designers know this function intimately as a priority encoder. However, even a software designer should realize that this function is feasible for hardware implementation for reasonable n. This function is examined more closely in Example 2. 2.2.2 Timing and Power To forward a 40-byte packet at OC-768 speeds, any networking function on the packet must complete in 8 nsec. Thus the maximum signal transmission delay from inputs to outputs on any logic path must not exceed 8 nsec. 2 To ensure this constraint, a model of signal transmission delay in a transistor is needed. Roughly speaking, each logic gate, such as a NAND or NOT gate, can be thought of as a set of capacitors and resistors that must be charged (when input values change) in order to compute output values. Worse, charging one input gate can cause the outputs of later gates to charge further inputs, and so on. Thus for a combinatorial function, the delay to compute the function is the sum of the charging and discharging delays over the worst-case path of transistors. Such path delays must fit within a minimum packet arrival time. Besides the time to charge capacitors, another source of delay is wire delay. More details can be found in