Method and apparatus for fair and efficient scheduling of variable-size data packets in an input-buffered multipoint switch

A method for scheduling transmissions of switching cells across an input-buffered network switch that connects a plurality of input channels to a plurality of output channels, each switching cell being associated with one of said plurality of input channels, said method including the steps of:

• storing a first plurality of requests in a first request buffer that buffers requests related to a first input channel, each said request corresponding to one of said switching cells and having a request buffer priority and a quality of service (QoS) priority;
• assigning request buffer priorities to each of said first plurality of requests ranging from highest request buffer priority to lowest request buffer priority;
• storing a second plurality of requests in a second request buffer that buffers requests related to a second input channel, each said request corresponding to one of said switching cells and having a request buffer priority and a QoS priority;
• assigning request buffer priorities to each of said second plurality of requests ranging from highest request buffer priority to lowest request buffer priority;
• accessing each request of said first and second pluralities of requests in parallel such that requests of all said request buffer priorities are accessed simultaneously;
• sorting said first and second pluralities of requests by QoS priority;
• arbitrating among said accessed and QoS sorted requests based upon said request buffer priority, availability of said first and second input channels, and availability of requested output channels;
• and
• issuing grants in response to said arbitration to said accessed and QoS sorted requests that have a highest request buffer priority and for which respective input channels and output channels are available.

An apparatus for scheduling cells in an input-buffered multipoint switch having input channels and output channels, wherein said cells have been assigned a particular quality of service (QoS) priority and wherein requests identify desired output channels for corresponding cells, comprising:

• a request buffer specific to each one of said input channels, each said request buffer having a plurality of register levels for storing requests of corresponding request buffer priority levels;
• a QoS priority indicator buffer specific to each one of said input channels, each said QoS priority indicator buffer having a plurality of register levels that are directly related to said register levels of said request buffers for storing QoS priority indicators that correspond to said requests stored in said request buffers;
• means, connected to said request buffers and said QoS priority indicator buffers, for sorting said requests by QoS priority;
• means, connected to said means for sorting, for arbitrating among said sorted requests on a QoS priority basis and for issuing request grants to highest request buffer priority requests that have available input channels and available output channels;
• a scheduler and first parallel data links between each register level of said request buffers and said means for sorting to provide said scheduler with simultaneous access to all of said requests stored in all of said request buffers;
• and
• second parallel data links between each register level of said QoS priority indicator buffers and said means for sorting that provide said scheduler with simultaneous access to all of said QoS priority indicators stored in all of said QoS priority indicator buffers.

An apparatus for scheduling packets in an input-buffered multipoint switch comprising:

• a plurality of input channels;
• a plurality of output channels;
• multilevel request buffers, each multilevel request buffer being specific to one of said plurality of input channels, said multilevel request buffers having discrete levels for storing requests having alternative quality of service (QoS) priorities, said requests having specific request buffer priorities that relate to said discrete levels within said multilevel request buffers;
• and
• scheduler means in communication with said multilevel request buffers for
• indicating a transmission status for each of said input and output channels, said transmission status being indicative of channel availability,
• arbitrating among selected requests which have an equal QoS priority and which are stored in any of said levels of said plurality of multilevel request buffers, said arbitrating being at least partially based upon a combination of said request buffer priorities and said transmission statuses of said input and output channels, and
• issuing grants to said requests in a channel-by-channel sequence based upon said arbitrating among said selected requests having equal QoS priority;
• said scheduler means including a mask generator circuit operationally connected to said multilevel request buffers to generate mask vectors that are indicative of each output channel that is requested at each of said alternative QoS priorities except the lowest QoS priority, each said mask vector being associated with one of said QoS priorities.