Efficient path based forwarding and multicast forwarding

• US 6,216,167 B1
• Filed: 06/29/1998
• Issued: 04/10/2001
• Est. Priority Date: 10/31/1997
• Status: Expired due to Term

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Momirov, Milan
• Primary Examiner(s): Luu, Le Hien
• Assistant Examiner(s): Jaroenchonwanit, Bunjob
• Application Number:
  US09/106,797
• Time in Patent Office: 1,016 Days
• Field of Search: 709/238, 709/235, 709/236, 709/239, 709/240, 709/242, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/351, 370/229, 370/230, 370/376, 370/388, 370/389, 370/390, 710/56, 710/57
• US Class Current: 709/238
• 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/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and apparatus for efficiently switching cells through a switch fabric are provided. According to one aspect of the present invention, logic for forwarding and filtering multicast data is distributed among various layers of a network device, such as a switch, router, bridge, or the like. Data is received at a first port of an input/output (I/O) card. A multicast group identifier corresponding to the data is determined. The data and the multicast group identifier are then transferred to a switching card which indexes into a first set of correlation data with the multicast group identifier to identify a set of egress forwarding paths that lead to I/O cards having members of the multicast group. The switching card forwards the data to the I/O cards via the set of egress forwarding paths identified. For their part, the I/O cards identify a set of ports associated with the multicast group by indexing into a second set of correlation data and forwarding the data to each of the ports identified. According to another aspect of the present invention, a network device comprises a backplane, multiple I/O cards, and a switch core. Correlation data, e.g., in the form of tables indexed by multicast group identifiers, is distributed between the I/O cards and the switch core. The I/O cards each include multiple ports, a first set of correlation data, and a forwarding and filtering mechanism. The first set of correlation data maps multicast group identifiers to ports that are members of the corresponding multicast groups. The forwarding and filtering mechanism is configured to forward multicast data based upon the first set of correlation data. The switch core includes a second set of correlation data and a forwarding and filtering mechanism. The switch core'"'"'s forwarding and filtering mechanism is configured to forward multicast data to member I/O cards based upon the second set of correlation data which maps multicast group identifiers to I/O cards that include member ports.

Claims

1. A method of forwarding multicast data through a network device, the method comprising the steps of:

receiving data at a first port of an input/output (I/O) card;

determining a multicast group identifier corresponding to the data;

transferring the data and the multicast group identifier to a switching card;

the switching card performing the steps of indexing into a first set of correlation data with the multicast group identifier to identify a set of egress forwarding paths that lead to input/output (I/O) cards having members of a multicast group corresponding to the multicast group identifier; and

forwarding the data and the multicast group identifier to one or more I/O cards via the set of egress forwarding paths identified; and

the one or more I/O cards performing the steps of indexing into a second set of correlation data with the multicast group identifier to identify a set of ports on the I/O card associated with the multicast group identifier, and forwarding the data to each of the ports in the set of ports identified.

2. The method of claim 1, wherein the one or more I/O cards further performing the steps of:

indexing into a third set of correlation data to identify a set of port interface devices (PIDs) on the I/O card that lead to ports that are associated with the multicast group; and

forwarding the data to each of the PIDs in the set of PIDs identified.

3. The method of claim 1, wherein the first set of correlation data is stored locally on the switching card, wherein the first set of correlation data comprises a table correlating multicast group identifiers with egress forwarding paths from the switching card to I/O cards, and wherein the step of indexing into a first set of correlation data with the multicast group identifier to identify a set of egress forwarding paths that lead to input/output (I/O) cards having members of a multicast group corresponding to the multicast group identifier further includes accessing a vector corresponding to the multicast group, the vector containing information indicative of the multicast group membership status of each egress forwarding path.

4. The method of claim 1, wherein the second set of correlation data is stored locally on a port interface device (PID) of the I/O card, wherein the second set of correlation data comprises a table correlating multicast group identifiers with a plurality of physical ports associated with the PID, and wherein the step of indexing into a second set of correlation data to identify a set of ports on the I/O card associated with the multicast group further includes accessing a vector corresponding to the multicast group, the vector containing information indicative of the multicast group membership status of each of the plurality of physical ports.

5. The method of claim 2, wherein the third set of correlation data is stored locally on a switch access controller of the I/O card, wherein the third set of correlation data comprises a table correlating multicast group identifiers with a plurality of port interface devices (PIDs) associated with the I/O card, and wherein the step of indexing into a third set of correlation data to identify a set of PIDs on the I/O card that lead to ports that are associated with the multicast group further includes accessing a vector corresponding to the multicast group, the vector containing information indicative of the multicast group membership status of each of the plurality of PIDs.

6. A method of forwarding multicast data through a network device, the method comprising the steps of:

transferring multicast data received at a first port and a multicast group identifier corresponding to the multicast data to a switch core;

the switch core indexing into a first set of correlation data with the multicast group identifier to determine a set of egress forwarding paths that lead to ports that are members of a multicast group corresponding to the multicast group identifier;

the switch core forwarding the multicast data and the multicast group identifier onto the set of egress forwarding paths;

one or more I/O interfaces receiving the multicast data forwarded from the switch core and indexing into a second set of correlation data with the multicast group identifier to determine a set of ports associated with the multicast group identifier; and

the one or more I/O interfaces forwarding the multicast data to each of the ports in the set of ports.

7. The method of claim 6, wherein each of the one or more I/O interfaces are coupled to an egress forwarding path through a switch access controller, and wherein each switch access controller performs the steps of:

indexing into a third set of correlation data to determine a set of I/O interfaces that have ports that are members of the multicast group; and

forwarding the multicast data to each of I/O interfaces in the set of I/O interfaces.

8. The method of claim 6, wherein the first set of correlation data is stored locally in the switch core, wherein the first set of correlation data comprises a table mapping multicast group identifiers to egress forwarding paths from the switch core to I/O cards, and wherein the step of indexing into a first set of correlation data with the multicast group identifier to determine a set of egress forwarding paths that lead to ports that are members of a multicast group corresponding to the multicast group identifier further includes accessing a vector corresponding to the multicast group, the vector containing information indicative of the multicast group membership status of each egress forwarding path.

9. The method of claim 6, wherein the second set of correlation data is stored locally in the one or more I/O interfaces, wherein the second set of correlation data comprises a table mapping multicast group identifiers to physical ports, and wherein the step of indexing into a second set of correlation data to determine a set of ports associated with the I/O interface that are members of the multicast group further includes accessing a vector corresponding to the multicast group, the vector containing information indicative of the multicast group membership status of a plurality of physical ports associated with the I/O interface.

10. The method of claim 7, wherein the third set of correlation data is stored locally on the switch access controller, wherein the third set of correlation data comprises a table mapping multicast group identifiers to I/O interfaces, and wherein the step of indexing into a third set of correlation data to determine a set of I/O interfaces that have ports that are members of the multicast group further includes accessing a vector corresponding to the multicast group, the vector containing information indicative of the multicast group membership status of each of a plurality of I/O interfaces.

11. A networking device comprising:

a backplane;

a plurality of input/output (I/O) cards coupled to the backplane, each of the plurality of I/O cards comprising

a plurality of ports,

a first set of correlation data that maps multicast group identifiers to member ports, the member ports being those of the plurality of ports that are members of the corresponding multicast groups, and

a first forwarding and filtering mechanism configured to forward multicast data onto the member ports associated with said multicast group identifier based upon the first set of correlation data; and

a switch core coupled to the backplane, the switch core comprising

a second set of correlation data that maps multicast group identifiers to member I/O cards, the member I/O cards being those of the plurality of I/O cards that include one or more member ports, and

a second forwarding and filtering mechanism configured to forward multicast data to member I/O cards associated with said multicast group identifier based upon the second set of correlation data.

12. The networking device of claim 11, wherein the backplane comprises a plurality of buses.

13. The networking device of claim 11, wherein the second forwarding and filtering mechanism is configured to forward multicast data received at a port of the plurality of ports to member I/O cards over egress forwarding paths by:

accessing the second set of correlation data with a multicast group identifier corresponding to the multicast data to determine a set of egress forwarding paths that lead to I/O cards having members of a multicast group corresponding to the multicast group identifier; and

forwarding the multicast data to one or more I/O cards via the set of egress forwarding paths.

14. The networking device of claim 11, wherein the first forwarding and filtering mechanism is configured to forward multicast data received on an egress forwarding path to member ports by:

accessing the first set of correlation data with a multicast group identifier corresponding to the multicast data to determine a set of ports that are members of the multicast group; and

forwarding the multicast data onto each of the ports in the set of ports.