ed to the buffered packets that are available at the outputs, as the packets have already been switched past the fabric core and therefore are ready for dispatching downstream essentially at any time. The HOL problem can be overcome by setting up queues at each input that are destined for each output. This scheme is called Virtual Output Queues (VOQs). This means, in the case of N outputs, that each input port maintains locally N queues where it buffers packets destined for each of the N ferent outputs. This can be translated from an implementation standpoint as saying that the input buffers of a line card are divided into N logical queues corresponding to each one of the N outputs the switch must be able to service. If more than one VOQ is available, some contention will occur for simultaneous access to the shared medium (such as the fabric core's bandwidth); therefore, arbitra- 11. Refer to Note 6. 12. Srinivasan Keshav, An Engineering Approach to Computer Networking: ATM Networks and the Telephone Network (Reading, Massachusetts: Addison-Wesley, 1997). 13. N. McKeown, V. Anantharam, and J. Walrand, "Achieving 100% Throughput in an Input-Queued Switch," Proceedings of IEEE INFOCOM '96 (March 1996). 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. SWITCH FABRICS 284 NETWORK PROCESSORS tion and scheduling capabilities need to be considered. At each time step, an arbiter will choose at most one packet from each input port, SO that all selected packets can ultimately make it through the switch fabric to their intended outputs without any conflict (for the same output port). This theme has many variations as switch fabric vendors strive to differentiate their products. For example, IBM whose switch fabrics we discuss later in this chapter, are based on a shared memory architecture with VOQs. This enables some low-priority traffic to actually make i