Multicast routing algorithm

• US 4,740,954 A
• Filed: 12/31/1986
• Issued: 04/26/1988
• Est. Priority Date: 12/31/1986
• Status: Expired due to Term

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Sincoskie, Walter D., Feldman, Stuart I., Cotton, Charles J.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Marcelo, Melvin
• Application Number:
  US06/948,115
• Time in Patent Office: 482 Days
• Field of Search: 370/60, 370/94, 370/62, 370/54, 370/88, 340/825.02, 340/825.07, 340/825.52
• US Class Current: 370/408
• 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

Abstract

A method for routing data packets correctly and efficiently among a plurality of hosts in a multicast is disclosed. The hosts are connected to a packet switching network comprising a plurality of packet switches interconnected by trunks. A memory associated with the route controller in each switch maintains a table whose entries are tuples of the form <address, trunk identification number, time>. In the case of multicast routing, the address is a multicast address. The trunk identification number is a number which uniquely identifies each of the trunks connected to the switch. Time is a timing parameter which is initially set to a certain predetermined value (designated Maxtime herein) and decremented periodically. When time reaches zero, the associated table entry is cleared. When a host wishes to join a multicast conversation (even if it is the first participant), it simply transmits a packet from itself to the multicast adddress. This packet will be broadcast over the entire spanning tree network. The host then continues to send packets to the multicast address, with a maximum interpacket time interval, smaller than Maxtime, to insure that at least one of the relevant table entries is not cleared.

Claims

1. A method for routing data packets among the members of a multicast in a packet switching network comprising switches interconnected by trunks, said method comprising the steps of:

maintaining in at least one of said switches a table wherein each entry includes a multicast address and trunk identification number,

receiving at said one switch by way of a trunk T, a packet destined to multicast address M,

searching said table for entries including the address M,

if the table includes no entry containing the address M, inserting an entry including the values M and T into the table, transmitting the packet on all trunks connected to said switch except the trunk T, and stopping further processing of said packet,

if the table includes one or more entries with the address M, but no entries with both the values M and T, inserting an entry with the values M and T into the table, and

if the table includes one or more entries with the address M, transmitting the packet on the trunks indicated in said entries, but not on the trunk T, and stopping further processing of said packet.

2. The method of claim 1 wherein said switches and trunks are arranged to form a spanning tree.

3. The method of claim 1 wherein each table entry includes a time parameter and said method includes the step of regularly decrementing said time parameter.

4. The method of claim 3 wherein the time parameter in a particular table entry is reset to a maximum value when a packet destined to the multicast address contained in said particular entry is received on the trunk contained in said particular entry.

5. The method of claim 4, wherein a particular table entry is cleared if, within a predetermined time interval, no packet destined to the multicast address contained in said particular entry is received on the trunk contained in said particular entry.

6. The method of claim 1 wherein each table entry includes a time parameter and said method includes the step of varying the time parameter in equal steps between an initial value and a final value.

7. A method for routing data packets among the members of a multicast in a packet switching network comprising switches interconnected by trunks, said method comprising the steps of:

maintaining in at least one switch a table of entries, each entry comprising a multicast address, a trunk identification number, and a time parameter which is regularly varied in equal steps,

receiving at said one switch a packet destined to multicast address M from trunk T,

looking up entries including said address M in said table,

if M is not in said table, inserting into said table an entry including M, T and an initial value of the time parameter, transmitting said packet over all trunks connected to said switch except trunk T, and stopping further processing of said packet,

if said table includes an entry containing M but not T, transmitting said packet on the trunk in said entry, and adding an entry including M, T, and the initial value of the time parameter, and

if said table includes an entry with M and T resetting said time parameter to its initial value, and stopping all further processing of the packet.

8. The method of claim 7 wherein said initial value of said time parameter is the maximal value of said time parameter and said time parameter is decremented downward from its maximal value.

9. A method for routing packets among a plurality of hosts in a multicast, said hosts being connected to a packet switch network, said method comprising the steps of:

transmitting a packet addressed to a specific multicast address from a first host to a plurality of packet switches in said network interconnected by trunks,

transmitting further packets from said first host to said specific multicast address, the time separation between said packets from said first host being less than or equal to a predetermined time interval,

transmitting packets to said specific multicast address from one or more other hosts, said packets from said other hosts being routed only to hosts participating in said multicast, and

maintaining at least one of said packet switches a table whose entries each comprise a multicast address and a trunk identification number.

10. The method of claim 9 wherein a host is dropped from said multicast by not transmitting a packet to said multicast address within a time that exceeds said predetermined interval.

11. The method of claim 10 wherein if one of said hosts moves from a first location to a second location in said network while engaged in said multicast, subsequent to the movement of said one host, said network ceases transmission of packets to said first location by deleting selected table entries.