Hybrid Circuit/Packet Network Scheduling With Multiple Composite Paths

Shihhao Tseng Cornell University, USA
Bo Bai Huawei Technologies Co., Ltd., Hong Kong
John Chi Shing Lui Chinese University of Hong Kong, Hong Kong


A switching/forwarding fabric with high-bandwidth one-to-one and low-bandwidth many-to-many data forwarding can be achieved by combing electronic packet switches (EPS) and optical circuit switches (OCS). This hybrid solution scales well but it is not suitable for cloud computing/datacenter applications, which typically rely on one-to-many and many-to-one communications. Recently, composite-path switching (cp-switching), which adds paths between EPS and OCS, is introduced to deal with this skewed traffic pattern. The state-of-the-art scheduling algorithm for cp-switches reduces, by heuristics, a cp-switching problem with one composite path to a hybrid switching problem without the composite path, and leverages existing scheduling techniques to tackle the latter problem. Unfortunately, the approach provides neither performance guarantee nor the support for multiple composite paths. In this paper, we systematically study the shortest time cp-switch scheduling problem with multiple composite paths and show that the problem can be expressed as an optimization problem with sparsity constraints. An LP-based algorithm is derived accordingly which supports multiple composite paths and more importantly, it provides performance guarantee. Simulations demonstrate that adding more composite paths can help shorten the schedule, and our approach outperforms existing methods by 30% to 70%.

You may want to know: