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.
Type de document :
Rapport
[Research Report] RR-1816, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00074856
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:35:10
Dernière modification le : mardi 17 avril 2018 - 11:28:29
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:45:41

Fichiers

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

52