Browse Prior Art Database

CONTENTION RESOLUTION BACKOFF ALGORITHM

IP.com Disclosure Number: IPCOM000009521D
Original Publication Date: 1999-Sep-01
Included in the Prior Art Database: 2002-Aug-29
Document File: 2 page(s) / 122K

Publishing Venue

Motorola

Related People

K. Aswarth Rao: AUTHOR [+3]

Abstract

Many random access algorithms have been implemented, investigated and studied for a period of time in data communication industry. Basically these algorithms can be categorized into following three classes: 1. Generalized Aloha algorithm: Every network user monitors its status after transmitting its access request, this request may be a new request or a retransmission of previous request since it has not been successfully accepted by the network. User can uniformly select a time slot to retransmit its request over next few time slots or to retransmit the request in the next time slot with certain probability, or using an exponential backoff process to handle the retransmission request in different algorithms. This kind of algorithm eventually becomes unstable and needs to generate the system throughput versus sys- tem average delay curve to investigate its system behavior.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 2

MOTOROLA Technical Developmenrs

CONTENTION RESOLUTION BACKOFF ALGORITHM

by K. Aswarth Rao, Yih G. Jan and Joel L. Gross

BACKGROUND

  Many random access algorithms have been implemented, investigated and studied for a period of time in data communication industry. Basically these algorithms can be categorized into following three classes:

   1. Generalized Aloha algorithm: Every network user monitors its status after transmitting its access request, this request may be a new request or a retransmission of previous request since it has not been successfully accepted by the network. User can uniformly select a time slot to retransmit its request over next few time slots or to retransmit the request in the next time slot with certain probability, or using an exponential backoff process to handle the retransmission request in different algorithms. This kind of algorithm eventually becomes unstable and needs to generate the system throughput versus sys- tem average delay curve to investigate its system behavior.

   2. Splitting Algorithm: It can be further classi- fied either as a tree searching or a stack splitting algorithm. User makes its new transmission or retransmission based on the continuous observations of the feedback link information. In tree searching algorithm new requests are not permitted while the resolution of existing collided requests are under way. In the operation it needs to calculate the colli- sion resolution interval and also to develop the so- called 'first transmission rule'. In the stack splitting algorithm, however, new requests are permitted dur- ing the collision resolution time interval and it does not need to calculate the collision resolution interval or consider the fust transmission rule. This algo- rithm is a stable process and its throughput is better than the ALOHA algorithm, however its average system delay is sometimes longer than the ALOHA algorithm and it may take a longer time for the algo- rithm to converge to the final solution.

  3. Adaptive P-Persistence Algorithm: This algo- rithm and its extensions are mainly proposed in CATV network. The network control station allo- cates the available time slots into two proper slots: the data time slots and the access request mm-slots. These mini-slots are further partitioned into two regions: one for the new requests and the other for the collided requests, The partition of these two regions are controlled by parameters involving the total number of time slots, the available mini-slots, the number of mini-slots dedicated for new requests and collided requests at every time instant and the final steady state system capacity. This algorithm is recently proposed in the CATV industry and is in the simulation test stage. It may not be easy or impossible to collect the information of how many users are collided i...