Method and apparatus for scheduling packets in a packet switch

• US 6,771,642 B1
• Filed: 01/08/1999
• Issued: 08/03/2004
• Est. Priority Date: 01/08/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Seaver, Terry R., Ngo, Khuong Hoang
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): LOGSDON, JOSEPH B
• Application Number:
  US09/227,118
• Time in Patent Office: 2,034 Days
• Field of Search: 370/229, 370/389, 370/390, 370/412, 370/415, 370/416, 370/432, 370/360
• US Class Current: 370/360
• CPC Class Codes: H04L 2012/5642 Multicast/broadcast/point-multipoint, e.g. VOD
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation

Abstract

The present invention reduces the number of multicast synchronization delays in a packet switch by determining the mix of packets pending at the input ports. When a sufficient number of multicast packets are ready for transferal, the packet switch preferably transmits a programmed number of multicast packets (or as many multicast packets that exist up to that programmed number). After transmitting these multicast packets, the packet switch resumes preferably transmitting unicast packets. Thus, the number of multicast synchronization delays is reduced over the prior art, the bandwidth utilization of the packet switch is correspondingly increased and the load due to multicast packets and unicast packet is balanced. One embodiment of the invention includes a timer that ensures that multicast packets are transmitted without undue delay.

Claims

1. A method for arbitrating between one or more unicast packets and one or more multicast packets for transferal through a packet switch having a plurality of inputs and a plurality of outputs, said method comprising steps of:

(a) determining a state switch trigger condition while said packet switch is in a first state, said first state being such that said packet switch preferentially transfers said one or more unicast packets from said plurality of inputs to said plurality of outputs, said state switch trigger condition including a sufficient number of multicast packets;

(b) switching from said first state to a second state responsive to said state switch trigger condition, said second state being such that said packet switch preferentially transfers some portion of a programmed number of multicast packets from said plurality of inputs to said plurality of outputs;

(c) transferring some portion of said programmed number of multicast packets up to said programmed number of multicast packets from said plurality of inputs to said plurality of outputs;

(d) switching from said second state to said first state responsive to completion of said step of transferring.

2. The method of claim 1, further including the step of repeating steps (a-d).

3. The method of claim 1, wherein the step of determining is responsive to an evaluation of the mix of said one or more unicast packets and said one or more multicast packets at said plurality of inputs.

4. The method of claim 1, wherein said packet switch includes at least one input queue and the step of determining further includes steps of:

examining one or more queued packets at said at least one input queue; and

determining the mix of said one or more unicast packets and said one or more multicast packets in said at least one input queue.

5. The method of claim 1, wherein said packet switch includes a timer and the step of determining further includes detecting expiration of said timer.

6. The method of claim 5, further including resetting said timer dependent on the mix of said one or more unicast packets and said one or more multicast packets.

7. The method of claim 5, further including resetting said timer dependent on a packet traffic load value of said packet switch.

8. The method of claim 1, wherein the first state is a unicast preference state and said second state is a multicast preference state.

9. An apparatus for arbitrating between one or more unicast packets and one or more multicast packets for transferal through a packet switch having a plurality of inputs and a plurality of outputs, said apparatus comprising:

a trigger determination mechanism configured to determine a state switch trigger condition while said packet switch is in a first state, said first state being such that said packet switch preferentially transfers said one or more unicast packets from said plurality of inputs to said plurality of outputs, said state switch trigger condition including a sufficient number of multicast packets;

a first state transition mechanism configured to switch said packet switch from said first state to a second state responsive to said state switch trigger condition determined by the trigger determination mechanism, said second state being such that said packet switch preferentially transfers some portion of a programmed number of multicast packets from said plurality of inputs to said plurality of outputs;

a multicast packet transfer mechanism configured to transfer said some portion of multicast packets up to said programmed number of multicast packets from said plurality of inputs to said plurality of outputs while said packet switch is in said second state; and

a second state transition mechanism configured to switch from said second state to said first state responsive to the multicast transfer mechanism completing said some portion of multicast packets.

10. The apparatus of claim 9, wherein the trigger determination mechanism is responsive to an evaluation mechanism that is responsive to the mix of said one or more unicast packets and said one or more multicast packets at said plurality of inputs.

11. The apparatus of claim 9, wherein said packet switch includes at least one input queue and the trigger determination mechanism further includes:

a packet examination mechanism configured to examine one or more queued packets at said at least one input queue; and

a packet mix determination mechanism configured to determine the mix of said one or more unicast packets and said one or more multicast packets in said at least one input queue responsive to the packet examination mechanism.

12. The apparatus of claim 9, wherein said packet switch includes a timer and the trigger determination mechanism further includes a timer expiration detection mechanism.

13. The apparatus of claim 12, further including a timer reset mechanism configured to reset said timer dependent on the mix of said one or more unicast packets and said one or more multicast packets.

14. The apparatus of claim 12, further including a timer reset mechanism configured to reset said timer dependent on a packet traffic load value of said packet switch.

15. The apparatus of claim 9, wherein said first state is a unicast preference state and said second state is a multicast preference state.

16. A method for arbitrating between one or more unicast packets and one or more multicast packets for transferal through a packet switch having a plurality of inputs and a plurality of outputs, said method comprising steps of:

determining a state switch trigger condition while said packet switch is in a first state, said first state being such that said packet switch preferentially transfers said one or more unicast packets from said plurality of inputs to said plurality of outputs, said packet switch including a timer wherein said step of determining further includes expiration of said timer;

switching from said first state to a second state responsive to said state switch trigger condition, said second state being such that said packet switch preferentially transfers said one or more multicast packets from said plurality of inputs to said plurality of outputs;

transferring said one or more multicast packets from one or more of said plurality of inputs to said plurality of outputs;

switching from said second state to said first state responsive to said step of transferring; and

resetting said timer dependent on a packet traffic load value of said packet switch.

17. An apparatus for arbitrating between one or more unicast packets and one or more multicast packets for transferal through a packet switch having a plurality of inputs and a plurality of outputs, said apparatus comprising:

a trigger determination mechanism configured to determine a state switch trigger condition while said packet switch is in a first state, said first state being such that said packet switch preferentially transfers said one or more unicast packets from said plurality of inputs to said plurality of outputs, said packet switch including a timer mechanism wherein said determination mechanism is responsive to expiration of said timer mechanism;

a first state transition mechanism configured to switch said packet switch from said first state to a second state responsive to said state switch trigger condition determined by the trigger determination mechanism, said second state being such that said packet switch preferentially transfers said one or more multicast packets from said plurality of inputs to said plurality of outputs;

a multicast transfer mechanism configured to transfer said one or more multicast packets from one or more of said plurality of inputs to said plurality of outputs while said packet switch is in said second state;

a second state transition mechanism configured to switch from said second state to said first state responsive to the multipacket transfer mechanism; and

resetting said timer mechanism dependent on a packet traffic load value of said packet switch.

18. A computer-readable medium carrying one or more sequences of instructions for arbitrating between one or more unicast packets and one or more multicast packets for transferal through a packet switch having a plurality of inputs and a plurality of outputs, wherein when said instructions are executed by one or more processors the instructions cause one or more processors to perform the steps of:

(a) determining a state switch trigger condition while said packet switch is in a first state, said first state being such that said packet switch preferentially transfers said one or more unicast packets from said plurality of inputs to said plurality of outputs, said state switch trigger condition including a sufficient number of multicast packets;

(b) switching from said first state to a second state responsive to said state switch trigger condition, said second state being such that said packet switch preferentially transfers some portion of a programmed number of multicast packets from said plurality of inputs to said plurality of outputs;

(c) transferring some portion of said programmed number of multicast packets up to said programmed number of multicast packets from said plurality of inputs to said plurality of outputs;

(d) switching from said second state to said first state responsive to completion of said step of transferring.

19. A computer-readable medium as recited in claim 18, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to carry-out the step of repeating steps (a-d).

20. A computer-readable medium as recited in claim 18, wherein the step of determining is responsive to an evaluation of the mix of said one or more unicast packets and said one or more multicast packets at said plurality of inputs.

21. A computer-readable medium as recited in claim 18, wherein said packet switch includes at least one input queue and the step of determining further includes steps of:

examining one or more queued packets at said at least one input queue; and

determining the mix of said one or more unicast packets and said one or more multicast packets in said at least one input queue.

22. A computer-readable medium as recited in claim 18, wherein said packet switch includes a timer and the step of determining further includes detecting expiration of said timer.

23. A computer-readable medium as recited in claim 22, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to reset said timer dependent on the mix of said one or more unicast packets and said one or more multicast packets.

24. A computer-readable medium as recited in claim 22, further comprising instructions which, when executed by the one or more processors cause the one or more processors to reset said timer dependent on a packet traffic load value of said packet switch.

25. A computer-readable medium as recited in claim 18, wherein the first state is a unicast preference state and said second state is a multicast preference state.

26. A computer-readable medium carrying one or more sequences of instructions for arbitrating between one or more unicast packets and one or more multicast packets for transferal through a packet switch having a plurality of inputs and a plurality of outputs, wherein when said instructions are executed by one or more processors, the instructions cause one or more processors to perform the steps of:

determining a state switch trigger condition while said packet switch is in a first state, said first state being such that said packet switch preferentially transfers said one or more unicast packets from said plurality of inputs to said plurality of outputs, said packet switch including a timer wherein said step of determining further includes expiration of said timer;

switching from said first state to a second state responsive to said state switch trigger condition, said second state being such that said packet switch preferentially transfers said one or more multicast packets from said plurality of inputs to said plurality of outputs;

transferring said one or more multicast packets from one or more of said plurality of inputs to said plurality of outputs;

switching from said second state to said first state responsive to said step of transferring; and

resetting said timer dependent on a packet traffic load value of said packet switch.