Packet scheduling particularly applicable to systems including a non-blocking switching fabric and homogeneous or heterogeneous line card interfaces

A method, comprising:

• generating a set of requests corresponding to packets desired to be sent from a particular input across a packet switch to a plurality of outputs;
• identifying a set of grants generated in response to the set of requests;
• maintaining an acceptance starting position;
• determining an acceptance advancement position;
• identifying a first m grants in a predetermined sequence starting from the acceptance starting position, where m is less than or equal to the maximum number of connections that can be used in a single packet time from the particular input;
• and
• updating the acceptance starting position in response to the first m grants including a particular acceptance corresponding to the acceptance advancement position.

An apparatus, comprising:

• a plurality of request generators;
• a plurality of grant arbiters coupled to the plurality of request generators;
• a plurality of acceptance arbiters coupled to the plurality of grant arbiters;
• wherein each of the plurality of request generators is configured for generating requests for its associated input of a plurality of inputs of a switch;
• wherein each of the plurality of grant arbiters is configured for generating grants based on one or more received requests, said grants corresponding to authorization to send to its associated output of a plurality of outputs of the switch, where said generating grants includes maintaining a grant starting position, determining a grant advancement position, identifying a first n requests in a predetermined sequence starting from the grant starting position, where n is less than or equal to the maximum number of packets that can be sent in a single packet time to said associated output;
• and updating the grant starting position in response to the first n grants including a particular grant corresponding to the grant advancement position;
• and
• wherein each of the plurality of acceptance arbiters is configured for generating acceptances based on one or more received grants, said acceptances corresponding to its associated input of the plurality of inputs.

An apparatus, comprising:

• means for identifying a set of requests corresponding to packets desired to be sent from a plurality of inputs across a packet switch to a particular output;
• means for maintaining a grant starting position;
• means for determining a grant advancement position;
• means for identifying a first n requests in a predetermined sequence starting from the grant starting position, where n is less than or equal to the maximum number of packets that can be sent in a single packet time to the particular output;
• and
• means for updating the grant starting position in response to the first n grants including a particular grant corresponding to the grant advancement position.

An apparatus, comprising:

• means for generating a set of requests corresponding to packets desired to be sent from a particular input across a packet switch to a plurality of outputs;
• means for identifying a set of grants generated in response to the set of requests;
• means for maintaining an acceptance starting position;
• means for determining an acceptance advancement position;
• means for identifying a first m grants in a predetermined sequence starting from the acceptance starting position, where m is less than or equal to the maximum number of packets that can be sent in a single packet time from the particular input;
• and
• means for updating the acceptance starting position in response to the first m grants including a particular acceptance corresponding to the acceptance advancement position.