Self-tuning dataflow I/O core

• US 6,308,214 B1
• Filed: 09/23/1998
• Issued: 10/23/2001
• Est. Priority Date: 09/23/1998
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Inktomi Corporation (Apollo Global Management, Inc.)
• Inventors: Brewer, Eric, Jha, Vikas, Semel, Ivry, Totty, Brian, Mattis, Peter, Plevyak, John
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Cardone, Jason D.
• Application Number:
  US09/159,468
• Time in Patent Office: 1,126 Days
• Field of Search: 709/225, 709/233, 709/234, 709/235, 709/236, 707/10, 707/103, 710/107, 710/109, 710/111, 710/220, 711/150, 370/230, 370/232, 370/458
• US Class Current: 709/233
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/568 Calendar queues or timing rings
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first

Abstract

A method and apparatus for managing data communications is provided. A circularly arranged set of buckets is disposed between input buffers and output buffers in a networked computer system. Connections among the system and clients are stored in the buckets. Each bucket in the set is successively examined, and each connection in the bucket is polled. During polling, the amount of information that has accumulated in a buffer associated with the connection since the last poll is determined. Based the amount, a period value associated with the connection is adjusted. The connection is then stored in a different bucket that is generally identified by the sum of the current bucket number and the period value. Polling continues with the next connection and the next bucket. In this way, the elapsed time between successive polls of a connection automatically adjusts to the actual operating bandwidth or data communication speed of the connection.

Claims

1. A method of managing a plurality of data communication connections having differing data communication rates, comprising the steps of:

A) assigning said data communication connections to a plurality of buckets that have a circular order;

B) establishing a bucket of said plurality of buckets as a current bucket;

C) establishing a connection assigned to said current bucket as a current connection;

D) communicating data over said current connection;

E) in response to communicating data over said current connection, re-assigning said current connection to a different bucket of said plurality of buckets based upon where said current bucket resides in said circular order and a bandwidth estimation of said current connection;

F) repeating steps (C), (D) and (E) for each connection assigned to said current bucket;

G) establishing a next bucket as a new current bucket, wherein said next bucket follows said current bucket in said circular order; and

H) repeating step (F) and (G) for each bucket of said plurality of buckets.

2. The method of claim 1 further comprising the steps of:

establishing a period value for each connection of said plurality of connections;

wherein the step of re-assigning said current connection to a different bucket is performed based on where said current bucket resides in said circular order and said period value.

3. The method of claim 2 further comprising the step of adjusting said period value based on how much data is communicated during step (D).

4. The method of claim 3 wherein:

said current connection is associated with a buffer that has a particular size; and

the step of adjusting said period value is performed based on how much data is communicated during step (D) relative to said particular size.

5. The method of claim 3 wherein:

the step of adjusting said period value includes the steps of

if an amount of data communicated during step (D) is greater than a high water mark, then decreasing the period value; and

if an amount of data communicated during step (D) is less than a low water mark, then increasing the period value.

6. The method of claim 2 wherein the step of re-assigning said current connection to a different bucket includes the steps of:

adding said period value to a first position value to generate a second position value, wherein said first position value indicates a position in said circular order of said current bucket; and

re-assigning said current connection to a bucket that has said second position value in said circular order.

7. The method recited in claim 2 establishing an initial value for said period value based upon information describing said current connection.

8. The method recited in claim 1, further comprising:

(J) continually querying each of the connections for I/O readiness, by back-to-back polls; and

(K) continually querying each of the connections for I/O readiness, by polling one of the connections, waiting for a pre-determined interval of time, and polling a next one of the connections.

9. The method recited in claim 8, further comprising:

adaptively selecting from among carrying out step (J) or carrying out step (K) according to an amount of processor resources that are available.

10. The method recited in claim 9, further comprising:

carrying out step (J) only when significant processor resources are available and carrying out step (K) only when limited processor resources are available.

11. The method recited in claim 1, wherein the step of re-assigning said current connection further comprises the steps of:

storing a high value and a low value that define limits upon an amount of data that may be buffered by said current connection between successive accesses to said current connection; and

adjusting said period value when an actual amount of data that is buffered by said current connection between successive accesses to said connection exceed said high value or falls below said low value.

12. The method recited in claim 1, further comprising:

measuring time elapsed in processing connections in a bucket; and

reducing a rate of establishing the connections when the measured time increases.

13. A computer-readable medium carrying one or more sequences of instructions for managing a plurality of data communication connections having differing data communication rates, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

A) assigning said data communication connections to a plurality of buckets that have a circular order;

B) establishing a bucket of said plurality of buckets as a current bucket;

C) establishing a connection assigned to said current bucket as a current connection;

D) communicating data over said current connection;

E) in response to communicating data over said current connection, re-assigning said current connection to a different bucket of said plurality of buckets based upon where said current bucket resides in said circular order and a bandwidth estimation of said current connection;

F) repeating steps (C), (D) and (E) for each connection assigned to said current bucket;

G) establishing a next bucket as a new current bucket, wherein said next bucket follows said current bucket in said circular order; and

H) repeating step (F) and (G) for each bucket of said plurality of buckets.

14. The computer readable medium recited in claim 13 wherein execution of said sequences of instructions further cause said processor to carry out the steps of:

establishing a period value for each connection of said plurality of connections;

wherein the step of re-assigning said current connection to a different bucket is performed based on where said current bucket resides in said circular order and said period value.

15. The computer readable medium of claim 14 establishing an initial value for said period value based upon information describing said current connection.

16. The computer readable medium of claim 14 wherein the step of re-assigning said current connection to a different bucket includes the steps of:

adding said period value to a first position value to generate a second position value, wherein said first position value indicates a position in said circular order of said current bucket; and

re-assigning said current connection to a bucket that has said second position value in said circular order.

17. The computer readable medium recited in claim 13, wherein the steps further comprise:

(J) continually querying each of the connections for I/O readiness, by back-to-back polls; and

(K) continually querying each of the connections for I/O readiness, by polling one of the connections, waiting for a pre-determined interval of time, and polling a next one of the connections.

18. The computer readable medium recited in claim 17, wherein the steps further comprise:

adaptively selecting from among carrying out step (J) or carrying out step (K) according to an amount of processor resources that are available.

19. The computer readable medium recited in claim 18, wherein the steps further comprise:

carrying out step (J) only when significant processor resources are available and carrying out step (K) only when limited processor resources are available.

20. The computer readable medium recited in claim 13 wherein execution of said sequences of instructions further cause said processor to carry out the step of adjusting said period value based on how much data is communicated during step (D).

21. The computer readable medium recited in claim 20 wherein:

said current connection is associated with a buffer that has a particular size; and

the step of adjusting said period value is performed based on how much data is communicated during step (D) relative to said particular size.

22. The computer readable medium of claim 20 wherein:

the step of adjusting said period value includes the steps of

if an amount of data communicated during step (D) is greater than a high water mark, then decreasing the period value; and

if an amount of data communicated during step (D) is less than a low water mark, then increasing the period value.

23. The computer readable medium of claim 13, wherein the step of re-assigning said current connection further comprises the steps of:

storing a high value and a low value that define limits upon an amount of data that may be buffered by said current connection between successive accesses to said current connection; and

adjusting said period value when an actual amount of data that is buffered by said current connection between successive accesses to said connection exceed said high value or falls below said low value.

24. The computer readable medium recited in claim 13, wherein the steps further comprise:

measuring time elapsed in processing connections in a bucket; and

reducing a rate of establishing the connections when the measured time increases.

25. A computer system, comprising:

a processor; and

a memory coupled to said processor, said memory comprising one or more sequences of instructions for managing a plurality of data communication connections having differing data communication rates, wherein execution of the one or more sequences of instructions by said processor causes the processor to perform the steps of;

A) assigning said data communication connections to a plurality of buckets that have a circular order;

B) establishing a bucket of said plurality of buckets as a current bucket;

C) establishing a connection assigned to said current bucket as a current connection;

D) communicating data over said current connection;

E) in response to communicating data over said current connection, re-assigning said current connection to a different bucket of said plurality of buckets based upon where said current bucket resides in said circular order and a bandwidth estimation of said current connection;

F) repeating steps (C), (D) and (E) for each connection assigned to said current bucket;

G) establishing a next bucket as a new current bucket, wherein said next bucket follows said current bucket in said circular order; and

H) repeating step (F) and (G) for each bucket of said plurality of buckets.