The optimal joint sequence design in the feedback-based two-stage switch

The feedback-based two-stage switch is scalable as it is configured by a predetermined and periodic joint sequence of configurations (Hu and Yeung, 2010). Its major problem is that the average packet delay is high under light traffic load. In this paper, we improve the performance of feedback-based switch while still ensuring in-order packet delivery and close to 100% throughput. We first show that the different sequences of configurations may endow a feedback-based switch with different delay performance. We propose to devise a tailor-made sequence of configurations for the coming traffic pattern. Given any traffic matrix, the optimal joint sequences that do exist can produce the lowest average packet delay. Then finding the optimal joint sequences is formulated as an ILP (Integer Linear Programming) problem. The simulation results demonstrate that the optimal joint sequence can cut down the average packet delay up to 14% under a random uniform traffic model and even 45% under a hot-spot traffic model. Last but not least, we also design a fast suboptimal algorithm for the practical implementation.