VIRTUAL CHANNEL STARVATION-FREE ARBITRATION FOR SWITCHES

Abstract

A switching system having input ports and output ports and comprising an input queued switch with virtual channels. Typically only one of these can, at a given time, access a given output port from among the output ports. Typically the input queued switch includes arbiter apparatus which controls the input ports and output ports to ensure that at least one input port, from among the input ports, transmits at most one cell at a time, and/or that at least one output port, from among the output ports, which receives a cell, receives that cell over only 1 virtual channel (VC) from among the virtual channels. The arbiter apparatus may function as a dispatch unit in which typically, at least one output port, from among the output ports, receives at most one cell at a time.

Claims

1. A switching system having plural input ports and plural output ports and comprising: an input queued switch with plural virtual channels, only one of which can, at a given time, access a given output port from among said plural output ports, wherein the input queued switch includes an arbiter apparatus that controls said plural input ports and plural output ports to ensure that at least one input port, from among said plural input ports, transmits at most one cell at a time, and also that at least one output port, from among said plural output ports, which receives a cell, receives that cell over only 1 virtual channel (VC) from among said plural virtual channels, wherein said arbiter apparatus functions as a dispatch unit in which at least one output port, from among said plural output ports, receives at most one cell at a time.

2. A system according to claim 1 wherein the arbiter apparatus comprises: a first set of arbiters which selects, for at least one output port O, at least one input port from among said plural input ports; and at least one virtual channel from among said plural virtual channels characterized in that said at least one input port has at least one queued cell, whose destination is output port O, in each of said at least one virtual channel, and a second set of arbiters, which selects, for each input port I from among said plural input ports, at least one output port O, from among said output ports, characterized in that said first set of arbiters selected input port I for output port O.

3. A system according to claim 2 wherein the first set includes, for each of plural output ports, a subset of arbiters to select, at least once, an input port I from among input ports which is requesting that output port as the input port I's destination and a virtual channel V from among virtual channels which is requesting that output port as virtual channel V's destination, thereby to provide plural subsets of arbiters.

4. A system according to claim 3 wherein at least one subset of arbiters includes an arbiter per virtual channel, thereby to define a DV arbiter per virtual channel, thus providing plural DV arbiters.

5. A system according to claim 4 wherein the at least one subset of arbiters also includes virtual channel select logic to select among said plural DV arbiters.

6. A system according to claim 3 wherein plural input port requests all to a single virtual channel and whose destinations all comprise a single output port, are all connected to a single DV arbiter in a single subset of arbiters, whereas input port requests to different virtual channels, but whose destinations all comprise a single output port, are connected to different DV arbiters in a single subset of arbiters.

7. A system according to claim 4 wherein at least one DV arbiter uses an arbitration scheme to select among input ports, and wherein said arbitration scheme used by said DV arbiter comprises a Round-robin scheme which uses circular priority to grant the requests.

8. A system according to claim 7 wherein the DV arbiter updates said circular priority only after receiving an accept, from the second set of arbiters, through the virtual channel select logic.

9. A system according to claim 5 wherein the virtual channel select logic uses an arbitration scheme to select a DV arbiter to pass a granted input port, from among said plural input ports, to the second set of arbiters, from among plural DV arbiters which each have a granted source.

10. A system according to claim 9 wherein said arbitration scheme used by the virtual channel select logic comprises a round robin arbitration scheme.

11. A system according to claim 5 wherein the DV arbiter selected by the virtual channel select logic generates a WRAP signal when all active input ports in that DV arbiter are granted or before again granting an input port.

12. A system according to claim 5 wherein once the VC select logic has selected a DV arbiter, thereby to define a currently selected DV arbiter, the VC select logic moves to a new DV arbiter only after receiving a WRAP signal from the currently selected DV arbiter.

13. A system according to claim 5 wherein the virtual channel select logic passes an accept to a selected DV arbiter, when and only when the second set of arbiters accepts a grant from the first set of arbiters.

14. A system according to claim 2 wherein at least one arbiter in the second set of arbiters uses a priority scheme in which a request, which has a given priority, receives a grant before other requests, which have priorities lower than the given priority, receive grants.

15. A system according to claim 5 wherein said switch uses credit-based flow control, whereby packets are transmitted to an output port, from among said output ports, only when buffer space is known to exist at the destination of said output port, to avoid packet drop in at least one switch.

16. A system according to claim 15 wherein, to support said credit-based flow control, the switch maintains a counter for every destination per virtual channel, which keeps track of buffer space per destination by decrementing the counter for every packet sent to a given destination and incrementing the counter for every credit returned from said given destination, and wherein credits are returned from a destination D from among said output ports, whenever a destination buffer at destination D is freed up.

17. A system according to claim 16 wherein Virtual Output Queues store incoming packets, and wherein each destination's and virtual channel's credit counter generates a ready indication whenever a given destination and a given virtual channel have enough credit to accommodate a packet, and wherein, when the ready indication is asserted, requests to transmit packets through said switch in all input ports' Virtual Output Queue of said destination and virtual channel are exposed to the dispatch unit, else all requests to transmit packets through said switch are masked, thereby to provide a “credit at dispatch” scheme of credit-based flow control.

18. A switching method comprising: providing an input queued switch with plural virtual channels, only one of which can, at a given time, access a given output port from among plural output ports; and using an arbiter apparatus to control plural input ports and said plural output ports, to ensure that at least one input port, from among said plural input ports, transmits at most one cell at a time, and also that at least one output port, from among said plural output ports, which receives a cell, receives that cell over only one virtual channel (VC) from among said plural virtual channels, thereby to function as a dispatch unit in which at least one output port, from among said plural output ports, receives at most one cell at a time.

19. A system according to claim 1 wherein the system has N inputs, M outputs, and K virtual channels and wherein the arbiter apparatus finds a set of up to min (M,N) cells to transmit over the switch.

20. A system according to claim 14 and wherein said priority scheme comprises a round robin scheme.

21. A system according to claim 14 and wherein said priority scheme comprises a Least Recently Used (LRU) scheme in which at least one request which got a grant less recently, has higher priority relative to requests which got grants more recently.

22. A system according to claim 15 wherein, to support said credit-based flow control, the switch maintains a counter for every destination per virtual channel, which keeps track of buffer space per destination by incrementing the counter for every packet sent to a given destination, and decrementing the counter for every credit returned from said given destination and wherein credits are returned from a destination D from among said output ports, whenever a destination buffer at destination D is freed up.

23. A system according to claim 17 wherein the virtual channel select logic does not pass said given virtual channel's DV arbiter's grants when said ready indication is not high.

24. A system according to claim 17 wherein the DV arbiter does not grant inputs when said ready indication is not high.

25. A system according to claim 16 wherein the counter is incremented each time a packet is sent to said given destination and is decremented each time a credit returns from said given destination.

26. A system according to claim 2 wherein at least one arbiter, corresponding to a source S, in the second set of arbiters, uses a priority scheme to accept at least one grant, from among plural grants to source S.

27. A system according to claim 2 wherein at least one arbiter in the second set of arbiters uses a priority scheme to accept a grant from among grants of DCS which have granted to this source.

28. A system according to claim 1 wherein said arbiter apparatus ensures that each input port, from among said plural input ports, transmits at most one cell at a time, and also that each output port, from among said plural output ports, which receives a cell, receives that cell over only 1 virtual channel (VC) from among said plural virtual channels, and wherein said arbiter apparatus functions as a dispatch unit in which each output port, from among said plural output ports, receives at most one cell at a time.

29. A switching method comprising, in an input queued switch with plural virtual channels, only one of which can, at a given time, access a given output port from among plural output ports: controlling plural input ports and said plural output ports, to ensure that at least one input port, from among said plural input ports, transmits at most one cell at a time, and also that at least one output port, from among said plural output ports, which receives a cell, receives that cell over only one virtual channel (VC) from among said plural virtual channels, whereby at least one output port, from among said plural output ports, receives at most one cell at a time.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0105] FIG. 1 is a simplified block diagram illustration of an input queued switch and associated input ports, output ports and destination buffer, all provided in accordance with certain embodiments. Typically, a given output port is connected to only one destination. This is typically the case for all of the output ports in the switch. Typically, destinations buffer space are not shared among output ports.

[0106] FIG. 2 is a simplified block diagram illustration of an input queued switch as a node interconnected with other nodes in a network, e.g. via physical channels which connect nodes, all provided in accordance with certain embodiments. Each node, e.g. computer/memory/network switches (switching system), typically generates and/or consumes and/or reroutes packets and/or cells and/or other information.

[0107] FIG. 3 is a simplified block diagram illustration of an input queued switch with multiple virtual channels and credit-based flow control (“credit at dispatch”) provided in accordance with certain embodiments, which may be used standalone or in any context shown or described herein.

[0108] FIG. 4 is a simplified block diagram illustration of a Credit at Dispatch scheme for credit-based flow control, as provided in accordance with certain embodiments, which may be used standalone or in any context shown or described herein (e.g. to implement the “credit at dispatch” of the switch in FIG. 3).

[0109] FIG. 5 is a simplified block diagram illustration of a Dispatch Unit (2-D arbiter) for N×M switch with K virtual channels (VC's), provided in accordance with certain embodiments, which may be used standalone or in any context shown or described herein.

[0110] FIG. 6 is a simplified block diagram illustration of a Destination Choose Source (DCS) arbiter, aka DCS arbiter, provided in accordance with certain embodiments, which may be used standalone or in any context shown or described herein.

[0111] FIG. 7 is a simplified block diagram illustration of a Source Choose Destination (SCD) arbiter, aka SCD arbiter provided in accordance with certain embodiments, which may be used standalone or in any context shown or described herein.

[0112] FIG. 8 is a simplified block diagram illustration of a pre-creditor scheme for credit-based flow control provided in certain embodiments.

[0113] FIG. 9 is a simplified block diagram illustration of a 2×3 switch with two virtual channels, all provided in accordance with certain embodiments.

[0114] FIG. 10 is a simplified block diagram illustration of a existing 2D arb for 2×3 switch with 2 virtual channels (VCs), all provided in accordance with certain embodiments.

[0115] FIG. 11 is a simplified block diagram illustration of an example of Starvation for RR DCS for D.sub.0 destination with a “credit at dispatch” scheme, all provided in accordance with certain embodiments.

[0116] FIG. 12 is a simplified block diagram illustration of a Rolling RR DCS for Do destination, all provided in accordance with certain embodiments.

[0117] FIG. 13 is a simplified block diagram illustration of a Starvation free Rolling RR DCS for D.sub.0 destination with a “credit at dispatch” scheme, all provided in accordance with certain embodiments.

[0118] FIG. 14 is a simplified block diagram illustration of an Example of Bandwidth unfairness with simple LRU virtual channel select logic, all provided in accordance with certain embodiments.

[0119] FIG. 15 is a simplified block diagram illustration of an Example of Bandwidth fairness with Wrap based LRU virtual channel select logic, all provided in accordance with certain embodiments.

[0120] FIG. 16 is a simplified block diagram illustration of Rolling RR-LRU 2D arb for 2×3 switch with 2 virtual channels (VCs), all provided in accordance with certain embodiments.

[0121] FIGS. 17a-17b, taken together, form a simplified block diagram illustration of RR-LRU 2D arbiter with pre-creditor crediting scheme for 2×3 switch with 2 virtual channels (VCs), which has area/power penalty, all provided in accordance with certain embodiments.

[0122] FIGS. 18a-18b, taken together, form a simplified block diagram illustration of an RR-LRU 2D arbiter provided in accordance with certain embodiments which uses a “credit at dispatch” crediting scheme for a 2×3 switch with 2 virtual channels (VCs) which has a virtual channel (VC) starvation issue.

[0123] FIGS. 19a-19b, taken together, form a simplified block diagram illustration of starvation free Rolling RR-LRU 2D arbiter with a “credit at dispatch” crediting scheme for a 2×3 switch with 2 virtual channels (VCs), all provided in accordance with certain embodiments.

[0124] FIG. 20 is a simplified block diagram illustration of an ARB efficiency RR+LRU vs LRU+LRU 2D ARB, all provided in accordance with certain embodiments.

[0125] FIG. 21 is a table comparing total credit between pre creditor scheme vs. “credit at dispatch” schemes, which is useful in understanding certain embodiments.

DETAILED DESCRIPTION OF CERTAIN EMBODIMENTS

[0126] A switching system is now described, e.g. as shown in FIG. 9. The switching system may have plural input ports and plural output ports and may include an input queued (IQ) switch with plural virtual channels, only one of which can, at a given time, access a given output port from among the plural output ports; this is typically the case for any given output port from among the plural output ports.

[0127] Typically, the input queued switch includes arbiter apparatus which controls the input ports and output ports to ensure that each input port transmits at most one cell at a time, and also that each output port which receives a cell, receives that cell over only one of the switch's virtual channels (VCs). The arbiter apparatus aka arbiter typically functions as a dispatch unit in which each output port, from among the plural output ports, receives at most one cell at a time.

[0128] Re FIG. 9's fabric (matrix) unit, typically, each input is uniquely connected to each output through a dedicated crosspoint or junction. The resulting set of crosspoints or junctions, for all inputs and outputs, may be referred to using the term Fabric or “Switch fabric” or Matrix. Packets may be transferred between a given input and a given output by selecting the cross point which uniquely connects that input to that output. This crosspoint selection is typically carried out by the Arbiter.

[0129] The Credit flow control block of FIG. 9, may be implemented in hardware and may run a “credit at dispatch” or “pre creditor” scheme, or any other appropriate scheme having logic for assigning credits to virtual channels and for incrementing or decrementing those credits under certain conditions. The Credit flow control block's exercise of flow control typically comprises allowing a packet for arbitration only if the packet's destination is guaranteed to have space or credit to accommodate the packet.

[0130] The Input Queued (IQ) switch architecture, e.g. as shown in FIG. 1 is commonly used in high-speed switches. FIG. 1 is a simplified block diagram illustration of an input queued switch along with input ports, output ports and destination buffer.

[0131] It is appreciated that the input queued switch e.g. of FIG. 1 is typically itself a node—e.g. as shown in FIG. 2.

[0132] In Input Queued architecture, buffers are deployed at the input of the switches. When a single queue is used at the input, IQ switches suffer from a problem, termed Head of Line (HOL) blocking, in which a request to a free destination is blocked by request to a destination that is busy. HOL blocking is eliminated by using Virtual Output Queuing (VOQ), where requests to each destination are stored in a separate queue. To improve network throughput and avoid deadlock, virtual channels (VCs) may be introduced. A virtual channel transports the independent packet or cell between nodes by (optionally increasing and then) dividing the resource (buffer storage) associated with each physical channel into several groups, where dividing may be done by the designer of the switch. Each virtual channel (VC) has its own set of VOQs for each output at each input. Virtual channels (VCs) may compete against one another to get access to physical channels.

[0133] Typically, a switching system is responsible for distributing resources. When distributing, typically, virtual channel resources must not be oversubscribed and/or conflict over a physical channel must be avoided.

[0134] Each input can receive up to one packet at a time which contain tag with destination details and virtual channel (VC) details. Based on virtual channel (VC) and destination detail, an arriving packet is moved to corresponding virtual channels (VCs) destination Virtual Output Queue. FIG. 3 shows N×M input queued switch with multiple (K) virtual channels, Virtual Output Queue and credit-based flow control.

[0135] Flow control may be used to avoid any packet drop in switches. Specifically, Credit-based flow control may be used to avoid any packet drops in switches. In credit-based flow control, packets are transmitted when (typically only when) buffer space is known to exist at the destination. To support credit-based flow control, a switch typically maintains counters for every destination per virtual channel (VC). This keeps track of buffer space at each destination D e.g. by decrementing the counter for every packet sent to destination, and incrementing the counter for every credit returned from destination D. Credits are returned from a destination whenever a destination buffer frees up. For a multi-VC switch, e.g. as shown in FIG. 1, each virtual channel (VC) has its own buffer at destination, credit counters at switch, and independent flow control.

[0136] Virtual Output Queues aka VOQ's typically store the incoming requests. A credit counter typically generates “ready” (a ready indication) whenever the destination has enough credit to accommodate a request. When “ready” is asserted, requests in all sources' Virtual Output Queue/s aka VOQ are typically exposed to the dispatch unit, else all requests are, typically, masked. Credit counters are per destination per virtual channel (VC) and are responsible for masking/unmasking of requests in corresponding virtual channels' (VCs′) corresponding destination Virtual Output Queue. This scheme is referred to as a “credit at dispatch” scheme. FIG. 4 shows the “credit at dispatch” scheme for credit-based flow control.

[0137] In input queued switches, each input port can transmit at most 1 cell at a time. Each output port can receive at most 1 cell at a time and each output port can receive cells over only 1 virtual channel (VC) at a time. A dispatch unit may ensure that above constraints are met. In an N input, M output, and K VC switch, a dispatch unit may find a set of up to min (N,M) cells to transmit over the switch.

[0138] FIG. 5 is a simplified block diagram illustration of a Dispatch Unit (“2-D arbiter”) for an N×M switch with K Virtual Channels (VCs) according to an embodiment of the invention. The Dispatch unit is referred to as a 2-D arbiter since the dispatch unit includes two sets of arbiters. The first set of arbiters, termed a “destination choose source” or “DCS” or “DCS set”, selects sources and virtual channels (VCs) requesting that destination. (e.g. selects a source and a virtual channel (VC) per destination) The first set of arbiters is typically followed by a second set of arbiters, termed a “source choose destination (SCD)” which selects among destinations which have selected this source (e.g. selects a destination, from among plural destinations which have selected a given source).

[0139] The Destination Choose Source (DCS), or first set of arbiters in the 2-D arbiter, typically provides each destination with a DCS, or DCS arbiter (aka “destination DCS”) to select among the sources requesting that destination. A Destination Choose Source (DCS) or “destination DCS” also typically includes VC select logic to arbitrate among the virtual channels (VCs) to that destination. Typically, the DCS arbiters of every destination are, functionally, exactly the same. For simplicity of explanation a single destination's DCS is now described, an example of which is illustrated in FIG. 6.

[0140] FIG. 6 is a simplified block diagram illustration of a DCS arbiter of a destination DM or D_M. The DCS arbiter of FIG. 6 typically includes arbiters for every virtual channel (VC) e.g. one arbiter per virtual channel. Each of these arbiters may be referred to as a “destination VC” arbiter or as a DV arbiter. The DCS arbiter of FIG. 6 also typically includes VC select logic to select among the DV arbiters. Typically, source requests to the same destination and the same virtual channel (VC) are connected to the same DV arbiter of the same DCS, whereas source requests to the same destination, but different virtual channels (VCs), are connected to different DV arbiters of the same DCS, as shown in FIG. 6. Each DV arbiter typically uses a suitable arbitration scheme e.g. a round-robin arbitration scheme to select among the sources. The round robin scheme typically uses a pointer which points to the highest priority request and is incremented (modulo N) to one location beyond the granted request. The arbiter e.g. DV arbiter typically selects the requesting input at or after the pointer in the round-robin schedule. All DV arbiters typically run in parallel and typically grant one of the sources. Typically, a DV arbiter updates its pointer only after receiving a Source Choose Destination (SCD) accept through the VC select logic.

[0141] The VC select logic (e.g. of FIG. 6) typically selects a DV arbiter from among all the DV arbiters which have a granted source. The selected DV arbiter grant (DCS grant) is passed to the SCD (e.g. of FIG. 3). The VC select logic uses a suitable arbitration scheme, e.g. a round robin arbitration scheme or least recently used scheme, to select among DV arbiters. The DV arbiter so selected generates a WRAP signal when all active sources in that DV arbiter are granted. Typically, the VC select logic is allowed to move to a new DV arbiter only after receiving a WRAP signal from currently selected DV arbiter. If the SCD (e.g. of FIG. 5) accept the grants from this DCS, then the VC select logic passes the accept to the selected DV arbiter.

[0142] A DCS with DV arbiter in a round robin arbitration scheme and VC select logic either in a round robin arbitration scheme or least recently used scheme, is referred as a “Rolling-RR arbiter” (e.g. the “Rolling RR DCS” of FIG. 6).

[0143] Referring again to FIG. 5, the Source Choose Destination (SCD), or “SCD set” is the second set of arbiters in the 2-D arbiter of FIG. 5. According to certain embodiments, every source has an SCD (aka “source SCD”) which selects among destination DCSs which have selected this source. Typically then, an SCD set includes plural source SCDs, one for each source. An SCD (typically each of the source SCDs) uses a suitable scheme e.g. a Least Recently Used (LRU) scheme or round robin scheme, to accept DCS grants. In an LRU scheme, at least one request (typically any request) which got a grant least recently, has highest priority relative to requests which got grants more recently, and is thus the first request in line to get the grant. Functionally the SCD arbiter of every source is exactly same (typically all source SCDs are functionally exactly the same).

[0144] FIG. 7 is a simplified block diagram illustration of a Source Choose Destination arbiter for a source SN or S_N.

[0145] Typically, the dispatch unit of FIG. 5 makes a connection between input and output nodes by performing all or any subset of the following operations 1-4, in any suitable order e.g. as shown:

[0146] Operation 1: Each input sends a request to at least one (typically each) output, to every virtual channel (VC) for which the input has at least one queued cell.

[0147] Operation 2: for each destination, each DV arbiter selects one source, from among the sources which have a request to this destination and virtual channel (VC). Typically, this results in one selected source per virtual channel (VC) per destination.

[0148] Operation 3: Each destination's VC select logic selects one of the DV arbiters' grants, from among the DV arbiters of this destination which have grants. Typically, this results in one selected virtual channel (VC) per destination.

[0149] Operation 4: Each source then arbitrates among those destination DCSs which have selected this source. Typically, this results in one selected destination per source.

[0150] It is appreciated that input queued switches may use any suitable crediting scheme to support credit-based flow control, such as but not limited to the following:

[0151] “Pre-creditor” scheme: in this scheme incoming requests are pre credited by deducting the destination credit and Dispatcher unit dispatches the pre credited requests e.g. as shown in FIG. 8.

[0152] “Credit at dispatch”: Credits are deducted only for dispatched request. Requests are placed to dispatch unit when destination has enough credit to support at least one request e.g. as shown in FIG. 4.

[0153] The existing Dispatch unit (e.g. FIG. 5 which is for a 2×3 switch with 2 virtual channels aka VCs may use any suitable arbitration scheme to make connections between input and output ports, such as but not limited to the following:

[0154] RR-LRU arbitration scheme: DCS arbiter uses Round Robin (RR) arbitration scheme and SCD arbiter uses Least Recently Used (LRU) scheme.

[0155] LRU-LRU arbitration scheme: DCS arbiter uses Least Recently Used (LRU) arbitration scheme and SCD arbiter uses Least Recently Used (LRU) scheme.

[0156] It is appreciated that existing switches may use the following combinations of crediting scheme and dispatch unit arbitration scheme:

[0157] “Pre-creditor” with RR-LRU algorithm—which may have a area/power penalty; or

[0158] “Credit at dispatch” with LRU-LRU algorithm—which may have a performance penalty.

[0159] Conventionally, a “Credit at dispatch” scheme, with an RR-LRU arbitration scheme, has performance, power and area benefit but may have a virtual channel (VC) starvation issue i.e. there may be VC request/s which remain unserved indefinitely. The dispatch unit described herein, e.g. the Rolling RR DCS-SCD illustrated in FIG. 5) solves the virtual channel (VC) starvation issue and also makes switches performance, power and area efficient.

[0160] An example of starvation may be appreciated by considering by way of example the 2×3 switch with 2 virtual channels (VCs) shown in FIG. 9. An existing RR-LRU dispatch unit for the 2×3 switch in FIG. 9, as shown in FIG. 10, has a DCS set, with a round robin arbiter per destination which selects a source and a virtual channel per destination, and a Source Choose Destination (SCD) set, with an LRU arbiter per source. An example of starvation is shown in FIG. 11, in which the DCS ARB D.sub.0 arbiter has 4 requests, S.sub.0VC.sub.0, S.sub.0VC.sub.1 S.sub.1VC.sub.0 and S.sub.1VC.sub.1.

[0161] The example of starvation shown in FIG. 11 involves two sources S.sub.0, S.sub.1, and two Virtual channels—VC.sub.0, VC.sub.1—going to a destination D.sub.0.

[0162] S.sub.0VC.sub.0 and S.sub.1VC.sub.0, belong to the same virtual channel, say VC.sub.0.

[0163] S.sub.0VC.sub.1 and S.sub.1VC.sub.1, belong to the same virtual channel, say VC.sub.1.

[0164] A round robin pointer moves in the S0VC0->S0VC1->S1VC0->S1VC1->S0VC0 . . . direction. If VC0 credit is available only after 3 clock cycles have elapsed from the time the VC0 credit is consumed, and if VC1 credit is always available, then D.sub.0 ARB may grant the request in the following order; the clock cycles 1-6 below may be seen in the top left, top right, middle left, middle right, bottom left and bottom right portions, respectively, of FIG. 11:

[0165] Clock cycle 1: Both VC.sub.0 and VC.sub.1 credits are available, and all 4 requests are exposed to ARB. ARB pointer is at S.sub.0VC.sub.0 and the ARB grants request S.sub.0VC.sub.0. ARB pointer is updated to favor the request which is just after the one granted, i.e. S.sub.0VC.sub.1. Grant of (or responsive to) request S.sub.0VC.sub.0 consumes VC.sub.0 credit.

[0166] Clock cycle 2: VC.sub.0 credit is not available and all VC.sub.0 requests are masked. ARB grants request S.sub.0VC.sub.1. ARB pointer is updated to point to next request S.sub.1VC.sub.0. Grant of request S.sub.0VC.sub.1 consumes VC.sub.1 credits.

[0167] Clock cycle 3: ARB sees request from only S.sub.0VC.sub.1 and S.sub.1VC.sub.1. ARB pointer will skip S.sub.1VC.sub.0 since the request is masked by credit unavailability and, instead, ARB grants request S.sub.1VC.sub.1. ARB pointer is updated to point to next request i.e. request S.sub.0VC.sub.0.

[0168] Clock cycle 4: VC.sub.0 credit is returned, and ARB sees all 4 requests. Since ARB pointer is at request S.sub.0VC.sub.0 the ARB grants request S.sub.0VC.sub.0. ARB pointer is updated to point to the next request which is S.sub.0VC.sub.1. Grant of request S.sub.0VC.sub.0 consumes VC.sub.0 credits.

[0169] Clock cycle 5: VC.sub.0 credit not available due to grant to S.sub.0VC.sub.0 in previous clock cycle, as occurred in clock cycle 2. The ARB grants request S.sub.0VC.sub.1 and ARB pointer is updated to favor the next request.

[0170] Clock cycle 6: VC.sub.0 credit is not available, and ARB sees requests from only S.sub.0VC.sub.1 and S.sub.1VC.sub.1 as occurred in clock cycle 3. The ARB pointer will skip S.sub.1VC.sub.0 since the request is masked by credit unavailability, and, instead, the ARB grants request S.sub.1VC.sub.1.

[0171] Unfortunately, the above scenario can repeat ad infinitum—causing request S.sub.1VC.sub.0 to be “starved” i.e. to remain unserved indefinitely.

[0172] However, according to certain embodiments, a “credit at dispatch” scheme is used by masking a request when credit not available to ensure no request is granted other than when credit is available. The masking feature of the “credit at dispatch” scheme, and the skipping that occurs in the round robin aka RR algorithm, yield virtual channel victimization. However, certain embodiments herein solve the virtual channel victimization problem by decoupling the masking feature of the credit at dispatch scheme from the skipping that occurs in round robin algorithms i.e. the embodiment may freeze a round robin pointer corresponding to virtual channel request/s which is/are (e.g. currently) masked by the “credit at dispatch” scheme. This may be achieved by splitting a single round robin arbiter into plural virtual channel specific round robin arbiters, or by replacing a single round robin arbiter with plural round robin arbiters, each of which is virtual channel-specific, in combination with virtual channel select logic to select one of the DV arbiter grant vectors, to avoid two grants to the same destination (Rolling RR DCS).

[0173] FIG. 12 shows a Rolling RR DCS for destination DO. When credit of any virtual channel runs out, the “credit at dispatch” scheme may mask all requests to that virtual channel's “exclusive” round robin arbiter and the round robin pointer may be stuck (frozen) until credit is returned to that virtual channel. As a result, i.e. due to this credit-at-dispatch request masking, no requests are skipped (e.g. no VC requests remain unserved indefinitely).

[0174] Still referring to the above presented virtual channel victimization scenario with RR arbiter replaced by Rolling-RR DCS arbiter, assume for simplicity that the virtual channel select logic is simple LRU. The clock cycles 1-4 below may be seen in the top left, top right, bottom left and bottom right quadrants, respectively, of FIG. 13:

[0175] Clock cycle 1: Both VC.sub.0 and VC.sub.1 credits are available, D.sub.0VC.sub.0 ARB sees request from S.sub.0VC.sub.0 and S.sub.1VC.sub.0, D.sub.0VC.sub.1 arbiter sees requests from S.sub.0VC.sub.1 and S.sub.1VC.sub.1. D.sub.0VC.sub.0 ARB grants request S.sub.0VC.sub.0 and D.sub.0VC.sub.1 arb grants request S.sub.0VC.sub.1. VC select logic selects or accepts grants from D.sub.0VC.sub.0 ARB. Virtual channel select logic pointer is updated to point to D.sub.0VC.sub.1 ARB. DV ARB pointer is updated if, and only if the grant is accepted by virtual channel select logic. In this case only VC.sub.0 ARB pointer is updated to point to next request i.e. request S.sub.1VC.sub.0 and D.sub.0VC.sub.1 ARB pointer are unchanged. Grant to request S.sub.0VC.sub.0 consumes VC.sub.0 credit.

[0176] Clock cycle 2: VC.sub.0 credit is not available due to grant to S.sub.0VC.sub.0 in previous clock cycle; all VC.sub.0 requests are masked. As a result, D.sub.0VC.sub.0 ARB sees no request. the pointer of D.sub.0VC.sub.1 ARB (which sees requests from S.sub.0VC.sub.1 and S.sub.1VC.sub.1) is at request S.sub.0VC.sub.1 so D.sub.0VC.sub.1 ARB grants request S.sub.0VC.sub.1. The VC select logic pointer is at D.sub.0VC.sub.1 thus the D.sub.0VC.sub.1 grants are accepted. VC select logic pointer is updated to favor D.sub.0VC.sub.0 ARB. The D.sub.0VC.sub.1 ARB pointer is updated to favor request S.sub.1VC.sub.1. The grant of request S.sub.0VC.sub.1 consumes VC.sub.1 credits.

[0177] Clock cycle 3: VC.sub.0 credit has not yet returned thus D.sub.0VC.sub.0 ARB sees no request. D.sub.0VC.sub.1 ARB sees requests from S.sub.0VC.sub.1 and S.sub.1VC.sub.1. D.sub.0VC.sub.1 ARB grants request S.sub.1VC.sub.1. VC select logic pointer is at D.sub.0VC.sub.0 but since there is no grant from D.sub.0VC.sub.0, the VC select logic accepts grants from D.sub.0VC.sub.1. The D.sub.0VC.sub.1 ARB pointer is updated to favor request S.sub.0VC.sub.1.

[0178] Clock cycle 4: VC.sub.0 credit is returned. The D.sub.0VC.sub.0 ARB sees requests S.sub.0VC.sub.0 and S.sub.1VC.sub.0. The D.sub.0VC.sub.1 ARB sees requests S.sub.0VC.sub.1 and S.sub.1VC.sub.1. The D.sub.0VC.sub.0 ARB grants request S.sub.1VC.sub.0 and D.sub.0VC.sub.1 ARB grants request S.sub.0VC.sub.1. VC select logic pointer, which is at D.sub.0VC.sub.0, accept grants from D.sub.0VC.sub.0 ARB. The VC select logic pointer is updated to favor D.sub.0VC.sub.1 ARB grants. The D.sub.0VC.sub.0 ARB pointer is updated to favor request S.sub.0VC.sub.0.

[0179] Thus in the above example, all requests are granted in 4 cycles, and zero requests are skipped, thereby to eliminate starvation.

[0180] The virtual channel select logic typically decides which DV ARB grants need to be considered. Having conventional or simple LRU logic with a grant pointer updated for every grant from DV ARB will lead to unfairness between virtual channels, e.g. as shown in FIG. 5. In this example VC0 has requests from both S0 and S1 whereas VC1 has only a request from S0. With this kind of traffic pattern, S0VC1 gets 50% of the bandwidth, whereas remaining 50% bandwidth is split between S0VC0 and S1VC0. This bandwidth split is seen in the grant vector in FIG. 14. The reason for this unfairness is, typically, that the grant pointer of the virtual channel select logic is updated for every grant from DV ARB, irrespective of the number of requests presented to that DV ARB. However, this bandwidth aka BW unfairness may be remedied by updating the virtual channel select logic grant pointer only after all active requests in the selected DV ARB are serviced e.g. as shown in FIG. 15. Virtual channel select logic may have input (e.g. wrap input) from DV ARB's which indicates when all active requests have been serviced. After (or responsive to) receiving wrap input, the virtual channel select logic pointer may be updated to favor the next DV ARB. As is apparent from the grant vector of FIG. 15, all requests, irrespective of their virtual channels, may get equal bandwidth.

[0181] FIG. 16 shows a starvation free dispatch unit (Rolling RR-LRU) described herein for 2×3 switch with 2 virtual channels (VCs) in FIG. 9.

[0182] FIGS. 17a-17b, taken together, show a pre-creditor crediting scheme with an existing RR-LRU dispatch unit for a 2×3 switch with 2 virtual channels (VCs), shown in FIG. 9, which has area and power penalty.

[0183] Area: Pre-creditor vs Credit at dispatch: The table of FIG. 21 shows buffer depth for a 6×6 switch with 2 virtual channels, assuming maximum transaction unit (MTU) 5, ready queue depth 1, and RTT (round trip latency excluding ready queue) 10. Extra credit indicates the credit which may be required to expose request/s from all sources to a destination per Virtual channel. From the table of FIG. 21, it is apparent that the pre-creditor scheme requires 2.7 times more credit compared to the “credit at dispatch” scheme. This factor increases with increase in switch size and in the number of virtual channels. A “credit at dispatch” scheme does not need a ready queue, thus the “credit at dispatch” crediting scheme is area efficient compared to the pre creditor scheme e.g. as shown in the table of FIG. 21.

[0184] These equations may be used for computation of credit:

[0185] Credit at dispatch

RTT+MTU

[0186] Pre creditor

RTT+MTU+ready queue depth+Extra credit (EC)

Where EC=(#src-1)*MTU

[0187] Performance: RR-LRU vs LRU-LRU: The graph of FIG. 20 shows ARB efficiency, comparing RR-LRU vs LRU-LRU arbitration schemes. From the graph it is apparent that in all test cases RR-LRU has more or higher or better performance compared to LRU-LRU, with a max performance gain of 30% and a min performance gain of 1%. These results are given for single beat only, for multi beat only, and for a mix of single beat and multi beat traffic, for a 6×6 switch.

[0188] From the graph (ARB efficiency RR vs LRU) of FIG. 20, it is apparent that the RR-LRU arbitration scheme has performance gain over LRU-LRU arbitration and from the table of FIG. 21, it is apparent that creditor at dispatch has area, hence power benefit, over pre creditor. Creditor at dispatch with Rolling RR-LRU arbitration scheme has both area/power and performance benefits, and is starvation free. Thus, virtual channel starvation free Rolling RR-LRU iSLIP algorithm is a useful solution for switches generally.

[0189] FIGS. 18a-18b, taken together, show the “credit at dispatch” crediting scheme with existing RR-LRU dispatch unit (for 2×3 switch with 2 virtual channels aka VCs in FIG. 9) which has a virtual channel (VC) starvation issue.

[0190] FIGS. 19a-19b, taken together, show the “credit at dispatch” crediting scheme with starvation free Rolling RR-LRU dispatch unit described herein, for 2×3 switch with 2 virtual channels aka VCs in FIG. 9. Thus FIGS. 19a-19b illustrate a “credit at dispatch” scheme with a Rolling RR-LRU dispatch unit which is a starvation free scheme.

[0191] The term “all” is used herein for simplicity, to describe example embodiments. It is appreciated however that alternatively, whatever is said herein to be true of or to characterize or to pertain to, “all” members of, or “each” member of, or “every” member of, a certain set can also, in other embodiments, be true of, or characterize or pertain to, most but not all members of that set, or all but a few members of that set, or at least one (but less than all) member/s of the set.

[0192] For example, a scheme may mask “all” requests, as described herein. But alternatively, most but not all requests, or all but a few requests, or plural requests, but less than all, may be masked. To give another example, flow controls are used to prevent any packet drop within switches as described herein. But alternatively, flow controls may be used to prevent most but not all packet drop within switches, or all but a few packet drop within switches, or at least one (but less than all) packet drop/s within switches.

[0193] It is appreciated that software components of the present invention may, if desired, be implemented in ROM (read only memory) form. The software components may, generally, be implemented in firmware or hardware, if desired, using conventional techniques. It is further appreciated that the software components may be instantiated, for example as a computer program product, or on a tangible medium. In some cases, it may be possible to instantiate the software components as a signal interpretable by an appropriate computer, although such an instantiation may be excluded in certain embodiments of the present invention.

[0194] It is appreciated that various features of the invention which are, for clarity, described in the contexts of separate embodiments may also be provided in combination in a single embodiment. Conversely, various features of the invention which are, for brevity, described in the context of a single embodiment, may also be provided separately, or in any suitable sub-combination.

[0195] It will be appreciated by persons skilled in the art that the present invention is not limited by what has been particularly shown and described hereinabove. Rather the scope of the invention includes, inter alia, the appended claims and equivalents thereof.