Multicast and unicast scheduling for a network device

• US 20030007498A1
• Filed: 09/11/2002
• Published: 01/09/2003
• Est. Priority Date: 05/14/1999
• Status: Active Grant

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Bay Networks, Inc. (Nortel Networks Corporation)
• Inventors: Angle, Richard L., Yin, Nanying, Ladwig, Geoffrey B., Jagannath, Shantigram V.
• Granted Patent: US 7,519,065 B2
• Time in Patent Office: Days
• US Class Current: 370/414
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/58 Changing or combining different scheduling modes, e.g. multimode scheduling
• CPC Class Codes: H04L 47/6205 Arrangements for avoiding head of line blocking
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin

Abstract

A method and apparatus are provided for scheduling unicast and multicast data in an input-queued network device. According to one aspect of the present invention, a combined schedule is created by pipelined staging of multicast and unicast scheduling. Multicast cells are scheduled for transmission among multiple interfaces of a crossbar by performing a multicast cell scheduling cycle for multiple classes of service that are supported by the network device. Then, unicast cells are scheduled for transmission among the interfaces at a lower priority than the previously scheduled multicast cells by performing a unicast cell scheduling cycle for the multiple classes of service using only those interfaces that remain unmatched after completion of the multicast cell scheduling cycle.

Claims

1. A method of performing multicast and unicast scheduling in a network device, the method comprising the steps of:

performing unicast cell scheduling each scheduling timeslot of a set of possible scheduling timeslots; and

performing multicast cell scheduling in parallel with and independent of the unicast cell scheduling during a subset of the possible scheduling timeslots.

2. The method of claim 1, wherein the network device includes a switched backplane controlled by two independent schedulers, a multicast scheduler and a unicast scheduler, and wherein:

the step of performing multicast cell scheduling in parallel with and independent of the unicast cell scheduling during a subset of the possible scheduling timeslots includes the multicast scheduler scheduling multicast cells for transmission among a plurality of interfaces of the switched backplane by performing a multicast cell scheduling cycle for a plurality of classes of service that are supported by the network device; and

the step of performing unicast cell scheduling each scheduling timeslot of a set of possible scheduling timeslots includes the unicast scheduler scheduling unicast cells for transmission among a plurality of interfaces of the switched backplane at a lower priority than the multicast cells scheduled by the multicast scheduler by performing a unicast cell scheduling cycle for the plurality of classes of service using only those interfaces that remain unmatched after completion of the multicast cell scheduling cycle.

3. The method of claim 2, wherein:

the step of performing multicast cell scheduling in parallel with and independent of the unicast cell scheduling during a subset of the possible scheduling timeslots includes the multicast scheduler outputting state information to the unicast scheduler; and

the step of performing unicast cell scheduling each scheduling timeslot of a set of possible scheduling timeslots includes the unicast scheduler identifying those of the interfaces that remain unmatched based upon the state information.

4. A method of combining multicast and unicast scheduling in a network device comprising the steps of:

scheduling multicast cells for transmission among a plurality of interfaces of a crossbar by performing a multicast cell scheduling cycle for a plurality of classes of service that are supported by the network device; and

scheduling unicast cells for transmission among the plurality of interfaces at a lower priority than the multicast cells scheduled by the multicast cell scheduling cycle by performing a unicast cell scheduling cycle for the plurality of classes of service using only those interfaces that remain unmatched after completion of the multicast cell scheduling cycle.

5. The method of claim 4, wherein the network device includes two independent schedulers, a multicast scheduler and a unicast scheduler, and wherein:

the step of scheduling multicast cells includes the multicast scheduler outputting state information to the unicast scheduler; and

the step of scheduling unicast cells includes the unicast scheduler identifying those of the interfaces that remain unmatched based upon the state information.

6. A method of combining multicast and unicast scheduling comprising the steps of:

scheduling multicast cells for transmission among a plurality of interfaces of a crossbar by performing a multicast cell scheduling cycle including a executing scheduling iterations for a plurality of classes of service that are supported by the network device and producing availability information indicative of those of the plurality of interfaces that remain available for scheduling; and

scheduling unicast cells for transmission among the plurality of interfaces at a lower priority than the multicast cells by performing a unicast cell scheduling cycle after the multicast cell scheduling cycle and using only those interfaces identified by the availability information.

7. A method of performing multicast and unicast scheduling in a network device, the method comprising the steps of:

during a first predetermined set of scheduling timeslots of a set of possible scheduling timeslots, performing both multicast cell scheduling and unicast cell scheduling, the multicast cell scheduling and the unicast cell scheduling operating in parallel and independent of each other; and

during a second predetermined set of scheduling timeslots of the set of possible scheduling timeslots, performing unicast cell scheduling based upon results of the multicast cell scheduling completed during a previous scheduling timeslot.

8. The method of claim 7, wherein the first predetermined set of scheduling timeslots comprises every other timeslot of the set of possible scheduling timeslots.

9. The method of claim 7, wherein the step of performing unicast cell scheduling based upon results of the multicast cell scheduling completed during a previous scheduling timeslot comprises performing unicast cell scheduling during timeslot t+1 based upon results of the multicast cell scheduling completed during timeslot t.

10. A method of combining multicast and unicast scheduling comprising the steps of:

performing a multicast cell scheduling cycle during timeslot t for multicast cells that are to be transmitted across a fabric of a network device during timeslot t+n, the fabric coupling each of a plurality of input ports to each of a plurality of output ports, the multicast cell scheduling cycle including a scheduling iteration for each class of service supported by the network device and producing availability information indicative of those of the plurality of input ports and output ports that remain available for scheduling during timeslot t+n; and

performing a unicast cell scheduling cycle during timeslot t+n based upon the availability information, the unicast cell scheduling cycle scheduling unicast cells for transmission across the fabric during timeslot t+n.

11. The method of claim 10, wherein n equals 0.

12. The method of claim 10, wherein n equals 1.

13. The method of claim 10, further comprising the step of performing a unicast cell scheduling cycle during timeslot t for unicast cells that are to be transmitted across the fabric during timeslot t in parallel with the step of performing a multicast cell scheduling cycle during timeslot t.

14. The method of claim 13, further comprising the step of performing a unicast cell scheduling cycle during every timeslot.

15. The method of claim 14, further comprising the step of performing a multicast cell scheduling cycle less frequently than every timeslot.

16. A network device comprising:

a plurality of input ports and output ports residing on a plurality of line cards;

a fabric coupled to the plurality of line cards, the fabric including a switched backplane allowing the simultaneous transfer of data among the plurality of input ports and output ports; and

a fabric configuration manager coupled to the fabric and the plurality of line cards, the fabric configuration manager including two independent schedulers, a multicast scheduler and a unicast scheduler, the multicast scheduler and the unicast scheduler operating independently and in parallel to match pairs of the plurality of ports for the transfer of multicast cells and unicast cells across the fabric, respectively, during a first predetermined set of scheduling timeslots, and during a second predetermined set of scheduling timeslots, the unicast scheduler performing unicast scheduling among those ports of the plurality of ports that remain unmatched by a prior multicast scheduling cycle.