System and method for automatic management of many computer data processing system pipes

• US 7,710,874 B2
• Filed: 06/04/2003
• Issued: 05/04/2010
• Est. Priority Date: 06/04/2003
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Singh, Raj K., Yedavalli, Rama M., Balakrishnan, Ganesh, Siegel, Michael S., Jeffries, Clark D., Corl, Everett A. Jr., Sabhikhi, Ravinder K.
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): Russell; Wanda Z
• Application Number:
  US10/454,052
• Publication Number:
  US 20040246976A1
• Time in Patent Office: 2,526 Days
• Field of Search: 370/338
• US Class Current: 370/235
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76

Abstract

A process control method and system including partitioning transmit decisions and certain measurements into one logical entity (Data Plane) and partitioning algorithm computation to update transmit probabilities into a second logical entity (Control Plane), the two entities periodically communicating fresh measurements from Data Plane to Control Plane and adjusted transmit probabilities from Control Plane to Data Plane. The transmit probability may be used in transmit/discard decisions of packets or instructions exercised at every arrival of a packet or instruction. In an alternative embodiment, the transmit probability may be used in transmit/delay decisions of awaiting instructions or packets exercised at every service event.

Claims

1. A method for automatically allocating bandwidth among many pipes in a network comprising:

(a) providing a first device in which a unit of information received is associated with one pipe of the many pipes;

(b) determining predefined characteristics of said unit of information;

(c) providing a second device (different from said first device) in which transmit probability Ti for each of the many pipes is being calculated, which includes the calculation of values of Ti for packets of previously established connections of the many of pipes, wherein said transmit probability Ti relates to discarding said unit of information, forwarding said unit of information, and delay in forwarding said unit of information based upon a comparison of said transmit probability Ti with a random number generated for a service event of said unit of information;

(d) transmitting from said second device to said first device the transmit probabilities Ti so calculated; and

(e) making, in said first device, a decision for said unit of information based upon the comparison of the transmit probability Ti with the random number for at least one of the many pipes.

2. The method of claim 1 wherein the predefined characteristics of packets are forwarded to the second device and are used to generate Ti.

3. The method of claim 2 wherein the first device includes a specialized computer.

4. The method of claim 3 wherein the specialized computer includes a network processor.

5. The method of claim 2 wherein the second device includes a general purpose computer.

6. The method of claim 1 wherein the unit of information includes packets.

7. The method of claim 1 wherein the unit of information includes instructions.

8. The method of claim 1 further including storing predefined information in said first device;

and periodically sending stored information to the second device.

9. The method of claim 8 wherein the stored information relates

to each pipe and includes

a) the current transmit probability Ti;

b) measured values such as the current transmitted rate of pipe I;

c) occupancy of the processing queue and the rate of change of the occupancy of the processing queue; and

d) various per-pipe configuration values including each pipe minimum bandwidth

guarantee mini, each pipe maximum bandwidth limit maxi, and each pipe precedence (an integer=0, 1, 2, 3, . . . ).

10. The method of claim 1 wherein the decision includes comprises discarding said unit of information.

11. The method of claim 1 wherein the decision includes comprises delay in forwarding said unit of information.

12. The method of claim 1 wherein the decision includes comprises forwarding the unit of information.

13. The method of claim 1, further comprising:

aggregating transmission rates of a set of pipes of the many pipes to produce a rate sum, comparing the rate sum with a maximum value, and reducing the Ti for the one pipe based on the rate sum exceeding the maximum value.

14. The method of claim 1 wherein the first device comprises a specialized computer.

15. The method of claim 1 wherein the second device comprises a general purpose computer.

16. A communication system including:

a plurality of flows to which packets are associated;

a random number generator for generating random numbers, wherein the random number generator generates random numbers for service events of Packets;

a special purpose computer including a memory for storing a Patricia tree data structure comprising flow characteristics information including transmit probability (Ti) for selected ones of the flows; and

a flow control device that associates a packet with a flow and uses the Ti for the flow and a random number to generate a decision for said packet, wherein said packet may be associated with an established connection, wherein further the decision relates to discarding said packet, forwarding said packet, and delaying said packet based on a comparison of the Ti with a random number of the random number generator during a service event.

17. The communication system of claim 16 wherein the decision is to drop said packet based upon the comparison of Ti and the random number.

18. The communication system of claim 17 wherein the decision is to postpone action on said packet.

19. The communication system of claim 18 wherein the packet includes computer instructions.

20. The communication system of claim 16 wherein the special purpose computer includes a network processor.

21. The communication system of claim 16 further including a general purpose computer executing a first predefined algorithm containing variables representing characteristic information for selected ones of the flows and generating transmission probability Tj;

and means for forwarding Tj to be stored in said Patricia tree data structure.

22. The communication system of claim 21 wherein the special purpose computer executes a second predefined algorithm containing flow characteristics associated with selected ones of the flow to generate Ti.

23. The communications systems of claim 22 wherein the first predefined algorithm and second predefined algorithm are identical.

24. The communication system of claim 16 wherein the communication system calculates new values for the transmission probability (Ti) for the selected ones of the flows based on an aggregation of the plurality of flows and a comparison of the aggregation with a maximum value of the aggregation.

25. A system, comprising:

a general purpose computer configured to calculate an aggregate value of transmission rates of a plurality of pipes, wherein the general purpose computer is configured to reduce a transmit probability (Ti) for a pipe of the plurality of pipes based on a comparison of the aggregate value with a maximum value of the bandwidth associated with the plurality of pipes; and

a network processor configured to compare the transmit probability (Ti) with a random number for a packet of an allowed session of the pipe, wherein the network processor is configured to either transmit or discard the packet based on the comparison of the transmit probability with the random number.