Achieving 100% Throughput in Two-stage Switch with Feedback

Abstract

The feedback-based two-stage switch in [9] elegantly solves the packet mis-sequencing problem without sacrificing the packet delay performance. In this paper, we prove that for any arbitrary work-conserving input port scheduler, the feedback- based two-stage switch can achieve 100% throughput under a speedup of two. We first establish the fluid model for feedback- based two-stage switch. Based on it, a joint queue occupancy function is derived by taking all packets arrived at input i and all packets destined for output j into account. By showing there is no fluid accumulation for this function, we prove that the feedback- based switch is stable under a speed up of two. Compared with other switches operating at a speedup of two, feedback-based two- stage switch does not require a central scheduler as its switch fabrics are configured according to a pre-determined and periodic sequence of switch configurations. It is thus more scalable and practical for implementation even under a speedup of two. © 2008 IEEE 203.