Method and system for controlling information flow between a producer and a buffer in a high frequency digital system

• US 6,606,666 B1
• Filed: 11/09/1999
• Issued: 08/12/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,962
• Time in Patent Office: 1,372 Days
• Field of Search: 709/213, 709/215, 709/217, 709/226, 709/227-233, 709/250, 709/312-313, 370/230, 370/352-353, 370/259, 370/389-390, 370/392, 370/398, 370/400, 370/402, 370/409-412, 370/414-416, 370/429, 370/424, 370/460, 370/462, 370/468
• US Class Current: 709/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/39 Credit based
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

An information handling system includes a producer that outputs packets, a buffer that receives packets from the producer, buffers the packets, and eventually outputs the packets, and a control unit that controls the flow of packets from the producer to the buffer. The control unit receives as inputs a producer output indication indicating that the producer has output a packet to the buffer and a buffer output indication indicating that the buffer has output a packet. Based upon a capacity of the buffer, a number of the producer output indications, a number of buffer output indications, and a number of grant messages output to the producer within a feedback latency of the control unit, the control unit whether the producer can output a packet without packet loss. In response to a determination that the producer can output a packet without packet loss, the control unit outputs a grant message to the producer indicating that the producer is permitted to output a packet.

Claims

1. A method for controlling packet flow from a producer to a buffer, said method comprising:

receiving as inputs at a control unit one or more producer output indications each indicating that said producer has output a respective packet to said buffer via a data path and one or more buffer output indications each indicating that said buffer has output a respective packet;

at said control unit, determining whether said producer can output a packet via said data path without packet loss, based upon a capacity of said buffer, how many packets have been output by said producer based upon said producer output indications, how many packets have been output by said buffer based upon said buffer output indications, and how many packets said control unit has authorized said producer to output based upon grant messages output to said producer within a feedback latency of said control unit, 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 to reach said producer from said control unit; 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 via a control path physically separate from said data path, said grant message indicating that said producer is authorized to output a packet.

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

calculating a sum of a buffer count indicating a number of packets residing in said buffer and a grant count indicating a 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 a buffer capacity of said buffer is larger than said sum plus a number of said producer output indications less a number of said buffer output indications.

3. The method of claim 2, wherein calculating said sum of said buffer count and said grant count comprises dynamically updating one or more registers maintaining said buffer count and said grant count.

4. The method of claim 2, wherein said step of calculating said sum comprises calculating a buffer count subject to latency of said buffer output indication reaching said control unit from said buffer.

5. The method of claim 1, wherein outputting a grant message comprises outputting a grant message indicating how many packets said producer is permitted to output.

6. The method of claim 1, and further comprising in response to receipt of said grant message at said producer, outputting at least one packet to said buffer.

7. The method of claim 6, wherein outputting at least one packet comprises outputting all information pertaining to said at least one packet, such that said producer retains no record of said at least one packet.

8. An information handling system, comprising:

a producer that outputs packets of information via a data path;

a buffer, coupled to said data path, that receives said packets from said producer and outputs said packets; and

a control unit coupled to said producer by a control path physically separate from said data path, wherein said control unit receives one or more producer output indications each indicating that said producer has output a respective packet and receives one or more buffer output indications each indicating that said buffer has output a respective packet, wherein said control unit determines whether said producer can output a packet via said data path without packet loss, based upon a capacity of said buffer, how many packets have been output by said producer based upon said producer output indications, how many packets have been output by said buffer based upon said buffer output indications, and how many packets said control unit has authorized said producer to output based upon grant messages output to said producer within a feedback latency of said control unit, and wherein said control unit, responsive to a determination that said producer can output a packet without packet loss, generates and outputs a grant message to said producer via said control path, said grant message indicating that said producer is authorized to output a packet,

wherein said feedback latency comprises a first latency for a producer output indication to reach said control unit from said producer and a second latency for a grant message to reach said producer from said control unit via said control path.

9. The information handling system of claim 8, wherein said control unit further comprises:

at least one register that maintains a buffer count of a number of packets residing in said buffer and a grant count of a number of grant messages output to said producer within a feedback latency of said control unit;

determination logic that determines if a buffer capacity of said buffer is larger than the sum of said buffer count and said grant count and a number of said buffer output indications less a number of said producer output indications, and in response to a determination that said buffer capacity is larger, outputs said grant message.

10. The information handling system of claim 9, wherein said buffer count is subject to latency of said buffer output indication reaching said control unit from said buffer.

11. The information handling system of claim 8, said grant message comprising an indication of how many packets said producer is permitted to output.

12. The information handling system of claim 8, wherein said producer is memoriless such that said producer has no record of packets that have been output.

13. The information handling system of claim 8, wherein said producer outputs a packet only in response to receipt of a grant message.

14. The information handling system of claim 8, wherein said information handling system comprises a processor and each packet represents a store request.

15. A controller for controlling packet transfer from a producer that outputs packets of information on a data path to a buffer that receives said packets from said producer and thereafter outputs said packets, said controller comprising:

a first input that receives one or more producer output indications each indicating that the producer has output a respective packet on said data path and a second input that receives one or more buffer output indications each indicating that the buffer has output a respective packet;

an output coupled to said producer by a control path physically separate from said data path; and

determination logic that determines whether said producer can output a packet on said data path without packet loss, based upon a capacity of said buffer, how many packets said producer has output as indicated by said producer output indications, how many packets said buffer has output as indicated by buffer output indications, and how many packets said controller has authorized said producer to output as indicated by grant messages output to said producer within a feedback latency of said controller, wherein said determination logic, in response to determining that said producer can output a packet via said data path without packet loss, generates and outputs a grant message to said producer via said control path, said grant message indicating that said producer is authorized to output a packet,

wherein said feedback latency comprises a first latency for a producer output indication to reach said controller from said producer and a second latency for a grant message to reach the producer from said controller via said control path.

16. The controller of claim 15, wherein

said controller further comprises at least one counter that maintains a buffer count of a number of packets residing in said buffer and a grant count of a number of grant messages output to said producer within a feedback latency of said controller; and

said determination logic determines that said producer can output a packet without packet loss if a buffer capacity of said buffer is larger than the sum of said buffer count and said grant count plus a number of said buffer output indications less a number of said producer output indications.

17. The controller of claim 16, wherein said buffer count is subject to latency of said buffer output indication reaching said controller.

18. The controller of claim 15, said grant message comprising an indication of how many packets said producer is permitted to output.

19. A program product for controlling packet transfer from a producer that outputs packets of information on a data path to a buffer that receives said packets from said producer and outputs said packets, said program product comprising:

input code that obtains one or more producer output indications each indicating that the producer has output a respective packet and one or more buffer output indications each indicating that the buffer has output a respective packet;

determination code that determines whether said producer can output a packet on said data path without packet loss, based upon a capacity of said buffer, how many packets said producer has output as indicated by said producer output indications, how many packets said buffer has output as indicated by said buffer output indications, and how many packets said producer has been authorized to output as indicated by grant messages output to said producer within a control feedback latency, wherein said determination code, responsive to determining that said producer can output a packet on said data path without packet loss, generates and outputs a grant message to said producer via a control path physically separate from said data path, said grant message indicating that said producer is authorized to output a packet,

wherein said control feedback latency comprises a first latency for said producer output indication to be received by said input code and a second latency for a grant message to reach the producer from said determination code via said control path; and

a computer-usable medium encoding said input code and said determination code.

20. The program product of claim 19, wherein:

said program product further comprises counter code that maintains a buffer count of a number of packets residing in said buffer and a grant count of a number of grant messages output to said producer within said control feedback latency; and

said determination code determines that said producer can output a packet without packet loss if a buffer capacity of said buffer is larger than the sum of said buffer count and said grant count plus a number of said buffer output indications less a number of said producer output indications.

21. The program product of claim 20, wherein said buffer count is subject to latency of said buffer output indication being received by said program product.

22. The program product of claim 19, said grant message comprising an indication of how many packets the producer is permitted to output.