Weighted fair share scheduler for large input-buffered high-speed cross-point packet/cell switches

A method for high-speed input buffered packet switching, comprising:

• providing a switching fabric for connecting input ports to output ports;
• for each input port, maintaining an input pointer which references an output port;
• for each output port, maintaining an output pointer which references an input port;
• in an arbiter,
• resetting input credits and output credits associated with input/output pairs,
• updating the input pointers and output pointers,
• matching inputs to outputs based on pending requests and available input and output credits;
• and
• in a scheduler, scheduling transmissions through the cross-bar switch according to the matching.

A method for high-speed input buffered packet switching, comprising:

• for each input port:
• associating a pointer with said port, the pointer referencing an output port, and
• associating, with said port, plural credit counters corresponding to different output ports;
• for each output port:
• associating a pointer with said port, the pointer referencing an input port, and
• associating, with said port, plural credit counters corresponding to different input ports;
• and
• during each time slot:
• for each input port not carrying traffic, if the associated credit counter corresponding to the output port referenced by the pointer associated with the input port has zero credits, reloading said credit counter with a specified weight and advancing the pointer,
• for each output port not carrying traffic, if the associated credit counter corresponding to the input port referenced by the pointer associated with the output port has zero credits, reloading said credit counter with a specified weight and advancing the pointer,
• selecting input-output paths for connection based on pending requests and credit counter values,
• for each selected input-output path, decrementing appropriate input port and output port credit counters.

A high-speed input buffered packet switch, comprising:

• a switching fabric for connecting input ports to output ports;
• an arbiter which allocates input credits and output credits to input/output pairs, updates pointers associated with each input and output, and performs arbitration;
• and
• a connection manager which monitors ongoing packet transmissions through the switch, and which performs credit decrements for each input and output involved in an ongoing transmission, the arbiter and connection manager being executed at each of plural time slots.

A high-speed input buffered packet switch, comprising:

• a switching fabric which connects input ports to output ports;
• a processing module associated with each input port and a processing module associated with each output port, each processing module executing independently of the other processing modules,
• each output processing module maintaining an output credit count for each input port and, responsive to requests from the input ports and the output credit counts, preselecting one of the requesting input ports according to a fairness algorithm,
• each input processing module maintaining an input credit count for each output port and, responsive to the preselections and the input credit counts, binding the input port to one of its preselecting output ports according to a fairness algorithm;
• and
• a scheduler which schedules transmissions through the switching fabric according to the bindings.