Method and system for controlling information flow in a high frequency digital system from a producer to a buffering consumer via an intermediate buffer and a shared data path

• US 6,604,145 B1
• Filed: 11/09/1999
• Issued: 08/05/2003
• Est. Priority Date: 11/09/1999
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Starke, William John, Clark, Leo James, Cargnoni, Robert Alan, Bell, Robert Henry Jr.
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): LIN, WEN TAI
• Application Number:
  US09/436,963
• Time in Patent Office: 1,365 Days
• Field of Search: 709/203, 709/215, 709/217, 709/226-228, 709/232, 709/233, 709/312, 709/313, 370/235, 370/352, 370/353, 370/431-433, 370/439, 370/400, 370/410, 370/412, 370/414, 370/416, 370/259, 370/230, 379/165
• US Class Current: 709/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/39 Credit based

Abstract

An information handling system includes a plurality of producers that output packets of information, at least one consumer of the packets, and an information pipeline coupling the consumer and at least a particular producer among the plurality of producers. The information pipeline includes a shared resource having a bandwidth shared by multiple of the plurality of producers. The information handling system further includes a control unit that regulates packet output of the particular producer and that receives as inputs a producer output indication indicating that the particular producer output a packet and a shared resource input indication indicating that a packet output by the particular producer has been accepted by the shared resource for transmission to the consumer. Based upon these inputs, a number of grant messages output to the particular producer within a feedback latency of the control unit, and a portion of the bandwidth allocated to the particular producer, the control unit whether the particular producer can output a packet without packet loss. In response to a determination that the particular producer can output a packet without packet loss, the control unit outputs a grant message to the particular producer indicating that the particular producer is permitted to output a packet.

Claims

1. A method of dynamically controlling ongoing packet flow from a producer among multiple producers to at least one consumer via an information pipeline containing an intermediate shared resource having a bandwidth, said method comprising:

at a control unit, receiving as inputs producer output indications each indicating that the producer has output a packet and shared resource input indications each indicating that a packet previously output by the producer has been accepted by said shared resource for transmission to said at least one consumer;

at said control unit, repetitively determining during ongoing packet flow from the producer to said at least one consumer whether said producer can output a packet without packet loss based upon how many packets have been output by said producer as indicated by said producer output indications, how many packets have been input into said shared resource as indicated by said shared resource input indications, bow many packets said control unit has permitted to be output by said producer as indicated by grant messages transmitted to said producer within a feedback latency of said control unit, and a portion of said bandwidth allocated to said producer, wherein said feedback latency includes a first latency for a producer output indication to reach said control unit from said producer and a second latency for a grant message generated by said control unit to reach said producer from said control unit and wherein said control unit determines whether said producer can output a packet without packet loss independently of any signaling by said at least one consumer; and

in response to a determination that said producer can output a packet without packet loss, said control unit generating and outputting a grant message to said producer indicating that said producer is permitted to output a packet.

2. The method of claim 1, wherein said information pipeline includes a buffer having a buffer capacity, and wherein said determination is further based upon a number of packets within said buffer and said buffer capacity.

3. The method of claim 2, wherein determining if said producer can output a packet without packet loss comprises:

calculating a sum of said number of buffered packets and said number of grant messages output to said producer within a feedback latency of said control unit; and

determining that said producer can output a packet without packet loss if said buffer capacity is larger than said sum plus a number of said producer output indications less a number of said shared resource input indications and less said portion of said bandwidth.

4. The method of claim 3, wherein calculating said sum comprises dynamically updating one or more registers maintaining said number of buffered packets and said number of grant messages.

5. The method of claim 3, and further comprising determining said portion of said bandwidth by reference to how many active producers are transmitting packets to said at least one consumer via said shared resource.

6. The method of claim 4, and further comprising dynamically determining a number of active producers by reference to a number of producers requesting permission to output a packet.

7. The method of claim 1, wherein determining if said producer can output a packet without packet loss comprises determining that said producer can output a packet without packet loss only in response to receipt by said control unit of an authorization to supply said grant message.

8. The method of claim 1, and further comprising:

in response to receipt of said grant message at said producer, outputting at least one packet, such that said producer retains no record of said at least one packet.

9. The method of claim 1, wherein said control unit determines whether said producer can output a packet without packet loss utilizing only information regarding packet flow at locations within said information pipeline at or preceding said shared resource.

10. The method of claim 1, wherein:

receiving producer output indications comprises receiving signaling from the producer separate from said information pipeline; and

receiving shared resource input indications comprises receiving external signaling at said control unit separate from said information pipeline.

11. The method of claim 1, wherein said plurality of producers, said consumer and said shared resource are each implemented as components of a single integrated circuit device, and wherein said receiving, said determining and said outputting are all performed within the single integrated circuit device.

12. The method of claim 1, wherein:

each producer output indication indicates that said producer has output one packet;

each shared resource input indication indicates that said consumer has received one packet;

each grant message indicates said producer is permitted to output one packet; and

said determining comprises determining based upon how many of said producer output indications and said shared resource input indications have been received by said control unit and based upon how many grant messages have been transmitted by said control unit.

13. An information handling system, comprising:

a plurality of producers that outputs packets of information and at least one consumer of said packets;

an information pipeline coupling said at least one consumer and at least a particular producer among said plurality of producers, wherein said information pipeline includes a shared resource having a bandwidth shared by multiple of said plurality of producers; and

a control unit that dynamically regulates ongoing packet output of said particular producer, said control unit receiving as inputs producer output indications each indicating that said particular producer has output a packet and shared resource input indications each indicating that a packet previously output by said particular producer has been accepted by said shared resource for transmission to said at least one consumer, wherein said control unit repetitively determines during ongoing packet flow from the particular producer to said at least one consumer whether said particular producer can output a packet without packet loss based upon how many packets have been output by said particular producer as indicated by said producer output indications, how many packets have been input into said shared resource as indicated by said shared resource input indications, how many packets said control unit has permitted to be output by said particular producer as indicated by grant messages transmitted to said particular producer within a feedback latency of said control unit, and a portion of said bandwidth allocated to said particular producer, and, responsive to a determination that said particular producer can output a packet without packet loss, generates and outputs a grant message to said particular producer indicating that said particular producer is permitted to output a packet;

wherein said feedback latency includes a first latency for a producer output indication to reach said control unit from said particular producer and a second latency for a grant message generated by said control unit to reach said particular producer from said control unit; and

wherein said control unit determines whether said producer can output a packet without packet loss independently of any signaling by said at least one consumer.

14. The information handling system of claim 13, wherein said information pipeline includes a buffer having a buffer capacity, and wherein said control unit further bases said determination upon a number of packets within said buffer and said buffer capacity.

15. The information handling system of claim 14, wherein said control unit determines that said particular producer can output a packet without packet loss if said buffer capacity is larger than a sum of said number of buffered packets and said number of grant messages output to said particular producer within a feedback latency of said control unit plus a number of said producer output indications less a number of said shared resource input indications and less said portion of said bandwidth.

16. The information handling system of claim 15, said control unit including one or more registers that maintain said number of buffered packets and said number of grant messages.

17. The information handling system of claim 15, wherein said control unit determines said portion of said bandwidth by reference to how many active producers among said plurality of producers are transmitting packets to said at least one consumer via said shared resource.

18. The information handling system of claim 17, and further comprising a global controller that dynamically determines a number of active producers by reference to a number of producers requesting permission to output a packet and communicates said number of active producers to said control unit.

19. The information handling system of claim 18, wherein said global controller supplies said control unit with an authorization to supply a grant message, and wherein said control unit outputs said grant message only in response to receipt of said authorization.

20. The information handling system of claim 13, wherein said particular producer is a memoriless produces that retains no record of said packets.

21. The information handling system of claim 13, wherein said control unit determines whether said particular producer can output a packet without packet loss utilizing only information regarding packet flow at locations within said information pipeline at or preceding said shared resource.

22. The information handling system of claim 13, and further comprising:

a first signaling connection between said particular producer and said control unit separate from said information pipeline; and

a second signaling connection between said information pipeline and said control unit for said shared resource input indications, wherein said second signaling connection is separate from said information pipeline.

23. The information handling system of claim 13, wherein said plurality of producers, said consumer and said shared resource are each implemented as components of a single integrated circuit device.

24. The information handling system of claim 13, wherein:

each producer output indication indicates that said producer has output one packet;

each shared resource input indication indicates that said consumer has received one packet;

each grant message indicates said producer is permitted to output one packet; and

said control unit determines whether said particular producer is permitted to output a packet based upon how many of said producer output indications and said shared resource input indications have been received by said control unit and based upon how many grant messages have been transmitted by said control unit.

25. A controller for dynamically controlling ongoing packet transfer from a particular producer to at least one consumer via an information pipeline including a shared resource having a bandwidth shared by multiple producers, said controller comprising:

an input set including producer output indications each indicating that said particular producer has output a packet and shared resource input indications each indicating that a packet previously output by said particular producer has been accepted by said shared resource for transmission to said at least one consumer; and

determination logic that repetitively determines during ongoing packet flow from the particular producer to said at least one consumer whether said particular producer can output a packet without packet loss, based upon how many packets have been output by said particular producer as indicated by said producer output indications, how many packets have been input into said shared resource as indicated by said shared resource input indications, how many packet said control unit has permitted to be output by said particular producer as indicated by grant messages transmitted to said particular producer within a feedback latency of said controller, and a portion of said bandwidth allocated to said particular producer, and, responsive to a determination that said particular producer can output a packet without packet loss, generates and outputs a grant message to said particular producer indicating that said particular producer is permitted to output a packet,

wherein said feedback latency includes a first latency for a producer output indication to reach said control unit from said particular producer and a second latency for a grant message generated by said controller to reach said particular producer from said control unit; and

wherein said control unit determines whether said producer can output a packet without packet loss independently of any signaling said at least one consumer.

26. The controller of claim 25, wherein said information pipeline includes a buffer having a buffer capacity, and wherein said determination logic further bases said determination upon a number of packets within said buffer and said buffer capacity.

27. The controller of claim 26, wherein said determination logic determines that said particular producer can output a packet without packet loss if said buffer capacity is larger than a sum of said number of buffered packets and said number of grant messages output to said particular producer within a feedback latency of said control unit plus a number of said producer output indications less a number of said shared resource input indications and less said portion of said bandwidth.

28. The controller of claim 27, said controller further comprising one or more registers that maintain said number of buffered packets and said number of grant messages.

29. The controller of claim 27, wherein said determination logic determines said portion of said bandwidth by reference to how many active producers among said plurality of producers are transmitting packets to said at least one consumer via said shared resource.

30. The controller of claim 25, wherein said controller outputs said grant message only in response to receipt of an authorization from a global controller.

31. The controller of claim 25, wherein said determination logic determines whether said particular producer can output a packet without packet loss utilizing only information regarding packet flow at locations within said information pipeline at or preceding said shared resource.

32. The controller of claim 25, wherein:

each producer output indication indicates that said producer has output one packet;

each shared resource input indication indicates that said consumer has received one packet;

each grant message indicates said producer is permitted to output one packet; and

said determination logic determines whether said particular producer is permitted to output a packet based upon how many of said producer output indications and said shared resource input indications have been received by said control unit and based upon how many grant messages have been transmitted by said control unit.

33. A program product for dynamically controlling ongoing packet transfer from a particular producer to at least one consumer via an information pipeline including a shared resource having a bandwidth shared by multiple producers, said program product comprising:

input code that obtains an input set including producer output indications each indicating that said particular producer has output a packet and shared resource input indications each indicating that a packet previously output by said particular producer has been accepted by said shared resource for transmission to said at least one consumer; and

determination code that repetitively determines during ongoing packet flow from the particular producer to said at least one consumer whether said particular producer can output a packet without packet loss based upon how many packets have been output by said particular producer as indicated by said producer output indications, how many packets have been input into said shared resource as indicated by said shared resource input indications, how many packets said control unit has permitted to be output by said particular producer as indicated by grant messages transmitted to said particular producer within a control feedback latency, and a portion of said bandwidth allocated to said particular producer, and, responsive to a determination that said particular producer can output a packet without packet loss, generates and outputs a grant message to said particular producer indicating that said particular producer is permitted to output a packet, wherein said control feedback latency includes a first latency for a producer output indication to reach said determination code from said particular producer and a second latency for a grant message generated by said determination code to reach said particular producer, and wherein said control unit determines whether said producer can output a packet without packet loss independently of any signaling by said at least one consumer; and

a data processing system usable medium encoding said input code and said determination code.

34. The program product of claim 33, wherein said information pipeline includes a buffer having a buffer capacity, and wherein said determination code further bases said determination upon a number of packets within said buffer and said buffer capacity.

35. The program product of claim 34, wherein said determination code determines that said particular producer can output a packet without packet loss if said buffer capacity is larger than a sum of said number of buffered packets and said number of grant messages output to said particular producer within said control feedback latency plus a number of said producer output indications less a number of said shared resource input indications and less said portion of said bandwidth.

36. The program product of claim 35, said program product further comprising counter code that dynamically maintains said number of buffered packets and said number of grant messages.

37. The program product of claim 35, wherein said determination code determines said portion of said bandwidth by reference to how many active producers among said plurality of producers are transmitting packets to said at least one consumer via said shared resource.

38. The program product of claim 33, wherein said determination code determines whether said particular producer can output a packet without packet loss utilizing only information regarding packet flow at locations within said information pipeline at or preceding said shared resource.

39. The program product of claim 33, wherein:

each producer output indication indicates that said producer has output one packet;

each shared resource input indication indicates that said consumer has received one packet;

each grant message indicates said producer is permitted to output one packet; and

said determination code determines whether said particular producer is permitted to output a packet based upon how many of said producer output indications and said shared resource input indications have been received by said control unit and based upon how many grant messages have been transmitted by said control unit.