Multiplex communications – Channel assignment techniques – Using time slots
Reexamination Certificate
1997-11-20
2002-06-18
Ton, Dang (Department: 2661)
Multiplex communications
Channel assignment techniques
Using time slots
Reexamination Certificate
active
06408009
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method for detecting collisions in a transmission channel which is accessed by stations 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 sending station 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. In an alternative embodiment a station employing the two distributed queues also can send a control minislot containing a destination identifier and a data slot length indicator.
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 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.
It has been known for some time that digital data can be transmitted over serial and broadcast media. A problem continuously faced by the designer of digital data communication equipment is efficient utilization of the transmission and receiving equipment as well as efficient utilization of the medium or channel over which the data is to be transmitted and received. A number of approaches have been developed in the past, most of which suffer from one or more drawbacks. One of the earlier well-known digital data control systems is the Aloha System, originally developed for a packet radio application at the University of Hawaii and put into public use more than twenty years ago. The Aloha System, in its pure form, is based upon a broadcast transmission followed by a listening period for an acknowledge signal from the receiving station. If no acknowledge signal is received, the transmitting station then retransmits randomly until it receives an acknowledgement signal indicating that successful transmission has been achieved. The Aloha System, in its pure form, allows variable length data slots or frames to be transmitted. However, Aloha suffers from the drawback that, on average, its Aloha maximum efficiency is about 18%.
An improvement over the pure Aloha system is slotted Aloha, which fixes the periods for data transmission to a fixed time or a slot time, also known as a data slot. The system uses the same transmission followed by acknowledgement as the pure Aloha but, due to the use of the fixed length data slots, achieves, maximally, up to 36% efficiency in channel utilization. CSMA systems have been developed which are useful for relatively short length systems, where “a”, which is the ratio of the signal propagation delay to the time duration between the beginning of frame or slot transmission and the termination of frame or slot transmission, is less than 0.5. In those systems, CSMA is attractive. In order to practice the CSMA protocol, each station sharing a broadcast or other medium “listens” to the medium and does not initiate a transmission unless its response to listening indicates that the channel is currently unoccupied by a transmission from any other station. Such systems, however, do not achieve high throughput, in part because the maximal dimension of the system is dictated by the propagation delay to frame length ratio. This does not provide for efficient channel utilization.
The CSMA/CD system provides an improved and more efficient protocol over that of the CSMA system because the CSMA system, upon hearing a collision occurring, backs off for a period of time determined by an exponential back-off algorithm which is executed in appropriate software or hardware logic.
A significant improvement over the prior systems involves a digital protocol wherein a number of nodes, or stations, may all be connected to a single broadcast medium, whether wired or wireless, or may be connected in a star configuration or other configurations. Each of the stations includes a nodal apparatus which has a storage which may include a memory for storing a conflict resolution queue and a transmission queue. The system is a slotted system in that periodically, and at regular intervals, one or more control minislot signals may be transmitted from a particular station followed by a data transmission in a data slot in response to conditions in the conflict resolution queue and in the transmission queue. Such a system achieves significantly improved utilization of the channel capacity, in some cases, approaching 1.00 of the channel capacity.
One of the drawbacks of such a distributed queue random access protocol system, which is disclosed in Xu, Wenxin, “Distributed Queuing Random Access Protocols for a Broadcast Channel,” Illinois Institute of Technology, Chicago, Ill., December, 1990, and U.S. Pat. No. 5,390,181, lies in the fact that for certain systems, such as local area network systems which not only have bursty transmission, but have transmission wherein the amount of data to be transmitted may vary significantly from time to time. Thus, if the fixed length data slot used in the basic distributed queue random access protocol is employed, there may be some channel inefficiencies which result due to the data slot not being entirely filled by a
Campbell Graham M.
Wu Chien-Ting
Illinois Institute of Technology
Paul Petersen Kinne & Erickson
Ton Dang
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-2949900