Method and device for determining a time-parameter

• US 6,901,081 B1
• Filed: 07/28/2000
• Issued: 05/31/2005
• Est. Priority Date: 08/17/1999
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Ludwig, Reiner
• Primary Examiner(s): Nguyen, Steven
• Assistant Examiner(s): TRAN, THIEN D
• Application Number:
  US09/628,660
• Time in Patent Office: 1,768 Days
• Field of Search: 370/519, 370/508, 370/503, 370/389, 370/252, 714/748, 714/749, 714/750, 714/751
• US Class Current: 370/519
• CPC Class Codes: H04L 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/188 Time-out mechanisms
• CPC Class Codes: H04L 1/20 using signal quality detector
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/37 Slow start
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method and device for determining a parameter (RTO) associated with a retransmission time-out feature in a data unit transmitter implementing a protocol (TCP) that provides an acknowledgment feature and a retransmission time-out feature, where according to one aspect decreasing values of the round trip time (RTT) are treated differently with respect to their influence on a mean deviation parameter (RTTVAR) than increasing values of the round trip time, where according to another aspect weight values (g, h, w) used in the determination of the parameter (RTO) are chosen such that at least one of them is time variable, and where according to a further aspect the parameter (RTO) is also calculated on the basis of a value (SR) indicative of the number of spurious time-outs in the communication.

Claims

1. A method of determining a parameter associated with a retransmission time-out feature in a data unit transmitter implementing a protocol that provides an acknowledgment feature of sending acknowledgment messages for the correct receipt of data units from the receiver to the sender of a communication, and provides said retransmission time-out feature of retransmitting data units if an acknowledgment does not arrive at the sender within a time-out period, comprising the steps of:

measuring a round trip time value the round trip time being indicative of the time that passes between the sending of a given data unit and the receipt of the acknowledgment corresponding to said given data unit,

calculating a new smoothed round trip time value at least on the basis of a stored smoothed round trip time value and said measured round trip time value,

calculating a new mean deviation value indicative of the mean deviation of said round trip time values over time, at least on the basis of a stored mean deviation value, said measured round trip time value and said stored smoothed round trip time value, and

calculating said parameter at least on the basis of said new smoothed round trip time value said new mean deviation value,

where a contribution of said measured round trip time value to said new mean deviation value is different if said measured round trip time value is smaller than a predetermined threshold that is determined on the basis of said stored smoothed round trip time value, than if said measured round trip time value is greater than said predetermined threshold.

2. The method of claim 1, wherein said predetermined threshold is equal to said stored smoothed round trip time value.

3. The method of claim 1, wherein said new mean deviation value is calculated as being equal to or smaller than said stored mean deviation value if said measured round trip time value is smaller than said predetermined threshold.

4. The method of claim 1, wherein said new mean deviation value is calculated as a function of said stored man deviation value said stored smoothed round trip time value, said measured round trip time value, and a weight factor if said measured round trip time value is larger than said predetermined threshold.

5. The method of claim 4, wherein said weight factor is variable over time.

6. The method of claim 5, wherein said new mean deviation value (RTTVAR(new)) is calculated as:

$\mathrm{RTTVAR}<br><br>\left(\mathrm{new}\right)=\mathrm{RTTVAR}<br><br>\left(\mathrm{old}\right)+h·<br><br>\left(\left(\mathrm{RTT}-\mathrm{SRTT}<br><br>\left(\mathrm{old}\right)\right)-\mathrm{RTTVAR}<br><br>\left(\mathrm{old}\right)\right)$

if said measured round trip time value (RTT) is greater or equal to said predetermined threshold (TH(SRTT(old))), where RTTVAR(new) represents the new mean deviation value, RTTVAR(old) represents the stored mean deviation value, SRTT(old) represents the stored round trip time value, RTT represents the measured round trip time value, and h represents said weight factor.

7. The method of claim 5, wherein said new mean deviation value (RTTVAR(new)) is calculated as $\mathrm{RTTVAR}$

(new)=RTTVAR⁡

(old)+h·

((RTT-SRTT⁡

(old))-RTTVAR⁡

(old))

if said measured round trip time value (RET) is greater or equal to said predetermined threshold (TH(SRTT(old))) and

(RTT−

SRTT(old))RTTVAR(old)≧

0,

and as $\mathrm{RTTVAR}<br><br>\left(\mathrm{new}\right)=\mathrm{RTTVAR}<br><br>\left(\mathrm{old}\right)+h^2·<br><br>\left(\left(\mathrm{RTT}-\mathrm{SRTT}<br><br>\left(\mathrm{old}\right)\right)-\mathrm{RTTVAR}<br><br>\left(\mathrm{old}\right)\right)$

if said measured round tip time value (RTT) is greater or equal to said predetermined threshold (TH(SRTT(old))) and

(RTT−

SRTT(old))−

RTTVAR(old)<

0,

where RTTVAR(new) represents the new mean deviation value, RTTVAR(old) represents the stored mean deviation value, SRTT(old) represents the stored round trip time value, RTT represents the measured round trip time value, and h represents said weight factor.

8. The method of claim 4, wherein a value of said weight factor at a given time is associated with a value indicative of the number of data units that were sent up to said given time, but that were not acknowledged up to said given time.

9. The method of claim 8, wherein said value indicative of the number of data units that were sent up to said given time, but that were not acknowledged up to said given time, is one of the

number of data units that were sent up to said given time, but that were not acknowledged up to said given time,

a smoothed average of said number of data units that were sent up to said given time, but that were not acknowledged up to said given time, and

the slow start threshold.

10. The method of claim 8, wherein said weight factor is equal to the inverse value of a sum of said value indicative of the number of data units that were sent up to said given time, but that were not acknowledged up to said given time, and one.

28. The method of claim 1, wherein an upper and a lower limit value are set for said parameter.

29. The method of claim 28, wherein said lower limit value is at least the sum of the measured round trip time value and the tick size where the tick size is the smallest period of time that a timing system in said data unit transmitter can resolve.

34. The method of claim 1, wherein the round trip time is measured for every data unit sent by said sender.

35. The method of claim 34, wherein said parameter is calculated each time that a round trip time value is measured.

40. A computer program product directly loadable into the internal memory of a digital computer, comprising software code portions for performing the method of claim 1 when said product is run on a digital computer.

11. A method of determining a parameter associated with a retransmission time out feature in a data unit transmitter implementing a protocol that provides an acknowledgment feature of sending acknowledgment messages for the correct receipt of data units from the receiver to the sender of a communication, and provides said retransmission time-out feature of retransmitting data units if an acknowledgment does not arrive at the sender within a time-out period, comprising the steps of:

measuring a round trip time value, the round trip time being indicative of the time that passes between the sending of a given data unit and the receipt of the acknowledgment corresponding to said given data unit,

calculating a new smoothed round trip time value at least on the basis of a stored smoothed round trip time value, said measured round trip time value, and a first weight factor,

calculating a new mean deviation value indicative of the mean deviation of said round trip time values over time, at least on the basis of a stored mean deviation value said measured round trip time value, said stored smoothed round trip time value and a second weight factor (h), and

calculating said parameter at least on the basis of said new smoothed round trip time value said new mean deviation value, and a third weight factor,

where at least one of said first, second and third weight factors is variable over time.

12. The method of claim 11, wherein a value at a given time of said at least one weight factor, is associated with a value indicative of the number of data units that were sent up to said given time, but that were not acknowledged up to said given time.

13. The method of claim 11, wherein said first, second and third weight factor are time dependent, and said first and second weight factor are identical, and said third weight factor is equal to the inverse value of said first weight factor.

14. The method of claim 12, wherein said first weight factor and said second weight factor is equal to an inverse value of a predetermined function of said value indicative of the number of data units that were sent up to said given time, but that were not acknowledged up to said given time, and said third weight factor is equal to said function.

15. The method of claim 14, wherein said predetermined function is the sum of said value indicative of the number of data units that were sent up to said given time, but that were not acknowledged up to said given time, and one.

16. The method of claim 12, wherein said value indicative of the number of data units that were sent up to said given time, but that were not acknowledged up to said given time, is one of the

number (N) of data units that were sent up to said given time, but that were not acknowledged up to said given time,

a smoothed average of said number of data units that were sent up to said given time, but that were not acknowledged up to said given time, and

the slow start threshold.

30. The method of claim 11, wherein an upper and a lower limit value are set for said parameter.

31. The method of claim 30, wherein said lower limit value is at least the sum of the measured round trip time value and the tick size, where the tick size is the smallest period of time that a timing system in said data unit transmitter can resolve.

36. The method of claim 11, wherein the round trip time is measured for every data unit sent by said sender.

37. The method of claim 36, wherein said parameter is calculated each time that a round trip time value is measured.

41. A computer program product directly loadable into the internal memory of a digital computer, comprising software code portions for performing the method of claim 11 when said product is run on a digital computer.

17. A method of determining a parameter associated with a retransmission time-out feature in a data unit transmitter implementing a protocol that provides an acknowledgment feature of sending acknowledgment messages for the correct receipt of data units from the receiver to the sender of a communication, and provides said retransmission time-out feature of retransmitting data units if an acknowledgment does not arrive at the sender within a time-out period, comprising the steps of;

measuring a round trip time value, the round trip time being indicative of the time that passes between the sending of a given data unit and the receipt of the acknowledgment corresponding to said given data unit,

calculating a new smoothed round trip time value at least on the basis of a stored smoothed round trip time value and said measured round trip time value,

calculating a new mean deviation value indicative of the mean deviation of said round trip time values over time, at least on the basis of a stored mean deviation value, said measured round trip time value and said stored smoothed round trip time value, and

calculating said parameter at least on the basis of said new smoothed round trip time value and said new mean deviation value

where said parameter is also calculated on the basis of a value indicative of the number of spurious time-outs that occurred in said communication between said sender and said receiver.

18. The method of claim 17, wherein said parameter is calculated as a product of a first factor that depends on said new smoothed round trip time value and said new mean deviation value and a second factor that depends on said value indicative of the number of spurious time-outs.

19. The method of claim 17, wherein said value indicative of the number of spurious time-outs is the sum of one and the product of the fraction of the number of data unit retransmissions caused by spurious time-outs divided by the total number of transmitted data units over a predetermined period of time and a multiplication factor.

20. The method of claim 19, wherein said multiplication factor is greater or equal to fifty.

21. The method of claim 17, wherein said value indicative of the number of spurious time-outs is a smoothed average determined on the basis of the number of spurious timeouts.

22. The method of claim 21, wherein said smoothed average (SR) is determined such that when an acknowledgment is received, it is determined if said acknowledgment indicates a spurious time-out, in which case a stored value of said smoothed average (SR) is updated as the minimum of an integer constant (N) and

SR+wsr·

(1−

SR),

where SR represents the stored value of said smoothed average, and war represents a weight factor, and

if said time-out is not a spurious time-out, said smoothed average is updated as the product of said stored value of said smoothed average and a predetermined factor.

23. The method of claim 22, wherein said weight factor is equal to 0.5.

24. The method of claim 22, wherein said predetermined factor is associated with a value indicative of the number of data units sent per cycle.

25. The method of claim 24, wherein said value indicative of the number of data units per cycle is determined on the basis of the slow start threshold.

26. The method of claim 25, wherein said value (M) is determined as

M=1.5·

ssthresh²

where M represents said value and ssthresh represents the slow start threshold.

27. The method of claim 24, wherein said predetermined factor is equal to

(1−

(K/M)),

where M represents said value (M) indicative of the number of data units sent per cycle, and K is a value with 0≦

K<

1.

32. The method of claim 17, wherein an upper and a lower limit value are set for said parameter.

33. The method of claim 32, wherein said lower limit value is at least the sum of the measured round trip time value and the tick size, where the tick size is the smallest period of time that a timing system in said data unit transmitter can resolve.

38. The method of claim 17, wherein the round trip time is measured for every data unit sent by said sender.

39. The method of claim 38, wherein said parameter is calculated each time that a round trip time value is measured.

42. A computer program product directly loadable into the internal memory of a digital computer, comprising software code portions for performing the method of claim 17 when said product is run on a digital computer.

43. A data unit transmitter arranged for implementing a protocol that provides an acknowledgment feature of sending acknowledgment messages for the correct receipt of data units from the receiver to the sender of a communication, and provides a retransmission time-out feature of retransmitting data units if an acknowledgment does not arrive at the sender within a time-out period, and arranged for determining a parameter associated with said retransmission time-out feature, comprising:

a round trip time measurer arranged for measuring a round trip time value, the round trip time being indicative of the time that passes between the sending of a given data unit and the receipt of the acknowledgment corresponding to said given data unit, and

a calculator arranged for

calculating a new smoothed round trip time value at least on the basis of a stored smoothed round trip time value and said measured round trip time value,

calculating a new mean deviation value indicative of the mean deviation of said round trip time values over time, at least on the basis of a stored mean deviation value said measured round trip time value and said stored smoothed round tip time value, and

calculating said parameter at least on the basis of said new smoothed round trip time value and said new mean deviation value,

where said calculator is furthermore arranged such that a contribution of said measured round trip time value to said new mean deviation value is different if said measured round trip time value a predetermined threshold that is determined on the basis of said stored smoothed round trip time value, than if said measured round trip time value is larger than said predetermined threshold.

44. A data unit transmitter arranged for implementing a protocol that provides an acknowledgment feature of sending acknowledgment messages for the correct receipt of data units from the receiver to the sender of a communication, and provides a retransmission time-out feature of retransmitting data units if an acknowledgment does not arrive at the sender within a time-out period, and arranged for determining a parameter associated with said retransmission time-out feature, comprising:

a round trip time measurer arranged for measuring a round trip time value, the round trip time being indicative of the time that passes between the sending of a given data unit and the receipt of the acknowledgment corresponding to said given data unit, and

a calculator arranged for

calculating a new smoothed round trip time value least on the basis of a stored smoothed round trip time value, said measured round trip time value, and a first weight factor,

calculating a new mean deviation value indicative of the mean deviation of said round trip time values over time, at least on the basis of a stored mean deviation value, said measured round trip time value, said stored smoothed round trip time value, and a second weight factor (h), and

calculating said parameter at least on the basis of said new smoothed round trip time value, said new mean deviation value, and a third weight factor,

where said calculator is furthermore arranged such that at least one of said first, second and third weight factors is variable over time.

45. A data unit transmitter arranged for implementing a protocol that provides an acknowledgment feature of sending acknowledgment messages for the correct receipt of data units from the receiver to the sender of a communication, and provides a retransmission time-out feature of retransmitting data units if an acknowledgment does not arrive at the sender within a time-out period, and arranged for determining a parameter associated with said retransmission time-out feature, comprising:

a round trip time measurer arranged for measuring a round trip time value, the round trip time being indicative of the time that passes between the sending of a given data unit and the receipt of the acknowledgment corresponding to said given data unit, and

a calculator arranged for

calculating a new smoothed round trip time value at least on the basis of a stored smoothed round trip time value and said measured round trip time value,

calculating a new mean deviation value indicative of the mean deviation of said round trip time values over time, at least on the basis of a stored mean deviation value, said measured round trip time value and said stored smoothed round trip time value, and

calculating said parameter at least on the basis of said new smoothed round trip time value said new mean deviation value,

where said calculator is furthermore arranged such that said parameter is also calculated on the basis of a value indicative of the number of spurious time-outs that occurred in said communication between said sender and said receiver.