Queueing delay guarantees in bandwidth packing

This paper proposes a new formulation for the bandwidth packing problem, as suring maximum service delay in telecommunications networks. The bandwidth packing problem is one of selecting calls, from a list of requests, to be r outed in the network. We limit the maximum queueing delay, while maximizing revenues generated from the routed calls. An efficient Lagrangean relaxati on based heuristic procedure for finding bounds and solutions to the proble m is demonstrated, and computational results from a variety of problem inst ances are reported. We show that the procedure is both efficient and effect ive in finding good solutions. (C) 1999 Elsevier Science Ltd. All rights re served.