A Lagrangean Relaxation Based Scheme For Allocation Of Bandwidth

In this paper we study the bandwidth packing problem in the presence of priority classes. The bandwidth packing problem is defined as the selection and routing of messages from a given list of messages with prespecified requirements on demand for bandwidth. The messages have to satisfy delay constraints and have to be routed over a network with given topology so that the revenue generated from routing these messages is maximized. Messages to be routed are classified into two priority classes. An integer programming based formulation of this problem is proposed and a Lagrangean relaxation based methodology is described for solving this problem. Several numerical experiments are conducted using a number of problem parameters such as percentage of messages, ratio of messages of lower to higher priority, capacity of links and high quality solutions to the bandwidth packing problem are generated under the different situations.published_or_final_versio