Multicast operations using prioritized state information

• US 8,018,964 B2
• Filed: 12/16/2005
• Issued: 09/13/2011
• 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: Shepherd, Gregory J, Eckert, Toerless
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): LOO, JUVENA W
• Application Number:
  US11/303,170
• Publication Number:
  US 20070140107A1
• Time in Patent Office: 2,097 Days
• Field of Search: 370/395, 370/397, 370/398, 370/399, 370230-235, 370/432, 370/312, 370/390.3, 370/390.31
• US Class Current: 370/432
• 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 network router implemented method comprising:

associating a first multicast state entry in a multicast routing table on the network router with a first class, wherein

the first multicast state entry identifies a first multicast state of a first multicast group, and

the first class identifies a first priority;

associating a second multicast state entry in the multicast routing table with a second class, wherein

the second multicast state entry identifies a second multicast state of a second multicast group, and

the second class identifies a second priority; and

selecting one of the first and second multicast state entries, wherein

said selecting is performed in response to a determination that an upstream router that is part of a first multicast distribution tree for the first multicast group and part of a second multicast distribution tree for the second multicast group is unavailable,

said selecting is determined according to highest priority provided by the first and second classes, and

said selecting is performed by a processor in the network router.

2. The method of claim 1 further comprising:

performing a multicast operation on the selected multicast state entry in the multicast routing table.

3. The method of claim 2 wherein the multicast operation comprises an RPF check, wherein the RPF (Reverse Path Forwarding) check is performed in support of building a multicast distribution tree for the selected multicast state entry.

4. The method of claim 1 further comprising:

transmitting a join message related to the selected multicast state entry in the multicast routing table.

5. The method of claim 4, wherein

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

6. The method of claim 5 wherein the join message comprises a PIM (Protocol Independent Multicast) join message.

7. The method of claim 1 further comprising:

including a first source identifier of the first multicast state entry in a forwarding information base, wherein the first source identifier is associated with a first index; and

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

the second source identifier is associated with a second index, and

the first priority is higher than the second priority if the first index is lower than the second index.

8. The method of claim 3 further comprising:

the RPF check is used to determine an available upstream router for the selected multicast state entry.

9. The method of claim 1, wherein

the first priority is higher than the second priority if the first class is associated with a higher quality of service than the second class.

10. The method of claim 1 further comprising:

associating a plurality of multicast state entries in the multicast routing table with the second class;

sequentially selecting, according to a first selection scheme, each of the plurality of multicast state entries on which to perform a first operation; and

sequentially selecting, according to a second selection scheme, each of the plurality of multicast state entries on which to perform a second operation, wherein

said first and second selection schemes provide a different ordering of the plurality of multicast state entries for the first and second operations, respectively.

11. The method of claim 10 wherein said first and second selection schemes use a round robin-type selection scheme.

12. A router element comprising:

a plurality of network line cards; and

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

associate a first multicast state entry in a multicast routing table on the router element with a first class, wherein

the first multicast state entry identifies a first multicast state of a first multicast group, and

the first class identifies a first priority,

associate a second multicast state entry in the multicast routing table with a second class, wherein

the second multicast state entry identifies a second multicast state of a second multicast group, and

the second class identifies a second priority, and

select one of the first and second multicast state entries, wherein

said selection is determined according to highest priority provided by the first and second classes, and

said selection is performed in response to a determination that an upstream router that is part of a first multicast distribution tree for the first multicast group and part of a second multicast distribution tree for the second multicast group is unavailable.

13. The router element of claim 12 further comprising:

the processor further configured to

perform a multicast operation on the selected multicast state entry in the multicast routing table.

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 state 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 first multicast state entry in the forwarding information base, and

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

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

16. The router element of claim 12, wherein

the first priority is higher than the second priority if a first response time for a first RPF check performed on the first multicast state entry is less than a second response time for a second RPF (Reverse Path Forwarding) check performed on the second multicast state entry.

17. The router element of claim 12 further comprising:

the processor further configured to

associate a plurality of multicast state entries in the multicast routing table with the second class,

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

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

said first and second selection schemes each provide a different ordering of the plurality of multicast state entries for the first and second operations, respectively.

18. An apparatus comprising:

a plurality of network line cards;

means for associating a first multicast state entry in a multicast routing table with a first class, wherein

the first multicast state entry identifies a first multicast state of a first multicast group, and

the first class identifies a first priority;

means for associating a second multicast state entry in the multicast routing table with a second class, wherein

the second multicast state entry identifies a second multicast state of a second multicast group, and

the second class identifies a second priority; and

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

said selecting is determined according to highest priority provided by the first and second classes, and

said selecting is performed in response to a determination that an upstream router that is part of a first multicast distribution tree for the first multicast group and part of a second multicast distribution tree for the second multicast group is unavailable.