CONTENTION RESOLUTION BACKOFF ALGORITHM
Permalink
Bookmark
Share
Twitter
Digg
Reddit
Facebook
Stumbleupon
Del.icio.us| IP.com Number | IPCOM000009521D |
|
|
|---|---|---|---|
| Dated | Sep 1, 1999 UTC | ||
| Size | 2 page(s) (121.6 KB) | ||
| Disclosed by |
|
||
Publication Summary
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.| Country | United States |
|---|---|
| Language | English (United States) |
| Related Person(s) |
(AUTHOR) K. Aswarth Rao (AUTHOR) Yih G. Jan (AUTHOR) Joel L. Gross |
| Copyright | Motorola Inc. September 1999 |
About this Publication
This document was submitted to IP.com's Prior Art Database and this preview is designed to provide you with information regarding the contents of this document by displaying up to the first four pages of the document as scaled page renderings and displaying a limited amount of text which was extracted from the document on the Text Preview Tab.
To find out more on how to obtain the entire document, click the Download tab. There is a charge for downloading some Prior Art Database documents; please examine carefully whether you believe this document fills your needs before purchasing.
For more information about the Prior Art Database, visit the Learn section of this website. Thank you for visiting IP.com's Prior Art Database! You may wish to check out our Global Patent Search website before you leave.
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...