Bandwidth calendaring: Dynamic services scheduling over Software Defined Networks
Lazaros Gkatzikis, Stefano Paris, Ioannis Steiakogiannakis, Symeon Chouvardas · 2016
Software Defined Networking enables centralized network control and hence paves the way for new services that use network resources more efficiently. Bandwidth Calendaring (BWC) is a typical such example that exploits the knowledge of future to optimally pack the arising demands over the network. In this paper, we consider a generic BWC instance, where a carrier network operator has to accommodate at minimum cost demands of predetermined, but time-varying, bandwidth requirements. Some of the demands may be flexible, i.e., can be scheduled within a specific time window. We demonstrate that the resulting problem is NP-hard and we propose a scalable problem decomposition based on column generation. Our numerical results reveal that the proposed solution approach is near-optimal and outperforms state-of-the art methods based on relaxation and randomized rounding by more than 20% in terms of network cost.