Multiplex communications – Communication over free space – Combining or distributing information via code word channels...
Reexamination Certificate
1999-03-08
2001-11-27
Marcelo, Melvin (Department: 2663)
Multiplex communications
Communication over free space
Combining or distributing information via code word channels...
C370S345000, C370S468000
Reexamination Certificate
active
06324172
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to networks for data communications. More specifically, this invention relates to the allocation of transmission rates among the producers in a data communications network. More specifically, this invention relates to the allocation of transmission rates on the reverse link of a wireless data communications network.
2. Description of Related Art and General Background
Channel capacity, a basic limitation of any system for data communications, may be defined as the rate at which information can be passed from one end of a transmission channel to the other, given some mode of transmission and some performance criteria (e.g. binary phase-shift keying modulation of a 1.9-GHz RF carrier using polar NRZ signaling, with a bit-error rate of 10
−5
). The rate at which information may be transferred from one point to another cannot exceed the ability of the particular method and medium of transmission to convey that information intelligibly. It follows that the rate at which a data producer outputs data into a transmission channel cannot exceed the channel capacity, commonly measured in units of information per units of time (e.g. Kbits/s).
Digital data are commonly transmitted in frames of predetermined length. In order to allow for error detection, it is also common to calculate and transmit a checksum along with each frame, so that the data may be verified by the receiver. This checksum is typically in the form of a cyclic redundancy check (CRC) value computed with a polynomial algorithm known to both the receiver and the transmitter. If the data in the received frame do not match the received checksum, the frame is rejected and must be re-transmitted or compensated for in another manner.
Two or more producers may wish to transmit information over the same channel. If, for example, the producers are also physically separated, then their transmissions may not be coordinated with each other. A data collision occurs when the several transmissions arrive at the consumer having together exceeded the available channel capacity. (Note that in a time-division multiple-access or TDMA wireless system, the channel capacity available to any producer may change over time as a function of the number of producers using the same frequency channel, in that the available capacity will be zero during any period when another producer is using the channel.) Such a collision causes all of the frames being transmitted to become irretrievably corrupted, no matter how complete their transmissions were to that point. If re-transmission is required (i.e. if the system cannot otherwise compensate for the loss of data), then the producers must re-send these frames in their entirety. Therefore, one may clearly see that data collisions directly and dramatically reduce the effective channel capacity.
When the sum of the producers' output rates may exceed the channel capacity, then the producers are competing for the same limited resource and some method of allocating the channel capacity among them becomes necessary. Such allocation methods may be static, dynamic, or some combination of the two.
Static allocation schemes are best suited for situations where the data producers' outputs remain relatively constant over time: in systems for voice transmission, for example. (We will assume here that the capacity of the channel itself remains relatively constant.) One characteristic of static allocation schemes is that they may be applied in a similar fashion to either wired or wireless networks. For example, several digitized voice signals may be time-division multiplexed over a single copper or fiber optic cable, or a number of analog voice signals may be time- and/or frequency-division multiplexed over the same radio frequency band, or several digitized voice signals may share the same radio frequency band at the same time by using code-division multiple access techniques.
Alternatively, the rates of data production may vary significantly from one moment to the next; i.e. the data traffic may be bursty. Traffic on high speed networks for data communications, for example, tends to be bursty. Static allocation techniques are not well suited for such environments. On one hand, data transmission applications are usually more tolerant of delays than voice transmission applications, so a producer will not usually require the regulated level of access to the channel which a static scheme provides. On the other hand, while backlogged and therefore outdated voice information may simply be discarded by the producer before transmission, discarding data information whose transmission has been delayed is not usually a viable option. Therefore, if a producer's store of data information should begin to accumulate faster than its buffering capacity can handle, the producer will temporarily need to use more of the channel capacity than it has been assigned. Even if other producers are currently idle, however, and plenty of channel capacity is presently available, a static scheme will not accommodate the temporary redistribution of capacity needed in this situation.
Suppose that a channel has a capacity of 200 Kbits/s; there are four producers A, B, C, and D, each having a maximum output rate of 200 Kbits/s; and 50 Kbits/s of the capacity as statically allocated to each producer. If each producer produces a steady stream of data at the allocated rate of 50 Kbits/s, then the allocation scheme may be said to be optimal. However, if instead, the traffic is bursty, with A having a packet of 50 Kbits to output at time 0.25 s, B and C each having a packet of 50 Kbits to output at time 0.5 s, and D having a packet of 50 Kbits to output at time 0.75 s. As shown in
FIG. 1
, 1 second is required for each producer to complete its transmission under the static scheme described above, even though it would take only 0.25 second if the producer were allowed to operate at its maximum output rate. It is notable that using a static allocation scheme in this bursty environment also causes much of the channel capacity to remain unused.
Now consider
FIG. 2
, in which channel capacity is allocated dynamically according to each producer's ability to use the channel during any given quarter-second. At time 0, only producer A has data to transmit. Therefore, we allocate the entire channel capacity of 200 Kbits/s to producer A, and it completes its task in 0.25 s, for a 75% savings over the static allocation scheme. At time 0.5 s, producers B and C each have data to transmit, so we allocate 50% of the channel capacity to each one, and they complete their tasks in 0.5 s, for a savings of 50%. (Note that a more optimal scheme would allow either B or C to use the entire channel, completing transmission in 0.25 s. The other producer would still complete in 0.5 s, using the entire channel between times 0.75 and 1.0 s.) At time 0.75 s, producer D has also data to transmit. We will assume that the scheme requires D to wait until producers B and C have finished, so that D begins transmission at 200 Kbits/s at time 1.0 s and finishes at 1.25 s, for a savings of 50%. Therefore, it is clear that in this bursty environment dynamic allocation can achieve an average savings in time with respect to each producer of greater than 50%.
As noted above, we have assumed that the capacity of the channel remains relatively constant. This assumption will not always hold in the real world, especially in cases where the channel is wireless. When the total capacity drops, a system that is using the full capacity of the channel under a purely static scheme will fail. A dynamic scheme, on the other hand, can usually be adapted to base its allocations on an updated report of the total capacity rather than on some fixed value.
For all of their advantages, however, dynamic allocation schemes may be much more complicated to implement than static ones. In static allocation, a fixed set of rules is developed and applied, and the only task during operation is to ensure compliance with these r
Baker Kent D.
Greenhaus Bruce W.
Marcelo Melvin
Ngoyen Chau
Qualcomm Incorporated
LandOfFree
Method of rate allocation in a data communications network 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 of rate allocation in a data communications network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of rate allocation in a data communications network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2599204