Apparatus and method for virtual output queue feedback

• US 7,180,862 B2
• Filed: 07/18/2002
• Issued: 02/20/2007
• Est. Priority Date: 07/18/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Lebizay, Gerald, Oliver, Neal C., Peebles, Brian E.
• Primary Examiner(s): To; Doris H.
• Assistant Examiner(s): Hyun; Soon D.
• Application Number:
  US10/199,543
• Publication Number:
  US 20040013124A1
• Time in Patent Office: 1,678 Days
• Field of Search: 370/389, 370/395.1, 370/395.21, 370412-418, 370/230, 370/235
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/266 Stopping or restarting the source, e.g. X-on or X-off
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 49/3045 Virtual queuing
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method of providing virtual output queue feedback to a number of boards coupled with a switch. A number of virtual queues in the switch and/or in the boards are monitored and, in response to one of these queues reaching a threshold occupancy, a feedback signal is provided to one of the boards, the signal directing that board to alter its rate of transmission to another one of the boards. Each board includes a number of virtual output queues, which may be allocated per port and which may be further allocated on a quality of service level basis.

Claims

1. A method performed in a switch for controlling congestion, the switch disposed on a board coupled with a backplane, wherein at least a separate source board and a separate destination board are also coupled with the backplane, the method comprising:

determining a queue occupancy of a virtual queue associated with an input port of the switch and with an output port of the switch, the input port communicatively coupled with the source board and the output port communicatively coupled with the destination board, the source board providing data to the switch for transmission to the destination board; and

sending a message from the switch to the source board if the queue occupancy of the virtual queue reaches a threshold occupancy, the message to direct the source board to alter a transmission rate to the destination board, wherein the threshold occupancy comprises a specified quantity of data, a specified number of packets, or a specified number of packet addresses;

wherein transmission rates from the source board to a number of other boards coupled with the backplane are unaltered by the message.

2. The method of claim 1, wherein the message directs the source board to lower the transmission rate to the destination board.

3. The method of claim 1, wherein the message directs the source board to interrupt transmission to the destination board.

4. A method performed in a switch for controlling congestion, the switch disposed on a board coupled with a backplane, wherein separate first, second, and third boards are also coupled with the backplane, the method comprising:

monitoring a number of virtual queues, each of the virtual queues corresponding to an input port of the switch and associated with an output port of the switch; and

sending a message from the switch to the first board if one of the virtual queues reaches a threshold occupancy, the first board communicatively coupled with the input port corresponding to the one virtual queue, the first board providing data to the switch for transmission to the second board and the third board, wherein the message directs the first board to alter a rate of transmission to the second board, the second board communicatively coupled with the output port associated with the one virtual queue, wherein the threshold occupancy comprises a specified quantity of data, a specified number of packets, or a specified number of packet addresses;

wherein a transmission rate from the first board to the third board is unaltered by the message, the third board communicatively coupled with an output port associated with another of the virtual queues.

5. The method of claim 4, wherein the message directs the first board to lower the rate of transmission to the second board.

6. The method of claim 4, wherein the message directs the first board to stop transmission to the second board.

7. A method comprising:

determining a number of queue occupancy values for a virtual queue associated with an input port of a switch and with an output port of the switch, the input port coupled with a source board and the output port coupled with a destination board;

determining a queue occupancy distribution based upon the number of queue occupancy values; and

providing a message to the source board if the queue occupancy distribution indicates the virtual queue has reached a threshold occupancy, the message to direct the board to alter a transmission rate to the destination board;

wherein transmission rates from the source board to a number of other output ports of the switch are unaltered by the message.

8. The method of claim 7, wherein the number of queue occupancy values are determined by periodically measuring the queue occupancy of the virtual queue.

9. The method of claim 7, wherein the message directs the source board to lower the transmission rate to the destination board.

10. The method of claim 7, wherein the message directs the source board to stop transmission to the destination board.

11. A method comprising:

determining a number of queue occupancy values for a virtual queue associated with an input port of a switch and with an output port of the switch, the input port coupled with a source board and the output port coupled with a destination board;

determining a queue occupancy distribution based upon the number of queue occupancy values; and

providing a message to the source board if the queue occupancy distribution indicates the virtual queue has reached a specified occupancy for a threshold percentage of time, the message to direct the source board to alter a transmission rate to the destination board;

wherein transmission rates from the source board to a number of other output ports of the switch are unaltered by the message.

12. The method of claim 11, wherein the number of queue occupancy values are determined by periodically measuring the queue occupancy of the virtual queue.

13. The method of claim 11, wherein the message directs the source board to lower the transmission rate to the destination board.

14. The method of claim 11, wherein the message directs the source board to stop transmission to the destination board.

15. A switch comprising:

a board, the board to couple with a backplane, wherein at least a separate source board and a separate destination board are coupled with the backplane;

an input port disposed on the board, the input port to communicatively couple with the source board, the source board providing data to the switch for transmission to the destination board;

a number of output ports disposed on the board, each of the output ports coupled with the input port;

a number of virtual queues disposed on the board and coupled with the input port, one of the virtual queues associated with one of the output ports, the one output port to communicatively couple with the destination board;

a feedback channel, the feedback channel to communicatively couple with the source board; and

feedback logic disposed on the board and coupled with the feedback channel and the number of virtual queues, the feedback logic to transmit a message over the feedback channel to the source board in response to the one virtual queue reaching a threshold occupancy, the message to direct the source board to alter a transmission rate to the destination board, wherein the threshold occupancy comprises a specified quantity of data, a specified number of packets, or a specified number of packet addresses;

wherein a transmission rate from the source board to at least one other board coupled with the backplane is unaltered by the message.

16. The switch of claim 15, wherein the number of virtual queues is one less than the number of output ports.

17. The switch of claim 15, wherein each of the virtual queues is associated with a priority level.

18. The switch of claim 15, wherein the message directs the source board to interrupt transmission to the destination board.

19. The switch of claim 15, wherein the message directs the source board to lower the transmission rate to the destination board.

20. A system comprising:

a backplane;

a number of boards coupled with the backplane, the number of boards including a first board providing data for transmission to a second of the boards; and

a switch coupled with the backplane, the switch including

an input port communicatively coupled with the first board,

a number of output ports, each of the output ports coupled with the input port, one of the output ports communicatively coupled with the second board,

a number of virtual queues coupled with the input port, one of the virtual queues associated with the one output port coupled with the second board,

a feedback channel communicatively coupled with the first board, and

feedback logic coupled with the feedback channel and the number of virtual queues, the feedback logic to transmit a message over the feedback channel to the first board in response to the one virtual queue reaching a threshold occupancy, the message to direct the first board to alter a transmission rate to the second board, wherein the threshold occupancy comprises a specified quantity of data, a specified number of packets, or a specified number of packet addresses,

wherein a transmission rate from the first board to at least one other of the number of boards is unaltered by the message.

21. The system of claim 20, wherein the number of virtual queues equals one less than the number of output ports.

22. The system of claim 20, wherein each of the virtual queues is associated with a priority level.

23. The system of claim 20, wherein the message directs the first board to lower the transmission rate to the second board.

24. The system of claim 20, wherein the message directs the first board to interrupt transmission to the second board.

25. A method comprising:

determining a number of queue occupancy values for a virtual queue associated with an input port of a switch;

determining a queue occupancy distribution based upon the number of queue occupancy values;

receiving a number of congestion warning messages from the switch;

determining a time period based upon the number of congestion warning messages; and

altering a rate of transmission from the virtual queue if the queue occupancy distribution indicates the queue occupancy of the virtual queue has reached a specified occupancy for a threshold percentage of time, the threshold percentage of time corresponding to the time period.

26. The method of claim 25, wherein the switch is operating in accordance with PCI Express.

27. The method of claim 25, wherein the switch is operating in accordance with Infiniband.

28. The method of claim 25, wherein the number of queue occupancy values are determined by periodically measuring the queue occupancy of the virtual queue.

29. An article of manufacture comprising:

a medium having content that, when accessed by a switch, causes the switch to perform a method for controlling congestion, the switch disposed on a board coupled with a backplane, wherein at least a separate source board and a separate destination board are also coupled with the backplane, the method comprising

determining a queue occupancy of a virtual queue associated with an input port of the switch and with an output port of the switch, the input port communicatively coupled with the source board and the output port communicatively coupled with the destination board, the source board providing data to the switch for transmission to the destination board; and

sending a message from the switch to the source board if the queue occupancy of the virtual queue reaches a threshold occupancy, the message to direct the source board to alter a transmission rate to the destination board, wherein the threshold occupancy comprises a specified quantity of data, a specified number of packets, or a specified number of packet addresses;

wherein transmission rates from the source board to a number of other boards coupled with the backplane are unaltered by the message.

30. The article of manufacture of claim 29, wherein the message directs the source board to lower the transmission rate to the destination board.

31. The article of manufacture of claim 29, wherein the message directs the source board to interrupt transmission to the destination board.

32. An apparatus comprising:

an input port, the input port to couple with a source board;

a number of output ports, each of the output ports coupled with the input port;

a number of virtual queues associated with the input port;

a feedback channel, the feedback channel to couple with the source board; and

feedback logic, the feedback logic to

determine a number of queue occupancy values for one of the virtual queues, the one virtual queue associated with one of the output ports, the one output port to couple with a destination board,

determine a queue occupancy distribution based upon the number of queue occupancy values, and

transmit a message over the feedback channel to the source board if the queue occupancy distribution indicates the one virtual queue has reached a threshold occupancy, the message to direct the source board to alter a transmission rate to the destination board,

wherein transmission rates from the source board to the other output ports are unaltered by the message.

33. The apparatus of claim 32, the number of queue occupancy values are determined by periodically measuring the queue occupancy of the one virtual queue.

34. The apparatus of claim 32, wherein the message directs the source board to interrupt transmission to the destination board.

35. The apparatus of claim 32, wherein the message directs the source board to lower the transmission rate to the destination board.

36. An apparatus comprising:

an input port, the input port to couple with a source board;

a number of output ports, each of the output ports coupled with the input port;

a number of virtual queues associated with the input port;

a feedback channel, the feedback channel to couple with the source board; and

feedback logic, the feedback logic to

determine a number of queue occupancy values for one of the virtual queues, the one virtual queue associated with one of the output ports, the one output port to couple with a destination board,

determine a queue occupancy distribution based upon the number of queue occupancy values, and

transmit a message over the feedback channel to the source board if the queue occupancy distribution indicates the one virtual queue has reached a specified occupancy for a threshold percentage of time, the message to direct the source board to alter a transmission rate to the destination board,

wherein transmission rates from the source board to the other output ports are unaltered by the message.

37. The apparatus of claim 36, wherein the number of queue occupancy values are determined by periodically measuring the queue occupancy of the one virtual queue.

38. The apparatus of claim 36, wherein the message directs the source board to interrupt transmission to the destination board.

39. The apparatus of claim 36, wherein the message directs the source board to lower the transmission rate to the destination board.