Arbiter for an input buffered communication switch
View Patent ↗An arbiter for a switch maintains a pair of counters for each flow of traffic at each input port: one counter (also called “first counter”) to indicate an ideal transfer of traffic, and another counter (also called “second counter”) to indicate the actual transfer of traffic. Both counters are incremented when traffic is received by the input port, and the second counter is decremented when a unit of traffic (such as a cell or packet) is about to be transmitted whereas the first counter is decremented in a fractional manner (relative to the unit of traffic) in each period of arbitration, based on available bandwidth. The arbiter selects one of the output ports (also called “winning output port”) of the switch, based at least partially on values of the two counters for each flow from the input port to one of the output ports, and generates a signal to approve transfer of traffic from the input port to the winning output port. In several embodiments, the above-described flow can be for either high priority traffic or for low priority traffic, and any bandwidth leftover from transferring high priority traffic is used in transferring low priority traffic. Specifically, the arbiter maintains additional counters for each port indicative of total bandwidth being used, and the additional counters are used to allocate leftover bandwidth in an iterative manner, until a flow from an input port to an output port is saturated, at which time the saturated flow is removed from iteration.
1. A method of transferring traffic through a switch comprising a plurality of input ports and a plurality of output ports, the method comprising:
incrementing a pair of counters for a flow of traffic from an input port destined to an output port, in response to receipt of traffic at the input port;
decrementing a counter (hereinafter “first counter”) in the pair of counters for each flow if the first counter is nonzero;
selecting one of the flows at the input port (hereinafter “winning flow”) based at least partially on values of counters in the pair for each flow from the input port to one of the output ports; and
generating a signal to transfer traffic in the winning flow at the input port.
2. The method of claim 1 wherein:
the decrementing of the first counter is based at least partially on a predetermined bandwidth requirement (hereinafter “weight”) of the flow.
3. The method of claim 1 further comprising:
decrementing the second counter corresponding to the winning output port of the input port;
periodically repeating said act of decrementing first counter unless the first counter is zero;
if a predetermined criterion is satisfied by counters in a pair for at least one flow from the input port during a period, then repeating said act of selecting, repeating said act of generating unless the second counter is zero, and repeating said act of decrementing the second counter.
4. The method of claim 3 wherein:
the predetermined criterion for the pair of counters comprises the first counter being less than or equal to the second counter.
5. The method of claim 3 wherein:
the predetermined criterion for the pair of counters comprises the first counter being less than the second counter by an amount based on an identity of the input port.
6. The method of claim 1 wherein:
said flow is one of a plurality of flows between said input port and said output port;
each flow is associated with at least two counters; and
said acts of (incrementing, decrementing first counter, selecting and generating) are performed at least once for each flow.
7. The method of claim 6 wherein:
said output port is one of a plurality of output ports coupled to said input port; and
the winning output port of the input port is selected only if a difference between counters for one of the flows to the winning output port is the maximum among differences between counters for all flows of all output ports.
8. The method of claim 6 wherein:
said output port is one of a plurality of output ports coupled to said input port; and
the winning output port of the input port is selected only if a difference between counters for one of the flows to the winning output port is the maximum among differences between counters for flows of all output ports that satisfy a predetermined criterion.
9. The method of claim 6 wherein:
the plurality of flows comprises at least a high priority flow and a low priority flow; and
the method further comprising maintaining a counter (hereinafter “used input port bandwidth”) for the input port indicative of total decrements in a period in the first counter of each flow between the input port and all output ports including said output port; and
the method further comprising using a difference (hereinafter “leftover input port bandwidth”) between the used input port bandwidth and a predetermined input port bandwidth for transferring traffic in the low priority flows from the input port.
10. The method of claim 9 wherein the plurality of flows consists of only the high priority flow and the low priority flow, and the method further comprises:
generating a signal (hereinafter “readiness signal”) indicative of readiness to transfer traffic from the input port to the output port if the first counter of the low priority flow is non-zero and if the leftover input port bandwidth is non-zero.
11. The method of claim 10 further comprising:
maintaining a counter (hereinafter “used output port bandwidth”) for each output port indicative of a sum of decrements in the first counter of each flow between said output port and all input ports including said input port; and
using a difference (hereinafter “leftover output port bandwidth”) between the used output port bandwidth and a predetermined output port bandwidth for transferring traffic in the low priority flows to the output port.
12. The method of claim 11 further comprising:
indicating an amount (hereinafter “requested amount”) of traffic from a low priority flow destined to the output port from each input port, based at least partially on the leftover output port bandwidth.
13. The method of claim 12 wherein:
the requested amount from an output port to the input port is obtained by proportional allocation of the leftover output port bandwidth among the low priority flows, based on the weights of the low priority flows.
14. The method of claim 13 further comprising:
indicating an amount (hereinafter “served amount”) of traffic from a low priority flow from the input port destined to the output port, based at least partially on (a) the leftover input port bandwidth, (b) the requested amount, and (c) the weight of the low priority flow from the input port.
15. The method of claim 14 further comprising:
repeating the acts of (a) generating the readiness signal, (b) indicating the requested amount; and (c) indicating the served amount.
16. The method of claim 1 wherein:
the first counter has a higher resolution than the second counter.
17. An apparatus comprising:
a communication switch comprising a buffer for holding traffic at an input port destined to an output port; and
a computer readable storage medium coupled to the communication switch, wherein the computer readable storage medium comprises a pair of counters for the buffer; and
a state machine to automatically increment the pair of counters in response to receipt of traffic at the input port, wherein the state machine decrements a counter (hereinafter “first counter”) in said pair, based at least partially on a predetermined bandwidth between the input port and the output port.
18. A method of transferring traffic through a switch comprising a plurality of input ports and an output port, the method comprising:
incrementing a pair of counters for a flow of traffic from an input port destined to an output port, in response to receipt of traffic at the input port;
decrementing a counter (hereinafter “first counter”) in the pair of counters for each flow if the first counter is nonzero;
selecting an input port (hereinafter “winning input port”) based at least partially on values of counters in the pair for at least one flow from the input port; and
generating a signal to transfer an amount of traffic from the winning input port, to the output port.