Methods and apparatus for achieving and maintaining optimum transmission rates and preventing data loss in a processing system nework

• US 5,627,970 A
• Filed: 08/08/1994
• Issued: 05/06/1997
• Est. Priority Date: 08/08/1994
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Keshav, Srinivasan
• Primary Examiner(s): Pan, Daniel H.
• Application Number:
  US08/287,018
• Time in Patent Office: 1,002 Days
• Field of Search: 395/800, 395/200.06, 395/200.02, 395/200.13, 395/200.07, 395/200.17, 395/200.1, 370/17, 370/84, 370/60, 370/94.1, 340/825.5, 364/DIG. 1, 364/DIG. 2
• US Class Current: 709/233
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

Disclosed are methods and systems for achieving and maintaining data transmission rates in processing system networks, independent of communication between the node and the processing system network, and including techniques for data transmission initialization, data retransmission, and buffer management. Data transmission initialization includes transmitting data packets from a source node over a network at an adaptive exponential transmission rate from a current operating point to an optimal operating point. The optimal operating point is a data transmission rate wherein data buffers are neither overflowing nor under-flowing. Data retransmission includes transmitting data packets at the optimal set point, detecting the loss of a transmitted data packet as a function of a timer-less acknowledgement signal, and retransmitting the lost data packet. Buffer management includes redetermining the optimal operating point in response to unexpected changes in the data transmission bandwidth of the network, wherein detection of such changes is preferably accomplished using a dynamic set point probing procedure.

Claims

1. A method for controlling data packet transmission from a source node over a processing system network said method comprising the steps of:

a) transmitting a data packet at an adaptive exponential transmission rate from a current operating point to a target operating point, said target operating point being an estimate of an optimal set point;

b) receiving an acknowledgement signal representative of a sequence number of a particular received transmitted data packet;

c) recalculating, upon a determination that said optimal set point has not been reached, said target operating point and returning to step a.

2. The method as set forth in claim 1 wherein said recalculating step further includes the step of determining if said optimal set point has been reached as a function of said acknowledgement signal.

3. The method as set forth in claim 1 further including the step of sending a data packet at an optimal operating rate corresponding to said optimal set point.

4. The method as set forth in claim 3 wherein each of said transmitted data packets includes a sequence number representative of the position of each of said transmitted data packets within a sequence of data packets transmitted from said source node and wherein said transmitting step is preceded by the step of assigning a current sequence number to each said data packet.

5. The method as set forth in claim 4 wherein said acknowledgement signal includes a key and an offset and further includes the step of evaluating said key and said offset for each received acknowledgment signal to determine if a prior transmitted data packet has been lost, and upon such a determination, re-transmitting said prior transmitted data packet from said source node.

6. The method as set forth in claim 5 further including the step of monitoring said key and said offset for each received acknowledgment signal to determine if said retransmitted data packet has been received.

7. The method as set forth in claim 6 further including the step of setting a timer as each said data packet is transmitted.

8. The method as set forth in claim 7 wherein a timeout bound is computed by evaluating the transmission throughput of said processing system network and further including, upon a determination that said timeout bound has been exceeded by said timer, the step of forwarding each said transmitted data packet and each said retransmitted data packet which have not been received.

9. The method as set forth in claim 7 wherein said monitoring step further includes the step of selectively examining said acknowledgment signals associated with said retransmitted data packets to determine if said key has changed and, upon a determination that said key has not changed, selectively sending previously transmitted and retransmitted data packets from said source node.

10. The method as set forth in claim 3 further including the step of increasing said optimal operating rate while probing a bottleneck buffer size to determine if said optimal operating rate has exceeded a boundary causing data packet loss, and upon such a determination, decreasing said optimal operating rate.

11. The method as set forth in claim 10 further including the step of repeating said increasing step while said data packets are transmitted at said optimal set point.

12. The method as set forth in claim 3 further including the step of determining whether a bottleneck buffer size is less than said optimal set point, and upon such a determination, redetermining said optimal set point utilizing said adaptive exponential transmission rate.

13. A method for controlling data packet transmission from a source node over a processing system network, said method comprising the steps of:

a) transmitting a next data packet at an optimal operating rate corresponding to an optimal set point, said next data packet including a sequence number representative of the position of said next data packet within a sequence of data packets transmitted from said source node;

b) receiving an acknowledgment signal of data signals at said source node for each received transmitted data packet, said acknowledgment signal including a key and an offset, and representative of the sequence number of a particular received transmitted data packet; and

c) evaluating each said acknowledgment signal as a function of said key and said offset to determine if a prior data packet has been received, and upon a determination that said prior data packet has not been received, retransmitting said prior data packet from said source node.

14. The method as set forth in claim 13 further including the step of returning to step a).

15. The method as set forth in claim 14 further including the step of monitoring said key and said offset for each received acknowledgment signal to determine if said retransmitted data packet has been received.

16. The method as set forth in claim 15 further including the step of starting a timer upon the transmission of a first data packet, and thereafter setting said timer as each subsequent data packet is transmitted.

17. The method as set forth in claim 15 wherein said monitoring step further includes the step of selectively examining said acknowledgment signals associated with said retransmitted data packets to determine if said key has changed and, upon a determination that said key has not changed, selectively sending previously transmitted and retransmitted data packets from said source node.

18. The method as set forth in claim 16 wherein a timeout bound is computed by evaluating the transmission throughput of said processing system network and further including, upon a determination that said timeout bound has been exceeded, the step of sending each said transmitted data packet and each said retransmitted data packet which have not been received.

19. The method as set forth in claim 13 further including the step of increasing said optimal operating rate while probing a bottleneck buffer size to determine if said optimal operating rate has exceeded a boundary causing data packet loss, and upon such a determination, decreasing said optimal operating rate.

20. The method as set forth in claim 19 further including the step of repeating said increasing step while said data packets are transmitted.

21. The method as set forth in claim 13 further including the step of determining whether the bandwidth of said processing system network has increased, and upon such a determination, redetermining said optimal set point corresponding to said optimal operating rate utilizing an adaptive exponential transmission rate.

22. The method as set forth in claim 13 wherein said transmitting step is preceded by a start-up phase including the step of sending ones of a plurality of data packets at an adaptive exponential transmission rate from a current operating point to a target operating point, said target operating point being an estimate of an optimal set point.

23. The method as set forth in claim 22 further including the step of recalculating, upon a determination that said optimal set point has not been reached, said target operating point.

24. The method as set forth in claim 23 further including the step of receiving said acknowledgement signal for each transmitted data packet.

25. The method as set forth in claim 24 further including the step of determining if said optimal set point has been reached as a function of said received acknowledgement signal.

26. A processing system for transmitting data packets from a source node over a processing system network independent of communication between said source node and said processing system network, said processing system comprising:

at least one memory storage device operable to store a plurality of processing system instructions; and

at least one processing unit for controlling data packet transmission from said source node over said processing system network by retrieving and executing at least one of said processing unit instructions from said memory storage device, said processing unit operable to;

transmit a current data packet from said source node over said integrated network to a destination node at an optimal operating rate corresponding to an optimal set point, wherein said current data packet includes a sequence number representative of the position of said current data packet within a sequence of data packets previously transmitted from said source node;

receive an acknowledgment signal for each received transmitted data packet, said acknowledgment signal including a key and an offset, and representative of the sequence number of a particular received transmitted data packet; and

evaluate each said acknowledgment signal as a function of said key and said offset to determine if a prior data packet has not been received by said destination node, and upon such a determination, retransmit said prior data packet from said source node to said destination node.

27. The processing system as set forth in claim 26 wherein said processing unit is further operable to utilize dynamic set point probing in conjunction with re-calculation of said optimal operating rate.

28. The processing system as set forth in claim 27 wherein said processing unit is further operable to probe a bottleneck buffer size in conjunction with the utilization of said dynamic set point probing.

29. The processing system as set forth in claim 26 wherein said processing unit is operable to initialize said processing system.

33. The processing system as set forth in claim 26 wherein said processing unit is further operable to monitor said key and said offset for each received acknowledgment signal to determine if said retransmitted data packet has been received.

34. The processing system as set forth in claim 33 wherein said processing is further operable to set a timer as each said data packet is transmitted.

35. The processing system as set forth in claim 34 wherein a timeout bound is computed by evaluating the transmission throughput of said processing system network and said processing unit is further operable, upon a determination that said timeout bound has been exceeded, to send each said transmitted data packet and each said retransmitted data packets which have not been received.

30. The processing system as set forth in claim 30 wherein said processing unit is operable, during said initialization, to send a series of data packets over said integrated network to said destination node at an adaptive exponential transmission rate from a current operating point corresponding to a current operating rate to a target operating point corresponding to a target operating rate, said target operating point being an estimate of said optimal set point.

31. The processing system as set forth in claim 30 wherein said processing unit is further operable to determine whether said optimal set point has been reached in response to said acknowledgment signal.

32. The processing system as set forth in claim 31 wherein said processing unit is further operable to recalculate, upon a determination that said optimal set point has not been reached, said target operating point.