Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1998-11-30
2002-10-29
Vincent, David (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
C370S329000, C370S468000
Reexamination Certificate
active
06473399
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to reliable data communications. In one particular example, the invention relates automatic repeat request (ARQ) type mechanisms used to increase the reliability of communications. In this example context the invention may be used to improve the efficiency of such ARQ-based communications.
BACKGROUND AND SUMMARY OF THE INVENTION
Data packet communications are typically “best effort” packet delivery systems. Best effort delivery makes an earnest attempt to deliver the packets, i.e., it does not discard them capriciously. Indeed, data packet services are typically called unreliable because the delivery is not guaranteed, i.e., packets may be lost, duplicated, delayed, or delivered out of order.
Nevertheless, many data communications applications require or at least benefit from a greater degree of reliability. One way of increasing the reliability of transmission is for two communication units to exchange of an acknowledgment message so they know if and when a particular message has been transferred successfully. The use of positive and/or negative acknowledgments with retransmission to increase reliability is typically referred to as automatic repeat request (ARQ). More specifically, a transmitter sends data units to a receiver. The receiver replies by sending back to the transmitter a positive acknowledgment if a data unit is properly received. A negative acknowledgment is sent if a data unit is not properly received, i.e., a data unit received with errors (or at least too many errors to correct efficiently) and a data unit simply not received. In the negative acknowledgment situation, the receiver then sends a request to the transmitter to retransmit the data units that were not properly received.
The concern then is when should a decision be made to retransmit a data unit. One approach is to use an ARQ timer to determine when to retransmit a data unit, (e.g., a protocol data unit). In particular, the timer may be started when the data unit is transmitted. If the timer expires before receiving a positive acknowledgment, the data unit is automatically retransmitted.
The drawback with such an ARQ timer is that it is quite difficult to set the ARQ timer to the best time-out value. If the time-out value is set too small, the ARQ timer will likely time out too early, i.e., before an acknowledgment could reasonably be expected to be received. In other words, if some additional time had been waited, the acknowledgment would have been received, thereby avoiding an unnecessary retransmission request and the retransmission of the data unit. Thus, a time-out value that is too small leads to undesired retransmit requests and retransmissions. Both waste communications resources which can be a particular problem in communications systems such as radio communications systems where bandwidth is quite limited. On the other hand, if the time-out value is set to too large, large and unnecessary delays in retransmission requests are generated. Such delays ultimately slow down the effective throughput of the communications system.
The problem of selecting the right time-out value is further complicated in systems where the data rate of the physical communications channel can vary. In some systems like the third generation cellular telephone systems that offer a wide variety of services, the data rate may change very rapidly, e.g., every radio frame—which may be on the order of ten milliseconds. An optimal time-out value for one data rate may well be too long or too short for other data rates. Consequently, it is quite difficult to assign the correct value to achieve an optimum time out under varying circumstances.
It is an object of the present invention to provide reliable as well as efficient data communications.
It is an object of the present invention to provide reliable as well as efficient data communications under a variety of conditions.
It is another object of the present invention to provide a mechanism to efficiently determine when one or more data units should have been received.
It is yet another object to provide an automatic retransmit request (ARQ) procedure that optimally adapts to different communication conditions, and in particular, different channel transmission rates.
The present invention avoids the drawbacks with a simple timer approach and meets the objectives described above by permitting a communication unit to determine both efficiently and accurately when one or more data units should be received under a variety of conditions. In particular, the present invention compensates for transmission delays and for varying transmission rates. While examples of the invention are disclosed below generally in an ARQ-type environment, the invention has broader application to any communications situation where a receiver requests transmission of and awaits reception of one or more data units.
During a communication between first and second communications nodes, the first node receives a sequence of data units transmitted from the second node. The first communications node determines that one or more of the transmitted data units was either not received at all or was erroneously received (i.e., corrupted). The first node then sends a request to the second node to retransmit the one or more data units not received or erroneously received. A retransmit timer is started when the retransmission request is sent. The retransmit timer accounts for the delay time period required for the retransmit request to reach the second node, for the second node to process the request and start transmitting the requested data units, and for the first retransmitted data unit to reach the first node.
When the timer indicates that the delay time period is over, a counter is started. Based on the counter's value, a determination is made whether all of the data units requested to be retransmitted has been properly received. If the determination indicates that the requested one or more data units has been retransmitted and properly received, no further action is taken. On the other hand, if the requested one or more data units to be retransmitted is not received or is erroneously received, the above-described procedure is repeated.
Preferably, this timer is started simultaneously with the sending of the request for retransmission from the first node to the second node. The counter is also preferably initialized at or before the starting of the timer. The count value is changed after each time interval during which a number of data units is transmitted between the first and second nodes. One example of such a time interval is a communications frame. In an example embodiment, the counter is incremented after each time interval with the number of data units that should have been received during that time interval. For example, if two data units are currently transmitted per time interval, the counter is incremented by two. When the count value reaches the number of data units requested to be retransmitted, this is a good time for the first communications node to decide whether the data units requested to be retransmitted have been properly received. At that point in time, those requested data units should have been retransmitted by the second communications node and received by the first communications node.
As explained above, the present invention may be advantageously employed in any request for transmission of data units. By accounting for the round trip delay of request to transmit certain data units, the counter then starts counting expected data units at a point in time from which it is reasonable to expect that the requested units will have been transmitted and possibly received. The counter adjusts to changes in transmission rate on the communications channel by changing its count value only by the number of data units that should be received per each time interval. Thus, more time is effectively provided when the transmission rate is lower and less time is allowed at higher transmission rates. The end result is an efficient and optimum balance
Johansson Mathias
Larsson Johan
Roobol Christian
Nixon & Vanderhye PC
Telefonaktiebolaget LM Ericsson (publ)
Vincent David
LandOfFree
Method and apparatus for determining an optimum timeout... 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 determining an optimum timeout..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining an optimum timeout... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3000578