System and method for amicable small group multicast in a packet-switched network

• US 6,757,294 B1
• Filed: 03/13/2000
• Issued: 06/29/2004
• Est. Priority Date: 03/13/2000
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Maruyama, Kiyoshi
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US09/524,409
• Time in Patent Office: 1,569 Days
• Field of Search: 370/401, 370/408, 370/428, 370/390, 370/432, 370/393, 370/402, 709/238, 709/250, 713/162
• US Class Current: 370/432
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• 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

Abstract

A method (and system) of creating a multicast packet by a source node in a world-wide network, includes providing each multicast packet with a predetermined indicator indicating that the packet includes a multicast packet, one of a plurality of multicast destinations being placed in a packet destination field and a list of remaining multicast destinations being provided in a packet header. A conventional router receiving a multicast packet handles it as a unicast packet and routes it in a conventional manner. A multicast-capable router receiving a multicast packet goes through a packet regeneration and routing process, creating multicast packets and/or unicast packets and then routing them using the conventional routing table. A destination node receiving a multicast packet goes through the packet regeneration and forwarding process, creating a multicast or unicast packet depending on the number of destinations in the received multicast packet and bouncing back the regenerated packet to the router to which the node is attached.

Claims

1. A method of creating a multicast packet by a source node in a world-wide network, comprising:

providing each multicast packet with a predetermined indicator indicating that the packet comprises a multicast packet,

one of a plurality of multicast destinations being placed in a packet destination field and a list of remaining multicast destinations being provided in a packet header.

2. The method according to claim 1, wherein any packet judged not to have said predetermined indicator is judged to be a unicast packet having a destination field carrying the packet destination itself.

3. The method according to claim 1, wherein said multicast packet is denoted by (S, Dp, 1(D1,D2, . . . ,Dk)) where S is the source node, Dp is a packet primary destination, and D1 through Dk are multicast destinations.

4. The method according to claim 1, wherein a routing table informs, for each destination D, to which next node a packet is to be routed to allow said packet to eventually reach the destination D.

5. The method according to claim 1, wherein said source node (S) creates said multicast packet having a form (S, Dp, 1(D1,D2, . . . ,Dk)) where Dp is one of the multicast destinations and D1 through Dk are the remaining k destinations such that there are k+1 multicast destinations in total and wherein Dp is a primary destination of the multicast packet.

6. The method according to claim 5, wherein the source node S randomly chooses one destination from the k+1 destinations, and sets the selected destination as the primary destination Dp of the multicast packet.

7. The method according to claim 1, further comprising:

judging a distance from the source node to all of the plurality of multicast destinations, and selecting a destination which is judged to be nearest to the source node.

8. The method according to claim 1, wherein when a conventional router, other than a multicast-capable router, has received a multicast packet, said router routes the packet to its destination Dp by referring to a routing table.

9. The method according to claim 1, further comprising:

when a packet has been received by a multicast-capable router, Rmc, judging whether or not the packet comprises a multicast packet.

10. The method according to claim 9, wherein if the packet is not judged to comprise a multicast packet, then the router processes and routes the packet as a unicast packet.

11. The method according to claim 1, further comprising:

if the packet is judged to comprise a multicast packet, then forwarding said packet to a packet regeneration process for creating multicast and/or unicast packets with selected destinations and forwarding the packets to a predetermined routing process, said predetermined routing process routing the regenerated packets as if the packets were unicast packets by referencing the routing table.

12. The method according to claim 1, further comprising:

when a packet arrives at a destination node D, said destination node D determines whether a primary destination node Dp is equal to destination node D, and checks whether the packet comprises a unicast packet or a multicast packet.

13. The method according to claim 12, wherein if the received packet is judged to comprise a unicast packet, no further routing of the packet occurs.

14. The method according to claim 12, wherein if the received packet is judged to comprise a multicast packet, then the destination D performs a packet regeneration and forwarding process.

15. The method according to claim 14, wherein said packet regeneration process comprises creating a packet with one of k destinations as the primary destination and eliminating the primary destination from the list of k destinations to create a list of k−

1 destinations.

16. The method according to claim 15, wherein the forwarding process includes sending the regenerated packet to any router to which the destination node attaches.

17. The method according to claim 1, wherein when a packet is received at a multicast-capable router, the router judges whether the packet comprises a multicast or unicast packet, wherein if said packet is judged to comprise the unicast packet, then said unicast packet is routed.

18. The method according to claim 17, wherein if the packet is judged to comprise a multicast packet, then the multicast packet is forwarded to a packet regeneration process.

19. The method according to claim 18, wherein said packet regeneration process processes a packet (S,Dp,1(D1,D2, . . . ,Dk)) such that for each destination, Dp, D1 through Dk, find its next-node (NN) from a routing table.

20. The method according to claim 19, further comprising:

for destinations judged to have the same next-node (NN), generating a multicast packet.

21. The method according to claim 20, wherein said generating of said multicast packet comprises one of setting MC=1 if the number of destinations is more than one, and setting MC=0 if the number of destinations is no more than one.

22. The method according to claim 21, further comprising:

selecting a nearest destination as a packet primary destination; and

maintaining remaining fields in the packet the same as the originally received packet.

23. The method according to claim 21, further comprising:

selecting a random destination as a packet primary destination; and

maintaining remaining fields in the packet the same as the originally received packet.

24. The method according to claim 22, further comprising:

forwarding the regenerated packet to the predetermined routing process for routing.

25. The method according to claim 23, further comprising:

forwarding the regenerated packet to the predetermined routing process for routing.

26. The method according to claim 1, each multicast destination node includes, packet regeneration and forwarding capability.

27. The method according to claim 1, wherein when a destination node D receives a multicast packet of the form (S,Dp,1(D1,D2, . . . ,Dk)), node D judges whether Dp is equal to D, and then checks to determine whether the packet comprises a multicast packet.

28. The method according to claim 27, wherein if the packet comprises a unicast packet, then the processing terminates.

29. The method according to claim 28, wherein if the packet comprises a multicast packet, then the node D performs a regeneration and forwarding process.

30. The method according to claim 29, wherein said regeneration and forwarding process comprises:

creating a multicast packet by setting source node S as the packet source address, selecting one destination from destinations D1 through Dk as the primary destination of the packet, one of setting MC=1 if the number of destinations is greater than 1 and setting MC=0 if the number of destinations is no more than 1, attaching a list of remaining k−

1 destinations, and setting remaining fields of said packet to be regenerated the same as those of the originally received packet.

31. The method according to claim 30, further comprising forwarding the regenerated packet to a router attached thereto.

32. A method of regenerating and routing a packet by a multicast capable router in a world-wide network, comprising:

receiving a multicast packet of the form (S,Dp,1(D1,D2, . . . . ,Dk)), where S denotes a source node, Dp denotes a primary destination, D1,D2, . . . ,Dk denotes a remainder of destinations, and “

1”

denotes that the packet is multicast;

for each destination, Dp, D1 through Dk, finding its next-node (NN) from a routing table;

judging whether any one of the destinations have the same next node (NN) as another destination; and

for the destinations judged to have the same next-node (NN), generating a multicast packet.

33. The method according to claim 32, wherein said generating of a multicast packet comprises:

determining whether a number of destinations with the same NN is greater than 1;

if the number of destination is judged to be greater than 1, then setting said indicator MC to 1 and selecting one of the destinations as a packet primary destination;

maintaining remaining fields in the packet to be regenerated the same as the originally received packet; and

forwarding the regenerated packet to the predetermined routing process.

34. The method according to claim 33, wherein if no destinations share a same NN, then MC is set to 0 and the packet is routed to the predetermined routing process.

35. The method according to claim 32, wherein if none of the destinations has the same next node (NM) as another destination, then a unicast packet is created for each destination and processed in a predetermined manner.

36. A method of handling, by a destination node in a world-wide network, each received multicast packet, comprising:

when a packet arrives at said destination node D, said destination node determining whether a primary destination node Dp is equal to the destination node D, and determining whether the packet comprises a unicast packet or a multicast packet; and

if the received packet is judged to comprise a multicast packet, performing, by said destination D, a packet regeneration and forwarding process,

wherein said packet regeneration process comprises;

creating a packet with one of k destinations as the primary destination and eliminating the primary destination from the list of k destinations to create a list of k−

1 destinations; and

sending the regenerated packet to any router to which the regenerated packet attaches.

37. The method according to claim 36, wherein said packet regeneration process creates a new packet from the received packet (S,Dp,1(D1,D2, . . . ,Dk)) such that one destination from D1 through Dk is selected as a primary destination and is placed into the packet destination field.

38. The method according to claim 37, wherein said generating of said multicast packet comprises one of setting MC=1 if the number of destinations is more than one, and setting MC=0 if the number of destinations is no more than one.

39. The method according to claim 38, further comprising:

selecting a nearest destination as the packet primary destination;

removing the selected destination from the list of destinations; and

maintaining remaining fields in the regenerated packet the same as the originally received packet.

40. The method according to claim 38, further comprising:

selecting a random destination as the packet primary destination;

removing the selected destination from the list of destinations; and

maintaining remaining fields in the regenerated packet the same as the originally received packet.

41. The method according to claim 40, further comprising forwarding the regenerated packet to the router to which it is attached.

42. The method according to claim 36, wherein said regeneration and forwarding process comprises:

creating a packet by setting source node S as a packet source address, selecting one destination from destinations D1 through Dk as the primary destination of the packet, setting MC=1 if the number of destinations is greater than 1 and setting MC=0 if the number of destinations is no more than 1, attaching a list of remaining k−

1 destinations, and setting remaining fields of the regenerated the same as those of the originally received packet.

43. A method of regenerating a packet by a receiving destination node in a world-wide network, comprises:

determining a number of remaining multicast destinations in the received packet;

providing a packet with a predetermined indicator indicating the packet comprises a multicast when the remaining number of multicast destinations is more than one, or indicating the packet comprises a unicast packet when the remaining number of multicast destinations is one, one of the plurality of multicast destinations being placed in the packet destination field and a list of remaining multicast destinations being provided in the packet header; and

forwarding the regenerated packet to the router from which the original packet was received.

44. A programmable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of creating a multicast packet by a source node in a world-wide network, the method comprising:

providing each multicast packet with a predetermined indicator indicating that the packet comprises a multicast packet,

one of a plurality of multicast destinations being placed in a packet destination field and a list of remaining multicast destinations being provided in a packet header.

45. A programmable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of regenerating and routing a packet by a multicast capable router in a world-wide network, comprising:

for each destination, Dp, D1 through Dk, finding its next-node (NN) from a routing table;

judging whether any one of the destinations have the same next node (NN) as another destination; and

for the destinations judged to have the same next-node (NN), generating a multicast packet having a predetermined indicator indicating that the packet comprises a multicast packet.

46. A programmable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of handling, by a destination node in a world-wide network, each received multicast packet, said method comprising:

when a packet arrives at said destination node D, said destination node determining whether a primary destination node Dp is equal to the destination node D, and determining whether the packet comprises a unicast packet or a multicast packet; and

if the received packet is judged to comprise a multicast packet, performing, by said destination D, a packet regeneration and forwarding process,

wherein said packet regeneration process comprises;

creating a packet with one of k destinations as the primary destination and eliminating the primary destination from the list of k destinations to create a list of k−

1 destinations; and

sending the regenerated packet to any router to which the regenerated packet attaches.

47. A programmable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of regenerating a packet by a receiving destination node in a world-wide network, said method comprising:

determining a number of remaining multicast destinations in the received packet;

providing a packet with a predetermined indicator indicating the packet comprises a multicast when the remaining number of multicast destinations is more than one, or indicating the packet comprises a unicast packet when the remaining number of multicast destinations is one, one of the plurality of multicast destinations being placed in the packet destination field and a list of remaining multicast destinations being provided in the packet header; and

forwarding the regenerated packet to the router from which the original packet was received.