Granted Patent B2

US 8,090,869 · App. 10/359,878 · Granted Jan 3, 2012

Abstract

Claims (102)

1. A method of determining how to forward cells from ingress queues to a switch fabric, comprising:

determining which cells are to be forwarded from ingress queues to exit first-in-first-out queues (FIFOs) in accordance with a priority-biased arbitration stage;

determining which cells are to be forwarded from said exit FIFOs to a switch fabric in accordance with a throughput-biased arbitration stage;

forwarding first cells from an ingress queue of said ingress queues to a first exit FIFO of said exit FIFOs;

forwarding second cells from said ingress queue to a second exit FIFO of said exit FIFOs; and

excluding said second exit FIFO from said throughput-biased arbitration until said first cells are sent from said first exit FIFO.

2. The method of claim 1 , wherein one of said ingress queues is a multicast ingress queue and one of said exit FIFOs is a multicast exit FIFO, further comprising:

forwarding a cell from a multicast ingress queue of said ingress queues to a multicast exit FIFO of said exit FIFOs; and

associating a channel exit port (CEP) designator with said cell in accordance with an exit port table.

3. The method of claim 2 , said associating comprising:

turning on one or more bits of a CEP designator in accordance with said exit port table such that said one or more bits identify respective egresses.

4. The method of claim 3 , wherein a CEP field to be associated with said cell is smaller than said CEP designator, further comprising:

partitioning said CEP designator into portions with lengths equal to that of a CEP field;

associating a first portion with said cell, wherein said first portion includes a first bit of said one or more bits;

setting an offset such that said first bit and said offset together correspond to a first bit location of said CEP designator;

replicating said cell if a second portion includes a second bit of said one or more bits;

associating said second portion with the replicated cell if said cell was replicated; and

setting an offset such that said second bit and said offset together correspond to a second bit location of said CEP designator.

5. The method of claim 4 , wherein said CEP designator is 64 bits long, said CEP field is 32 bits long, and said offset is a high/low bit.

6. The method of claim 1 , further comprising:

excluding an ingress queue from said priority-biased arbitration stage if a buffer of said switch fabric that corresponds to said ingress queue is unavailable.

7. The method of claim 1 , further comprising:

setting an exit FIFO limit;

allowing an ingress queue of said ingress queues to forward cells to plurality of said exit FIFOs; and

excluding said ingress queue from said priority-biased arbitration stage if said plurality is at least said exit FIFO limit.

8. The method of claim 7 , further comprising:

verifying a first exit FIFO of said plurality includes cells from said ingress queue;

verifying a second exit FIFO of said plurality is available;

setting an ordering bit associated with said second exit FIFO;

setting an ordering tag associated with said first exit FIFO, wherein said ordering tag identifies said second FIFO;

checking said ordering bit; and

excluding said second exit FIFO from said throughput-biased arbitration stage if said ordering bit is set.

9. The method of claim 8 , further comprising:

identifying said second exit FIFO from said ordering tag;

clearing said ordering bit;

clearing said ordering tag; and

forwarding a cell from said first exit FIFO in accordance with said throughput-biased arbitration stage.

10. The method of claim 1 , wherein a first subset of said ingress queues includes one or more multicast queues and a second subset of said ingress queues includes one or more unicast queues, further comprising:

setting a probability of selection for each of a plurality of priorities, wherein said pluralities are organized from a lowest priority to a highest priority;

generating a number;

selecting a priority of said plurality of priorities using said number in accordance with the probability of selection for said priority;

excluding from said priority-biased arbitration stage a first subset of said ingress queues if said first subset does not include cells of the selected priority or higher and a second subset of said ingress queues includes cells of said selected priority or higher; and

excluding from said priority-biased arbitration stage said second subset of said ingress queues if said second subset does not include cells of said selected priority or higher and said first subset of said ingress queues includes cells of said selected priority or higher,

wherein said first subset includes one or more multicast queues and said second subset includes one or more unicast queues.

11. The method of claim 10 , wherein said second subset does not include any multicast queues, further comprising:

excluding from said priority-biased arbitration stage said first subset if a queue of said second subset was excluded in a preceding priority-biased arbitration stage.

12. The method of claim 1 , further comprising:

setting a probability of selection for each of a plurality of priorities, wherein said pluralities are organized from a lowest priority to a highest priority;

generating a number, wherein said number corresponds to a first priority of said plurality of priorities in accordance with the probability of selection for said first priority;

selecting a second priority if said ingress queues do not include non-empty queues having said first priority;

establishing a third priority that equals said second priority if said ingress queues do not include non-empty queues having said first priority;

establishing said third priority that equals said first priority if said ingress queues include non-empty queues having said first priority;

selecting a non-empty queue having said third priority; and

forwarding from said non-empty queue.

13. The method of claim 12 , wherein said second priority is selected by round robin and said non-empty queue is selected by round robin.

14. The method of claim 12 , further comprising:

reestablishing said third priority at a higher priority if said higher priority is a strict priority, wherein said ingress queues include non-empty queues of said higher priority.

15. The method of claim 1 , further comprising:

excluding an exit FIFO of said exit FIFOs from said throughput-biased arbitration if an egress queue associated with said exit FIFO is unavailable.

16. The method of claim 1 , further comprising:

excluding an exit FIFO of said exit FIFOs from said throughput-biased arbitration when said exit FIFO targets an egress queue that is targeted by a multicast cell that is already being transmitted, if said exit FIFO is a multicast FIFO.

17. The method of claim 1 , further comprising:

checking an ordering field of an exit FIFO of said exit FIFOs, wherein said ordering field indicates another exit FIFO of said exit FIFOs is first in line; and

excluding said exit FIFO from said throughput-biased arbitration stage.

18. The method of claim 1 , wherein a first subset of said exit FIFOs includes one or more multicast exit FIFOs and a second subset of said exit FIFOs includes one or more unicast exit FIFOs, further comprising:

excluding a first subset of said exit FIFOs from said throughput-biased arbitration stage if no exit FIFO of said first subset is selectable, wherein said first subset includes one or more multicast exit FIFOs;

excluding a second subset of said exit FIFOs from said throughput-biased arbitration stage if no exit FIFO of said second subset is selectable, wherein said second subset includes one or more unicast exit FIFOs;

excluding said first subset from said throughput-biased arbitration stage if a multicast exit FIFO won a previous throughput-biased arbitration at said throughput-biased arbitration stage, unless said second subset is excluded from said throughput-biased arbitration stage; and

excluding said second subset from said throughput-biased arbitration stage if a unicast exit FIFO won a previous throughput-biased arbitration at said throughput-biased arbitration stage, unless said first subset is excluded from said throughput-biased arbitration stage.

19. The method of claim 1 , further comprising:

selecting an exit FIFO for forwarding cells by round robin.

20. The method of claim 1 , wherein said cells comprise portions of packets, wherein start-of-packet (SOP) cells and end-of-packet (EOP) cells respectively encapsulate first and last portions of said packets, and wherein said EOP cells include EOP indicators for said packets.

21. The method of claim 20 , wherein a subset of said ingress queues are multicast queues, further comprising:

establishing a maximum number of multicast ingress queues that may be active at one time, wherein said multicast ingress queues are a subset of said ingress queues, wherein an active multicast ingress queue has forwarded a first SOP cell, but has not forwarded a first EOP cell that is associated with said first SOP cell, and wherein an inactive multicast ingress queue has forwarded a second EOP cell for every associated second SOP cell;

making said maximum number of multicast ingress queues active by forwarding SOP cells; and

excluding inactive multicast ingress queues from said priority-biased arbitration stage until at least one active queue becomes inactive.

22. A system for performing priority-biased arbitration, comprising:

a plurality of ingress queues;

a priority-biased arbitration engine configured to arbitrate between said plurality of ingress queues;

a plurality of exit first-in-first-out queues (FIFOs) configured to forward cells from said plurality of ingress queues to a switching fabric;

a plurality of ordering fields, respectively associated with said exit FIFOs, configured to contain a value that indicates whether the respective exit FIFOs are not first in line;

an ordering tag, respectively associated with said exit FIFOs, configured to contain a value that identifies a next exit FIFO, wherein said next exit FIFO is next in line; and

a throughput-biased arbitration engine configured to arbitrate between said exit FIFOs, wherein the ordering tag determines an order in which at least two of the exit FIFOs are processed at the throughput-biased arbitration engine to forward the cells from the plurality of exit FIFOs to the switching fabric.

23. The system of claim 22 , further comprising:

a plurality of FIFO counters, respectively associated with said ingress queues, configured to contain a value representative of how many exit FIFOs are in use by said respective ingress queues;

a FIFO limit register configured to contain a value representative of a maximum number of FIFOs that said respective ingress queues are permitted to use; and

a comparator, coupled to a FIFO counter of said FIFO counters and said FIFO limit register, configured to exclude an ingress queue of said ingress queues from arbitration by said priority-biased arbitration engine if the FIFO counter associated with said ingress queue contains a value equal to or greater than the value of said FIFO limit register.

24. The system of claim 22 , further comprising:

a plurality of probability registers, respectively associated with priorities, configured to contain values that represent probabilities of selecting said respectively associated priorities;

a number generator, coupled to said plurality of probability registers, configured to generate a number indicative of a priority based on said values; and

circuitry configured to exclude a subset of said ingress queues from arbitration by said priority-biased arbitration engine.

25. The system of claim 24 , further comprising:

a second plurality of probability registers, respectively associated with said priorities, configured to contain second values that represent probabilities of selecting said respectively associated priorities; and

second circuitry configured to exclude a second subset of said ingress queues from arbitration by said priority-biased arbitration engine using a priority selected using said second plurality of probability registers.

26. A method of determining how to forward cells from ingress queues to a switch fabric, comprising:

determining which cells are to be forwarded from ingress queues to exit first-in-first-out queues (FIFOs) in accordance with a priority-biased arbitration stage, wherein one of said ingress queues is a unicast ingress queue and one of said exit FIFOs is a unicast exit FIFO;

determining which cells are to be forwarded from said exit FIFOs to a switch fabric in accordance with a throughput-biased arbitration stage;

forwarding a cell from a unicast ingress queue of said ingress queues to a unicast exit FIFO of said exit FIFOs;

encoding a CEP designator according to said unicast ingress queue;

decoding said CEP designator into a CEP field and an offset, wherein said CEP field and said offset correspond to said unicast ingress queue and are used to determine the unicast exit FIFO to which the cell is forwarded; and

associating said CEP field and said offset with said cell.

27. The method of claim 26 , wherein said decoded CEP designator is 64 bits long, said CEP field is 32 bits long, and said offset is a high/low bit.

Assignments (10)