Collision-Resolution Algorithms and Random-Access Communications.

Abstract

The problem considered is the random-accessing by very many transmitters of a common receiver over a time-slotted collision-type channel with feedback. A collision-resolution algorithm (CRA) is a protocol for the transmission and retransmission of packets such that, after a collision, all transmitters eventually and simultaneously learn that all the colliding packets have been successfully retransmitted. Focus is placed on a CRA due to Capetanakis (the CCRA) and a slight modification thereof (the MCCRA). The fundamental (traffic-independent properties of the CCRA and MCCRA are derived by means of a recursive analysis, with emphasis on the mean and variance of the number of slots required to resolve a collision among N packets. These results are then used to analyze by a Markovian approach the performance of various random-access algorithms, built upon the CCRA and MCCRA, for the case of infinitely many identical sources generating Poisson traffic. The maximum stable throughput is determined for each random-access algorithm, and tight upper and lower bounds are developed for the delay-throughput characteristic of the 'obvious' random-access algorithm built upon the CCRA.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1980
Accession Number
ADA086695

Entities

People

  • James L. Massey

Organizations

  • University of California, Los Angeles

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Communication Systems
  • Engineering
  • Equations
  • Error Analysis
  • Feedback
  • Markov Chains
  • Multiple Access
  • Multiplexing
  • Probability
  • Probability Distributions
  • Random Variables
  • Steady State
  • Terminals
  • Throughput
  • Time Intervals
  • Transmitters

Fields of Study

  • Computer science

Readers

  • Mathematical Modeling and Probability Theory.
  • Radio communications and signal processing.