Designated router assignment per multicast group address/range

• US 7,911,977 B2
• Filed: 05/31/2005
• Issued: 03/22/2011
• Est. Priority Date: 05/31/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Boers, Arjen, Wijnands, Ijsbrand
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): Davenport; Mon Cheri S
• Application Number:
  US11/140,856
• Publication Number:
  US 20060268869A1
• Time in Patent Office: 2,121 Days
• Field of Search: 707/10, 709/201, 709/242, 709/238, 709/239, 719/328, 370/389, 370/390, 370/401, 370/432, 370/351, 370/254, 370/255, 370/238
• US Class Current: 370/255
• 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

Abstract

Each of several routers connected to a LAN elects the same router as the designated router for a multicast group identified by a multicast address. Each of the several routers implements a method for electing the designated router. The method includes in one embodiment, generating several values corresponding to the several routers, respectively. The several values are generated as a function of the several routers'"'"' IP addresses, respectively, and an IP address of a first multicast group. The values, in one embodiment, are then compared to determine which is the largest. Thereafter each router elects as the designated router for the multicast group, the router corresponding to the largest value.

Claims

1. A method comprising:

a first router selecting a designated router for a first multicast group, wherein the selecting the designated router for the first multicast group comprises

the first router, in response to the first router receiving an IGMP membership report that comprises an IP address of the first multicast group,

generating a first value for the first router and a second value for a second router, wherein the first and second values are generated using a hash algorithm, and

using the first and second values to select itself or the second router as the designated router for the first multicast group, wherein

the first and second routers are on a network; and

the first router selecting a designated router for a second multicast group, wherein

the designated router for the first multicast group is distinct from the designated router for the second multicast group, and

the selecting the designated router for the second multicast group comprises

the first router, in response to the first router receiving an IGMP membership report that comprises an IP address of the second multicast group,

generating a third value for the first router and a fourth value for the second router, wherein the third and fourth values are generated using the hash algorithm, and

using the third and fourth values to select itself or the second router as the designated router for the second multicast group, wherein

the IP address of the first multicast group is distinct from the IP address of the second multicast group.

2. The method of claim 1 wherein the first router is one of a plurality of routers directly coupled to a LAN, and wherein the second router is one of the plurality of routers directly coupled to the LAN.

3. The method of claim 1 further comprising:

the second router selecting the designated router for the first multicast group, wherein the selecting the designated router for the first multicast group comprises

generating a fifth value for the first router and a sixth value for the second router, wherein the first and fifth values are identical and the second and sixth values are identical;

the second router selecting the designated router for the second multicast group, wherein the selecting the designated router for the second multicast group comprises

generating a seventh value for the first router and an eighth value for the second router, wherein the third and seventh values are identical and the fourth and eighth values are identical;

the second router selecting itself as the designated router for the second multicast group using the seventh and eighth values; and

the second router selecting the first router as the designated router for the first multicast group using the fifth and sixth values.

4. The method of claim 1 further comprising:

the first router receiving a first multicast data packet after the first router selects itself as the designated router for the first multicast group, wherein the first multicast data packet comprises first multicast data and the IP address of the first multicast group; and

the second router receiving a second multicast data packet after the first router selects the second router as the designated router for the second multicast group, wherein the second multicast data packet comprises second multicast data and the IP address of the second multicast group.

5. The method of claim 4 further comprising:

the first router transmitting the first multicast data to a LAN; and

the second router transmitting the second multicast data to the LAN.

6. The method of claim 1 further comprising:

the first router generating the first value as a function of an IP address of the first router and the IP address of the first multicast group;

the first router generating the second value as a function of an IP address of the second router and the IP address of the first multicast group;

the first router comparing the first value to the second value; and

the first router selecting itself as the designated router for the first multicast group in response to comparing the first and second values.

7. The method of claim 6 further comprising;

the first router generating the third value as a function of the IP address of the first router and the IP address of the second multicast group;

the first router generating the fourth value as a function of the IP address of the second router and the IP address of the second multicast group;

the first router comparing the third value to the fourth value; and

the first router selecting the second router as the designated router for the second multicast group in response to comparing the third and fourth values.

16. The method of claim 1 wherein the first router selects itself as the designated router for the first multicast group if the first value is numerically greater than the second value, and wherein the first router selects the second router as the designated router for the first multicast group if the second value is numerically greater than the first value.

17. The method of claim 3 wherein the second router selects itself as the designated router for the first multicast group if the sixth value is numerically greater than the fifth value, and wherein the second router selects the first router as the designated router for the first multicast group if the fifth value is numerically greater than the sixth value.

8. An apparatus comprising:

a first router, the first router comprising;

a first circuit for generating first and second values using a hash algorithm, wherein

the first circuit, in response to the first router receiving an IGMP membership report that comprises an IP address of a first multicast group,

generates the first value for the first router, and

generates the second value for a second router, wherein

the first and second routers are on a network, and

the first router is configured to use the first and second values to select itself or the second router as a designated router for the first multicast group; and

the first circuit further configured to generate third and fourth values using the hash algorithm, wherein

the first circuit, in response to the first router receiving an IGMP membership report that comprises an IP address of a second multicast group,

generates the third value for the first router, and

generates the fourth value for the second router, wherein

the first router is further configured to use the third and fourth values to select itself or the second router as a designated router for the second multicast group,

the designated router for the first multicast group is distinct from the designated router for the second multicast group, and

the IP address of the first multicast group is distinct from the IP address of the second multicast group.

9. The apparatus of claim 8 further comprising:

the second router, the second router comprising;

a second circuit for generating fifth and sixth values, wherein the fifth value is generated for the first router, and wherein the sixth value is generated for the second router,

wherein the first and fifth values are identical to each other, and

wherein the second and sixth values are identical to each other.

10. The apparatus of claim 8 wherein the first router is configured to select itself or the second router as the designated router for the first multicast group, wherein the first router selects itself as the designated router for the first multicast group if the first value is numerically greater than the second value, and wherein the first router selects the second router as the designated router for the first multicast group if the second value is numerically greater than the first value.

11. The apparatus of claim 9 wherein the second router is configured to select itself or the first router as the designated router for the first multicast group, wherein the second router selects itself as the designated router for the first multicast group if the sixth value is numerically greater than the fifth value, and wherein the second router selects the first router as the designated router for the first multicast group if the fifth value is numerically greater than the sixth value.

12. The apparatus of claim 8 wherein the first router is configured to select itself or the second router as the designated router for the second multicast group, wherein the first router selects itself as the designated router for the second multicast group if the third value is numerically greater than the fourth value, and wherein the first router selects the second router as the designated router for the second multicast group if the fourth value is numerically greater than the third value.

13. The apparatus of claim 9 wherein the second circuit is configured to generate seventh and eighth values, wherein the seventh value is generated for the first router, and wherein the eighth value is generated for the second router, and wherein the third and seventh values are identical and the fourth and eighth values are identical.

18. The method of claim 8 wherein the first value is generated as a function of the first router'"'"'s IP address and the IP address of a first multicast group, the second value is generated as a function of the second router'"'"'s IP address and the IP address of the first multicast group, the third value is generated as a function of the first router'"'"'s IP address and the IP address of the second multicast group, and the fourth value is generated as a function of the second router'"'"'s IP address and the IP address of the second multicast group.

14. An apparatus comprising:

means for generating values, wherein

in response to a first router receiving an IGMP membership report that comprises

an IP address of a first multicast group,

a first value is generated for the first router using a hash algorithm, and

a second value is generated for a second router using the hash algorithm, and

in response to the first router receiving an IGMP membership report that comprises an IP address of a second multicast group,

a third value is generated for the first router using the hash algorithm, and

a fourth value is generated for the second router using the hash algorithm, wherein

the IP address of the first multicast group is distinct from the IP address of the second multicast group; and

means for selecting a designated router, wherein

the first router or the second router is selected as a designated router for the first multicast group using the first and second values,

the first router or the second router is selected as a designated router for the second multicast group using the third and fourth values,

the designated router for the first multicast group is distinct from the designated router for the second multicast group, and

the first and second routers are on a network.

15. The apparatus of claim 14 wherein the means for selecting selects the first router as the designated router for the first multicast group if the first value is numerically greater than the second value, and wherein the means for selecting selects the second router as the designated router for the first multicast group if the first value is numerically less than the second value.