Self-tuning dataflow I/O core

• US 6,848,005 B1
• Filed: 04/09/2001
• Issued: 01/25/2005
• 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, Totty, Brian, Semel, Ivry, Mattis, Peter, Plevyak, John, Jha, Vikas
• Primary Examiner(s): Cardone, Jason D.
• Application Number:
  US09/829,873
• Time in Patent Office: 1,387 Days
• Field of Search: 709/233, 709/232, 709/236, 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 mechanism 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 on 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 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 and establishing another bucket as a fast 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;

waiting until the earlier of (1) when any connection in the fast bucket is ready for communication or (2) when a pre-defined period of time elapses; and

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

2. The computer system recited in claim 1, wherein the steps further comprise always placing each newly established connection in the fast bucket until a pre-determined number of bytes have been communicated on the newly established connection.

3. The computer system recited in claim 1, 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.

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

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 and establishing another bucket as a fast 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;

waiting until the earlier of (1) when any connection in the fast bucket is ready for communication or (2) when a pre-defined period of time elapses; and

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

5. The method recited in claim 4, further comprising always placing each newly established connection in the fast bucket until a pre-determined number of bytes have been communicated on the newly established connection.

6. The method recited in claim 4, further comprising:

measuring time elapsed in processing connections in a bucket; and

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

7. 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 and establishing another bucket as a fast 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;

waiting until the earlier of (1) when any connection in the fast bucket is ready for communication or (2) when a pre-defined period of time elapses; and

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

8. The computer readable media recited in claim 7, wherein the steps further comprise always placing each newly established connection in the fast bucket until a pre-determined number of bytes have been communicated on the newly established connection.

9. The computer readable media recited in claim 7, 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.