HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Optimal Routing Problems and Multimodularity

Eitan Altman 1 Sandjai Bhulai 2 Bruno Gaujal Arie Hordijk
2 SLOOP - Simulation, Object Oriented Languages and Parallelism
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this paper we study the static assignment of packets to M parallel heterogeneous servers with no buffers. Blocked packets are lost and the objective is to minimize the average number of lost packets. The paper is divided into three parts. In the first part we formulate the problem as a Markov Decision Problem with partial observation and we derive an equivalent full observation problem. From this full observation problem we derive some structural results. We establish, in particular, the existence of an optimal periodic policy. The second part of the paper deals with computational aspects of the problem. We use multimodularity to derive an algorithm to compute optimal policies and show that for two servers the cost function is multimodular. In the third part we consider the same problem with well known arrival processes, such as the Poisson Process, the Markov Modulated Poisson Process and the Markovian Arrival Process.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 11:19:33 AM
Last modification on : Friday, February 4, 2022 - 3:15:49 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:28:39 PM


  • HAL Id : inria-00072937, version 1



Eitan Altman, Sandjai Bhulai, Bruno Gaujal, Arie Hordijk. Optimal Routing Problems and Multimodularity. RR-3727, INRIA. 1999. ⟨inria-00072937⟩



Record views


Files downloads