Token based flow control for data communication

• US 7,908,372 B2
• Filed: 06/12/2007
• Issued: 03/15/2011
• Est. Priority Date: 06/19/2006
• Status: Active Grant

• Current Assignee: Liquid Computing Corporation, Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Liquid Computing Corporation
• Inventors: Munter, Ernst, Kemp, Michael F., Huang, Kaiyuan
• Primary Examiner(s): Jean; Frantz B
• Application Number:
  US11/761,827
• Publication Number:
  US 20070294435A1
• Time in Patent Office: 1,372 Days
• Field of Search: 709/225, 709/251, 709/234
• US Class Current: 709/225
• CPC Class Codes: G06F 15/173 using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
• CPC Class Codes: H04L 1/1614 using bitmaps
• CPC Class Codes: H04L 1/1685 the supervisory signal being transmitted in response to a specific request, e.g. to a polling signal
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/35 by embedding flow control information in regular packets, e.g. piggybacking
• CPC Class Codes: H04L 47/746 Reaction triggered by a failure

Abstract

An embodiment of one of the inventions disclosed herein is a computer system that includes a plurality of interconnected computational hosts, each of which are connected to one of a plurality of buffers. Each of the buffers includes a plurality of buffer spaces. Each of the computational hosts may be configured such that each transfer of a data packet from one of the plurality of computational hosts acting as a source of the data packet to another one of the plurality of computational hosts acting as a destination of the data packet is controlled by an availability of buffer spaces in the buffer coupled to the destination computational host.

Claims

1. A method of controlling a transmission of data packets from one of a plurality of source computational hosts to a destination computational host in a computer system, comprising the steps of:

providing a buffer coupled to the destination computational host, the buffer including a plurality of buffer spaces, each of which being configured to receive and store a data packet;

distributing, by the destination computational host, a selected number of tokens to selected ones of the plurality of source computational hosts, each token representing an available one of the plurality of buffer spaces;

sending, by one of the plurality of source computational hosts having at least one token distributed to it by the destination computational host, a data packet to the destination computational host and correspondingly discarding one of the tokens distributed thereto;

requesting, by any source computational host whose number of tokens distributed to it by the destination computational host has fallen below a first selectable threshold, additional tokens from the destination computational host, and

distributing, by the destination computational host, additional tokens to the requesting source computational host and periodically distributing additional tokens to any of the plurality of source computational hosts having sent data packets to the destination computational host, subject to a number of available buffer spaces.

2. The method of claim 1, wherein an aggregate number of tokens distributed in the first distributing step does not exceed a number of the buffer spaces of the buffer.

3. The method of claim 1, further comprising steps of freeing up a buffer space and creating a new token that is available for distribution by the destination computational host to one of the plurality of source computational hosts.

4. The method of claim 1, wherein the requesting step includes piggybacking the request for additional tokens in a next data packet sent to the destination computational host after the number of available tokens distributed to the requesting source computational host by the destination computational host falls below the first selectable threshold.

5. The method of claim 1 wherein, responsive to the destination computational host receiving the request for additional tokens, the destination computational host determining whether and how many data packets it can distribute to the requesting source computational host based upon a number of available buffer spaces, diminished by a number of tokens available to other computational hosts in the computer system that were distributed by the destination computational host.

6. The method of claim 1, wherein the requesting step includes piggybacking the request for additional tokens in a next data packet and subsequent data packets sent to the destination computational host after the number of available tokens distributed to the requesting source computational host by the destination computational host falls below a second selectable threshold that is lower than the first selectable threshold.

7. The method of claim 1, further including a step of regulating a rate at which data packets are sent to the destination computational host by correspondingly regulating at least one of a number of tokens distributed and a rate at which tokens are distributed to any of the plurality of source computational hosts that are sending data packets to the destination computational host.

8. A non-transitory machine-readable medium having data stored thereon representing sequences of instructions which, when executed by a computer system, controls a transmission of data packets from one of a plurality of source computational hosts to a destination computational host in the computer system by performing the steps of:

providing a buffer coupled to the destination computational host, the buffer including a plurality of buffer spaces, each of which being configured to receive and store a data packet;

distributing, by the destination computational host, a selected number of tokens to selected ones of the plurality of source computational hosts, each token representing an available one of the plurality of buffer spaces;

sending, by one of the plurality of source computational hosts having at least one token distributed to it by the destination computational host, a data packet to the destination computational host and correspondingly discarding one of the tokens distributed thereto;

requesting, by any source computational host whose number of tokens distributed to it by the destination computational host has fallen below a first selectable threshold, additional tokens from the destination computational host, and

distributing, by the destination computational host, additional tokens to the requesting source computational host and periodically distributing additional tokens to any of the plurality of source computational hosts having sent data packets to the destination computational host, subject to a number of available buffer spaces.

9. A method of transmitting data packets between a plurality of computational hosts of a computer system, comprising steps of:

associating a buffer with each of the computational hosts of the computer system, each buffer including a plurality of buffer spaces, each of which are configured to receive and store a data packet;

distributing, by at least some of the computational hosts of the computer system, a selected number of tokens to at least some of the other computational hosts, each distributed token representing an available one of the plurality of buffer spaces of the associated buffer;

enabling any computational host to transmit a data packet to a selected other computational host of the plurality of computational hosts as long as the sending computational host has at least one token that was distributed to it by the selected other computational host;

requesting, by any computational host whose number of tokens provided by an other computational host in the computer system falls below a first selectable threshold, additional tokens from the other computational host;

distributing, by the other computational host, one or more additional tokens to the requesting computational host, subject an availability of free buffer spaces, and periodically distributing, by any computational host having received one or more data packets, one or more additional tokens to any of the plurality of computational hosts having sent it data packets, subject an availability of free buffer spaces.

10. The method of claim 9, wherein an aggregate number of tokens distributed by each computational host in the first distributing step does not exceed a number of the buffer spaces of the associated buffer.

11. The method of claim 9, further comprising steps of freeing a buffer space and correspondingly creating a new token that is available for distribution to one of the plurality of computational hosts.

12. The method of claim 9, wherein the requesting step includes piggybacking the request for additional tokens in a next data packet sent to the other computational host after the number of available tokens provided by the other computational host falls below the first selectable threshold.

13. The method of claim 9 wherein, responsive to a computational host receiving the request for additional tokens from the requesting computational host, the receiving computational host determining whether and how many tokens to send to the requesting computational host based upon a difference of a number of available buffer spaces in a buffer coupled to the receiving computational host and a sum of a number of tokens available to the requesting computational host and provided to it by the receiving computational host and a number of available tokens provided by the receiving computational host in any of the other computational hosts in the computer system.

14. The method of claim 9, wherein the requesting step includes piggybacking the request for additional tokens in a next and subsequent data packets sent to the other computational host after the number of available tokens available to the source computational host and provided by the other computational host falls below a second selectable threshold.

15. The method of claim 9, further including a step of regulating a rate at which data packets are transmitted by computational hosts of the computer system by correspondingly regulating at least one of a number of tokens distributed and a rate at which tokens are distributed to computational hosts in the computer system that are transmitting data packets.

16. A non-transitory machine-readable medium having data stored thereon representing sequences of instructions which, when executed by a computer system, causes a transmission of data packets between a plurality of computational hosts of the computer system, by performing the steps of:

associating a buffer with each of the computational hosts of the computer system, each buffer including a plurality of buffer spaces, each of which are configured to receive and store a data packet;

distributing, by at least some of the computational hosts of the computer system, a selected number of tokens to at least some of the other computational hosts, each distributed token representing an available one of the plurality of buffer spaces of the associated buffer;

enabling any computational host to transmit a data packet to a selected other computational host of the plurality of computational hosts as long as the sending computational host has at least one token that was distributed to it by the selected other computational host;

requesting, by any computational host whose number of tokens provided by an other computational host in the computer system falls below a first selectable threshold, additional tokens from the other computational host;

distributing, by the other computational host, one or more additional tokens to the requesting computational host, subject an availability of free buffer spaces, and

periodically distributing, by any computational host having received one or more data packets, one or more additional tokens to any of the plurality of computational hosts having sent it data packets, subject an availability of free buffer spaces.

17. A method of controlling a number of data packets a source computational host can send to a destination computational host of a computer system, comprising the steps of:

providing the source computational host with a selected number of tokens;

limiting the number of data packets the source computational host can send the destination computational host to a number of data packets that is equal to the selected number of tokens, the number of tokens being selected based upon a number of available buffer spaces in a buffer coupled to the destination computational host;

decrementing a number of tokens available to the source computational host with each data packet sent from the source computational host to the destination computational host, and

requesting, by the source computational host, additional tokens from the destination computational host when a number of tokens available to the source computational host falls below a first selectable threshold.

18. The method of claim 17, wherein the requesting step includes piggybacking the request for additional tokens in a next data packet sent to the destination computational host after the number of available tokens falls below the first selectable threshold.

19. The method of claim 17, wherein the providing step selects the number of tokens based upon a difference of a number of available buffer spaces in the buffer coupled to the destination computational host and a number of tokens already provided to the source computational host and to any other computational hosts in the computer system by the destination computational host.

20. The method of claim 17, wherein the requesting step includes piggybacking the request for additional tokens in a next and subsequent data packets sent to the destination computational host after the number of available tokens available to the source computational host and provided by the destination computational host falls below a second selectable threshold.

21. The method of claim 17, further including a step of regulating a rate at which data packets can be sent by the source computational host to the destination computational host by regulating at least one of the selected number of tokens and a rate at which the selected number of tokens are provided to the source computational host.

22. A method of controlling a number of messages that a first node of a computer system is allowed to send to a second node of the computer system, comprising the steps of:

sending, from the first to the second node, a first token granting message that enables the second node to send numbered messages to the first node up to a first source sequence number, wherein the first source sequence number represents x more tokens than a source sequence number y of tokens currently in possession by the second node, each token enabling the second node to send one message to the first node, which first token granting message is not received by the second node;

enabling the second node to send to the first node numbered messages up to the source sequence number y;

sending, by the first node to the second node, a second token granting message that enables the second node to send numbered messages to the first node up to a second source sequence number, wherein the second source sequence number represents x′

more tokens than a source sequence number y′

of tokens, wherein y′

=x +y, and

sending, by the second node to the first node, a selected number of messages numbered up to a source sequence number equal to x′

+y′

, such that the second node is granted a number of tokens that is equal to the number of tokens it would have received had the second node received the first token granting message.

23. The method of claim 22, wherein each message includes a data packet.

24. The method of claim 22, wherein the first node includes a buffer having a plurality of buffer spaces and wherein each token represents an available buffer space in the buffer of the first node.