A linear programming based heuristic algorithm for bandwidth packing problem with scheduling

Abstract

In this article, we consider a variant of the bandwidth packing problem, in which some demands need to be scheduled within given time windows. The emergence of cloud services has introduced a new challenge to the bandwidth packing problem. For example, a typical cloud service network consists of multiple data centres (DCs), and a huge amount of data must be exchanged between DCs to ensure the integrity of the data. This operation is not necessarily real-time, which allows network operators to schedule the demands over time. Motivated by a real-life network service provider in South Korea, we developed a practical heuristic algorithm for the problem. The algorithm utilises an open source linear programming solver. The performance of the proposed algorithm was assessed on the real-life telecommunication network in South Korea. The computational results showed that the proposed approach can provide near-optimal solutions within a short time.