Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
1997-04-10
2001-09-18
Luther, William (Department: 2664)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S447000, C370S461000
Reexamination Certificate
active
06292493
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method for detecting collisions in a transmission channel using a distributed queueing random access protocol (DQRAP) wherein broadcast channel time is divided into a plurality of slots, each of which includes one data slot and one or more control minislots, and each of a plurality of sending stations maintains two common distributed queues. One queue, the data transmission queue, is used to organize the order of data transmission, and the other queue, the collision resolution queue, is used to resolve collisions that have occurred and to prevent collisions by new arrivals. The protocol includes data transmission rules, request transmission rules and queueing discipline rules.
2. Description of Prior Art
Investigation of multiple, random access control methods has been an active research area since as early as 1970. The well known CSMA protocols were then developed and later followed by multiple access methods which utilized various forms of feedback to improve performance by reducing or avoiding the occurrence of collisions. These included collision resolution schemes, now called tree-and-window collision resolution algorithms (CRA). The CSMA protocols achieved high throughput with minimal delay with low offered loads, and they have gained wide application in local area networks. In fact with zero propagation delay, collisions in slotted CSMA can be completely avoided and the performance of CSMA then corresponds to that of a perfect scheduling protocol, such as an M/D/1 queue. However, the CSMA protocols are not stable when traffic is heavy and while dynamic control mechanisms can improve performance, the unstable nature cannot be changed.
The first CRA included a tree algorithm which achieved a maximum throughput of 0.43, and was stable for all input rates of less than 0.43. This stable characteristic of the tree algorithm has attracted much attention in both the communications and information theory areas. The tree algorithm was improved by increasing the maximum throughput to 0.462. The next improvement was the 0.487 window protocol. The tree and window protocols are based on efficient use of channel feedback to resolve collisions and require transmitter coordination. It has been shown that the upper bound of throughput of all algorithms based on ternary feedback is 0.568, the tightest upper bound to date.
It is widely believed that the best achievable throughput is in the neighborhood of 0.5. If the amount of channel feedback is increased to indicate the number of packets involved in each collision, then throughput up to one may be achieved. However, the known algorithms in this context achieve only 0.533 throughput. Some known protocols achieve higher throughput than 0.5 by using control minislots (CMS) to obtain extra feedback. Among such known protocols, the announced arrival random access protocols (AARA) achieve the best performance with respect to throughput and delay characteristics. With three minislots the AARA protocol achieves a throughput of 0.853. However, to achieve throughput approaching one, the AARA protocol must use an infinite number of minislots. Obviously, the AARA protocols do not achieve or approach the bound of performance in this context. All existing tree protocols seem to use data slots to resolve collisions. In this process, channel capacity is lost either to empty slots or to collisions. All suggested improvements to tree protocols increased the channel throughput by reducing empty slots and collided slots, but none eliminated this type of loss.
SUMMARY OF THE INVENTION
It is one object of this invention to provide a method for controlling multiple access of a transmission channel through the detection of collisions by comparing a plurality of different patterns within a control minislot.
It is another object of this invention to assign different Binomial coefficients to a plurality of sending stations and to use such Binomial coefficients to detect collisions.
It is still another object of this invention to use a distributed queueing random access protocol in various systems, such as with packet radio, satellite, broadband cable, cellular voice, and other passive optical networks.
The distributed queueing random access protocol (DQRAP) of this invention is a stable random multiple access protocol for use in a broadcast channel shared by an infinite number of bursty stations. The DQRAP according to this invention is based on tree protocols with minislots. These tree protocols use minislots to provide extra feedback in order to reduce the number of empty and collided slots. However, the DQRAP according to this invention uses the minislots for collision resolution and resolves the data slots for data transmission. Implicitly, even though counters are often used, conventional tree algorithms use a single queue which performs as a collision resolution queue. The method according to this invention achieves the desired performance by introducing an additional queue, the data transmission queue, to schedule data transmission parallel to contention resolution and thereby nearly eliminating contention in the data slots. The DQRAP of this invention, using as few as three minislots, achieves a performance level which approaches that of a hypothetical perfect scheduling protocol, such as the M/D/1 system, with respect to throughput and delay.
REFERENCES:
patent: 4774707 (1988-09-01), Raychaudhuri
patent: 5303234 (1994-04-01), Kou
patent: 5390181 (1995-02-01), Campbell et al.
Xu, Wenxin, “Distributed Queueing Random Access Protocols for a Broadcast Channel”, thesis paper, Illinois Institute of Technology, Chicago Illinois, Dec. 1990.
Campbell Graham M.
Xu Wenxin
Illinois Institute of Technology
Luther William
Pauley Peterson Kinne & Fejer
LandOfFree
Method and apparatus for detecting collisions on and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for detecting collisions on and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for detecting collisions on and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2463284