314 CHAPTER 13 Switching Notice that if one had to choose four cells among eight choices, the simplest design would assign the eight choices (in pairs) to four 2-by-2 knockout concentrators. This logic will pick four winners, the desired quantity. While this logic is certainly much simpler than using four separate knockout trees, it can be very unfair. For example, suppose two very heavy traffic sources, S1 and S2, happen to be paired up, while another heavy source, S3, is paired up with a light source. In this case S1 and S2 would get roughly half the traffic that S3 obtains. It is to avoid these devious examples of unfairness that the knockout logic uses k separate trees, one for each position. The naive way to implement the trees is to begin running the logic for the Position j tree strictly after all the logic for the Position j - 1 tree has completed. This ensures that all eligible losers have been collected. A faster implementation trick is explored in the exercises. Hopefully, this design should convince you that fairness is hard to implement correctly. This is a theme that will be explored again in the discussion of iSLIP. While the knockout switch is important to understand because of the techniques it intro- duced, it is complex to implement and makes assumptions about traffic distributions. These assumptions are untrue for real topologies in which more than k clients frequently gang up to concurrently send to a popular server. More importantly, researchers devised relatively simple ways to combat HOL blocking without going to output queuing. 13.7 AVOIDING HEAD-OF-LINE BLOCKING BY USING PARALLEL ITERATIVE MATCHING The main idea behind parallel iterative matching (PIM) [AOST93] is to reconsider input queu- ing but to retrofit it to avoid head-of-line blocking. It does so by allowing an input port to schedule not just the head of its input queue, but also other cells, which can make progress when the head is blocked. At first glance, this looks very hard. There could be a hundred thousand cells in each queue; attempting to maintain even 1 bit of scheduling state for each