Multiplex communications – Generalized orthogonal or special mathematical techniques
Reexamination Certificate
1998-02-06
2001-02-20
Nguyen, Chau (Department: 2663)
Multiplex communications
Generalized orthogonal or special mathematical techniques
C370S329000
Reexamination Certificate
active
06192026
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to communication network protocols for medium access. In particular, the present invention relates to communication network protocols in the context of a wireless medium and in the context of communication networks that utilize fixed minimum packet sizes.
Data communications devices (DCDs) on certain common types of network must share the communication medium. The function of a medium access control (MAC) protocol is to allow each DCD the opportunity to seize the medium to transmit its data according to the rules of the protocol. In order to facilitate effective data communications, the opportunities to transmit should occur such that the wait time between opportunities is not excessive. In addition, access to the medium should be distributed fairly among the DCDs. A number of MAC protocols have been developed and fielded in wired networks.
These protocols include ALOHA, slotted-ALOHA, CSMA, and CSMA-CD. The ALOHA system is described in N. Abramson, “The ALOHA System—Another Alternative for Computer Communications,” 1970 Fall Joint Computer Conference, AFIPS Conference Proceedings, Vol. 37, AFIPS Press, Montvale N.J., 1970, the contents of which are herein incorporated by reference. CSMA and CSMA-CD systems are described in Anthony S. Acampora, “An Introduction to Broadband Networks,” Plenum Press, New York, N.Y., 1994, the contents of which are herein incorporated by reference.
ALOHA and slotted-ALOHA are random access schemes that could be adapted fairly easily to wireless networks. However, these MAC protocols suffer from poor maximum bus utilization.
While CSMA and CSMA-CD exhibit much better bus utilization, these protocols are much better suited to wired networks than wireless for the following reason: The operation of both CSMA and CSMA-CD depend upon each DCD in the network being able to sense when any of the other DCDs is transmitting. A DCD only transmits when it has determined that the bus is not currently in use by another DCD. This requirement becomes problematic in a wireless network since it often occurs that not every DCD in the network is within range of all the others.
FIG. 1
depicts a simple wireless network
100
with 3 DCDs
102
. B communicates with both A and C. A and C are separated by too large a distance to detect when the other is transmitting, and are therefore obviously unable to communicate directly. To illustrate the problem that can arise, suppose A is transmitting to B. Since C cannot detect A's transmissions, it will mistakenly assume that the medium is not being used. Then, suppose that C, mistakenly believing that the bus is idle, attempts to transmit a message to B. As a result, a data collision occurs at B and the messages transmitted by both A and C are corrupted or one of the messages is lost. A situation such as this is commonly referred to as the “hidden terminal problem.”
FIG. 2
depicts a solution to the hidden terminal problem. A wireless network
200
includes several DCDs
202
and a specialized central DCD
204
, also referred to as an access point (AP)
204
. Each DCD
202
communicates through AP
204
. AP
204
allocates the use of the medium by all DCDs
202
making up the network. In order to be integrated into the network configuration, any remote DCD
202
must be within the coverage area of AP
204
. This ensures that DCD
202
is able to receive, and will therefore adhere to, the commands issued by AP
204
concerning use of the medium.
MAC protocols using this network architecture have been implemented for cellular communication systems, wherein the base stations serve as APs and the cellular phones serve as the DCDs. However, because the nature of voice traffic is quasi-continuous and relatively low bandwidth, cellular MAC protocols are designed with circuit-switched channel assignments. The available spectrum is divided into frequency channels and/or time slots and/or spread spectrum spreading code channels that are assigned to a user for the duration of a call, regardless of whether there is any voice activity. This type of MAC protocol is inefficient in a typical computer or multi-media network due to the inherently bursty nature of its traffic. Exchanging bursty traffic over a circuit-switched network results in the circuit-switched connections frequently sitting idle.
With a demand-assigned protocol, usage of the bus is allocated dynamically by a bus arbiter according to the traffic demands of each DCD on the network. One example of a demand assigned MAC protocol is DQRUMA which is described in Mark J. Karol, Zhao Liu, and Kai Y. Eng, “An Efficient Demand-Assignment Multiple Access Protocol for Wireless Packet Networks”. ACM/Baltzer Wireless Networks, Vol. 1, No. 3, pp. 267-279, 1995, the contents of which are herein incorporated by reference. Under this protocol, each DCD that has data to transmit notifies the AP. Any DCDs needing to use the bus submit their requests during a predefined, regularly reoccurring, time period called the request access (RA) slot. Whenever more than one DCD submits a request during the predefined period, all those requests are lost in a collision. In effect, the access request process operates like a slotted-ALOHA system, i.e. time-aligned random-access transmissions.
Upon receiving a valid access request, the AP sends back an acknowledgement message, and places the terminal's ID in a queue with other DCDs whose access requests were received but that have not yet been able to complete their transmissions. The AP manages the queue according to any one of many possible assignment algorithms. The AP notifies a given DCD shortly before its turn to use the bus. The DCD then uses the bus for a fixed, and reasonably short, period of time. If the DCD hasn't finished transmitting all of its data at the end of its allotted bus access period, it tacks a “piggyback request” onto the end of its transmission. The piggyback request lets the AP know that the DCD that just finished transmitting needs the bus again. This is equivalent to submitting a contention-free access request, helping to complete transfers which have already started. In addition, the piggyback request scheme significantly reduces the number of DCDs contending for access in the RA slot.
A demand-assigned protocol such as DQRUMA possesses many desirable features for a wireless data network as has just been described. However, it also possesses several undesirable qualities making it difficult to implement on many wireless networks. For instance, DQRUMA assumes the existence of simultaneous parallel uplink (traffic going into the AP) and downlink (traffic coming out of the AP) channels between the AP and the DCDs. If the parallel channels each have equal capacity, the bus can only operate at maximum efficiency when traffic into and out of the AP is perfectly balanced between uplink and downlink. Whenever the traffic is not balanced, one of the channels must operate below capacity. It is difficult, if not impossible, to reallocate bandwidth between the uplink and downlink channels in response to varying loads.
The only practical way to obtain two simultaneous channels in a wireless system is through frequency division duplexing (FDD), i.e., uplink traffic resides on one carrier frequency and downlink traffic resides on another. Often, frequency spectrum allocations for a given application do not lend themselves to the implementation of FDD systems. Unless the uplink and downlink frequency bands can be separated (into non-contiguous blocks) the analog filtering (diplexer) requirements for the wireless transceiver become extremely difficult if one is to avoid wasting a large portion of the spectrum.
In DQRUMA, requests for access to the bus, and the acknowledgements of those requests, are relatively short messages. The DQRUMA protocol is designed to use short requests and acknowledgement messages and longer data packets. However, in certain systems, such as networks that employ OFDM (Orthogonal Frequency Division Multiplexing), it is difficult to vary the size of
Jones Vincent K.
Pollack Michael A.
Raleigh Gregory G.
Boakye Alexander
Cisco Systems Inc.
Nguyen Chau
Ritten, Van Pelt & Yi LLP
LandOfFree
Medium access control protocol for OFDM wireless networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Medium access control protocol for OFDM wireless networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Medium access control protocol for OFDM wireless networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2609904