Bounds and policies for dynamic routing in loss networks
成果类型：
Article
署名作者：
Bertsimas, D; Chryssikou, T
署名单位：
Massachusetts Institute of Technology (MIT)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.47.3.379
发表日期：
1999
页码：
379-394
关键词：
摘要：
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.