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 - ENS Paris, 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
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 17, 2015 - 4:59:16 PM
Last modification on : Thursday, March 17, 2022 - 10:08:33 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:15:49 PM


Publisher files allowed on an open archive




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



Record views


Files downloads