On the necessary and sufficient requirement of a CIOQ switch to emulate an Output Queued switch

There has been much interest to emulate the behavior of Output Queued switches. The early result of such attempts was reported by Prabhakar and McKeown using the CIOQ switches with speedup factor of 4. Subsequently, Stoica and Zhang and independently Chuang et al. showed that a speedup of 2 in conjunction with their scheduling schemes would be sufficient for CIOQ switches to emulate Output Queued switches.Additionally, Chuang et al. showed that in “Average Sense” a speedup of 2−1/N is necessary and sufficient for CIOQ to emulate Output Queued switch behavior.Our paper reports that in the “Strict Sense” a speedup of 2 is both necessary and sufficient. We show this requirement using examples for 2x2 and 3x3 switches. Then, with a constructed traffic pattern, it is proved that in the “Strict Sense” a speedup of 2 is necessary to emulate the behavior of an Output Queued switch for any switch size N.Combining this result with the previous scheduling schemes, we conclude that in the “Strict Sense”, a speedup of 2 is the necessary and sufficient condition to emulate the behavior of an Output Queued switch, using a CIOQ switch.Additionally, easing the assumptions and allowing the packet segmentation, it is shown that the speedup requirement to emulate the behavior of an Output Queued switch can be reduced to values even smaller than 2−1/N. For this case a lower bound of 3/2 and an upper bound of 2 is proved.