Fair buffer credit distribution flow control

• US 6,337,865 B1
• Filed: 09/23/1998
• Issued: 01/08/2002
• Est. Priority Date: 09/23/1998
• Status: Expired due to Term

• Current Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Original Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Inventors: Seto, Pak-Lung, Rege, Satish
• Primary Examiner(s): TON, DANG T
• Application Number:
  US09/158,761
• Time in Patent Office: 1,203 Days
• Field of Search: 370/400, 370/450, 370/389, 370/395, 370/252, 370/254, 370/449, 370/451, 370/453, 370/456, 370/454, 370/459, 370/460, 370/461, 370/462, 370/503, 370/447, 370/463, 370/403, 370/404-409
• US Class Current: 370/450
• CPC Class Codes: H04L 12/417 with deterministic access, e.g. token passing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/39 Credit based

Abstract

A data transfer management method is provided for transferring data between nodes of a multi-node communication system. The method provides target nodes with fair opportunity to transfer data to originator nodes in the communication system. The originator node initiates data transfer by establishing a connection with one or more target nodes. The originator node signals target nodes to transfer data by generating and transmitting credit tokens over the network. Before a target node can transfer data to the originator node, it must receive and absorb at least one credit token from the originator. All credit tokens transmitted by the originator node and not absorbed by target nodes return back to the originator node. Each target node is provided with buffer credit tokens up to its quota in a rotating manner.

Claims

1. In a communication system comprising a plurality of data processing nodes including at least one originator node and a plurality of target nodes, each data processing node including means for controlling data transmission and/or reception from other data processing nodes over a communication network, a method for providing the target nodes with fair opportunity to transfer data to the originator node, the method comprising the steps of:

For the originator node;

(a) maintaining at least one originator state, the originator state including a first state and a second state;

(b) when the originator node desires to receive at least one data packet,

(1) generating a credit token of;

(i) a first type if the originator state is in the first state, or (ii) a second type if the originator state is in the second state; and

(2) transmitting the credit token over the communication network to signal one or more target nodes to transfer data to the originator node; and

(c) toggling the originator state from one state to another if an originator toggle condition is satisfied; and

For each target node;

(d) maintaining;

(1) a count of credit tokens absorbed by the target node over the network from the originator node, and (2) a quota of the number of credit tokens the target node may absorb from the originator node;

(e) maintaining at least one target state, the target state including;

(1) a first state indicating that the target node can only absorb credit tokens of the first type from the originator node and (2) a second state indicating that the target node can only absorb credit tokens of the second type from the originator node;

(f) receiving a credit token from the originator node over the network;

(g) absorbing the received credit token if;

(1) the credit token is of a type corresponding to the target state, and (2) said count is less than said quota for the target node;

(h) incrementing said count by one if the credit token is absorbed; and

(i) toggling the target state from one state to another if a target toggle condition is satisfied.

2. The method of claim 1, wherein for at least one target node the step of absorbing a credit token in step (g) is further conditioned on the target node having one or more data packets to transmit to the originator node over the network.

3. The method of claim 1, wherein for at least one target node the target toggle condition in step (i) comprises the count being equal to the quota of the target node.

4. The method of claim 1, further comprising the step of each target node retransmitting a received credit token over the network if the target node cannot absorb the credit token in step (g).

5. The method of claim 1, wherein the communication network comprises a ring interconnect topology.

6. The method of claim 1, wherein the communication network comprises a tree interconnect topology.

7. The method of claim 1, wherein two or more of the target nodes have different quotas for the number of credit tokens each node may absorb from the originator node.

8. The method of claim 1, further comprising the step of:

for at least one target node, if the credit count is greater than zero, transmitting an available data packet to the originator node over the network and decrementing said count by one.

9. The method of claim 1, wherein the originator toggle condition in step (c) comprises receiving a credit token previously generated by the originator node back from the network.

10. The method of claim 1, wherein the originator toggle condition in step (c) comprises transmitting the Nth credit token.

11. The method of claim 1, wherein the target toggle condition in step (i) comprises a credit token being absorbed in step (g).

12. In a communication system comprising a plurality of data processing nodes including at least one originator node and a plurality of target nodes, each data processing node including means for controlling data transmission and/or reception from other data processing nodes over a communication network, a method for providing the target nodes with fair opportunity to transfer data to the originator node, the method comprising the steps of:

For the originator node;

(a) maintaining at least one originator state, the originator state including a first state and a second state;

(b) when the originator node desires to receive at least one data packet,

(1) generating a credit token of;

(i) a first type if the originator state is in the first state, or (ii) a second type if the originator state is in the second state; and

(2) transmitting the credit token over the communication network to signal one or more target nodes to transfer data to the originator node; and

(c) toggling the originator state from one state to another upon receiving a credit token previously generated by the originator node back from the network;

For each target node;

(d) maintaining;

(1) a count of credit tokens absorbed by the target node over the network from the originator node, and (2) a quota of the number of credit tokens the target node may absorb from the originator node;

(e) maintaining at least one target state, the target state including;

(1) a first state indicating that the target node can only absorb credit tokens of the first type from the originator node and (2) a second state indicating that the target node can only absorb credit tokens of the second type from the originator node;

(f) receiving a credit token from the originator node over the network;

(g) absorbing the received credit token if;

(1) the credit token is of a type corresponding to the target state, and (2) said count is less than said quota for the target node;

(h) incrementing said count by one if the credit token is absorbed;

(i) toggling the target state from one state to another if said count is equal to the quota; and

(j) re-transmitting a received credit token over the network if the target node cannot absorb the credit token in step (g).

13. The method of claim 12, wherein for at least one target node the step of absorbing a credit token in step (g) is further conditioned on the target node having one or more data packets to transmit to the originator node over the network.

14. The method of claim 12, wherein two or more of the target nodes have different quotas for the number of credit tokens each node may absorb from the originator node.

15. The method of claim 12, further comprising the step of:

for at least one target node, if the credit count is greater than zero, transmitting an available data packet to the originator node over the network and decrementing said count by one.

16. In a communication system comprising a plurality of data processing nodes including at least one originator node and a plurality of target nodes, each data processing node including means for controlling data transmission and/or reception from other data processing nodes over a communication network, a method for providing the target nodes with fair opportunity to transfer data to the originator node, the method comprising the steps of:

For the originator node;

(a) maintaining at least one originator state, the originator state including a first state and a second state;

(b) when the originator node desires to receive at least one data packet,

(1) generating a credit token of;

(i) a first type if the originator state is in the first state, or (ii) a second type if the originator state is in the second state; and

(2) transmitting the credit token over the communication network to signal one or more target nodes to transfer data to the originator node; and

(c) toggling the originator state from one state to another upon receiving a credit token previously generated by the originator node back from the network;

For each target node;

(d) maintaining;

(1) a count of credit tokens absorbed by the target node over the network from the originator node, and (2) a quota of the number of credit tokens the target node may absorb from the originator node;

(e) maintaining at least one target state, the target state including;

(1) a first state indicating that the target node can only absorb credit tokens of the first type from the originator node and (2) a second state indicating that the target node can only absorb credit tokens of the second type from the originator node;

(f) receiving a credit token from the originator node over the network;

(g) absorbing the received credit token if;

(1) the credit token is of a type corresponding to the target state, and (2) said count is less than said quota for the target node;

(h) incrementing said count by one if the credit token is absorbed;

(i) toggling the target state from one state to another if a credit token is absorbed in step (g); and

(j) re-transmitting a received credit token over the network if the target node cannot absorb the credit token in step (g).

17. The method of claim 16, wherein for at least one target node the step of absorbing a credit token in step (g) is further conditioned on the target node having one or more data packets to transmit to the originator node over the network.

18. The method of claim 16, wherein two or more of the target nodes have different quotas for the number of credit tokens each node may absorb from the originator node.

19. The method of claim 16, further comprising the step of:

for at least one target node, if the credit count is greater than zero, transmitting an available data packet to the originator node over the network and decrementing said count by one.

20. A multi-node communication system for providing data transfer among a plurality of data processing nodes over a communication network, the system comprising:

(a) at least one originator node comprising a logic circuit configured by program instructions to perform the steps of;

(1) maintaining at least one originator state, the originator state including a first state and a second state;

(2) when the originator node desires to receive at least one data packet,

(i) generating a credit token of;

(1) a first type if the originator state is in the first state, or (2) a second type if the originator state is in the second state; and

(ii) transmitting the credit token over the communication network to signal one or more target nodes to transfer data to the originator node; and

(3) toggling the originator state from one state to another if an originator toggle condition is satisfied; and

(b) at least one target node comprising a logic circuit configured by program instructions to perform the steps of;

(1) maintaining;

(i) a count of credit tokens absorbed by the target node over the network from the originator node, and (ii) a quota of the number of credit tokens the target node may absorb from the originator node;

(2) maintaining at least one target state, the target state including;

(i) a first state indicating that the target node can only absorb credit tokens of the first type from the originator node and (ii) a second state indicating that the target node can only absorb credit tokens of the second type from the originator node;

(3) receiving a credit token from the originator node over the network;

(4) absorbing the received credit token if;

(i) the credit token is of a type corresponding to the target state, and (ii) said count is less than said quota for the target node;

(5) incrementing said count by one if the credit token is absorbed; and

(6) toggling the target state from one state to another if a target toggle condition is satisfied.

21. The system of claim 20, wherein:

(1) the originator node further comprises means for controlling data transmission and/or reception from other nodes over the communication network, (2) the target node further comprises means for controlling data transmission and/or reception from other nodes over the communication network.

22. The system of claim 20, further comprising a plurality of target nodes, wherein at least one target node includes program instructions for absorbing a credit token further conditioned on the target node having one or more data packets to transmit to the originator node.

23. The system of claim 20, wherein the target toggle condition comprises the count being equal to the quota of the target node.

24. The system of claim 20, wherein the target node further includes program instructions for re-transmitting a received credit token over the network if the target node cannot absorb the credit token.

25. The system of claim 20, further comprising a plurality of target nodes, wherein two or more of the target nodes have different quotas for the number of credit tokens each node may absorb from the originator node.

26. The system of claim 20, wherein the target node further comprises program instructions wherein if the credit count is greater than zero, the target node transmits an available data packet to the originator node over the network and decrements said count by one.

27. The system of claim 20, wherein the originator toggle condition comprises receiving a credit token previously generated by the originator node back from the network.

28. The system of claim 20, wherein the originator toggle condition comprises transmitting the Nth credit token.

29. The system of claim 20, wherein the target toggle condition comprises a credit token being absorbed by target node.

30. A multi-node communication system for providing data transfer among a plurality of data processing nodes over a communication network, the system comprising:

(a) at least one originator node comprising a logic circuit configured by program instructions to perform the steps of;

(1) maintaining at least one originator state, the originator state including a first state and a second state;

(2) when the originator node desires to receive at least one data packet,

(i) generating a credit token of;

(1) a first type if the originator state is in the first state, or (2) a second type if the originator state is in the second state; and

(ii) transmitting the credit token over the communication network to signal one or more target nodes to transfer data to the originator node; and

(3) toggling the originator state from one state to another upon receiving a credit token previously generated by the originator node back from the network; and

(b) at least one target node comprising a logic circuit configured by program instructions to perform the steps of;

(1) maintaining;

(i) a count of credit tokens absorbed by the target node over the network from the originator node, and (ii) a quota of the number of credit tokens the target node may absorb from the originator node;

(2) maintaining at least one target state, the target state including;

(i) a first state indicating that the target node can only absorb credit tokens of the first type from the originator node and (ii) a second state indicating that the target node can only absorb credit tokens of the second type from the originator node;

(3) receiving a credit token from the originator node over the network;

(4) absorbing the received credit token if;

(i) the credit token is of a type corresponding to the target state, and (ii) said count is less than said quota for the target node;

(5) incrementing said count by one if the credit token is absorbed;

(6) toggling the target state from one state to another if said count is equal to the quota; and

(7) re-transmitting a received credit token over the network if the target node cannot absorb the credit token.

31. The system of claim 30, wherein at least one target node comprises program instructions for absorbing a credit token further conditioned on the target node having one or more data packets to transmit to the originator node.

32. The system of claim 30, further comprising a plurality of target nodes, wherein two or more of the target nodes have different quotas for the number of credit tokens each target node may absorb from the originator node.

33. A multi-node communication system for providing data transfer among a plurality of data processing nodes over a communication network, the system comprising:

(a) at least one originator node comprising a logic circuit configured by program instructions to perform the steps of;

(1) maintaining at least one originator state, the originator state including a first state and a second state;

(2) when the originator node desires to receive at least one data packet,

(i) generating a credit token of;

(1) a first type if the originator state is in the first state, or (2) a second type if the originator state is in the second state; and

(ii) transmitting the credit token over the communication network to signal one or more target nodes to transfer data to the originator node; and

(3) toggling the originator state from one state to another upon receiving a credit token previously generated by the originator node back from the network; and

(b) at least one target node comprising a logic circuit configured by program instructions to perform the steps of;

(1) maintaining;

(i) a count of credit tokens absorbed by the target node over the network from the originator node, and (ii) a quota of the number of credit tokens the target node may absorb from the originator node;

(2) maintaining at least one target state, the target state including;

(i) a first state indicating that the target node can only absorb credit tokens of the first type from the originator node and (ii) a second state indicating that the target node can only absorb credit tokens of the second type from the originator node;

(3) receiving a credit token from the originator node over the network;

(4) absorbing the received credit token if;

(i) the credit token is of a type corresponding to the target state, and (ii) said count is less than said quota for the target node;

(5) incrementing said count by one if the credit token is absorbed;

(6) toggling the target state from one state to another if the received credit token is absorbed by the target node; and

(7) re-transmitting a received credit token over the network if the target node cannot absorb the received credit token.

34. The system of claim 33, wherein at least one target node comprises program instructions for absorbing a credit token further conditioned on the target node having one or more data packets to transmit to the originator node over the network.

35. The system of claim 33, further comprising a plurality of target nodes, wherein two or more of the target nodes have different quotas for the number of credit tokens each target node may absorb from the originator node.

36. The system of claim 33, wherein the target node further comprises program instructions for transmitting an available data packet to the originator node over the network if the credit count is greater than zero, and decrementing said count by one.