PDL Abstract

Scheduling Techniques for Hybrid Circuit/Packet Networks

In 11th International Conference on emerging Networking EXperiments and Technologies (CoNEXT 2015), Heidelberg, Germany, December 2015.

He Liu†, Matthew K. Mukerjee, Conglong Li, Nicolas Feltman, George Papen*, Stefan Savage*, Srinivasan Seshan, Geoffrey M. Voelker*, David G. Andersen, Michael Kaminsky^, George Porter*,
Alex C. Snoeren

Carnegie Mellon University
* University of California, San Diego
^ Intel Labs
† Google, Inc.


A range of new datacenter switch designs combine wireless or optical circuit technologies with electrical packet switching to deliver higher performance at lower cost than traditional packet-switched networks. These “hybrid” networks schedule large traffic demands via a high-rate circuits and remaining traffic with a lower-rate, traditional packet-switches. Achieving high utilization requires an efficient scheduling algorithm that can compute proper circuit configurations and balance traffic across the switches. Recent proposals, however, provide no such algorithm and rely on an omniscient oracle to compute optimal switch configurations. Finding the right balance of circuit and packet switch use is difficult: circuits must be reconfigured to serve different demands, incurring non-trivial switching delay, while the packet switch is bandwidth constrained. Adapting existing crossbar scheduling algorithms proves challenging with these constraints. In this paper, we formalize the hybrid switching problem, explore the design space of scheduling algorithms, and provide insight on using such algorithms in practice. We propose a heuristic-based algorithm, Solstice that provides a 2.9X increase in circuit utilization over traditional scheduling algorithms, while being within 14% of optimal, at scale.