US 7,023,840 B2 · Multiserver scheduling system and method for a fast switching element

Abstract

A scheduling system and methodology for use in a network switch element having multiserver, multiple-arbiter architecture. Ingress ports and egress ports coupled to the cross-connect fabric of the network element are provided with multiple ingress and egress arbiters, respectively, for effectuating an iterative arbitration strategy such as RGA or RG. Arbiter architectures include singe-arbiter-per-port; single-arbiter-per-server; multiple-arbiters-per-port; and multiple-arbiters-per-server arrangements, wherein the arbiters can be implemented using RRA, BTA, Flexible Ring, or any other arbiter technology. Depending on the iteration strategy, ingress arbiter architecture and egress arbiter architecture, a variety of iterative, multiserver-capable scheduling algorithms can be obtained, which scheduling algorithms can also be implemented in QoS-aware network nodes.

Claims59

Dependent claims

A network element having a switching apparatus for switching information between a plurality of ingress ports and a plurality of egress ports via a cross-connect matrix disposed therebetween, comprising:

a plurality of ingress servers associated with each of said ingress ports, said ingress servers operating to serve a plurality of virtual output queues (VOQs) supported by a corresponding ingress port;
a plurality of egress servers associated with each of said egress ports, each of said egress servers operating to serve outgoing traffic supported by a corresponding egress port;
at least one ingress arbiter associated with each of said ingress ports and at least one egress arbiter associated with each of said egress ports, said at least one ingress arbiter and egress arbiter for effectuating a particular type of arbitration;
and
a scheduler operating to configure said cross-connect matrix for transporting a plurality of transmission units from at least one of said ingress ports to at least one of said egress ports during each time slot associated with said cross-connect matrix, wherein said scheduler effectuates a particular scheduling mechanism based at least in part upon an ingress arbiter architecture, an egress arbiter architecture and a predetermined arbitration iteration strategy.

2 more elements

A scheduling methodology for use in a network switching element having a cross-connect fabric disposed between a plurality of ingress ports and a plurality of egress ports, each of said ingress ports having a plurality of ingress servers and each of said egress ports having a plurality of egress servers, wherein each ingress port supports a plurality of virtual output queues (VOQs), said scheduling methodology comprising the steps:

for each matrix cycle associated with said cross-connect fabric, initializing a scheduling matrix and a request matrix, said request matrix for building requests associated with an arbitration iteration strategy used in computing matches between said ingress servers and egress servers;
performing an arbitration iteration to obtain a current match matrix;
updating said request matrix and said scheduling matrix based on said current match matrix;
if all of said plurality of ingress servers associated with a particular ingress port are matched, removing requests, issued from said particular ingress port, from said request matrix;
if all of said plurality of egress servers associated with a particular egress port are matched, removing requests, directed to said particular egress port, from said request matrix;
resetting said current match matrix and performing next arbitration iteration using said updated request matrix;
and
upon encountering a particular stop condition, terminating further iterations and forwarding said updated scheduling matrix to a controller for configuring at least one connection path in said cross-connect fabric based on said updated scheduling matrix so as to effectuate transfer of transmission units between matched ingress and egress servers.

5 more elements

Dependencies are inferred from the claim text.

Multiserver scheduling system and method for a fast switching element

Life of this patent

Multiserver scheduling system and method for a fast switching element

Life of this patent

Abstract

Claims59