Small group multicast in a computer network

• US 7,978,718 B2
• Filed: 05/07/2006
• Issued: 07/12/2011
• Est. Priority Date: 02/29/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bion, Joel, Tweedly, Alex, Farinacci, Dino, Shand, Mike
• Primary Examiner(s): Phan; Man
• Assistant Examiner(s): Mansoury; Nourali
• Application Number:
  US11/429,699
• Publication Number:
  US 20060203819A1
• Time in Patent Office: 1,892 Days
• Field of Search: 370/408, 370/390, 370/312, 370/389, 370/391, 370/392, 370/393, 370/401, 370/428, 370/432
• US Class Current: 370/408
• 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 router that is interconnected to a source end station, comprising:

a processor; and

a memory configured to store;

a data structure including a multicast distribution tree for a multicast group, the multicast distribution tree configured to specifically identify a path through a computer network from the router that is interconnected to the source end station to a destination end station, and

software that, when executed by the processor of the router that is interconnected to the source end station, causes the router, upon receipt of a multicast data packet associated with the multicast group from the source end station, to encapsulate the received multi-cast data packet in a unicast data packet having a header, and to write the multicast distribution tree from the memory into the header of the encapsulating unicast data packet, to permit multicast transmission from the router to the destination end station, the multicast distribution tree represented in the header by a tree list and an address list, 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 of the entries of the tree list describes the depth of the network device in the multicast distribution tree, and wherein each the entries of the address list corresponds to the network device specified in one of the entries of the tree list and includes an address for the network device.

2. The router of claim 1 wherein the data structure is 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 router of claim 2 wherein the one or more trace packets are originally sent by the destination end station toward the source end station interconnected to the router.

4. The router of claim 1 wherein the data structure comprises:

an indication of the tree list.

5. The router of claim 1 wherein the data structure comprises:

an indication of the address list.

6. The router of claim 1 wherein the entries of the tree list and the address list are interleaved.

7. The router of claim 1 wherein the multicast data packet is a Small Group Multicast (SMG) packet.

8. A method comprising the steps of:

storing a data structure in a memory of a router that is interconnected to a source end station, the data structure including a multicast distribution tree for a multicast group, the multicast distribution tree specifically identifying a path through a computer network, from the router that is interconnected to the source end station to a destination end station;

receiving, by the router that is interconnected to the source end station, a multicast data packet from the source end station, the multicast data packet associated with the multi-cast group;

encapsulating, by the router that is interconnected to the source end station, the received multicast data packet in a unicast data packet having a header; and

writing, by the router that is interconnected to the source end station, the multicast distribution tree from the memory to the header of the encapsulating unicast data packet, the multicast distribution tree represented in the header by a tree list and an address list, wherein the entries of the tree list are encoded according to a depth encoding scheme where the entries of the tree list are arranged in an order from parent to child and each of the entries of the tree list describes the depth of the network device in the multicast distribution tree, and wherein each of the entries of the address list corresponds to the network device specified in one of the entries of the tree list and includes an address for the network device.

9. The method of claim 8 further comprising the step of:

transmitting the encapsulating unicast data packet that includes the multicast data packet, by the router, to a particular network device, the network device specifically identified in the tree list and the address list in the header of the encapsulating unicast data packet.

10. The method of claim 8 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.

11. The method of claim 10 wherein the one or more trace packets received by the router are originally sent by the destination end station toward the source end station interconnected to the router.

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

storing in the data structure an indication of the tree list.

13. The method of claim 8 further comprising the step of:

storing in the data structure an indication of the address list.

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

interleaving the entries of the tree list and the address list.

15. The method of claim 8 wherein the multicast data packet is a Small Group Multicast (SMG) packet.

16. A router that is interconnected to a source end station having a memory, comprising:

means for maintaining a multicast distribution tree for a multicast group in the memory, the multicast distribution tree specifically identifying a path extending from the router that is interconnected to the source end station to a destination end station;

means for receiving a multicast data packet including a multicast group number that corresponds to the multicast group;

means for encapsulating the received multicast data packet in a unicast data packet having a header; and

means for writing a tree list having one or more entries and an address list having one or more entries into the header of the encapsulating unicast data packet, wherein the entries of the tree list are encoded according to a depth encoding scheme where the entries of the tree list are arranged in an order from parent to child and each of the entries of the tree list describes the depth of the network device in the multicast distribution tree, and wherein each of the entries of the address list corresponds to the network device specified in one of the entries of the tree list and includes an address for the network device.