Method and system for creating small group multicast over an existing unicast packet network

• US 6,785,275 B1
• Filed: 03/13/2000
• Issued: 08/31/2004
• Est. Priority Date: 03/13/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boivie, Richard Harold, Maruyama, Kiyoshi
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US09/524,410
• Time in Patent Office: 1,632 Days
• Field of Search: 370/390, 370/393, 370/401, 370/408, 370/397, 709/238, 398/82
• US Class Current: 370/390
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/16 Multipoint routing

Abstract

A routing table for use with a router in a world-wide network, includes an existing routing table with a multicast-destination (MD) column.

Claims

1. A routing table in a router in a wide-area packet-switched network, said routing table comprising:

a plurality of conventional routing table columns, including columns for destination D, next-node NN, and distance to destination d(D); and

a multicast destination (MD) column having a capability to list a unicast address.

2. The routing table according to claim 1, wherein said MD column represents that, for each destination row in the routing table, an MD entry exists for use by a multicast-capable router when it has received a multicast packet for routing.

3. The routing table according to claim 1, wherein for each destination node D, the MD entry indicates either destination address Dmc of a multicast-capable router Rmc in the network or the destination D itself.

4. The routing table according to claim 3, wherein if the MD entry is equal to D when there is no router Rmc along a predetermined shortest route from a current router to a destination D.

5. The routing table according to claim 3, wherein the MD entry is equal to Dmc when there is a router Rmc along a predetermined shortest route to the destination D.

6. The routing table according to claim 1, wherein a source node (S) of a multicast packet creates a multicast packet of the form (S,Dmc,1(D1,D2, . . . ,Dk)) where address Dmc is the nearest router Rmc to the source node.

7. The routing table according to claim 6, wherein said source node is informed of the destination address Dmc of the nearest multicast-capable router Rmc.

8. The routing table according to claim 6, wherein said source node performs a discovery method to locate the nearest router Rmc.

9. The routing table according to claim 3, wherein if a received packet comprises a multicast packet, the packet is routed to its destination Dmc by referencing said routing table, and

wherein when a packet has been received by a multicast-capable router Rmc, said Rmc router first checks whether or not the specified destination is itself, and, if the destination is not itself, the Rmc router processes the packet as a unicast packet and routes the packet,

wherein if the destination is itself and said packet comprises a multicast packet, then the packet is processed with a multicast-routing process.

10. The routing table according to claim 9, wherein said multicast-routing process comprises:

referencing the MD column of the routing table to perform a packet regeneration and routing process.

11. The routing table according to claim 10, wherein said packet regeneration process creates either unicast packets or multicast packets with no duplication thereof, and forwards the created packets to an existing Internet Protocol (IP) unicast packet routing process.

12. The routing table according to claim 11, wherein each regenerated packet is routed as a unicast packet and is sent to a next-node by referencing the routing table, and wherein a last multicast capable router Rmc to a destination node D creates a unicast packet, such that each destination node receives a unicast packet.

13. The routing table according to claim 9, wherein said each multicast packet carries multicast destinations, and its Internet Protocol (IP) destination address includes one of the multicast-capable routers in the network.

14. The routing table according to claim 6, wherein the source node knows its nearest router Rmc so that any multicast packet created by said source node is sent to the nearest known router Rmc having said address Dmc for multicasting, and

wherein if the source node is unaware of such a router Rmc, the source node is prevented from creating a multicast packet, and creates only a unicast packet for each destination.

15. The routing table according to claim 6, wherein each source node is informed of its nearest router Rmc when said source node joins a network.

16. The routing table according to claim 6, wherein each source node performs a discovery process to each multicast destination to find the nearest router Rmc.

17. The routing table according to claim 6, wherein a discovery process is run to provide said routing table, said discovery process including running a traceroute to a destination, and sending each node along the traceroute a multicast packet having the form (S,Dt,1(S)), where Dt is a node along the traceroute, wherein said sending is performed from the nearest node Dt first.

18. The routing table according to claim 6, wherein when said node Dt comprises a router Rmc, a unicast packet of (S,S) or an Internet Control Message Protocol (ICMP) message is returned to the source node,

when a unicast packet of (S,S) has been received from said node Dt and if the return is the first return, then said node Dt is chosen as the nearest router Rmc to the source node S.

19. A routing system, including:

a routing unit for updating a next-node (NN) column of a routing table and for routing unicast packets by referencing the NN column of the routing table;

a packet regeneration unit for referencing the multicast destination (MD) column of the routing table and for selectively creating copies of at least one of unicast and multicast packets; and

a multicast-destination (MD) discovery unit for updating the MD column of the routing table.

20. A method of processing a packet, comprising:

receiving a packet at a router;

checking, by said router, if the packet'"'"'s destination is itself or not;

if the packet'"'"'s destination is not the router, then routing said packet in a predetermined manner; and

if the received packet'"'"'s destination is itself and if the packet is a multicast packet such that MC=1, then forwarding the packet to a packet regeneration process.

21. The method according to claim 20, wherein the packet regeneration processing includes:

for a packet having a form of (S,Dmc,1(D1,D2, . . . ,Dk)), for each destination, D1 through Dk, finding the multicast destination MD from the routing table;

for those destinations having a same MD, generating a multicast packet having a form (S,MD,1(destinations)) with remaining fields in the packet the same as an originally received packet; and

for each of those destinations where the MD entry is the same as the destination such that MD=D, creating a unicast packet of the form (S, D) with remaining fields in the packet the same as the originally received packet.

22. The method according to claim 21, wherein the packet regeneration processing further includes:

providing the regenerated packets to the predetermined routing process for routing.

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

running an MD discovery process for each and every destination periodically.

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

running a multicast destination (MD) discovery process for each destination whenever a portion of the routing table has changed, a multicast-capable router has been added, or any router has been upgraded to be multicast-capable.

25. The method according to claim 23, wherein said MD discovery process includes:

setting MD=D for every destination D in the routing table;

running a traceroute to destination D, to generate a sequence of routers Dt to the destination D; and

based on the sequence of routers to the destination D, forwarding a test multicast packet of form (S, Dt, 1(S)) to a nearest router Dt, and finding the first router Dt which returns the unicast message of (S, S) or the router Dt returns no ICMP.

26. The method according to claim 25, wherein said Dt is the nearest Rmc and its address Dmc is placed in the MD entry of the routing table for the destination D, and wherein when no Rmc has been found, the MD value remains as D itself.

27. A method for extending a routing table, comprising:

adding a multicast-destination (MD) column to an existing routing table, wherein said MD column represents that, for each destination row in the routing table, there is an MD entry for use by a multicast-capable router when it has received a multicast packet for routing.

28. A method of using a routing table, comprising:

referencing a column (MD) of a routing table to perform a packet regeneration and routing process,

wherein said MD column represents that, for each destination row in the routing table, there is an MD entry for use by a multicast-capable router when it has received a multicast packet for routing.

29. A method of learning of a nearest multicast-capable router by a source node, comprising:

running a traceroute to a destination; and

sending each node along the traced route a multicast packet having the form (S,Dt,1(S)), where Dt is a node along the traced route, and wherein such sending is performed first from a nearest node Dt.

30. The method according to claim 29, wherein when node Dt comprises a router Rmc, a unicast packet of (S,S) or an Internet Control Message Protocol (ICMP) message is returned to the source node,

when a unicast packet of (S,S) has been received from node Dt and if the return is the first return, then node Dt is chosen as the nearest router Rmc to the source node.

31. A method of regenerating a packet in a router in a network, comprising:

for a packet having a form of (S,Dmc,1(D1,D2, . . . ,Dk)), for each destination, D1 through Dk, finding the multicast destination (MD) from a routing table;

for those destinations having the same MD, generating a multicast packet having a form (S,MD,1(destinations)) with remaining fields in the packet the same as an originally received packet; and

for each of the destinations where the MD is the same as the destination such that MD=D, creating a unicast packet of the form (S, D) with remaining fields in the packet the same as the originally received packet.

32. The method according to claim 31, wherein the packet regeneration processing further includes:

providing the regenerated packets to an existing routing process for routing.

33. A programmable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of extending an existing routing table, comprising:

including a multicast-destination (MD) column in said routing table such that the MD column is for packet regeneration.

34. A programmable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of processing a packet, said method comprising:

receiving a packet at a router;

checking, by said router, if the packet'"'"'s destination is itself or not;

if the packet'"'"'s destination is not the router, then routing said packet in a predetermined manner; and

if the received packet'"'"'s destination is itself and if an entry in a routing table indicates that the packet is a multicast packet (e.g., MC=1), then forwarding the packet to a packet regeneration process.

35. 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 in a router in a network, said method comprising:

for a packet having a form of (S,Dmc,1(D1,D2, . . . ,Dk)), for each destination, D1 through Dk, finding the multicast destination (MD) from a routing table;

for those destinations having the same MD, generating a multicast packet having a form (S,MD,1(destinations)) with remaining fields in the packet the same as an originally received packet; and

for each of the destinations where the MD is the same as the destination such that MD=D, creating a unicast packet of the form (S, D) with remaining fields in the packet the same as the originally received packet.

36. A programmable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of learning of a nearest multicast-capable router by a source node, said method comprising:

running a traceroute to a destination; and

sending each node along the traced route a multicast packet having the form (S,Dt,1(S)), where Dt is a node along the traced route, and wherein such sending is performed first from a nearest node Dt.