Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-01-10T01:58:17.953Z Has data issue: false hasContentIssue false
  • English
  • Français

On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel

Published online by Cambridge University Press:  01 July 2016

Guy Fayolle ,
Philippe Flajolet  and
Micha Hofri
Guy Fayolle*
Affiliation:
INRIA
Philippe Flajolet*
Affiliation:
INRIA
Micha Hofri*
Affiliation:
Technion-Israel Institute of Technology
*
∗INRIA, Domaine de Voluceau, BP 103, 78153 Le Chesnay Cedex, France.
∗INRIA, Domaine de Voluceau, BP 103, 78153 Le Chesnay Cedex, France.
∗∗Computer Science Department, Technion–Israel Institute of Technology, Haifa 32000, Israel.
Get access Rights & Permissions [Opens in a new window]

Abstract

We analyse a stack protocol of the Capetanakis–Tsybakov–Mikhailov type for resolving collisions in a random multiple-access channel. We obtain a functional equation for the generating function of the expected collision resolution interval (CRI) durations, which is non-local with a non-commutative iteration semigroup. Using Mellin transform techniques and geometric properties of the iteration semigroup we show that for arrival rates smaller than a fixed threshold, the mean CRI duration for n initial colliders is asymptotically proportional to n. Ergodicity conditions are also demonstrated.

Keywords

ASYMPTOTIC ANALYSISFUNCTIONAL EQUATIONMELLIN TRANSFORMPROTOCOLRANDOM ACCESSTREE ALGORITHM
Type
Research Article
Information
Advances in Applied Probability , Volume 18 , Issue 2 , June 1986 , pp. 441 - 472
Copyright
Copyright © Applied Probability Trust 1986 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

References

Çinlar, E. (1975) Introduction to Stochastic Processes. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Davies, B. (1978) Integral Transforms and their Applications. Springer-Verlag, New York.CrossRefGoogle Scholar
Doetsch, G. (1955) Handbuch der Laplace Tranformation. Birkauser, Basel.CrossRefGoogle Scholar
Fayolle, G. (1975) Étude du comportement d&un canal radio partagé entre plusieurs utilisateurs. Thèse Docteur Ingénieur, Université Paris VI.Google Scholar
Fayolle, G. and Hofri, M. (1982) On the capacity of a collision channel under stack-based collision resolution algorithms. Dept of Computer Science, Technion.Google Scholar
Knuth, D. E. (1973) The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass.Google Scholar
Massey, J. L. (1981) Collision resolution algorithms and random access communication. In Multiuser Communications, ed. Longo, G., CISM Courses and Lectures 265, Springer-Verlag, New York, 73–137.Google Scholar
Tsybakov, B. A. and Vvedenskaya, N. D. (1980) Random multiple-access stack algorithm. Probl. Inf. Trans. 16, 230–243.Google Scholar
Vvendskaya, N. D. and Tsybakov, B. S. (1983) Random multiple-access of packets on a channel with errors (in Russian). Probl. Perd. Inf. 19, 52–68.Google Scholar

Reference added in proof

Fayolle, G., Flajolet, P., Hofri, M. and Jacquet, P. (1985) Analysis of a stack algorithm for random multiple-access communication. IEEE Trans. Inf Theory 31, 244–254.CrossRefGoogle Scholar