Switch fabric scheduling with fairness and priority consideration

A switch fabric, comprising:

• a plurality of ingress ports;
• a plurality of egress ports;
• a crossbar selectively configurable to couple ingress ports to egress ports;
• a scheduler coupled to the ingress ports, the egress ports, and the crossbar, the scheduler comprising,
• a shuffle component that receives a shuffle control value that indicates a particular rearrangement of request matrix elements, wherein a request matrix represents requests from particular ingress ports for particular egress ports, and wherein the shuffle control component generates a shuffled request matrix, including,
• rearranging, according to the shuffle control value, a set of request matrix elements selected from a group comprising request matrix rows and request matrix columns;
• and
• rearranging, according to a reversed shuffle control value, a set of matrix elements comprising a member of the group that was not selected to be rearranged according to the shuffle control value;
• performing arbitration on the shuffled request matrix to generate a shuffled grant matrix that represents shuffled granted requests;
• and
• a de-shuffle component that generates a grant matrix, including applying a de-shuffle control value to shuffled grant matrix elements including rows and columns;
• wherein the grant matrix is used to configure the crossbar.

A method for scheduling data through a component in a network, the method comprising:

• allocating egress port bandwidth for each of a plurality of egress ports to various inputs;
• assigning credits to each of the various inputs in proportion to a predetermined bandwidth allocation for an egress port;
• if an input requests access to an egress port and the input has at least one credit for the requested egress port, allowing the request to proceed to an arbiter;
• and
• when an input receives a grant of access to a requested egress port from the arbiter, decrementing the credits of the input for the egress port by one.

An apparatus for scheduling data through a network component, the apparatus comprising:

• a plurality of component ingress ports, each comprising a plurality of ingress port queues;
• a plurality of ingress port processors, each receiving requests for access to multiple component egress ports from a plurality of ingress port queues, wherein an egress port processor includes,
• credit update circuitry for receiving an initial number of credits for each queue, wherein the initial number of credits for a queue corresponds to an allocation of bandwidth by one egress port to one queue;
• request processing circuitry coupled to the credit update circuitry and coupled to receive a request from a queue for access to an egress port, wherein the request processing circuitry determines whether to allow the request to proceed to an arbiter based on criteria including whether a requesting queue's number of credits is greater than a predetermined saturation value.

A method for scheduling data through a network component in a network that uses a strict priority scheme, the method comprising:

• allocating egress port bandwidth for each of a plurality of component egress ports to various component ingress ports in a weighted round robin manner, wherein the allocation includes assigning credits to each of the various ingress ports in proportion to a bandwidth allocation for an egress port;
• determining which pending requests from ingress ports for egress ports will be passed to a crossbar scheduler, wherein the determination depends on a current number of credits assigned to an ingress port and a current strict priority assigned to the ingress port;
• passing requests to the crossbar scheduler in the form of a request matrix;
• operating on the request matrix, including,
• generating a shuffled request matrix using the crossbar scheduler, including;
• rearranging, according to a shuffle control value, a set of request matrix elements selected from a group comprising request matrix rows and request matrix columns;
• and
• rearranging, according to a reversed shuffle control value, a set of matrix elements comprising a member of the group that was not selected to be rearranged according to the shuffle control value;
• performing arbitration on the shuffled request matrix using to generate a shuffled grant matrix that represents shuffled granted requests;
• generating a grant matrix, including applying a de-shuffle control value to shuffled grant matrix elements including rows and columns;
• and
• using the grant matrix to configure the crossbar.

A method, comprising:

• generating a plurality of values, in the form of a matrix, representing a plurality of requests to transfer a plurality of data between a plurality of ingress ports and a plurality of egress ports;
• generating a random series of numbers representing matrix elements selected from a group comprising matrix rows and matrix columns;
• rearranging, responsive to the random series of numbers, a set of matrix elements selected from the group;
• and,
• rearranging, responsive to a reverse random series of numbers, a set of matrix elements comprising a member of the group that was not selected to be rearranged responsive to the random series of numbers.

A method, comprising:

• assigning a plurality of credit values to each of a respective plurality of inputs in proportion to a predetermined bandwidth allocation for an egress port;
• determining whether an input in the plurality of inputs requests access to the egress port;
• determining whether a credit value associated with the input is greater than a predetermined threshold value;
• allowing the request to proceed to an arbiter responsive to the determining steps;
• and
• decrementing the credit value of the input for the egress port responsive to the input receiving a grant of access to the egress port from the arbiter.