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.