Exact Solution to Bandwidth Packing Problem with Queuing Delays

The bandwidth packing problem seeks to select and route a set of calls from a given list, each with a pre-specified requirement for bandwidth, on an undirected communication network such that the revenue generated is maximized. In this paper, we present a model and an exact solution approach for the bandwidth packing problem with queuing delay costs under stochastic demand and congestion. We provide a more general model than available in the extant literature by assuming a general service time distribution on the links. The problem, under Poison call arrivals, is thus set up as a network of spatially distributed independent M/G/1 queues. However, the presence of delay cost in the objective function makes the resulting integer programming model nonlinear. We present an exact solution approach based on piecewise linearization and cutting plane algorithm. Computational results indicate that the proposed solution method provides optimal solution in reasonable computational times. Comparisons of our exact solution method with the Lagrangean relaxation based solution reported in the literature for the special case of exponential service times clearly demonstrate that our solution approach outperforms the latter, both in terms of the quality of solution and computational times. Using numerical examples, we demonstrate that the service time variability, if not correctly represented in the model, can result in a solution very different from the optimal.