Multicast routing algorithm
First Claim
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, andif 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.
6 Assignments
0 Petitions
Accused Products
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.
-
Citations
11 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8)
-
-
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. - View Dependent Claims (10, 11)
-
Specification