Small group multicast in a computer network

• US 20060203819A1
• Filed: 05/07/2006
• Published: 09/14/2006
• Est. Priority Date: 02/29/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Farinacci, Dino, Bion, Joel, Tweedly, Alex, Shand, Mike
• Granted Patent: US 7,978,718 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• 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/26 Route discovery packet
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A data structure is stored in a memory of a router, the router located along a path between a source end station and a plurality of destination end stations in a multicast distribution tree. In response to receipt of trace packets containing a listing of network devices in the multicast distribution tree, the data structure is updated. When the source end station desires to send a multicast packet, it transmits a packet to the router. The router then writes the path information stored in the data structure into the packet. Such path information may include a tree list that specifies the arrangement of network devices along the multicast distribution tree and an address list that specifies the Internet Protocol (IP) addresses of these network devices along the multicast distribution tree. By storing the complete description of the network devices of the multicast distribution tree in the packet, routing demands on the devices along the multicast path are minimized.

Claims

1. A memory of a router for storing data for use in multicast transmission through a computer network, the memory comprising:

a data structure stored in the memory, the data structure including a multicast distribution tree adapted to be written into a header of a multicast packet by the router to permit multicast transmission from the router to a destination end station, the multicast distribution tree including a listing configured to specifically identify a path through the computer network for the multicast data packet.

2. The memory of claim 1 wherein the listing of the data structure is configured to be constructed from contents of one or more trace packets received by the router, each trace packet containing a listing of one or more network devices along the path through the computer network from the router to at least one destination end station.

3. The memory of claim 2 wherein the one or more trace packets are originally sent by a source end station interconnected to the router.

4. The memory of claim 1 wherein the listing comprises:

a tree list having one or more entries, each entry adapted to specify a network device along the multicast distribution tree of the multicast data packet.

5. The memory of claim 4 wherein the listing comprises:

an address list having one or more entries, each entry corresponding to one of the network devices specified in the tree list and including an Internet Protocol (IP) address for that network device.

6. The memory of claim 5 wherein the entries of the tree list and the address list are interleaved, such that corresponding IP address for a particular network device is stored in a memory location proximate to the corresponding tree list entry.

7. The memory of claim 4 wherein the entries of the tree list are encoded according to a parent encoding scheme where each entry in the tree list includes a reference to that network device'"'"'s parent the multicast distribution tree.

8. The memory of claim 4 wherein the entries of the tree list are encoded according to a depth encoding scheme where the entries in the tree list are arranged in an order from parent to child and each entry in the tree list describes the depth of that network device in the multicast distribution tree.

9. The memory of claim 1 wherein the multicast packet is a Small Group Multicast (SMG) packet.

10. A method for using a memory of a router to store data for use in multicast transmission through a computer network, the method comprising the steps of:

storing a data structure in the memory, the data structure including a multicast distribution tree, the multicast distribution tree including a listing configured to specifically identify a path through the computer network for a multicast data packet from the router to a destination end station; and

writing, by the router, the data structure from the memory to a header of the multicast packet.

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

transmitting the packet by the router to a network device, the network device specifically identified in the listing in the header of the multicast packet.

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

constructing the data structure from contents of one or more trace packets received by the router, each trace packet containing a listing of one or more network devices along the path through the computer network from the router to at least one destination end station.

13. The method of claim 12 wherein the one or more trace packets received by the router are originally sent by a source end station interconnected to the rout

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

storing in the data structure a tree list having one or more entries, each entry adapted to specify a network device along the multicast distribution tree of the multicast data packet.

15. The method of claim 14 further comprising the step of:

storing in the data structure an address list having one or more entries, each entry corresponding to one of the network devices specified in the tree list and including an Internet Protocol (IP) address for that network device.

16. The method of claim 15 further comprising the step of:

interleaving the entries of the tree list and the address list, such that corresponding IP address for a particular network device is stored in a memory location proximate to the corresponding tree list entry.

17. The method of claim 14 further comprising the step of:

encoding the entries of the tree list according to a parent encoding scheme where each entry in the tree list includes a reference to the network device'"'"'s parent in the multicast distribution tree.

18. The method of claim 14 further comprising the step of:

encoding the entries of the tree list according to a depth encoding scheme where the entries in the tree list are arranged in an order from parent to child and each entry in the tree list includes the depth of that network device in the multicast distribution tree.

19. The method of claim 10 wherein the multicast packet is a Small Group Multicast (SMG) packet.

20. A data structure stored in a memory of a router, comprising:

a list of addresses of routers adapted to be written into a multicast data packet giving the path through a multicast system of routers for delivery of the multicast packet to a desired end station.