Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-04-07
2001-08-21
Hsu, Alpus H. (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S447000, C370S462000
Reexamination Certificate
active
06278713
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates, in general, to protocols for transmitting digital data and, in particular, to protocols for short haul digital systems such as local area networks.
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 mission 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., Dec., 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 particular data transmission, thus causing some wastage of channel capacity. Likewise, inefficiency may result because a frame longer than the data slot must be segmented and, of course, associated with its own respective control minislots which effectively add unneeded overhead. What is needed is a system which employs conflict resolution queues and transmission queues in combination with a flexible data slot assignment and control system to enhance further the inherent efficiencies in the distributed queue random access protocol system.
SUMMARY OF THE INVENTION
The present invention relates to nodal apparatus and networks employing multiple distributed queues wherein the efficiency of channel utilization, whether on a broadcast channel, star channel or other types of channels is substantially equivalent to the offered load up to an offered load of one. In the event that the offered load is greater than the channel capacity, the inventive system allows the channel utilization to remain at one independently of offered loads of one or above, less the overhead allocated to the control minislots.
The system which provides sufficient channel utilization is a distributed queue random access protocol (DQRAP) system, wherein multiple nodes each include a memory for storing a conflict resolution queue which includes a counter that is incremented when a collision occurs during any control minislot (CMS). An index or other identification is attached to a particular count when the local station has attempted to transmit during a control minislot and detects a collision signal resulting from that control minislot. A second queue is also kept within the nodal station, which queue contains a counter that is incremented for each collision-free minislot access. An index is attached to particular queue numbers to identify the ordinal numeral, or position in the queue, occupied by the particular local station. Thus, each station maintains a conflict resolution queue with a counter having been marked to identify when the station may seek access to control minislots and a transmission queue indicating when the station may transmit during data slots. It may be appreciated that when there is no minislot collision and the transmission queue counter is zero at a local station, the station may immediately transmit its data during that data slot. Each station is further provided with a system for varying the length of a data slot following the control minislot during a particular frame to accommodate, to some extent, variable length data sets which are to be transmitted over the system. In effect, this provides on-the-fly reallocation of the relative proportion of slot time accorded to control minislots versus data slots, thereby enhancing the overall efficiency of the system. In the event that the transmission queue is equal to zero, the dynamic reallocation enters what may be termed an asynchronous mode, wherein stations essentially transmit without control minislots having been sent. In the event that no data or very little data is being sent, the data slot can be shrunk to as little as the round-trip propagation delay between a station and the head-end. In this system, the propagation delay is selected to be the maximum propagation delay between the most distant station and the head-end. The “shrunken” data slot allows beacon or timing signals to be sent out from a single station, which signals reach the head-end and then are reflected or retransmitted on the receiving lines to all stations other than the head-end station, to provide synchronization for slot times on
Campbell Graham M.
Wu Chien-Ting
Ho Duc
Hsu Alpus H.
Illinois Institute of Technology
Pauley Petersen Kinne & Fejer
LandOfFree
Method and apparatus for distributed queue digital data... 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 distributed queue digital data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for distributed queue digital data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2527004