Multicast routing with multicast virtual output queues and shortest queue first allocation

• US 6,603,772 B1
• Filed: 03/31/1999
• Issued: 08/05/2003
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Moussavi, Farshid, Shah, Dhaval N.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): PHAM, BRENDA H
• Application Number:
  US09/282,539
• Time in Patent Office: 1,588 Days
• Field of Search: 370/390, 370/389, 370/392, 370/411-418, 370/432
• US Class Current: 370/432
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3045 Virtual queuing

Abstract

The invention includes a method and apparatus for routing multicast traffic with better performance and reduced Head of Line blocking. This is achieved by means of the use of multiple virtual output queues for each input interface that handles multicast traffic, called “multicast virtual output queues” (MVOQs). Schemes for allocation of queues including random allocation, round robin, and Shortest Queue First (SQF) allocation can further improve performance. In an alternative embodiment, global MVOQs that can be used as queues by multiple input interfaces, can be used instead of MVOQs associated with a specific input interface.

Claims

1. A method of operating a switching device, said switching device receiving messages belonging to a plurality of multicast flows, comprising the steps of:

receiving, for each multicast flow of said plurality of multicast flows, a sequence of multicast messages;

associating each one message in each said sequence to a selected one of a set of multicast virtual output queues, said set of multicast virtual output queues having more than one and less than 2^N individual multicast virtual output queues for each one of a plurality of N output interfaces, and N is 2 or greater; and

sending a head element of one of said set of multicast virtual output queues to said output interfaces.

2. A method as in claim 1, wherein said step of associating includes steps of

selecting a shortest one of said set of multicast virtual output queues at a time of performance of said steps for receiving; and

performing said steps of associating in response to a result of said steps of selecting.

3. A method as in claim 1, wherein said steps of associating include steps of

selecting a shortest one of said set of multicast virtual output queues at a time of performance of said steps for receiving a first said message;

and

wherein said steps for associating operate to associate said first message with said shortest queue.

4. A method as in claim 1, wherein said steps of receiving include receiving a first said message;

said steps of associating include steps of (a) incrementing a counter for said selected queue; and

(b) appending said first message to said selected queue; and

said steps of sending include steps of (a) selecting one of said queues;

(b) sending a head element from said selected queue to a set of output interfaces; and

(c) decrementing said counter for said selected queue.

5. A method as in claim 1, wherein said steps of associating include steps of:

selecting a random one of said set of multicast virtual output queues at a time of performance of said steps of receiving; and

performing said steps of associating in response to a result of said steps of selecting.

6. A method as in claim 1, wherein said steps of associating include steps of

selecting one of said set of multicast virtual output queues at a time of performance of said steps of receiving wherein the step of selection uses a round robin technique;

and

performing said steps of associating in response to a result of said steps of selecting.

7. A method as in claim 1, wherein said steps of associating include steps of

selecting a random one of said set of multicast virtual output queues at a time of performance of said steps of receiving a first said message;

and

wherein said steps of associating operate to associate said first message with said randomly selected queue.

8. A method as in claim 1, wherein said steps of associating include steps of

selecting a round-robin one of said set of multicast virtual output queues at a time of performance of said steps of receiving a first said message;

and

wherein said steps of associating operate to associate said first message with said round robin queue.

20. A computer readable medium containing computer executable instructions for performing the method recited in claim 1, claim 5 or claim 10.

21. An electromagnetic signal propagating on a computer network, the electromagnetic signal carrying information for executing on a computer the method of claim 1, claim 5 or claim 10.

9. A method of operating a switching device, said switching device receiving messages belonging to a plurality of multicast flows, comprising the steps of:

receiving, for each multicast flow of said plurality of multicast flows, a sequence of multicast messages;

associating each one message in each said sequence to a selected one of a set of multicast virtual output queues, said set of multicast virtual output queues having more than one and less than 2^N individual multicast virtual output queues for each one of a plurality of N output interfaces, and N is 2 or greater; and

sending a head element of one of said set of multicast virtual output queues to said output interfaces in accordance with a policy to reduce head-of-line blocking.

10. A method of operating a switching device, said switching device receiving messages belonging to a plurality of multicast flows, comprising the steps of:

receiving a multicast message of a flow;

determining if said flow is assigned to a multicast virtual output queue (MVOQ) and in the event it is not assigned to a MVOQ, selecting a multicast virtual output queue (MVOQ) for said flow, said MVOQ selected from a plurality of available MVOQs (the selected MVOQ), said selecting based upon a policy, where said policy is chosen to distribute multicast flows over said plurality of MVOQs to reduce head-of-line blocking;

receiving a second multicast message of said flow; and

assigning said second multicast message to said selected MVOQ.

11. The method of claim 10 further comprising:

implementing a number of said MVOQs where said number is greater than or equal to 1 and less than 2^N, where N is a number of output ports of said switching device, and N is 2 or greater.

12. The method of claim 10, wherein said policy is a Shortest Queue First policy where said selected MVOQ is selected as an MVOQ with a count that is the smallest of all the MVOQs in the plurality of MVOQs.

13. The method of claim 12 wherein said count is a number of cells in the MVOQ.

14. The method of claim 12 wherein said count is a total count for the MVOQ.

15. The method of claim 12 wherein said count is a total number of bytes in the MVOQ.

16. The method of claim 10 wherein said policy is a random assignment policy where said selected MVOQ is selected by random assignment of said flow to an MVOQ from said plurality of MVOQs.

17. The method of claim 10 wherein said policy is a round robin policy where said selected MVOQ is selected in a sequential cyclical order from said plurality of MVOQs.

18. The method of claim 10 wherein said policy is a combination of allocation policies.

19. The method of claim 10 further comprising the step of:

creating an entry in a flow table, said entry associated with said flow wherein said flow table is used to assign multicast messages associated with said flow to said selected MVOQ.

22. An apparatus for operating a switching device, said switching device receiving messages belonging to a plurality of multicast flows, comprising:

a circuit adapted to receive a multicast message of a flow;

a circuit adapted to implement a plurality of multicast virtual output queues (MVOQs);

a circuit adapted to determine if said flow is assigned to a multicast virtual output queue (MVOQ) and in the event that it is not assigned to a MVOQ select a multicast virtual output queue (MVOQ) from said plurality of MVOQs based upon a policy where said policy is chosen to distribute multicast flows over said plurality of MVOQs to reduce head-of-line blocking;

a circuit adapted to receive a second multicast message of said flow; and

a circuit adapted to assign said second multicast message to said selected MVOQ.

23. The apparatus of claim 22 further comprising:

a circuit adapted to implement a number of said MVOQs where said number is greater than or equal to 1 and less than 2^N, where N is a number of output ports of said switching device, and N is 2 or greater.

24. The apparatus of claim 22, wherein said policy is a Shortest Queue First policy where said selected MVOQ is selected as an MVOQ with a count that is the smallest of all the MVOQs in the plurality of MVOQs.

25. The apparatus of claim 24 wherein said count is a number of cells in the MVOQ.

26. The apparatus of claim 24 wherein said count is a total count for the MVOQ.

27. The apparatus of claim 24 wherein said count is a total number of bytes in the MVOQ.

28. The apparatus of claim 22 wherein said policy is a random assignment policy where said selected MVOQ is selected by random assignment of said flow to an MVOQ from said plurality of MVOQs.

29. The apparatus of claim 22 wherein said policy is around robin policy where said selected MVOQ is selected in a sequential cyclical order from said plurality of MVOQs.

30. The apparatus of claim 22 wherein said policy is a combination of allocation policies.

31. The apparatus of claim 22 further comprising:

a circuit adapted to create an entry in a flow table wherein said entry is associated with said flow and said flow table is used to assign multicast messages associated with said flow to said selected MVOQ.

32. The apparatus of claim 31 wherein said flow table is implemented in a content addressable memory (CAM).

33. The apparatus of claim 22 wherein said circuit adapted to determine if said flow is assigned to a multicast virtual output queue is a processor operating under program control.

34. An apparatus for operating a switching device, said switching device receiving messages belonging to a plurality of multicast flows, comprising:

a circuit adapted to receive a multicast message of a flow;

means for determining if said flow is assigned to a multicast virtual output queue (MVOQ) and in the event that it is not assigned to an MVOQ, selecting a multicast virtual output queue (MVOQ) for said flow, said MVOQ selected from a plurality of available MVOQs (the selected MVOQ), said selecting based upon a policy, where said policy is chosen to distribute multicast flows over said plurality of MVOQs to reduce head-of-line blocking;

a circuit adapted to receive a second multicast message of said new multicast flow; and

a circuit adapted to assign said second multicast message to said selected MVOQ.

35. The apparatus of claim 34 further comprising:

a circuit adapted to implement a number of said MVOQs where said number is greater than or equal to 1 and less than 2^N, where N is a number of output ports of said switching device, and N is 2 or greater.

36. The apparatus of claim 34, wherein said policy is a Shortest Queue First policy where said selected MVOQ is selected as the MVOQ with a count that is the smallest of all the queues in the plurality of MVOQs.

37. The apparatus of claim 36 wherein said count is a number of cells in the MVOQ.

38. The apparatus of claim 36 wherein said count is a total count for the MVOQ.

39. The apparatus of claim 36 wherein said count is a total number of bytes in the MVOQ.

40. The apparatus of claim 34 wherein said policy is a random assignment policy where said selected MVOQ is selected at random from said plurality of MVOQs.

41. The apparatus of claim 34 wherein said policy is a round robin policy where said selected MVOQ is selected in a round robin fashion from said plurality of MVOQs.

42. The apparatus of claim 34 wherein said policy is a combination of allocation policies.

43. The apparatus of claim 34 further comprising:

a circuit adapted to create an entry in a flow table wherein said entry is associated with said flow and said flow table is used to assign multicast messages associated with said flow to said selected MVOQ.

44. The apparatus of claim 43 wherein said flow table is implemented in a content addressable memory (CAM).

45. The apparatus of claim 34 wherein said circuit adapted to determine if said flow is assigned to a multicast virtual output queue is a processor operating under program control.