1. Technical Field
This invention relates to a technique for maintaining efficient data communication in event of a retransmission timeout.
2. Background Information
TCP (Transmission Control Protocol) is a communication protocol widely used for data communication between a transmitter device and a receiver device. A transmitter device divides data for transmission to a receiver device into a plurality of portions, each portion of the data having a predetermined data size and being transmitted as a data block (hereinafter, a “segment”). Each segment contains each divided portion of the data and a unique header appended thereto, included in which header is a sequence number for uniquely identifying a divided portion of the data contained in each segment. Thus numbered segments are transmitted to a receiver device sequentially in ascending order. A receiver device, upon receiving a segment, returns a communication message (hereinafter, an “acknowledgement”) for acknowledging the receipt of the segment. There is written in the acknowledgement a sequence number of a segment which a receiver device expects to receive next (hereinafter, an “acknowledgement number”). When a segment is safely received by a receiver device, an acknowledgement number should be larger than the sequence number of the segment received. Receiving such an acknowledgment at a transmitter device enables a determination to be made as to whether a transmitted segment has safely been received by a receiver device. A transmitter device transmits a subsequent segment to a receiver device only after receiving an acknowledgement for a transmitted segment.
A segment transmitted from a transmitter device, however, sometimes does not reach a receiver device before a retransmission timeout expires in a case that congestion occurs in a communication network used for data communication between the transmitter device and the receiver device. When no acknowledgement is received at a transmitter device within a predetermined time period since the time when a segment was transmitted, the transmitter device regards a segment as being lost (i.e., “segment loss”). The transmitter device then performs a retransmission of the apparently lost segment. Reliability of communication is thus ensured when communication is performed according to TCP.
However, at the expense of ensuring reliability, data transmission efficiency is caused to deteriorate. To attain a balance between the reliability and efficiency of data transmission, TCP prescribes that segments can be transmitted from a transmitter device in succession up to a certain number without an acknowledgement from a receiver device being received; and the number of segments that can be transmitted is incremented each time an acknowledgement is received for a transmitted segment. Such a segment transmission method is called “window control”, and the number of segments transmitted in succession a “congestion window size.”
When a retransmission timeout occurs where such window control is being performed, a transmission device retransmits an oldest segment (i.e., a segment having the smallest sequence number) from among transmitted segments that have not been acknowledged and reduces the congestion window size to a minimum value (for example, a value in bytes corresponding to one segment), which would otherwise cause an influx of a large number of segments to an already congested network state. After the congestion window size is once reduced, a transmitter device again increases the congestion window size according to a predetermined algorithm each time it receives an acknowledgement for a transmitted segment.
Two types of algorithms, a Slow Start algorithm and a Congestion Avoidance algorithm, are used when the congestion window size is increased by a transmitter device according to TCP. The Slow Start algorithm exponentially increases a congestion window size, and the Congestion Avoidance algorithm linearly increments the congestion window size. A transmitter device which transmits a segment based on TCP generally performs the Slow Start algorithm until the congestion window size reaches a predetermined threshold, and performs the Congestion Avoidance algorithm after the congestion window size reaches the threshold. Congestion is thus avoided in data communication based on TCP.
A transmitter device which transmits a segment according to TCP retransmits a segment, being triggered not only by a retransmission timeout occurring but also by a receipt of more than one, for example three, acknowledgments (hereinafter, duplicate ACKs) having the same acknowledgement number. The segment retransmission triggered by duplicate ACKs is performed without waiting for the expiration of the retransmission timeout, and therefore, is called a “Fast Retransmit” algorithm. When the Fast Retransmit algorithm is performed, the congestion window size is reduced to a predetermined size, for example, one-half of the current window size at the time of the Fast Retransmit, and the thus once reduced congestion window size is increased again each time an acknowledgment is received for a transmitted segment according to the Congestion Avoidance algorithm. This is called “Fast Recovery” since the congestion window size is increased using the Congestion Avoidance algorithm without performing the Slow Start algorithm beforehand. A transmitter device thus retransmits a segment, being triggered either by a retransmission timeout occurring or a receipt of duplicate ACKs, according to TCP.
However, a retransmission timeout and a receipt of duplicate ACKs occur independently from each other; for example, after a segment is retransmitted according to the Fast Retransmit algorithm, a retransmission timeout may take place due to timeout expiration when waiting for an acknowledgement from a receiver device for the segment just retransmitted according to the Fast Retransmit algorithm. In such a case, the congestion window size is reduced to a predetermined value at the time of retransmission according to the Fast Retransmit algorithm, and is then again reduced to a minimum value at the time of a subsequent retransmission timeout. As a result, data transmission efficiency is significantly deteriorated.
A technique for such a problem has been proposed in Laid-Open Publication Japanese Patent Application, JP 2001-352339 and in “Responding to Fast Timeouts in TCP” (Reiner Ludwig, IETF, Jul. 24, 2002).
JP 2001-352339 proposes a technique for restoring the congestion window size when it is determined by a transmitter device that the retransmission timeout was invalid, where the congestion window size was reduced to a minimum value at an event of a latest retransmission timeout. Specifically, a receiver device is caused to report to a transmitter device an event where identical segments are received in duplicate. In a case where the transmitter device receives such a report, the transmitter device increases the congestion window size to a predetermined value. In a conventional method, the two identical segments, an originally transmitted segment and a retransmitted segment, are transmitted to a receiver device in a case where the retransmission of a segment is performed as a result of a retransmission timeout occurring. If each of the two segments is safely received by the receiver, retransmission of a segment triggered by a timeout will have been unnecessary, and thus a reduction in the congestion window size triggered by the retransmission timeout will also have been unnecessary. The technique proposed in JP 2001-352339 enables a transmitter device to restore this once decreased congestion window size, thereby to avoid any unwanted, unnecessary decrease in congestion window size.
According to the technique proposed by Ludwig, a transmitter device is caused to perform the Fast Recovery algorithm in a case where one or two duplicated acknowledgement(s) is/are received from a receiver device before the expiration of a retransmission timeout and one or more duplicated acknowledgement is further received after the retransmission timeout expires.
Even if the algorithm proposed in JP 2001-352339 is applied, however, a second retransmission timeout might occur before a transmitter device receives a report from a receiver device notifying the transmitter device of receipt of two identical segments. In more detail, in a case where a large number of segments (hereinafter, original segments) are transmitted from a transmitter device before an acknowledgement is received, according to a current congestion window size, and one of the original segments is retransmitted as a result of a first retransmission timeout, the retransmitted segment will be received by a receiver device after the original segments are received by the receiver device. As a result, a second retransmission timeout may expire before receiving a report from the receiver device, i.e., before determining the first timeout was valid. FIG. 9 is an example of such a case where five segments having sequence numbers of 500, 1000, 1500, 2000, and 2500 are transmitted from a transmitter device and a retransmission timeout expires for the first segment having the sequence number 500, resulting in a retransmission of the first segment (500). As shown in the figure, the retransmitted segment (500) reaches the receiver device after the four segments having the sequence numbers of 1000 to 2500 are received by the receiver device. A second retransmission timeout for the retransmitted segment (500) is then likely to occur before the transmitter device receives a report from the receiver device that two identical segments (500) have been received.
Also, the technique proposed by Ludwig only serves a very limited situation where one or two acknowledgements are received before a retransmission timeout expires and one or more acknowledgement is received after the retransmission timeout occurring.
USPTO Backgrounds
USPTO Backgrounds