Exact Solution to Bandwidth Packing Problem with Queuing Delays

Navneet Vidyarthi, Sachin Jayaswal and Vikranth Babu Tirumala Chetty

No WP2013-11-04, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: The bandwidth packing problem seeks to select and route a set of calls from a given list, each with a pre-specifi ed 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 di fferent from the optimal.

Date: 2013-11-07
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.iima.ac.in/sites/default/files/rnpfiles/10525497742013-11-04.pdf English Version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:12140

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().