Transmission Control Protocol/Internet Protocol (TCP/IP) is the basic communication language or protocol of the Internet. It can also be used as a communications protocol in a private network (either an intranet or an extranet). When one is set up with direct access to the Internet, his or her computer is provided with a copy of the TCP/IP program just as many of the other computers that he or she may send messages to or get information from also has a copy of TCP/IP.
TCP/IP is a two-layer protocol. The higher layer, TCP, manages the assembling of a message or file into smaller packets that are transmitted over the Internet and received by a TCP layer that reassembles the packets into the original message. The lower layer, IP, handles the address part of each packet so that it is routed to the correct destination. Each gateway computer on the network checks this address to determine where to forward the message. Even though some packets from the same message are routed differently than others, they are reassembled at the destination.
In TCP/IP, there is a limit on the number of bytes that can be transmitted before confirmation, usually in the form of an Acknowledgment (ACK), is received. This limit is typically referred to as a current send window (snd_wnd) and is constantly updated during the lifetime of a TCP session. The current snd_wnd is calculated as the minimum of the sender congestion window (cwnd) and the receiver advertised window (rcvwnd). The sender cwnd is an attempt by the sender to estimate from past experience the amount of data it can send without causing network congestion. At the beginning of a TCP session, the sender cwnd starts low and gradually increases as the sender learns how much bandwidth is available. The rcvwnd depends on the memory and processing capabilities of the receiver and is typically 64 Kbytes (the maximum allowed by TCP). However, the rcvwnd could be significantly smaller. The rcvwnd value is typically fixed during the connection and it places an upper limit on the maximum send window (max_snd_wnd) when there is no congestion or packet loss that would limit the sender cwnd. The current snd_wnd value increases until it reaches the max_snd_wnd value, which is typically equal to the rcvwnd. For example, the rcvwnd in a personal computer (PC) running Windows is 64 Kbytes. However, in some TCP/IP implementations such as Sun Solaris 2.6/2.7, the rcvwnd could be 8 Kbytes. In the case of 64 Kbytes, TCP/IP cannot send a single Kbyte past the 64th Kbyte if none of the previous 64 Kbytes sent have been acknowledged by the TCP/IP instance with which it is communicating. (Some examples of TCP/IP instances are web page server, email server, and PC.) In other words, once the 64 Kbyte limit is reached, the TCP/IP becomes a stop-and-wait protocol with significantly decreased throughput.
Referring to FIG. 1, a Server or other Host 102 transmits 64 Kbyte frames consisting of, for example, 1.5 Kbyte packets to a Mobile Station (MS) 104. As shown, delay is introduced during the transport of the packets from the Server 102 to the MS 104. In the system, the transmission speed (link speed) is low and the delay is high. The MS 104 receives the first 1.5 Kbyte packet in the first frame and sends a TCP/IP ACK back to the Server 102 while other packets in the same frame are still being transmitted. Because the Server 102 receives the ACK before the entire 64 Kbytes are sent, TCP/IP in the Server 102 does not have to stop transmitting packets and throughput is not decreased. (See bolded lines in FIG. 1.)
FIG. 2 illustrates the transmission of 1.5 Kbyte packets in 64 Kbyte frames in a system where the transmission speed is high and the transport delay is low. In such a case, as in FIG. 1, the MS 104 receives the first 1.5 Kbyte packet and sends a TCP/IP ACK back to the Server 102 while other packets in the same 64 Kbyte frame are still being transmitted. Again, because the Server 102 receives the ACK before the entire 64 Kbytes are sent, TCP/IP in the Server 102 does not have to stop transmitting packets and throughput is not decreased. (See bolded lines in FIG. 2.)
FIG. 3 illustrates the transmission of 1.5 Kbyte packets in 64 Kbyte frames in a system where the transmission speed is high and the transport delay is high. In this case, the Server 102 sends the entire first 64 Kbyte frame to the MS 104 without receiving a TCP/IP ACK for any of the 1.5 Kbyte packets in the first frame. In this situation, the TCP/IP in the Server 102 cannot begin sending any of the packets in the second set of 64 Kbytes in the download. Instead, the TCP/IP becomes a stop-and-wait protocol with significantly decreased throughput.
Next generation CDMA systems, such as CDMA 2000, achieve link speeds higher than current CDMA systems and the maximum delay that can be tolerated is decreased. At 300 Kbps, with a 64 Kbyte max TCP window, the maximum delay that can be tolerated is 2.7 seconds. If current RLP methods are used in next generation CDMA systems, delay is likely to exceed 2.7 seconds in many calls because at higher data rates, the TCP window is exhausted in a shorter time. In CDMA 2000, data calls use RLP to correct errors on the radio link. RLP attempts to correct radio errors in accordance with the method specified in Section 10 of TIA/EIA/IS-707-A-2 (IS-707-A-2). A copy of IS-707-A-2 may be obtained via a world wide web site located at www.tiaonline.org, or by writing to Telecommunications Industry Association, 1300 Pennsylvania Ave., Suite 350, Washington, D.C. 20004 USA. In accordance with IS-707-A-2, RLP attempts to correct radio errors as follows: Consider a new frame before it is transmitted across the radio link for the first time. If the frame is “erased” by the radio link, for Y rounds, the RLP receiver instance (RLP in the receiving device) sends S(Y) number of NAKs to the sender requesting S(Y) copies of the frame. That is, in the first round, the RLP sends S(1) NAKs to the source requesting transmission of S(1) copies of the frame. If none of the copies (retransmissions) arrive, in the second round, RLP sends S(2) NAKs to the source requesting S(2) more copies of the frame. The number of NAKs S(1) and S(2) are negotiated by the RLP at the beginning of the RLP session. This process continues for Y rounds. If all rounds are unsuccessful, RLP aborts (gives up) and the frame that the packet was a part of is corrupted and must be retransmitted by TCP/IP. If two or more TCP/IP packets in a row contain at least one RLP segment or frame, each of which was unsuccessfully retransmitted and led to an abort, TCP/IP is very likely to time out. When TCP/IP times out it typically takes approximately two to three seconds for the corrupted packets to be resent. This is a significant delay, and thus the number of aborts should be minimized.
As the Frame Error Rate (FER) increases, the probability of an RLP abort increases. The amount of overhead caused by RLP retransmissions is represented roughly by the equation F*S(1), where F is the FER seen by the frames and, as set forth above, S(Y) represents the number of NAKs sent for round number Y. In other words, F*S(1) is a good approximation for the average number of retransmissions that must be sent for each new RLP frame that is sent. Thus, the throughput of RLP is roughly 1/(1+F*S(1)), because for every one new frame sent (the numerator), the total number of frames that must be sent is 1+F*S(1) (the denominator). For example, if S(Y) increases from 1 to 3 and F=10%, the RLP throughput decreases from 91% to 77% (1/(1+(0.10*1)=0.91 to 1/(1+(0.30*1)=0.77). However, if S(1)=3 rather than S(1)=1, the average RLP ordered delay decreases significantly because an RLP frame whose original transmissions is erased, is much more likely to be successfully retransmitted in its first round of retransmissions. (If one sends three retransmissions, it is much more likely that at least one will succeed than if only one is sent.) It follows that a frame delivered in the first round of retransmissions experiences less delay than a frame delivered in the second round of retransmissions.
A paper written by John Harris & Manish Airy describes a method that shows that the average ordered delay decrease in the case described above is roughly 33% (from roughly 220 ms to roughly 145 ms). The paper is entitled Analytical Model for Radio Link Protocol for IS-95 CDMA Systems and is published in IEEE Vehicular Technology Conference Proceedings in Spring 2000 (VTC 2000-Spring Tokyo. 2000 IEEE 51st, Volume: 3, 2000 Page's 2434-2438 vol.3). It can be seen from this case that by negotiating more NAKs per round in RLP, one can reduce the RLP delay and decrease the occurrence of TCP/IP becoming a stop-and-wait protocol. However, as described earlier, increasing the number of NAKs per round can cause a decrease in RLP throughput. As shown in FIG. 1, when transmission speed is low, there is no TCP/IP stop-and-wait problem and thus no need to unnecessarily decrease RLP throughput.
Aborts also contribute to decreased RLP throughput in an RLP sender instance (RLP in a sender device). When a data frame is transmitted from a sender device to a receiver device, a copy of the frame is stored in the sender's retransmission buffer. If the frame is not received at the receiver device, the RLP receiver instance sends a NAK X (where X identifies the erased frame's sequence number) to the sender. The RLP sender receives the NAK X requesting retransmission of frame X and attempts to retrieve the copy of frame X from the retransmission buffer. The retransmission buffer has a finite fixed size. For example, consider a case where the retransmission buffer holds exactly D number of RLP frames, where D=256. When the 257th RLP frame is sent, the sender's RLP retransmission buffer is full, and the first (oldest) RLP frame is deleted from the retransmission buffer to make room for the 257th RLP frame. If the RLP sender instance receives a NAK for retransmission of an RLP frame that has been deleted from the RLP retransmission buffer, the RLP sender instance is not capable of satisfying the NAK by retransmitting the RLP frame. When this happens, an RLP miss occurs. For example, an RLP miss generally occurs when a NAK for retransmission of a frame X is received after frame Y, and (Y−X) is greater than D. An RLP frame that experiences a miss, is aborted by RLP (i.e., RLP gives up on the frame and leaves the error to be potentially retransmitted by an application or higher level transport protocol). This causes extra delay and poorer quality of service for the end user. Reducing the RLP delay, as described earlier, reduces the probability of an RLP miss. This is because, an RLP miss tends to occur when a frame must be retransmitted a long time after its original transmissions, e.g. after many rounds of retransmission attempts. If retransmissions succeed in the earlier rounds, the problem of an RLP miss is reduced. One can decrease the RLP delay as described earlier, but this adds cost due the decrease in throughput. Thus, if the RLP miss problem is occurring, the delay should occur.
An RLP miss can be detected at both the sender and receiver. At the RLP sender, an RLP miss can be detected when the RLP receiver receives a NAK that it cannot satisfy because it has deleted it as described earlier. At the RLP receiver, it is more difficult to detect that an RLP miss has occurred. However, for example, if the RLP negotiates a 1,1,1,1,1 scheme, one can track the percent of RLP NAKs that are successful (result in a retransmission) in each round. For example, if 95% of the NAKs in the first 4 rounds are successful, but 0% of the NAKs in the 5th round are successful, the NAK miss problem is occurring in the 5th round. Additionally, if a sufficiently small percentage of the NAKs are last round NAKs, the NAK miss problem is not significant. Further, the RLP receiver can probe for the existence of the NAK miss problem by preemptively sending NAKs for frames that it does not need retransmissions for in order to probe the sender's retransmission buffer depth.
Thus, there is a need for an apparatus and method for dynamically adjusting the number of NAKs sent by an RLP receiver instance when an RLP error is detected in cases where the link speed into the RLP receiver is high, when the TCP window of the sender approaches the maximum, or when the percentage of NAKs for which retransmissions cannot be fulfilled approaches a threshold. There is also a need for an apparatus and method for dynamically adjusting the number of retransmissions sent by an RLP sender instance when a NAK is received in cases where the link speed out of the RLP sender is high, when the TCP window of the sender approaches the maximum or when the percentage of NAKs for which retransmissions cannot be fulfilled approaches a threshold.
USPTO Backgrounds
USPTO Backgrounds