Queueing delay guarantees in bandwidth packing

This paper proposes a new formulation for the bandwidth packing problem, assuring maximum service delay in telecommunications networks. The bandwidth packing problem is one of selecting calls, from a list of requests, to be routed in the network. We limit the maximum queueing delay, while maximizing revenues generated from the routed calls. An efficient Lagrangean relaxation based heuristic procedure for finding bounds and solutions to the problem is demonstrated, and computational results from a variety of problem instances are reported. We show that the procedure is both efficient and effective in finding good solutions.