Bounds and Policies for Dynamic Routing in Loss Networks

Dimitris Bertsimas and Thalia Chryssikou
Additional contact information
Dimitris Bertsimas: Massachusetts Institute of Technology, Cambridge, Massachusetts
Thalia Chryssikou: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1999, vol. 47, issue 3, 379-394

Abstract: We consider the problem of maximizing a weighted sum of expected rewards in steady-state in multiclass loss networks under dynamic routing and admission control, with Poisson arrivals and exponentially distributed holding times. By aggregating the underlying Markov decision process, we derive linear programming relaxations that contain the achievable performance region under all admissible policies and lead to a series of progressively tighter upper bounds. These relaxations allow stronger bounds at the expense of higher computational times. We further propose a series of routing and admission control policies from the relaxations that outperform, in computational experiments, other heuristic policies, such as the dynamic alternative routing with trunk reservation and the least busy alternative routing, variations of which are used in practice. The suboptimality guarantees defined as best bound/best policy range from 0 to 2.5% under symmetry conditions (symmetric network topology, arrival rates, link capacities, rewards), and from 4% to 10% under asymmetry conditions. We discuss the qualitative behavior of these policies and obtain insights about their performance.

Keywords: programming; dynamic/optimal control; upper bounds for performance of loss network; communication heuristics; policies for dynamic routing (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.3.379 (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:inm:oropre:v:47:y:1999:i:3:p:379-394

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().