Address translation mechanism for a high-performance network switch

• US 5,740,171 A
• Filed: 03/28/1996
• Issued: 04/14/1998
• Est. Priority Date: 03/28/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Cafiero, Luca, Mazzola, Mario, Edsall, Tom
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Jung, Min
• Application Number:
  US08/621,718
• Time in Patent Office: 747 Days
• Field of Search: 370/392, 370/393, 370/395, 370/396, 370/400, 370/401, 370/466, 370/474
• US Class Current: 370/392
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]

Abstract

An address translation mechanism quickly and efficiently renders forwarding decisions for data flames transported among ports of a high-performance switch on the basis of, inter alia, virtual local area network (VLAN) associations among the ports. The translation mechanism comprises a plurality of forwarding tables, each of which contains entries having unique index values that translate to selection signals for ports destined to received the data frames. Each port is associated with a unique index value and a VLAN identifier to facilitate multicast data transfers within the switch at accelerated speeds and addressing capabilities.

Claims

1. An address translation mechanism for quickly rendering forwarding decisions for data frames transported among ports of a high-performance switch, the translation mechanism comprising:

a plurality of forwarding tables, each table containing entries having unique index values that translate to selection signals for ports destined to receive the data frames;

means for transforming a numerical quantity to a key value for accessing a selected table entry; and

a comparison circuit arrangement for validating the contents of the selected table entry, the circuit arrangement comparing he numerical quantity with a similar value stored in the selected entry to ensure that the contents of the entry contain a correct unique index value.

2. The address translation mechanism of claim 1, wherein said means for transforming comprises means for hashing said numerical quantity to provide a signal value indicative of said key value, such that said key value maps into one location of each of said plurality of forwarding tables.

3. The address translation mechanism of claim 1, wherein each of said plurality of forwarding tables comprises means responsive to said key value for selecting one of said unique index values.

4. The address translation mechanism of claim 1, wherein each of said plurality of forwarding tables comprises a plurality of similar values each of which is uniquely associated with one of said unique index values stored in the table.

5. The address translation mechanism of claim 1, wherein said comparison circuit arrangement comprises means for providing a comparison status signal value which is asserted when said similar value is equal to said numerical quantity.

6. The address translation mechanism of claim 5, further comprising

means for monitoring the validity of table entries within said plurality of forwarding tables, and for providing a table status signal value indicative thereof;

means for comparing said table status signal value and said comparison status signal value, and for outputting said similar value when said table status signal and said comparison status signal values are asserted.

7. The address translation mechanism of claim 6, further comprising means for translating said unique associated index signal value to a selection signal value indicative of which ports receive the data frames.

8. The address translation mechanism of claim 6, further comprising

means for receiving a data frame;

and

means, for parsing said received data flame to determine a destination address value and color value indicative of the ports to receive and retain said received data frame, and for providing said numerical quantity which is indicative of said destination address and said color value of said received data frame.

9. Apparatus for quickly and efficiently rendering forwarding decisions for a data frame transferred among ports of a network switch via a bus, the data frame containing a media access control (MAC) address of a network entity destined to receive the frame and a color identifier representing a virtual local area network association of the port transferring the frame over the bus, the apparatus comprising:

a bus interface circuit for parsing the data frame to extract the MAC address and color identifer;

means, responsive to the extracted MAC address and color identifier, for producing an index value; and

a target logic circuit coupled to the producing means, the target logic circuit translating the index value to a coded signal that selects one of a port and group of ports for receiving the data frame.

10. The apparatus of claim 9 wherein the producing means comprises:

a forwarding table containing an entry for storing the index value and a MAC/color value; and

a hashing element coupled to the forwarding table, the hashing element generating a key in response to the extracted MAC address and color identifier, the key mapping to the entry of the forwarding table.

11. The apparatus of claim 10 wherein the producing means further comprises means, coupled to the forwarding table, for ensuring that the entry contains a correct index value.

12. The apparatus of claim 11 wherein the ensuring leans comprises:

a first multiplexer having an input coupled to the forwarding table and an output, the first multiplexer enabled by a translation controller to select the MAC/color value of the entry; and

a comparator having an input coupled to the output of the first multiplexer, the comparator performing a comparison operation between (i) the extracted destination address and color identifier and (ii) the selected MAC/color value to generate a comparison signal.

13. The apparatus of claim 12 wherein the ensuring means further comprises:

a second multiplexer having an input coupled to the forwarding table and an output, the second multiplexer enabled by the translation controller to select the index value of the entry; and

a third multiplexer having one input coupled to the output of the second multiplexer and another input receiving the extracted color identifier, the third mutiplexer enabled by the comparison signal to select one of the index value and extracted color identifier depending upon a state of the comparison signal.

14. The apparatus of claim 9 wherein the target logic circuit comprises:

a store unit having a plurality of locations each containing a bit string that functions as a port mask, wherein each bit of the port mask corresponds to a specific port of the switch and wherein the coded signal is derived from the port mask; and

a controller coupled to the store unit, the controller mapping the index value to a location of the store unit to generate the coded signal.

15. A method for quickly and efficiently rendering forwarding decisions for a data frame transferred among ports of a network switch in accordance with a bus transaction over a switching bus, the method comprising the steps of:

A. parsing the data frame at a forwarding engine to extract a media access control (MAC) address and color identifer value from the frame, the MAC address specifying the destination address of a network entity receiving the frame and the color identifier value representing a virtual local area network association of the port transferring the frame through the switch;

B. producing an index value in response to the extracted MAC address and color identifier at a translation circuit of the engine; and

C. translating the index value to a coded signal at a target logic circuit, the coded signal selecting one of a port and group of ports for receiving the frame.

16. The method of claim 15 wherein step B comprises the steps of:

B1. storing the index value and a MAC/color value in one of a plurality of entries of a forwarding table of the engine; and

B2. generating a key in response to the extracted MAC address and color identifier using a hashing element of the engine.

17. The method of claim 16 wherein step B further comprises the step of:

B3. mapping the key mapping to the one entry of the forwarding table.

18. The method of claim 17 wherein step B still further comprises the steps of:

B4. comparing the extracted destination address and color identifier with the MAC/color value of the one entry; and

B5. generating a comparison signal in response to the comparing step to ensure that the one entry contains a correct index value.

19. The method of claim 15 wherein step C comprises the steps of:

C1. storing a bit string in one of a plurality of locations of a target logic store unit, each bit of the string corresponding to a specific port of the switch; and

C2. mapping the index value to the one location of the target logic store unit to derive the coded signal.

20. The method of claim 15 further comprising the step of:

D. transferring the frame over the bus in accordance with a current bus transaction contemporaneous with the performance of steps A-C.