Flow control method and apparatus

• US 7,313,627 B1
• Filed: 09/29/2000
• Issued: 12/25/2007
• Est. Priority Date: 09/30/1999
• Status: Expired due to Term

• Current Assignee: Data Expedition, Inc.
• Original Assignee: Data Expedition, Inc.
• Inventors: Noble, Seth Bradley
• Primary Examiner(s): Coulter; Kenneth R.
• Application Number:
  US09/676,016
• Time in Patent Office: 2,643 Days
• Field of Search: 709230-235
• US Class Current: 709/233
• 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/29 using a combination of thresholds
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A method that schedules a data flow adjustment, the data flow between a pair of nodes communicatively coupled by a network, the scheduling responsive to networking performance statistics.

Claims

1. A method, comprising:

recurring adjustment of an ongoing data flow between a pair of nodes communicatively coupled by a network, said recurring adjustment performed by way of alterations made to characteristics of said flow, such alterations being scheduled and determined in response to ongoing observations of networking performance statistics related to said flow'"'"'s previous behavior;

said recurring adjustment including;

scheduling flow control adjustments specified by a flow timeout pointer positioned with respect to a flow timeout threshold value;

said positioning of said flow timeout pointer including setting a delay between when a last adjustment is made and when a next adjustment is made;

said setting a delay including;

calculating a first flow timeout threshold level;

calculating a second flow timeout threshold level; and

setting either the first flow timeout threshold level or the second flow timeout threshold level as the flow timeout threshold value based on a status of the ongoing data flow;

wherein;

setting said second flow timeout threshold level as the flow timeout threshold value makes the delay longer than setting said first flow timeout threshold level as the flow timeout threshold value.

2. The method of claim 1 wherein said networking performance statistics further comprise a window transit time over said network.

3. The method of claim 1 wherein said networking performance statistics further comprise an average delay over said network.

4. The method of claim 1 wherein said networking performance statistics further comprise an arrival rate of expected messages.

5. The method of claim 1 wherein said networking performance statistics further comprise a state of a queue that receives messages from said network, said queue within a first node of said pair of nodes.

6. The method of claim 1 further comprising inquiring whether or not a flow increase is desirable in light of said networking performance statistics.

7. The method of claim 6 further comprising comparing said networking performance statistics against a minimum performance level and not scheduling a said data flow adjustment if said minimum performance level is not achieved.

8. The method of claim 1 wherein said recurring adjustment further comprises increasing said data flow according to a first flow increase schedule until data associated with said data flow is lost on said network.

9. The method of claim 8 wherein said recurring adjustment further comprises increasing said data flow according to a second flow increase schedule after said data is lost, said second said flow increase schedule having a rate of flow increases less than said first flow increase schedule.

10. The method of claim 1 further comprising adjusting said flow timeout threshold value in response to said networking performance statistics.

11. The method of claim 10 further comprising adjusting said flow timeout threshold value to a position corresponding to a reduced rate of flow increase if data associated with said data flow is lost on said network.

12. The method of claim 1 wherein said flow timeout threshold value corresponds to a factor of a window size used to control said data flow.

13. The method of claim 1 wherein said recurring adjustment further comprises adjusting a window size.

14. The method of claim 13 wherein said window size is adjusted by a datagram size.

15. A method, comprising:

a) updating statistics that characterize an existing transaction over a network between a client and a server so that said statistics reflect an arrival event, said transaction comprising a series of messages sent to said client from said server that each contain their own portion of data that is desired by said client,

wherein, said arrival event is the arrival of one of said messages at said client, said statistics being maintained by said client; and

b) inquiring at said client whether increasing the informational flow of said transaction is appropriate in light of said arrival event

wherein if said informational flow increase is deemed appropriate, said client scheduling said informational flow increase so as to be implemented not until after at least some of said data, that has yet to arrive at said client, arrives at said client;

wherein said scheduling further includes identifying a specific amount of data that is to be received at said client after said client'"'"'s most recent, previous informational flow increase but before said information flow increase is to be implemented;

wherein said identifying further includes setting a flow threshold pointer that points to a value indicative of said specific amount, said method further including advancing, as a result of a subsequent arrival event, a flow timeout pointer toward said flow threshold pointer, said advancing being an amount that is commensurate with the portion size of said data being carried by a message that was received by said client so as to trigger said subsequent arrival event.

16. The method of claim 15 wherein said statistics further comprise the state of a queue within said client that queues messages that have been received from said network.

17. The method of claim 16 further comprising said client refusing to allow said increase in said informational flow because said queue state has reached a size that indicates a minimum performance level has been reached.

18. The method of claim 15 wherein said statistics further comprise a window transit time, said window having a size that corresponds to an amount of said data allowed to be in transit on said network by said client, said window transit time being an estimate of the amount of time needed for said amount of data to be retrieved from said server.

19. The method of claim 18 further comprising said client refusing to allow said increase in said informational flow because said window transit time has reached a value that indicates a minimum performance level has been reached.

20. The method of claim 15 wherein said statistics further comprise an average delay time, said average delay time being the average amount of time said client spends waiting for a plurality of said messages to arrive.

21. The method of claim 20 further comprising said client refusing to allow said increase in said informational flow because said average delay time has reached a value that indicates a minimum performance level has been reached.

22. The method of claim 15 wherein said statistics further comprise an average rate at which said messages arrived to said client.

23. The method of claim 22 further comprising said client refusing to allow said increase in said informational flow because said average rate has increased since a previous increase in informational flow was implemented.

24. The method of claim 15 further comprising implementing said information flow increase after said flow timeout pointer has reached said flow threshold pointer.

25. The method of claim 24 further comprising resetting said flow timeout pointer to the same value each time said flow timeout pointer reaches said flow threshold pointer.

26. The method of claim 24 wherein said identifying a specific amount further comprises inquiring whether said transaction has experienced any loss events and, if so, identifying said specific amount as a first value;

otherwise, if said transaction has not experienced any loss events, identifying said specific amount as a second value, said first value greater than said second value.

27. The method of claim 26 wherein said first value is calculated as a multiple of a window size, said window size being an amount of said data allowed to be in transit on said network by said client.

28. The method of claim 15 further comprising, if said informational flow increase is deemed appropriate, said client increasing a window size, said window size being an amount of said data allowed to be in transit on said network by said client.

29. The method of claim 28 wherein said window size is increased by a datagram size, said datagram size being a measurement of the size of said portions of data being carried by said messages.

30. The method of claim 15 further comprising, if said informational flow increase is deemed appropriate, said client increasing a datagram size, said datagram size being a measurement of the size of said portions of data being carried by said messages.

31. The method of claim 30 further comprising increasing said datagram size only if a window size has already reached a limit, said window size being an amount of said data allowed to be in transit on said network by said client.

32. The method of claim 15 further comprising inquiring at said client whether decreasing the informational flow of said transaction is appropriate if a second message that is associated with said transaction has not been received by said client within a time period established for said message.

33. The method of claim 15 further comprising said client reducing the informational flow between said client and said server if a second message that is associated with said transaction has not been received by said client within a time period established for said message.

34. A method, comprising:

a) updating statistics that characterize an existing transaction over a network between a client and a server so that said statistics reflect an arrival event, said transaction comprising a series of messages sent to said client from said server that each contain their own portion of data that is desired by said client, wherein, said arrival event is the arrival of one of said messages at said client, said statistics being maintained by said client; and

b) said client increasing the informational flow of said transaction in light of said arrival event by scheduling said informational flow increase so as to be implemented not until after at least some of said data, that has yet to arrive at said client, arrives at said client, and wherein, said scheduling further includes identifying a specific amount of data that is to be received at said client after said client'"'"'s most recent, previous informational flow increase but before said information flow increase is to be implemented, and wherein, said identifying further includes setting a flow threshold pointer that points to a value that is indicative of said specific amount, said method further including advancing, as a result of a subsequent arrival event, a flow timeout pointer toward said flow threshold pointer, said advancing being an amount that is commensurate with the portion size of said data being carried by a message that was received by said client so as to trigger said subsequent arrival event.

35. The method of claim 34 wherein said statistics further comprise the state of a queue within said client that queues messages that have been received from said network.

36. The method of claim 35 further comprising said client refusing to allow said increase in said informational flow because said queue state has reached a size that indicates a minimum performance level has been reached.

37. The method of claim 34 wherein said statistics further comprise a window transit time, said window having a size that corresponds to an amount of said data allowed to be in transit on said network by said client, said window transit time being an estimate of the amount of time needed for said amount of data to be retrieved from said server.

38. The method of claim 37 further comprising said client refusing to allow said increase in said informational flow because said window transit time has reached a value that indicates a minimum performance level has been reached.

39. The method of claim 34 wherein said statistics further comprise an average delay time, said average delay time being the average amount of time said client spends waiting for a plurality of said messages to arrive.

40. The method of claim 39 further comprising said client refusing to allow said increase in said informational flow because said average delay time has reached a value that indicates a minimum performance level has been reached.

41. The method of claim 34 wherein said statistics further comprise an average rate at which said messages arrived to said client.

42. The method of claim 41 further comprising said client refusing to allow said increase in said informational flow because said average rate has increased since a previous increase in informational flow was implemented.

43. The method of claim 34 further comprising implementing said information flow increase after said flow timeout pointer has reached said flow threshold pointer.

44. The method of claim 43 further comprising resetting said flow timeout pointer to the same value each time said flow timeout pointer reaches said flow threshold pointer.

45. The method of claim 34 wherein said identifying a specific amount further comprises inquiring whether said transaction has experienced any loss events and, if so, identifying said specific amount as a first value;

otherwise, if said transaction has not experienced any loss events, identifying said specific amount as a second value, said first value greater than said second value.

46. The method of claim 45 wherein said first value is calculated as a multiple of a window size, said window size being an amount of said data allowed to be in transit on said network by said client.

47. The method of claim 34 further comprising said client increasing a window size in order to implement said informational flow increase, said window size being an amount of said data allowed to be in transit on said network by said client.

48. The method of claim 47 wherein said window size is increased by a datagram size, said datagram size being a measurement of the size of said portions of data being carried by said messages.

49. The method of claim 34 further comprising said client increasing a datagram size in order to implement said informational flow increase, said datagram size being a measurement of the size of said portions of data being carried by said messages.

50. The method of claim 49 further comprising increasing said datagram size only if a window size has already reached a limit, said window size being an amount of said data allowed to be in transit on said network by said client.

51. The method of claim 34 further comprising inquiring at said client whether decreasing the informational flow of said transaction is appropriate if a second message that is associated with said transaction has not been received by said client within a time period established for said message.

52. The method of claim 34 further comprising said client reducing the informational flow between said client and said server if a second message that is associated with said transaction has not been received by said client within a time period established for said message.

53. A machine readable storage medium having instructions that when executed by a processing system cause said processing system to perform a method, said method comprising:

a) updating statistics that characterize an existing transaction over a network between a client and a server so that said statistics reflect an arrival event, said transaction comprising a series of messages sent to said client from said server that each contain their own portion of data that is desired by said client, wherein, said arrival event is the arrival of one of said messages at said client, said statistics being maintained by said client; and

b) inquiring at said client whether increasing the informational flow of said transaction is appropriate in light of said arrival event

wherein if said informational flow increase is deemed appropriate, said client scheduling said informational flow increase so as to be implemented not until after at least some of said data, that has vet to arrive at said client, arrives at said client;

wherein said scheduling further includes identifying a specific amount of data that is to be received at said client after said client'"'"'s most recent, previous informational flow increase but before said information flow increase is to be implemented;

wherein said identifying further includes setting a flow threshold pointer that points to a value indicative of said specific amount, said method further including advancing, as a result of a subsequent arrival event, a flow timeout pointer toward said flow threshold pointer, said advancing being an amount that is commensurate with the portion size of said data being carried by a message that was received by said client so as to trigger said subsequent arrival event.

54. The machine readable storage-medium of claim 53 wherein said statistics further comprise the state of a queue within said client that queues messages that have been received from said network.

55. The machine readable storage medium of claim 54 wherein said method further comprises said client refusing to allow said increase in said informational flow because said queue state has reached a size that indicates a minimum performance level has been reached.

56. The machine readable storage medium of claim 53 wherein said statistics further comprise a window transit time, said window having a size that corresponds to an amount of said data allowed to be in transit on said network by said client, said window transit time being an estimate of the amount of time needed for said amount of data to be retrieved from said server.

57. The machine readable storage medium of claim 56 wherein said method further comprises said client refusing to allow said increase in said informational flow because said window transit time has reached a value that indicates a minimum performance level has been reached.

58. The machine readable storage medium of claim 53 wherein said statistics further comprise an average delay time, said average delay time being the average amount of time said client spends waiting for a plurality of said messages to arrive.

59. The machine readable storage medium of claim 58 wherein said method further comprises said client refusing to allow said increase in said informational flow because said average delay time has reached a value that indicates a minimum performance level has been reached.

60. The machine readable storage medium of claim 53 wherein said statistics further comprise an average rate at which said messages arrived to said client.

61. The machine readable storage medium of claim 60 wherein said method further comprises said client refusing to allow said increase in said informational flow because said average rate has increased since a previous increase in informational flow was implemented.

62. The machine readable storage medium of claim 53 wherein said method further comprises implementing said information flow increase after said flow timeout pointer has reached said flow threshold pointer.

63. The machine readable storage medium of claim 62 wherein said method further comprises resetting said flow timeout pointer to the same value each time said flow timeout pointer reaches said flow threshold pointer.

64. The machine readable storage medium of claim 53 wherein said identifying a specific amount further comprises inquiring whether said transaction has experienced any loss events and, if so, identifying said specific amount as a first value;

otherwise, if said transaction has not experienced any loss events, identifying said specific amount as a second value, said first value greater than said second value.

65. The machine readable storage medium of claim 64 wherein said first value is calculated as a multiple of a window size, said window size being an amount of said data allowed to be in transit on said network by said client.

66. The machine readable storage medium of claim 53 wherein said method further comprises, if said informational flow increase is deemed appropriate, said client increasing a window size, said window size being an amount of said data allowed to be in transit on said network by said client.

67. The machine readable storage medium of claim 66 wherein said window size is increased by a datagram size, said datagram size being a measurement of the size of said portions of data being carried by said messages.

68. The machine readable storage medium of claim 66 wherein said method further comprises, if said informational flow increase is deemed appropriate, said client increasing a datagram size, said datagram size being a measurement of the size of said portions of data being carried by said messages.

69. The machine readable storage medium of claim 68 wherein said method further comprises increasing said datagram size only if a window size has already reached a limit, said window size being an amount of said data allowed to be in transit on said network by said client.

70. The machine readable storage medium of claim 53 wherein said method further comprises inquiring at said client whether decreasing the informational flow of said transaction is appropriate if a second message that is associated with said transaction has not been received by said client within a time period established for said message.

71. The machine readable storage medium of claim 53 wherein said method further comprises said client reducing the informational flow between said client and said server if a second message that is associated with said transaction has not been received by said client within a time period established for said message.

72. A machine readable storage medium having instructions that when executed by a processing system cause said processing to perform a method, said method comprising:

a) updating statistics that characterize an existing transaction over a network between a client and a server so that said statistics reflect an arrival event, said transaction comprising a series of messages sent to said client from said server that each contain their own portion of data that is desired by said client, wherein, said arrival event is the arrival of one of said messages at said client, said statistics being maintained by said client; and

b) said client increasing the informational flow of said transaction in light of said arrival event by scheduling said informational flow increase so as to be implemented not until after at least some of said data, that has yet to arrive at said client, arrives at said client, and wherein, said scheduling further includes identifying a specific amount of data that is to be received at said client after said client'"'"'s most recent, previous informational flow increase but before said information flow increase is to be implemented, and wherein, said identifying further includes setting a flow threshold pointer that points to a value that is indicative of said specific amount, said method further including advancing, as a result of a subsequent arrival event, a flow timeout pointer toward said flow threshold pointer, said advancing being an amount that is commensurate with the portion size of said data being carried by a message that was received by said client so as to trigger said subsequent arrival event.

73. The machine readable storage medium of claim 72 wherein said statistics further comprise the state of a queue within said client that queues messages that have been received from said network.

74. The machine readable storage medium of claim 73 wherein said method further comprises said client refusing to allow said increase in said informational flow because said queue state has reached a size that indicates a minimum performance level has been reached.

75. The machine readable storage medium of claim 72 wherein said statistics further comprise a window transit time, said window having a size that corresponds to an amount of said data allowed to be in transit on said network by said client, said window transit time being an estimate of the amount of time needed for said amount of data to be retrieved from said server.

76. The machine readable storage medium of claim 75 wherein said method further comprises said client refusing to allow said increase in said informational flow because said window transit time has reached a value that indicates a minimum performance level has been reached.

77. The machine readable storage medium of claim 72 wherein said statistics further comprise an average delay time, said average delay time being the average amount of time said client spends waiting for a plurality of said messages to arrive.

78. The machine readable storage medium of claim 77 wherein said method further comprises said client refusing to allow said increase in said informational flow because said average delay time has reached a value that indicates a minimum performance level has been reached.

79. The machine readable storage medium of claim 72 wherein said statistics further comprise an average rate at which said messages arrived to said client.

80. The machine readable storage medium of claim 79 wherein said method further comprises said client refusing to allow said increase in said informational flow because said average rate has increased since a previous increase in informational flow was implemented.

81. The machine readable storage medium of claim 72 wherein said method further comprises implementing said information flow increase after said flow timeout pointer has reached said flow threshold pointer.

82. The machine readable storage medium of claim 81 wherein said method further comprises resetting said flow timeout pointer to the same value each time said flow timeout pointer reaches said flow threshold pointer.

83. The machine readable storage medium of claim 72 wherein said identifying a specific amount further comprises inquiring whether said transaction has experienced any loss events and, if so, identifying said specific amount as a first value;

otherwise, if said transaction has not experienced any loss events, identifying said specific amount as a second value, said first value greater than said second value.

84. The machine readable storage medium of claim 83 wherein said first value is calculated as a multiple of a window size, said window size being an amount of said data allowed to be in transit on said network by said client.

85. The machine readable storage medium of claim 72 wherein said method further comprises said client increasing a window size in order to implement said informational flow increase, said window size being an amount of said data allowed to be in transit on said network by said client.

86. The machine readable storage medium of claim 85 wherein said window size is increased by a datagram size, said datagram size being a measurement of the size of said portions of data being carried by said messages.

87. The machine readable storage medium of claim 72 wherein said method further comprises said client increasing a datagram size in order to implement said informational flow increase, said datagram size being a measurement of the size of said portions of data being carried by said messages.

88. The machine readable storage medium of claim 87 wherein said method further comprises increasing said datagram size only if a window size has already reached a limit, said window size being an amount of said data allowed to be in transit on said network by said client.

89. The machine readable storage medium of claim 72 wherein said method further comprises inquiring at said client whether decreasing the informational flow of said transaction is appropriate if a second message that is associated with said transaction has not been received by said client within a time period established for said message.

90. The machine readable storage medium of claim 72 wherein said method further comprises said client reducing the informational flow between said client and said server if a second message that is associated with said transaction has not been received by said client within a time period established for said message.

91. A machine readable medium having instructions that when executed by a processing system cause said processing to perform a method, said method comprising:

recurring adjustment of an ongoing data flow between a pair of nodes communicatively coupled by a network, said recurring adjustment performed by way of alterations made to characteristics of said flow, such alterations being scheduled and determined in response to ongoing observations of networking performance statistics related to said flow'"'"'s previous behavior;

said recurring adjustment including;

scheduling flow control adjustments specified by a flow timeout pointer positioned with respect to a flow timeout threshold value;

said positioning of said flow timeout pointer including setting a delay between when a last adjustment is made and when a next adjustment is made;

said setting a delay including;

calculating a first flow timeout threshold level;

calculating a second flow timeout threshold level; and

setting either the first flow timeout threshold level or the second flow timeout threshold level as the flow timeout threshold value based on a status of the ongoing data flow;

wherein;

setting said second flow timeout threshold level as the flow timeout threshold value makes the delay longer than setting said first flow timeout threshold level as the flow timeout threshold value.

92. The machine readable storage medium of claim 91 wherein said networking performance statistics further comprise a window transit time over said network.

93. The machine readable storage medium of claim 91 wherein said networking performance statistics further comprise an average delay over said network.

94. The machine readable storage medium of claim 91 wherein said networking performance statistics further comprise an arrival rate of expected messages.

95. The machine readable storage medium of claim 91 wherein said networking performance statistics further comprise a state of a queue that receives messages from said network, said queue within a first node of said pair of nodes.

96. The machine readable storage medium of claim 91 further comprising inquiring whether or not a flow increase is desirable in light of said networking performance statistics.

97. The machine readable storage medium of claim 96 further comprising comparing said networking performance statistics against a minimum performance level and not scheduling a said data flow adjustment if said minimum performance level is not achieved.

98. The machine readable storage medium of claim 91 wherein said recurring adjustment further comprises increasing said data flow according to a first flow increase schedule until data associated with said data flow is lost on said network.

99. The machine readable storage medium of claim 98 wherein said recurring adjustment further comprises increasing said data flow according to a second flow increase schedule after said data is lost, said second said flow increase schedule having a rate of flow increases less than said first flow increase schedule.

100. The machine readable storage medium of claim 91 further comprising adjusting said flow timeout threshold value in response to said networking performance statistics.

101. The machine readable storage medium of claim 100 further comprising adjusting said flow timeout threshold value to a position corresponding to a reduced rate of flow increase if data associated with said data flow is lost on said network.

102. The machine readable storage medium of claim 91 wherein said flow timeout threshold value corresponds to a factor of a window size used to control said data flow.

103. The machine readable storage medium of claim 91 wherein said recurring adjustment further comprises adjusting a window size.

104. The machine readable storage medium of claim 103 wherein said window size is adjusted by a datagram size.