Multicast operations using prioritized state information

• US 20070140107A1
• Filed: 12/16/2005
• Published: 06/21/2007
• Est. Priority Date: 12/16/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Eckert, Toerless, Shepherd, Gregory
• Granted Patent: US 8,018,964 B2
• Time in Patent Office: Days
• US Class Current: 370/216
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• 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 45/28 using route fault recovery
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A classification mechanism to allow selected classes of multicast entries to be acted upon in a chosen order of priority during multicast distribution tree convergence is provided. Such prioritization allows for the designation of customers, networks or multicast groups to receive faster convergence of multicast distribution trees to modified multicast distribution trees in response to unavailability of an upstream router, and in performing other multicast-related tasks (e.g., PIM joins and prunes). One aspect of the present invention provides for multicast entries (also called multicast states) that are at a same priority level to be acted upon in a fair manner, thereby avoiding having certain multicast entries and their associated users from being acted upon consistently last.

Claims

1. A method comprising:

associating a first multicast entry with a first class;

associating a second multicast entry with a second class; and

selecting one of the first and second multicast entries, wherein

said selecting is determined using the first and second classes.

2. The method of claim 1 further comprising:

performing a multicast operation on the selected multicast entry.

3. The method of claim 2 wherein the multicast operation comprises an RPF selection task.

4. The method of claim 1 further comprising:

transmitting a join message related to the selected multicast entry.

5. The method of claim 4, wherein

the join message is in support of building a multicast tree for the selected multicast entry.

6. The method of claim 5 wherein the join message comprises a PIM join message.

7. The method of claim 1 further comprising:

including a first source identifier of the selected multicast entry in a forwarding information base; and

including a second source identifier of the unselected multicast entry in the forwarding information base, wherein

the first source identifier is associated with a lower index than the second source identifier.

8. The method of claim 1 further comprising:

associating the first class with a first priority;

associating the second class with a second priority; and

said selecting selects the first multicast entry if the second priority is lower than the first priority.

9. The method of claim 1 further comprising:

associating the first and second class levels with quality of service for multicast operation response.

10. The method of claim 1 further comprising:

associating a plurality of multicast entries with the second class;

sequentially selecting each of the plurality of multicast entries with the second class on which to perform a first operation; and

sequentially selecting each of the plurality of multicast entries with the second class on which to perform a second operation, wherein

said sequentially selecting provides a different ordering of the plurality of multicast entries for the first and second operations.

11. The method of claim 10 wherein said sequential selection is a round robin selection scheme.

12. A router element comprising:

a plurality of network line cards;

a processor coupled to the network line cards wherein the processor is configured to

associate a first multicast entry with a first class,

associate a second multicast entry with a second class, and

select one of the first and second multicast entries, wherein

said selecting is determined using the first and second classes.

13. The router element of claim 12 further comprising:

the processor further configured to

perform a multicast operation on the selected multicast entry.

14. The router element of claim 12 further comprising:

a first network line card of the plurality of network line cards, wherein

the first network line card is configured to transmit a join message related to the selected multicast entry.

15. The router element of claim 12 further comprising:

a memory coupled to the processor and configured to store a forwarding information base; and

the processor further configured to

include a first source identifier of the selected multicast entry in the forwarding information base, and

include a second source identifier of the unselected multicast entry in the forwarding information base, wherein

the first source identifier is associated with a lower index than the second source identifier.

16. The router element of claim 12 further comprising:

the processor further configured to

associate the first class with a first priority,

associate the second class with a second priority, and

select the first multicast entry if the second priority is lower than the first priority.

17. The router element of claim 12 further comprising:

the processor further configured to

associate a plurality of multicast entries with the second class,

sequentially select each of the plurality of multicast entries with the second class on which to perform a first operation, and

sequentially select each of the plurality of multicast entries with the second class on which to perform a second operation, wherein

said sequentially selecting provides a different ordering of the plurality of multicast entries for the first and second operations.

18. An apparatus comprising:

a plurality of network line cards;

means for associating a first multicast entry with a first class;

means for associating a second multicast entry with a second class; and

means for selecting one of the first and second multicast entries, wherein

said selecting is determined using the first and second classes.