Achieving Flow Level Constant Performance Guarantees for CICQ Switches without Speedup

Performance guarantees provided by switches can be at different granularity: port level and flow level. As a trade-off, it is usually more expensive to provide performance guarantees at finer granularity. Existing solutions for switches to provide flow level performance guarantees require either expensive hardware support or centralized scheduling algorithms with multiple iterations. In this paper, we present the Flow-level Fair Scheduling (FFS) algorithm to provide flow level performance guarantees for Combined-Input- Crosspoint-Queued (CICQ) switches, which are special crossbar switches with a small exclusive buffer at each crosspoint of the crossbar. FFS uses hierarchical and multidimensional fair queueing to emulate the ideal Generalized Processing Sharing (GPS) model. The main features of FFS include: constant performance guarantees, bounded crosspoint buffer sizes, no speedup requirement, and distributed operation. We theoretically analyze the performance of FFS, and conduct simulations to verify the analytical results.