Method and apparatus for providing multicast messages across a data communication network

• US 7,925,778 B1
• Filed: 02/13/2004
• Issued: 04/12/2011
• Est. Priority Date: 02/13/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Boers, Arjen, Wijnands, Ijsbrand, Cai, Yiqun
• Primary Examiner(s): Nguyen; Dustin
• Application Number:
  US10/779,183
• Time in Patent Office: 2,615 Days
• Field of Search: 370/389, 370/390, 370/392, 370/466, 370/351, 370/328, 370/395.2, 370/401, 209/207, 359/124, 709/238, 709/245, 398/26
• US Class Current: 709/238
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• 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/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing

Abstract

A method and apparatus for providing multicast messages across a data communication network, the method comprising receiving a multicast message and adding to the multicast message a vector stack including at least one address of a router to which the multicast message is to be sent. The multicast message and the vector stack are then forwarded. At the first router indicated by the vector stack, the next address to which the multicast message is to be sent is read. This is repeated as necessary until the multicast message is received by the final address in the vector stack. The multicast message is then routed to the address indicated in the original multicast message.

Claims

1. One or more non-transitory computer readable media storing instructions which, when executed by one or more computing devices, cause the one or more computing devices to perform:

at a first node, adding to a multicast message a vector stack including addresses of two or more border routers in a path towards a destination of the multicast message, wherein a first address in the vector stack is an address of a second node in a first autonomous system;

forwarding the multicast message and the vector stack;

receiving the multicast message and the vector stack at the second node;

determining that the first address of the vector stack is the address of the second node;

in response to determining that the first address of the vector stack is the address of the second node, removing the first address from the vector stack, and forwarding the multicast message and the vector stack towards the second address of the addresses in the vector stack, wherein the second address is an address of a third node in a second autonomous system, and wherein the third node is coupled to other nodes in the second autonomous system, and wherein the first node and the second node are unaware of addresses for the other nodes in the second autonomous system.

2. One or more non-transitory computer-readable media as recited in claim 1, wherein the multicast message is a multicast Join message.

3. One or more non-transitory computer-readable media as recited in claim 1, wherein the instructions, when executed by the one or more computing devices, cause the one or more computing devices to perform adding the vector stack at least in part by adding to the vector stack addresses of at least one router in each autonomous system of two or more autonomous systems between a source of the multicast message and a destination of the multicast message.

4. One or more non-transitory computer-readable media as recited in claim 1, wherein the instructions, when executed by the one or more computing devices, cause the one or more computing devices to perform adding the vector stack at least in part by adding to the vector stack addresses of any border router in each autonomous system of two or more autonomous systems in a path between a source of the multicast message and a destination of the multicast message.

5. One or more non-transitory computer-readable media as recited in claim 1, wherein the second node is an Autonomous System Boundary Router (ASBR) of the first autonomous system, and wherein the third node is an ASBR of the second autonomous system.

6. One or more non-transitory computer-readable media as recited in claim 1, wherein the instructions, when executed by the one or more computing devices, cause the one or more computing devices to perform adding the vector stack by adding to the vector stack the address of each Autonomous System Boundary Router (ASBR) of a plurality of ASBRs to be traversed on a path between a source of the multicast message and a destination of the multicast message;

wherein the second node is a first ASBR of the first autonomous system and the third node is a second ASBR of the second autonomous system.

7. One or more non-transitory computer-readable media as recited in claim 1, wherein the instructions when executed by the one or more computing devices, cause the one or more computing devices to perform determining the addresses of the two or more border routers to be added to the vector stack from forwarding information.

8. One or more non-transitory computer-readable media as recited in claim 1, wherein the instructions, when executed by the one or more computing devices, cause the one or more computing devices to perform:

repeating as necessary until the multicast message is received by a final address of the addresses in the vector stack;

receiving the multicast message and the vector stack at another node;

determining that another address of the vector stack is an address of the other node;

in response to the determining that the other address of the vector stack is the address of the other node, removing the other address from the vector stack, and forwarding the multicast message and the vector stack towards a next address of the addresses in the vector stack.

9. One or more non-transitory computer-readable media as recited in claim 1, wherein the instructions, when executed by the one or more computing devices, cause the one or more computing devices to perform:

adding to the multicast message a route distinguisher relevant to the multicast message;

forwarding the multicast message and the route distinguisher;

identifying a next-hop based on the route distinguisher;

wherein the route distinguisher identifies a virtual private network comprising a multicast distribution tunnel that spans the first autonomous system and the second autonomous system.

10. One or more apparatuses for providing multicast messages across a data communication network, the one or more apparatuses comprising:

one or more network interfaces that are coupled to the data network for receiving and sending one or more packets therefrom and sending one or more packets thereto;

one or more processors;

one or more non-transitory computer-readable media storing one or more stored sequences of instructions which, when executed by one or more processors, cause the one or more processors to carry out the steps of;

at a first node, adding to a multicast message a vector stack including addresses of two or more border routers in a path towards a destination of the multicast message, wherein a first address in the vector stack is an address of a second node in a first autonomous system;

forwarding the multicast message and the vector stack;

receiving the multicast message and the vector stack at the second node;

determining that the first address of the vector stack is the address of the second node;

in response to determining that the first address of the vector stack is the address of the second node, removing the first address from the vector stack, and forwarding the multicast message and the vector stack towards a second address of the addresses in the vector stack, wherein the second address is an address of a third node in a second autonomous system, and wherein the third node is coupled to other nodes in the second autonomous system, and wherein the first node and the second node are unaware of addresses for the other nodes in the second autonomous system.

11. One or more apparatuses as recited in claim 10, wherein the multicast message is a multicast Join message.

12. One or more apparatuses as recited in claim 10, wherein the instructions, when executed by the one or more processors, cause the one or more processors to perform adding the vector stack at least in part by adding to the vector stack addresses of at least one router in each autonomous system of two or more autonomous systems between a source of the multicast message and a destination of the multicast message.

13. One or more apparatuses as recited in claim 10, wherein the instructions, when executed by the one or more processors, cause the one or more processors to perform adding the vector stack at least in part by adding to the vector stack addresses of any border router in each autonomous system of two or more autonomous systems in a path between a source of the multicast message and a destination of the multicast message.

14. One or more apparatuses as recited in claim 10, wherein the second node is an Autonomous System Boundary Router (ASBR) of the first autonomous system, and wherein the third node is an ASBR of the second autonomous system.

15. One or more apparatuses as recited in claim 10, wherein the instructions, when executed by the one or more processors, cause the one or more processors to perform adding the vector stack by adding to the vector stack the address of each Autonomous System Boundary Router (ASBR) of a plurality of ASBRs to be traversed on a path between a source of the multicast message and a destination of the multicast message;

wherein the second node is a first ASBR of the first autonomous system and the third node is a second ASBR of the second autonomous system.

16. One or more apparatuses as recited in claim 10, wherein the instructions, when executed by the one or more processors, cause the one or more processors to perform determining the addresses of the two or more border routers to be added to the vector stack from forwarding information.

17. One or more apparatuses as recited in claim 10, wherein the instructions, when executed by the one or more processors, cause the one or more processors to perform:

repeating as necessary until the multicast message is received by a final address of the addresses in the vector stack;

receiving the multicast message and the vector stack at another node;

determining that another address of the vector stack is an address of the other node;

in response to the determining that the other address of the vector stack is the address of the other node, removing the other address from the vector stack, and forwarding the multicast message and the vector stack towards a next address of the addresses in the vector stack.

18. One or more apparatuses as recited in claim 10, wherein the instructions, when executed by the one or more processors, cause the one or more processors to perform:

adding to the multicast message a route distinguisher relevant to the multicast message;

forwarding the multicast message and the route distinguisher;

identifying a next-hop based on the route distinguisher;

wherein the route distinguisher identifies a virtual private network comprising a multicast distribution tunnel that spans the first autonomous system and the second autonomous system.

19. A method for providing multicast messages across a data communication network, the method comprising:

at a first node, adding to a multicast message a vector stack including addresses of two or more border routers in a path towards a destination of the multicast message, wherein a first address in the vector stack is an address of a second node in a first autonomous system;

forwarding the multicast message and the vector stack;

receiving the multicast message and the vector stack at the second node;

determining that the first address of the vector stack is the address of the second node;

in response to determining that the first address of the vector stack is the address of the second node, removing the first address from the vector stack, and forwarding the multicast message and the vector stack towards the second address of the addresses in the vector stack, wherein the second address is an address of a third node in a second autonomous system, and wherein the third node is coupled to other nodes in the second autonomous system, and wherein the first node and the second node are unaware of addresses for the other nodes in the second autonomous system;

wherein the method is performed by one or more computing devices.

20. A method as recited in claim 19, wherein the multicast message is a multicast Join message.

21. A method as recited in claim 19, wherein adding the vector stack comprises adding to the vector stack addresses of at least one router in each autonomous system of two or more autonomous systems between a source of the multicast message and a destination of the multicast message.

22. A method as recited in claim 19, wherein adding the vector stack comprises adding to the vector stack addresses of any border router in each autonomous system of two or more autonomous systems in a path between a source of the multicast message and a destination of the multicast message.

23. A method as recited in claim 19, wherein the second node is an Autonomous System Boundary Router (ASBR) of the first autonomous system, and wherein the third node is an ASBR of the second autonomous system.

24. A method as recited in claim 19, wherein adding the vector stack comprises adding to the vector stack the address of each Autonomous System Boundary Router (ASBR) of a plurality of ASBRs to be traversed on a path between a source of the multicast message and a destination of the multicast message;

wherein the second node is a first ASBR of the first autonomous system and the third node is a second ASBR of the second autonomous system.

25. A method as recited in claim 19, further comprising determining the addresses of the two or more border routers to be added to the vector stack from forwarding information.

26. A method as recited in claim 19, further comprising:

repeating as necessary until the multicast message is received by a final address of the addresses in the vector stack;

receiving the multicast message and the vector stack at another node;

determining that another address of the vector stack is an address of the other node;

in response to the determining that the other address of the vector stack is the address of the other node, removing the other address from the vector stack, and forwarding the multicast message and the vector stack towards a next address of the addresses in the vector stack.

27. A method as recited in claim 19, further comprising:

adding to the multicast message a route distinguisher relevant to the multicast message;

forwarding the multicast message and the route distinguisher;

identifying a next-hop based on the route distinguisher;

wherein the route distinguisher identifies a virtual private network comprising a multicast distribution tunnel that spans the first autonomous system and the second autonomous system.