Skip to Main content Skip to Navigation
Reports

Linear probing with lazy deletions, parking problem with exponential sojourn time, receiver release Cambridge ring and other related problems

Abstract : In this paper we intend to give an exact analytical evaluation of some parameters arising in a general bin-packing problem. There is an infinite sequence of cells ranked from the left to the right. A cell is either empty, either busy, i.e. contains an item. Items are generated over the cells according to independent Poisson processes of l item per cell and per time unit. When an item is generated on an empty cell it enters the cell which therefore becomes busy. When an item is generated on a busy cell, it tries the next cell on the right and so forth, until it finds an empty cell which it enters. Each stored item has a sojourn time in the cell which is supposed to be exponential of mean one. When the item leaves a cell it disappears completely, i.e. quits the system, the cell immediately becomes empty and available for a next item. We give an exact evaluation of the steady state of the system in terms of a Taylor expansion with respect to variable l.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074856
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 4:35:10 PM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:45:41 PM

Identifiers

  • HAL Id : inria-00074856, version 1

Collections

Citation

Philippe Jacquet. Linear probing with lazy deletions, parking problem with exponential sojourn time, receiver release Cambridge ring and other related problems. [Research Report] RR-1816, INRIA. 1992. ⟨inria-00074856⟩

Share

Metrics

Record views

113

Files downloads

79