Multicast support for small groups

• US 6,502,140 B1
• Filed: 01/29/1999
• Issued: 12/31/2002
• Est. Priority Date: 01/29/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Boivie, Richard H.
• Primary Examiner(s): Le, N.
• Assistant Examiner(s): Benson, Walter
• Application Number:
  US09/240,549
• Time in Patent Office: 1,432 Days
• Field of Search: 370/352, 370/408, 370/60, 370/236, 370/390, 370/401, 709/218, 709/219, 709/227, 709/238, 709/245
• 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/16 Multipoint routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A method for multicasting data packets includes the steps of preparing at least one packet at a source node and transmitting the packet to at least one intermediate node. The packet includes a payload portion and multicast route information. The multicast route information includes information for use by the intermediate node to forward the packet to at least two destination nodes. According to another aspect of the invention, a method for multicasting data packets in a packet-based data network includes the step of transmitting an Internet Protocol (“IP”) packet from a source node to a first node. The IP packet includes an IP header and an IP payload containing an encapsulated multicast (EM) datagram, the EM datagram comprising an EM header and an EM payload. The EM header includes multicast routing information instructing the first node to transmit the EM payload to at least two second and third nodes. According to another embodiment, a system including various network nodes is adapted to implement the described method.

Claims

1. A method for multicasting data packets in a packet-based data network comprising the source node steps of:

preparing at a source node where a multicast communications originates at least one packet comprising a payload portion and multicast route information so that the multicast route information causes the packet to be muted only once over any given route which is part of a multicast tree when the packet is simultaneously sent to more than one destination node; and

transmitting the packet from the source node to two or more destination nodes with at least one intermediate node;

wherein the multicast route information includes destination routing information for use by the at least one intermediate node to forward the packet to at least two destination nodes, without the need to transmit the packet to a centralized entity and without the need to store multicast routing information at the at least one intermediate node,

wherein the multicast route information comprises a plurality of route definitions, wherein at least two route definitions within the plurality of route definitions share a common node and wherein the at least two route definitions have been folded so that nodes beyond the common node that are beyond the common node and within the at least two route definitions are grouped and identified as routing information for the packet beyond the common node, and wherein the common node is only specified once.

2. The method of claim 1 wherein the multicast route information nests to a variable depth within the packet.

3. The method of claim 1 wherein the intermediate node transmits the packet responsive to receiving the packet, and further comprising the step of replicating the at least one packet before transmitting the packet.

4. The method of claim 1 wherein at least one node in the data network performs multicast routing by performing the steps of:

reading the packet received;

locating an address identifying the at least one node in the multicast routing information; and

replicating and forwarding the packet based on the instructions for the at least one node.

5. The method of claim 1 wherein the step of preparing at least one packet comprises determining the multicast routing information for the multicast flow.

6. The method of claim 5 wherein the step of preparing at least one packet comprises determining a route for each of the desired destinations.

7. The method of claim 5, wherein the step of preparing at least one packet comprises sending a unicast record-route packet, under the Internet Protocol (IP), to each desired destination and building a multicast distribution tree and multicast routing information.

8. The method of claim 5 wherein the step of preparing at least one packet step comprises using a traceroute program under the (IP).

9. The method of claim 1 further comprising the intermediate node step of:

receiving the packet transmitted by the source node and sending an Internet Control Message Protocol (ICMP) message when a new multicast tree is required.

10. The method of claim 1 further comprising the intermediate node steps of:

receiving the packet transmitted by the source node;

detecting that the source code requires new multicasting information; and

transmitting a message to the source node indicating that new multicasting information is required.

11. The method of claim 10 wherein the step of transmitting a message comprises transmitting an ICMP error message to the source node.

12. The method of claim 10 wherein the detecting step comprises the step of:

transmitting an ICMP message indicating that the routing information is incorrect at the intermediate node.

13. The method of claim 12 wherein the detecting step includes the step of:

transmitting an ICMP message indicating that the intermediate node does not have a route to at least one of the next hops specified in the received packet.

14. The method of claim 12 wherein the detecting step includes the step of:

transmitting an ICMP message indicating that the intermediate node must use for transmission the same link as the one it received the packet from, responsive to the received packet.

15. The method of claim 12 wherein the detecting step includes the step of:

transmitting an ICMP message indicating that the intermediate node must send multiple packets on the same link, responsive to the received packet.

16. The method of claim 10 wherein the source node uses a higher level protocol to inform the multicast function when connection quality deteriorates.

17. The method of claim 10 wherein the detecting step includes the step of:

receiving at the source node an ICMP error message from the intermediate node and modifying the routing tree responsive thereto.

18. The method of claim 1 wherein at least one intermediate node receives the packet transmitted by the source node, the intermediate node is not programmed to process the received multicast packet, and the method comprises the step of:

transmitting an ICMP error message from the intermediate node to the source node.

19. The method according to claim 1, wherein the multicast route information does not include identification of nodes that forward fewer than two copies of the packet.

20. A method for multicasting data packets in a packet-based data network comprising the steps of:

preparing at a source node where a multicast communications originates at least one packet under a first protocol comprising a payload portion and multicast route information so that the multicast route information causes the packet to be routed only once over any given route which is part of a multicast tree when the packet is simultaneously sent to more than one destination node; and

transmitting the packet from a source node to a first node, the packet comprising a header and a payload containing an encapsulated multicast (“

EM”

) datagram, the EM datagram comprising an CM header and an EM payload;

the EM header comprising multicastrouting information instructing the first node to transmit the EM payload to at least second and third nodes;

wherein the method does not require the source node to transmit the packet to a centralized entity and the method does not require multicast routing information be stored at intermediate nodes, and

wherein the multicast route information comprises a plurality of route definitions, wherein at least two route definitions within the plurality of route definitions share a common node and wherein the at least two route definitions have been folded so that nodes beyond the common node that are beyond the common node and within the at least two route definitions are grouped and identified as routing information for the packet beyond the common node, and wherein the common node is only specified once.

21. The method of claim 20 wherein the multicast routing information is recursively nested at a variable depth within the packet.

22. The method of claim 20 wherein the routing information further comprises instructions for instructing the second node to transmit the EM payload to a fourth node.

23. The method of claim 20 wherein the first protocol is the IP.

24. The method of claim 20 wherein the first protocol header comprises a destination address identifying the first node and a protocol field identifying the EM protocol to be used.

25. The method of claim 20 wherein the EM header comprises at least one byte indicating the header length and a plurality of bytes that include multicast routing information.

26. The method of claim 20 wherein the EM header comprises a version number identifying the version of the specified protocol being used.

27. The method of claim 20 wherein the EM header comprises a header checksum.

28. The method of claim 20 wherein the packet comprises a marker indicating the end of the multicast routing information.

29. A computer readable medium comprising instructions for:

transmitting an IP packet from a source node where a multicast communications originates to a first node, the IP packet comprising an IP header and an IP payload containing an encapsulated multicast (EM) datagram, the EM datagram comprising an EM header and an EM payload;

the EM header comprising multicast routing information instructing the first node to transmit the EM payload to at least two second and third nodes, without the need to transmit the packet to a centralized entity and without the need to store multicast routing information at tho first nodo;

wherein the multicast routing information causes the packet to be routed only once over any given route which is part of a multicast tree when the packet is simultaneously sent to at least two second and third nodes, and

wherein the multicast routing information comprises a plurality of route definitions, wherein at least two route definitions within the plurality of route definitions share a common node and wherein the at least two route definitions have been folded so that nodes beyond the common node that are beyond the common node and within the at least two route definitions are grouped and identified as routing information for the packet beyond the common node, and wherein the common node is only specified once.

30. The medium of claim 29 wherein the multicast routing information is recursively nested at a variable depth within the IP packet.

31. The medium of claim 29 wherein the EM header further comprises routing information instructing the second node to transmit the EM payload to at least a fourth node.

32. The medium of claim 29 wherein the EM header further comprises routing information instructing the third node to transmit the EM payload to at least a fourth node.

33. The medium of claim 29 wherein the IP header comprises a destination address identifying the first node and a protocol field identifying the EM protocol to be used.

34. The medium of claim 29 wherein the EM header comprises at least one byte indicating the header length and a plurality of bytes that include multicast routing information.

35. The medium of claim 29 wherein the EM header further comprises a version number identifying the version of the specified protocol being used.

36. The medium of claim 29 wherein the EM header further comprises a header checksum.

37. The medium of claim 29 wherein the EM header further comprises a marker indicating the end of the multicast routing information.

38. A method for multicasting data packets in a packet-based data network comprising the steps of:

receiving at least one data packet, wherein the at least one data packet includes multicast routing information for forwarding specified packets to at least two other nodes, without the need to transmit the packet to a centralized entity and without the need to store multicast routing information at intermediate nodes;

processing the multicast routing information included in the at least one data packet to determine downstream routing; and

preparing at least two data packets for transmission to at least two nodes, and sending those data packets;

wherein the multicast routing information causes the packet to be routed only once over any given route which is part of a multicast tree when the packet is simultaneously sent to more than one destination node, and

wherein the multicast route information comprises a plurality of route definitions, wherein at least two route definitions within the plurality of route definitions share a common node and wherein the at least two route definitions have been folded so that nodes beyond the common node that are beyond the common node and within the at least two route definitions are grouped and identified as routing information for the packet beyond the common node, and wherein the common node is only specified once.

39. A method for preparing at least one multicast packet, for use in a packet-based data network, comprising the step of:

creating at a source node where a multicast communications originates a header designating at least two destination nodes;

creating a payload portion comprising data to be delivered to the at least two destination nodes; and

including, in the packet, multicast routing information for use by at least one intermediate node to mute the multicast packets to at least two destination nodes, without the need to transmit the packet to a centralized entity and without the need to store multicast routing information at the at least one intermediate node;

wherein the multicast routing information causes the packet to be routed only once over any given route which is part of a multicast tree when the packet is simultaneously sent to more than one destination node, and

wherein the multicast route information comprises a plurality of route definitions, wherein at least two route definitions within the plurality of route definitions share a common node and wherein the at least two route definitions have been folded so that nodes beyond the common node that are beyond the common node and within the at least two route definitions are grouped and identified as routing information for the packet beyond the common node, and wherein the common node is only specified once.

40. The method of claim 39 wherein the step of including multicast routing information in the packet further comprises including the multicast routing information in the payload portion.

41. The method of claim 39 wherein the multicast routing information is recursively nested to an variable depth within the at least one packet and available to each of the intermediate nodes that is to route the payload to a destination node.

42. A multicast packet comprising:

a data payload;

a header identifying a source node where a multicast communications originates, at least an intermediate node, and a protocol type;

the payload including routing information for use by the intermediate node to route the multicast packet to at least two other nodes, without the need to transmit the packet to a centralized entity and without the need to store multicast routing information at the intermediate node;

wherein the multicast routing information causes the packet to be routed only once over any given route which is part of a multicast tree when the packet is simultaneously sent to more than one destination node, and

wherein the multicast route information comprises a plurality of route definitions, wherein at least two route definitions within the plurality of route definitions share a common node and wherein the at least two route definitions have been folded so that nodes beyond the common node that are beyond the common node and within the at least two route definitions are grouped and identified as routing information for the packet beyond the common node, and wherein the common node is only specified once.

43. A data network system comprising a plurality of nodes, wherein at least some of the plurality of nodes comprise:

means for preparing at a source node where a multicast communications originates at least one packet comprising a payload portion and a multicast route information so that the multicast route information causes the packet to be routed only once over any given route which is part of a multicast tree when the packet is simultaneously sent to more than one destination node and wherein the multicast route information comprises a plurality of route definitions, wherein at least two route definitions within the plurality of route definitions share a common node and wherein the at least two route definitions have been folded so that nodes beyond the common node that are beyond the common node and within the at least two route definitions are grouped and identified as routing information for the packet beyond the common node, and wherein the common node is only specified once; and

means for transmitting multicast packets from the source node to two or more destination nodes including a payload and multicast route information for use by intermediate nodes to route the packets to designated destinations, without the need to transmit the packets to a centralized entity and without the need to store multicast routing information at the intermediate nodes; and

means for receiving data.

44. The data network system according to claim 43, wherein the multicast route information does not include identification of nodes that forward fewer than two copies of the packet.