Skip to Main content Skip to Navigation
Conference papers

Online Bandwidth packing with symmetric distribution

Marc Lelarge 1
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt
Abstract : We consider the following stochastic bin packing process: the items arrive continuously over time to a server and are packed into bins of unit size according to an online algorithm. The unpacked items form a queue. The items have random sizes with symmetric distribution. Our first contribution identifies some monotonicity properties of the queueing system that allow to derive bounds on the queue size for First Fit and Best Fit algorithms. As a direct application, we show how to compute the stability region under very general conditions on the input process. Our second contribution is a study of the queueing system under heavy load. We show how the monotonicity properties allow one to derive bounds for the speed at which the stationary queue length tends to infinity when the load approaches one. In the case of Best Fit, these bounds are tight. Our analysis shows connections between our dynamic model, average-case results on the classical bin packing problem and planar matching problems.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184778
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 4:59:16 PM
Last modification on : Thursday, July 1, 2021 - 5:58:02 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:15:49 PM

File

dmAH0136.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184778, version 1

Collections

Citation

Marc Lelarge. Online Bandwidth packing with symmetric distribution. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. pp.519-532. ⟨hal-01184778⟩

Share

Metrics

Record views

281

Files downloads

547