System and method for regulating message flow in a digital data network

• US 6,570,850 B1
• Filed: 04/23/1998
• Issued: 05/27/2003
• Est. Priority Date: 04/23/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Giganet, Inc. (Broadcom, Inc.)
• Inventors: Roman, Harold E., Prohaska, Richard F., Williams, James B., Gutierrez, Maria C., Clayton, Shawn A., Godiwala, Nitin D., Follett, David R.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Duong, Frank
• Application Number:
  US09/065,118
• Time in Patent Office: 1,860 Days
• Field of Search: 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/395, 370/463, 370/400, 709/232, 709/233, 709/235, 710/29
• US Class Current: 370/231
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5682 Threshold; Watermark
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/16 in connection oriented networks, e.g. frame relay
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A system includes a plurality of computers interconnected by a network including one or more switching nodes. The computers transfer messages over virtual circuits established thereamong. A computer, as a source computer for one or more virtual circuit(s), schedules transmission of messages on a round-robin basis as among the virtual circuits for which it is source computer. Each switching node which forms part of a path for respective virtual circuits also forwards messages for virtual circuits in a round-robin manner, and, a computer, as a destination computer for one or more virtual circuit(s), schedules processing of received messages in a round-robin manner. Round-robin transmission, forwarding and processing at the destination provides a degree of fairness in message transmission as among the virtual circuits established over the network. In addition, messages are transmitted in one or more cells, with the round-robin transmission being on a cell basis, so as to reduce delays which may occur for short messages if a long messages were transmitted in full for one virtual circuit before beginning transmission of a short message for another virtual circuit. For each virtual circuit, the destination computer and each switching node along the path for the virtual circuit can generate a virtual circuit flow control message for transmission to the source computer to temporarily limit transmission over the virtual circuit if the amount of resources being taken up by messages for the virtual circuit exceeds predetermined thresholds, further providing fairness as among the virtual circuits. In addition, each switching node or computer can generate link flow control messages for transmission to neighboring devices in the network to temporarily limit transmission thereto if the amount of resources taken up by all virtual circuits exceeds predetermined thresholds, so as to reduce the likelihood of message loss.

Claims

1. A system comprising at least two devices interconnected by a network including at least one communication link, each device including a network interface for transferring messages over the network, at least one of the devices as a source device, transmitting messages over at least one virtual circuit established over the network, and at least one other of the devices, as a destination device, receiving the messages over the at least one virtual circuit,

A the network interface of the destination device including a receive section including a buffer configured to buffer messages received over the at least one virtual circuit, and a destination flow control circuit being configured to (i) generate a set virtual circuit flow control message associated with the virtual circuit for transfer over the communication link to the source device when a portion of the buffer occupied by messages received over the at least one virtual circuit exceeds a selected virtual circuit flow control threshold level, and (ii) generate a set link flow control message for transmission over the communication link when the portion of the buffer occupied by messages exceeds a selected link flow control threshold level;

and

B the network interface of the source device including a transmit section configured to transmit messages over the at least one virtual circuit, and a source flow control circuit configured to (i) in response to receipt by the source device of the set virtual circuit flow control message associated with the at least one virtual circuit, disable the transmit section from transmitting messages over the at least one virtual circuit, and (ii) in response to receipt by the source device of the set link flow control message over the communication link connected thereto, disable the transmit section from transmitting messages over the communication link.

2. A system as defined in claim 1 in which the network includes a switching node which is configured to form part of a path for the at least one virtual circuit, the switching node being connected to receive messages transmitted by the source device over the at least one virtual circuit over one communication link connected to said switching node, buffer the received messages in an internal buffer, and transmit the buffered messages theat were received over the at least one virtual circuit over another communication link connected to said switching node thereby to forward messages for the at least one virtual circuit downstream over the at least one virtual circuit, the switching node further being configured to, if the occupancy of the switching node'"'"'s buffer by messages from the at least one virtual circuit exceeds a selected virtual circuit threshold level, generate and transmit a virtual circuit flow control message over the one communication link, thereby to forward the virtual circuit flow control message upstream over the virtual circuit to disable the source device for that virtual circuit from transmitting messages thereover.

3. A system as defined in claim 2 in which the switching node is further configured to, if the occupancy of the its buffer exceeds a selected switching node link threshold level, generate and transmit link flow control messages over a plurality of the communication links connected thereto over which it receives messages.

4. A system as defined in claim 1 in which the destination flow control circuit is further configured to generate the set virtual circuit flow control message in further response to the portion of the buffer occupied by messages received over all virtual circuits.

5. A system as defined in claim 4 in which the destination flow control circuit is further configured to generate a clear virtual circuit flow control message associated with the at least one virtual circuit, the source flow control circuit being further configured to enable the transmit section to thereafter transmit messages over the at least one virtual circuit.

6. A system as defined in claim 5 in which the destination flow control circuit is configured to generate the clear virtual circuit flow control circuit for the at least one virtual circuit in relation to the portion of the buffer occupied by messages received over all virtual circuits and the portion of the buffer occupied by messages received over the at least one virtual circuit.

7. A system as defined in claim 1 in which the destination flow control circuit is further configured to generate a clear link flow control message for transmission over the communication link, after it has generated a set link flow control message, when the portion of the buffer occupied by messages falls below the selected link flow control threshold level by a predetermined amount.

8. A network interface for use in a destination device configured to receive messages over a communication link, each message being associated with a virtual circuit, the network interface comprising:

A. a buffer configured to buffer messages received over virtual circuit; and

B. a destination flow control circuit being configured to (i) generate a set virtual circuit flow control message associated with the virtual circuit for transfer over the communication link to the source device when a portion of the buffer occupied by messages received over the virtual circuit exceeds a selected virtual circuit flow control threshold level, and (ii) generate a set link flow control message for transmission over the communication link when the portion of the buffer occupied by messages exceeds a selected link flow control threshold level.

9. A network interface as defined in claim 8 in which the destination flow control circuit is further configured to generate the set virtual circuit flow control message in further response to the portion of the buffer occupied by messages received over all virtual circuits.

10. A network interface as defined in claim 9 in which the destination flow control circuit is further configured to generate a clear virtual circuit flow control message associated with the at least one virtual circuit, the source flow control circuit being further configured to enable the transmit section to thereafter transmit messages over the at least one virtual circuit.

11. A network interface as defined in claim 10 in which the destination flow control circuit is configured to generate the clear virtual circuit flow control circuit for the at least one virtual circuit in relation to the portion of the buffer occupied by messages received over all virtual circuits and the portion of the buffer occupied by messages received over the at least one virtual circuit.

12. A network interface as defined in claim 8 in which the destination flow control circuit is further configured to generate a clear link flow control message for transmission over the communication link, after it has generated a set link flow control message, when the portion of the buffer occupied by messages falls below the selected link flow control threshold level by a predetermined amount.

13. A network interface for use in a source device configured to transmit messages over a communication link, each message being associated with a virtual circuit, the network interface comprising:

A. a transmit section configured to transmit messages over the virtual circuit; and

B. a source flow control circuit configured to (i) in response to receipt by the source device of a set virtual circuit flow control message associated with the virtual circuit, disable the transmit section from transmitting messages over the virtual circuit, and (ii) in response to receipt by the source device of a set link flow control message over the communication link connected thereto, disable the transmit section from transmitting messages over the communication link.

14. A switching node for use in connection with a network, the switching node forming part of a path for a virtual circuit between a source device and a destination device, the switching node comprising:

A. a message receiver configured to receive messages transmitted by the source device over the virtual circuit for which the switching node forms part of the path over one communication link connected thereto,

B. an internal buffer configured to buffer received messages received by the message receiver;

C. a message transmitter configured to transmit the buffered messages over the virtual circuit over another communication link connected thereto, thereby to forward messages for the virtual circuit downstream over the virtual circuit; and

D. a virtual circuit flow control message generator configured to, if the occupancy of the switching node'"'"'s buffer by messages from a particular virtual circuit exceeds a selected virtual circuit threshold level, generate and enabled to be transmitted a virtual circuit flow control message over the one communication link, thereby to forward the virtual circuit flow control message upstream over the virtual circuit to disable the source device for that virtual circuit from transmitting messages thereover.

15. A switching node as defined in claim 14 further including a link flow control message generator configured to, if the occupancy of the buffer exceeds a selected switching node link threshold level, generate and enable to be transmitted link flow control messages over a plurality of the communication links connected thereto over which it receives messages.

16. A method of operating a system comprising at least two devices interconnected by a network including at least one communication link, each device including a network interface for transferring messages over the network, at least one of the devices as a source device, transmitting messages over at least one virtual circuit established over the network, and at least one other of the devices, as a destination device, receiving the messages over the at least one virtual circuit, the method comprising the steps of

A. in connection with the network interface of the destination device

(i) buffering messages received over the at least one virtual circuit in a buffer

(ii) generating a set virtual circuit flow control message associated with the virtual circuit for transfer over the communication link to the source device when a portion of the buffer occupied by messages received over the at least one virtual circuit exceeds a selected virtual circuit flow control threshold level, and

(ii) generating a set link flow control message for transmission over the communication link when the portion of the buffer occupied by messages exceeds a selected link flow control threshold level;

and

B. in connection with the network interface of the source device

(i) normally transmitting messages over the at least one virtual circuit,

(ii) in response to receipt by the source device of the set virtual circuit flow control message associated with the at least one virtual circuit, disabling transmission of messages over the at least one virtual circuit, and

(iii) in response to receipt by the source device of the set link flow control message over the communication link connected thereto, disable transmission of messages over the communication link.

17. A method as defined in claim 16, the network further including a switching node which forms part of a path for the at least one virtual circuit, the method including the steps of, in connection with the switching node,

A. receiving messages transmitted by the source device over the at least one virtual circuit over one communication link connected thereto,

B. buffering received messages received by the message receiver in an internal buffer;

C. transmitting the buffered messages received over the at least one virtual circuit over another communication link connected thereto, thereby to forward messages for the at least one virtual circuit downstream over the at least one virtual circuit; and

D. if the occupancy of the switching node'"'"'s buffer by messages received over the at least one virtual circuit exceeds a selected virtual circuit threshold level, generating and enabling to be transmitted a virtual circuit flow control message over the one communication link, thereby to forward the virtual circuit flow control message upstream over the virtual circuit to disable the source device for that virtual circuit from transmitting messages thereover.

18. A method as defined in claim 17 further including a link flow control message generation step of enabling the switching node to, if the occupancy of the buffer exceeds a selected switching node link threshold level, transmit link flow control messages over a plurality of the communication links connected thereto over which it receives messages.

19. A method as defined in claim 16 in which the set virtual circuit flow control message is further generated in response to the portion of the buffer occupied by messages received over all virtual circuits.

20. A method as defined in claim 19 further including the steps of

A. in connection with the network interface of the destination device, generating a clear virtual circuit flow control message associated with the at least one virtual circuit, and

B. in connection with the network interface of the source device, enabling the transmit section to, after receipt of the clear virtual circuit flow control message transmit messages over the at least one virtual circuit.

21. A method as defined in claim 20 in which the clear virtual circuit flow control message is generated for the virtual circuit in relation to the portion of the buffer occupied by messages received over all virtual circuits and the portion of the buffer occupied by messages received over the at least one virtual circuit.

22. A method as defined in claim 21 in which the destination flow control circuit is further configured to generate a clear link flow control message for transmission over the communication link, after it has generated a set link flow control message, when the portion of the buffer occupied by messages falls below the selected link flow control threshold level by a predetermined amount.

23. A method as defined in claim 19 further including the step of generating a clear virtual circuit flow control message associated with the at least one virtual circuit for transmission to the source device.

24. A method as defined in claim 23 in which the clear virtual circuit flow control circuit is generated for the at least one virtual circuit in relation to the portion of the buffer occupied by messages received over all virtual circuits and the portion of the buffer occupied by messages received over the at least one virtual circuit.

25. A method of operating a network interface for use in a destination device configured to receive messages over a communication link, each message being associated with a virtual circuit, the method including the steps of:

A. buffering messages received over the virtual circuit in a buffer,

B. generating a set virtual circuit flow control message associated with the virtual circuit for transfer over the communication link to a source device when a portion of the buffer occupied by messages received over the virtual circuit exceeds a selected virtual circuit flow control threshold level, and

C. generating a set link flow control message for transmission over the communication link when the portion of the buffer occupied by messages exceeds a selected link flow control threshold level.

26. A method as defined in claim 25 in which the set virtual circuit flow control message is further generated in response to the portion of the buffer occupied by messages received over all of said virtual circuits.

27. A method as defined in claim 26 in which the destination flow control circuit is further configured to generate a clear virtual circuit flow control message associated with the at least one virtual circuit, the source flow control circuit being further configured to enable the transmit section to thereafter transmit messages over the at least one virtual circuit.

28. A method of operating a network interface for use in a source device configured to transmit messages over a communication link, each message being associated with a virtual circuit, the method comprising the steps of:

A. transmitting messages over at least one virtual circuit; and

B. in response to receipt by the source device of a set virtual circuit flow control message associated with the at least one virtual circuit, disabling the transmission of messages over the at least one virtual circuit, and

C. in response to receipt by the source device of a set link flow control message over the communication link connected thereto, disabling the transmission of messages over the communication link.

29. A method of operation a switching node for use in connection with a network, the switching node forming part of a path for a virtual circuit between a source device and a destination device, the method comprising the steps of:

A. receiving messages transmitted by the source device over the virtual circuit for which the switching node forms part of the path over one communication link connected thereto,

B. buffering received messages in an internal buffer;

C. transmitting the buffered messages over the virtual circuit over another communication link connected thereto, thereby to forward messages for the virtual circuit downstream over the virtual circuit; and

D. if occupancy of the switching node'"'"'s buffer by messages from a particular virtual circuit exceeds a selected virtual circuit threshold level, performing a virtual circuit flow control message generation step in which a virtual circuit flow control message is generated and enabled to be transmitted over the one communication link, thereby to forward the virtual circuit flow control message upstream over the virtual circuit to disable the source device for that virtual circuit from transmitting messages thereover.

30. A method as defined in claim 29 further including a link flow control message generation step in which, if the occupancy of the its buffer exceeds a selected switching node link threshold level, the switching node is enabled to generate link flow control messages and transmit them over a plurality of the communication links connected thereto over which it receives messages.