Most present day switching systems, in Internet routers and data-center switches, employ a single input-queued crossbar to interconnect input ports with output ports Such switches need to compute a matching, between input and output ports, for each switching cycle (time slot) The main challenge in designing such matching algorithms is to deal with the unfortunate tradeoff between the quality of the computed matching and the computational complexity of the algorithm In this work, we propose a general approach that can significantly boost the performance of both SERENA and iSLIP, yet incurs only O(1) additional computational complexity at each input output port Our approach is a novel proposing strategy, called Queue-Proportional Sampling (QPS), that generates an excellent starter matching We show, through rigorous simulations, that when starting with this starter matching, iSLIP and SERENA can output much better final matching decisions, as measured by the resulting throughput and delay performance, than they otherwise can

Jun (Jim) Xu has been a Professor in the School of Computer Science at Georgia Institute of Technology since 2000. A major thrust of his research lies in Network Algorithmics, the science of designing high-speed Internet routers, firewalls, and measurement devices. He started to work in the area of Big Data in early 2000’s, long before it was called Big Data. He received ACM Sigmetrics 2004 Best Student Paper Award, and has been an ACM Distinguished Scientist since 2010.