Efficient multicast mapping in a network switch

• US 5,903,564 A
• Filed: 08/28/1997
• Issued: 05/11/1999
• Est. Priority Date: 08/28/1997
• Status: Expired due to Fees

• Current Assignee: Ascend Communications, Inc. (Nokia Corporation)
• Original Assignee: Ascend Communications, Inc. (Nokia Corporation)
• Inventors: White, David J., Ganmukhi, Mahesh N., Palnati, Prasasth R.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Tran, Maikhanh
• Application Number:
  US08/919,840
• Time in Patent Office: 621 Days
• Field of Search: 370/389, 370/390, 370/392, 370/395, 370/397, 370/399, 370/409, 370/413, 370/414, 370/412
• US Class Current: 370/399
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• 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/253 using establishment or release of connections between ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags

Abstract

An apparatus and technique for facilitating mapping of a Multicast Circuit Identifier ("MID") to a Local Circuit Identifiers ("CID") is disclosed. Table entries for such mapping can be disposed in non-contiguous memory locations. A pointer is employed in ca h entry to indicate the location of any subsequent memory location associated with the MID. CIDs and associated memory locations are allocated only for ports that participate in a connection. To implement the apparatus and technique a first table provides an index into a second table based upon the MID. The second table includes entries having a port identification field, a pointer field and a CID field. The CID field indicates the CID associated with the port indicated by the port identification field. The CID is written to the header of the copy of the cell to be transmitted to the indicated port. The pointer indicates further entries in the second table that are associated with other copies of the cell to be transmitted in the multicast connection, if such entries exist. The CID is employed to obtain a Virtual Path Identifier ("VPI") and Virtual Circuit Identifier ("VCI") from a third table.

Claims

1. A method for mapping a first identifier associated with a data unit to a second identifier associated with the data unit in a telecommunications switch having a plurality of ports, comprising the steps of:

assigning one entry per first identifier in a first memory table;

assigning one entry per second identifier in a second memory table;

writing, in at least one entry in the first table, a pointer to an entry in the second table;

writing, in at least one entry in the second table, a second identifier and a pointer to an entry in the second table;

employing the first identifier as an index into the first table to obtain a corresponding pointer from the first table;

employing the pointer obtained from the first table as an index into the second table to obtain a corresponding second identifier and pointer from the second table;

associating the second identifier obtained from the second table with the data unit; and

employing the pointer obtained from the second table to determine whether any further entry in the second table is applicable to the data unit.

2. The method of claim 1, wherein a further entry in the second table is determined to be applicable to the data unit, and including the further step of employing the pointer obtained from the second table as an index into the second table to obtain an additional corresponding second identifier and an additional pointer from the second table.

3. The method of claim 2 including the further step of associating the additional second identifier obtained from the second table with a copy of the data unit.

4. The method of claim 1 including the further step of writing a port identifier in each entry in the second table.

5. The method of claim 4 including the further step of transmitting the data unit through the port indicated by the port identifier.

6. The method of claim 1 wherein the switch includes a third memory table and including the further step of assigning one entry per second identifier in the third table.

7. The method of claim 6 including the further step of writing, in each entry in the third table, a Virtual Path Identifier and a Virtual Circuit Identifier.

8. The method of claim 7 including the further step of employing the second identifier obtained from the second table as an index into the third table to obtain a corresponding Virtual Path Identifier and Virtual Circuit Identifier from the third table, and associating the Virtual Path Identifier and Virtual Circuit Identifier obtained from the third table with the data unit.

9. Apparatus for mapping a first identifier associated with a data unit to a second identifier associated with the data unit in a telecommunications switch having a plurality of ports, comprising:

a first table having one entry per first identifier; and

a second table having one entry per second identifier;

said first table including a pointer to an entry in the second table in at least one entry and said second table including a second identifier and a pointer to an entry in the second table in at least one entry, wherein the first identifier is employed as an index into the first table to obtain a corresponding pointer from the first table, and the pointer obtained from the first table is employed as an index into the second table to obtain a corresponding second identifier and pointer from the second table, the second identifier obtained from the second table being associated with the data unit and the pointer obtained from the second table being employed to determine whether any further entry in the second table is applicable to the data unit.

10. The apparatus of claim 9 wherein, when a further entry in the second table is determined to be applicable to the data unit, the pointer obtained from the second table is employed as an index into the second table to obtain-?n an additional corresponding second identifier and an additional pointer from the second table.

11. The apparatus of claim 10 wherein, the additional second identifier obtained from the second table is associated with a copy of the data unit.

12. The apparatus of claim 9 wherein each entry in the second table includes a port identifier.

13. The apparatus of claim 12 wherein the data unit is transmitted through the port indicated by the port identifier.

14. The apparatus of claim 9 further including a third memory table having one entry per second identifier.

15. The apparatus of claim 14 wherein a Virtual Path Identifier and a Virtual Circuit Identifier are written in each entry in the third table.

16. The apparatus of claim 15 wherein the second identifier obtained from the second table is employed as an index into the third table to obtain a corresponding Virtual Path Identifier and Virtual Circuit Identifier from the third table, and the Virtual Path Identifier and Virtual Circuit Identifier obtained from the third table are associated with the data unit.

17. A method for mapping a first Virtual Path Identifier and a first Virtual Circuit Identifier associated with an Asynchronous Transfer Mode cell to a second Virtual Path Identifier and a second Virtual Circuit Identifier in an Asynchronous Transfer Mode switch a plurality of ports, comprising the steps of:

employing the first Virtual Path Identifier and first Virtual Circuit Identifier to provide a Multicast Circuit Identifier;

assigning one entry per Multicast Circuit Identifier in a first table;

assigning one entry in a second table for each copy of the multicast cell to be transmitted;

assigning one entry in a third table for each entry in the second table;

writing, in at least one entry in the first table, a pointer to an entry in the second table;

writing, in at least one entry in the second table, a port identifier, a Connection Identifier and a pointer to an entry in the second table;

writing, in at least one entry in the third table, the second Virtual Path Identifier and the second Virtual Circuit Identifier;

employing the Multicast Circuit Identifier as an index into the first table to obtain a corresponding pointer from the first table;

employing the pointer obtained from the first table as an index into the second table to obtain a corresponding output port, Connection Identifier, and pointer from the second table;

associating the Connection Identifier obtained from the second table with the cell;

employing the Connection Identifier as an index into the third table to obtain the second Virtual Path Identifier and second Virtual Circuit Identifier;

associating the second Virtual Path Identifier and the second Virtual Circuit Identifier with the cell;

transmitting the cell through the output port indicated by the port identifier obtained from the second table; and

employing the pointer obtained from the second table to determine whether any further entry in the second table is applicable to the cell.