Multiplex communications – Channel assignment techniques – Arbitration for access to a channel
Reexamination Certificate
1998-05-04
2001-05-22
Ton, Dang (Department: 2661)
Multiplex communications
Channel assignment techniques
Arbitration for access to a channel
C370S464000, C370S465000, C370S478000
Reexamination Certificate
active
06236662
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to multi access communication methods that allow a variable number of users to exchange voice and data information. The methods of the present invention allow for highly optimized throughput rates while also minimizing the probability of network detection and interception; otherwise known as low probability of detection and interception, or LPD/LPI.
2. Description of the Related Art
A central problem of multi-access communications is that of sharing a communications medium between a multiplicity of nodes where each node has random requirements for transmitting or receiving packets of data. The communications medium, acting as a server, does not know which nodes contain packets. Similarly, nodes are unaware of packets at other nodes. If two or more nodes transmit simultaneously to a hidden node, the reception is garbled. If none of the nodes transmits, the medium is unused. This results in an inefficient and underutilization of the communications medium. Likewise, when a transmission requires links through multiple nodes to reach an intended receiver, situations arise where the optimum path is not always selected. Therefore, data packets can arrive out of order where a later sent data packet arrives before an earlier sent one due to selecting a shorter or more optimum path for the later sent packet. While this feature does not present a burdensome problem for voice communications, data communications are another matter.
A number of multi-access communication techniques have been developed to accommodate this generic problem of queuing the data packets in a network configuration in order to minimize collisions. Two basic strategies have been adopted. One is a free-for-all approach in which nodes normally send new packets immediately, hoping for no interference from other nodes. The other strategy deals with scheduling, or reserving, the channel in response to the dynamic requirements of the individual nodes. One communications technique within the free-for-all approach is the Aloha system. When each node in the Aloha system receives a new data packet, the node transmits it immediately rather than waiting. If a data packet is involved in a collision, it is retransmitted after a random delay. If the transmission times for two data packets overlap at all, then the parity checks on those packets will fail and retransmission will be required. A limited type of feedback is provided when the intended receiver rebroadcasts the composite received signal so that each node, after a given propagation delay, can determine whether or not its transmitted packets were correctly received. Maximum efficiency of this system is 18% utilization of the channel.
An improvement to the Aloha system is the Slotted Aloha. The basic idea of this multi-access communications technique is that each unbacklogged node simply transmits a newly arriving data packet in the first slot after data packet arrival, thus risking occasional collisions but achieving a very small delay. When a collision occurs in slotted Aloha, the collision is discovered at the end of the slot by each node sending one of the colliding data packets, creating a backlog. Instead of a backlogged node re-transmitting in the next slot after being involved in a collision, the node waits for some random number of slots before retransmitting to avoid the same collision again. Maximum efficiency of the Slotted Aloha system is double that of the unslotted Aloha system, that is, approximately 36%. However, an advantage of the Aloha system over the Slotted Aloha is that the Aloha can be used with variable length data packets, while the Slotted Aloha requires long data packets to be broken up to fit into slots and short data packets to be expanded to fill up slots.
An improvement in system efficiency over the Aloha and Slotted Aloha techniques can be found in a modified free-for-all approach known as Carrier Sense Multiple Access CSMA. Using CSMA, a data packet is not allowed to start if the channel is sensed to be busy. This technique is critically dependent on the ratio of propagation delay to data packet transmission time. The ratio represents the time required for all sources to detect an idle channel after a transmission ends. A smaller ratio allows CSMA to decrease delay and increase throughput significantly over Aloha type techniques. Nonetheless, the performance of CSMA degrades with an increase in the ratio of the propagation delay to data packet transmission time and thus also degrades with increasing channel rate and with decreasing data packet size. Thus, efficiency varies with the varying lengths of the data packets. However, collisions still occur when two nodes listen and then initiate a transmission to the same node, resulting in garbled data. Slotted CSMA is variation of CSMA in which idle slots have a fixed duration equal to the ratio of the propagation delay to data packet transmission time. In Slotted CSMA, if a packet arrives at a node while a transmission is in progress, the data packet is regarded as backlogged and begins transmission with a certain probability after each subsequent idle slot. The data packets arriving during an idle slot are transmitted in the next slot as usual. This technique is called Nonpersistent CSMA. Efficiency of the CSMA type techniques vary from 30% with CSMA and up to 80% using Slotted CSMA.
Scheduling or reserving the channel provides the other major approach to multi-access communication techniques. System throughput and efficiency can be increased if short packets are sent in either a contention mode or a time division multiplex TDM mode and if the short packages are used to reserve longer noncontending slots for the actual data. Thus, the slots wasted by idles or collisions are all short, leading to a higher overall efficiency. The channel can be reserved by a pre-arranged fixed allocation or can be reserved dynamically. Dynamic reservations further divide into the use of collision resolutions and the use of TDM to make the reservations for channel use.
CSMA/Collision Detection CSMA/CD is an example of the use of collision resolution to make implicit reservations. In this situation, all the nodes hear each other so that when one node transmits a packet, all the other nodes hear that packet. In addition, as in carrier sensing, a node can listen to the channel before transmitting. Finally, it is possible for a node to listen while transmitting, allowing for collision detection. If one node starts transmitting and no other node starts before the signal of the first node has propagated throughout the cable, the first node is guaranteed to finish its packet without collision. Thus, this technique can be viewed as the first portion of a packet as making a reservation for the rest of the data to be exchanged. In terms of system efficiency, CSMA/CD becomes increasingly inefficient with increasing propagation delay, with increasing data rate, and with decreasing packet size.
Collision resolution is more difficult for packet radio nets when not all nodes can hear the transmissions of all other nodes. The complication arises in obtaining feedback on the information sent so as to know which nodes received the data without a collision. The techniques mentioned earlier, such as Slotted Aloha and Aloha, are applicable and to a certain extent, some of the ideas of carrier sensing and reservations can still be used. For example, when an unbacklogged node receives a packet to transmit either a new packet entering the network or a packet in transit that has to be forwarded to another node, it sends the packet in the next slot. If no acknowledgment or ACK of the correct reception arrives within some time-out period, the node becomes unbacklogged when all of its packets have been transmitted and acknowledged or ACKed successfully.
While such multi-access communication methods have proven to be reliable, collision resolution is a central problem that effects system efficiency within the chosen communications medium.
SUMMARY OF THE INVENTION
It
BAE SYSTEMS Aerospace Inc.
Onders Edward A.
Ritchie William B.
Ton Anthony
Ton Dang
LandOfFree
Multirate time reservation multi-access protocol does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multirate time reservation multi-access protocol, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multirate time reservation multi-access protocol will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2509738