An analysis of a contention resolution algorithm. Another approach
type: Item
instance of: scholarly article
title: An analysis of a contention resolution algorithm. Another approach
zbMATH Open document ID: 0623.68035
DOI: 10.1007/BF00264363
author: Wojciech Szpankowski
published in: Acta Informatica
publication date: 1987-01-01T00:00:00Z
review text: A single multiaccess channel is studied with the outcome of a transmission being either 'idle', 'success', or 'collision' (ternary channel). Packets involved in a collision must be retransmitted, and an efficient way to solve a collision is known in the literature as Gallager-Tsybakov-Mikhailov algorithm. Performance analysis of the algorithm is quite hard. In fact, it bases on a numerical solution of some recurrence equations and on a numerical evaluation of some series. The obvious drawback of it is lack of insight into the behavior of the algorithm. We shall present a new approach of looking at the algorithm and discuss some attempts of analyzing its performance. In particular, expected lengths of a resolution interval and a conflict resolution interval as well as throughput of the algorithm will be discussed using asymptotic approximation and ''a small input rate'' approximation.
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 94A05
zbMATH DE Number: 4011926
zbMATH Keywords: packet-switching network
zbMATH Keywords: communication channel
zbMATH Keywords: conflict resolution
zbMATH Keywords: multiaccess channel
zbMATH Keywords: ternary channel
zbMATH Keywords: collision
zbMATH Keywords: Performance analysis
zbMATH Keywords: recurrence equations
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/bf00264363
OpenAlex ID: W2036687772
description: scientific article; zbMATH DE number 4011926