Network switch with hash table look up

• US 6,457,058 B1
• Filed: 07/12/2001
• Issued: 09/24/2002
• Est. Priority Date: 09/29/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ullum, Daniel, Edsall, Thomas J., Hang, Soei-Shin
• Primary Examiner(s): Geckil, Mehmet B.
• Application Number:
  US09/904,431
• Time in Patent Office: 439 Days
• Field of Search: 709/238, 709/245, 709/236, 711/216, 711/206, 711/208, 711/209, 711/205, 370/259, 370/401, 370/409, 370/392, 370/428, 370/474, 370/423, 370/360, 370/380, 370/381
• US Class Current: 709/238
• CPC Class Codes: H04L 12/467 Arrangements for supporting untagged frames, e.g. port-based VLANs
• CPC Class Codes: H04L 12/4675 Dynamic sharing of VLAN information amongst network nodes configuration of the network or of network elements H04L41/08
• 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/745 Address table lookup; Address filtering

Abstract

An improved look up mechanism for accessing a RAM to obtain forwarding information for data frames being transported among ports of a high-performance switch is provided. The look up mechanism includes a multi-page look up table and associated hashing technique. A media access control (MAC) address and a virtual local area network (VLAN) identifier are transformed with a hash function to obtain a hash key. The hash key is an address pointing to a particular entry in the look up table. A virtual first page is also derived from the hash key, which selects a particular physical page of the look up table to be initially accessed each time that MAC address/VLAN pair is used. The look up mechanism may also be used to access a short cut table containing Layer 3 short cut information. In either case, ultimately, the likelihood is increased that a match will be found on the first RAM access, thus maintaining high-speed switch performance.

Claims

1. A look up mechanism for a switch, the look up mechanism comprising:

a look up table;

a look up table handler coupled to the look up table;

at least one hashing element coupled to the look up table handler, the hashing element hashing a set plurality of fields of a data packet defining an address, the hashing element producing a hash key; and

the look up table handler using first selected bits of the hash key to map the plurality of fields to a page of the look up table, and second selected bits of the hash key to map to an entry in said page.

2. The apparatus of claim 1 wherein the look up table further comprises:

a first table and a second table, the first table holding virtual pages of the look up table in a data RAM and the second table holding bits indicating validity of entries in a corresponding virtual page, in a tag RAM.

3. The apparatus of claim 2 wherein the data RAM further comprises:

a plurality of pages with each page containing a plurality of entries.

4. The apparatus of claim 2 wherein the tag RAM further comprises:

a plurality of pages.

5. The apparatus of claim 1, wherein the set plurality of fields further comprises:

a media access control (MAC) field and a virtual local area network (VLAN) tag field.

6. The apparatus of claim 1, further comprising:

a comparison circuit arrangement, the comparison circuit arrangement comparing the entry mapped by the hashed set plurality of fields with the set plurality of fields, and generating a signal indicating whether a match was found.

7. The apparatus of claim 6 further comprising:

a forwarding engine responsive to the signal, to forward the data packet to a port indicated by the entry in the event that the signal indicates a match, and to advance to a next page of the look up table in the event that the signal indicates that no match was found.

8. The apparatus of claim 1, further comprising:

a predetermined set of bits from the hash key, the predetermined set of bits being decoded by the look up table handler to obtain a page number, the page number corresponding to a physical page of the look up table to be initially accessed in response to receipt of a data packet having a received the plurality of fields.

9. The apparatus of claim 8 wherein the predetermined set of bits further comprises:

a three most significant bits of the hash key.

10. The apparatus of claim 1, wherein an input to the hashing element further comprises:

a hash configuration quantity which is a constant added to the address to be hashed whereby fewer addresses hash to the same hash key.

11. The apparatus of claim 1, wherein the look up table further comprises:

information for a layer higher than the layer containing a media access control layer.

12. The apparatus of claim 11, wherein the information further comprises:

short cut information for layer 3.

13. A look up mechanism for a switch, the look up mechanism comprising:

a look up table;

a look up table handler;

at least one hashing element coupled to the look up table handler;

the hashing element hashes a MAC/VLAN pair to produce a hash key, and the look up table handler uses first selected bits of the hash key to map the MAC/VLAN pair to a page of the look up table, and second selected bits of the hash key to map to an entry in said page.

14. A look up mechanism for a switch, the look up mechanism comprising:

a look up table;

a hashing element coupled to the look up table, the hashing element generating a hash key in response to a MAC/VLAN pair received by the forwarding engine;

the hash key comprising a plurality of bits; and

a look up table handler, the look up table handler programmed to derive, from a first set of bits of the hash key, a virtual first page for a MAC/VLAN pair, the virtual first page mapping a virtual first page to a physical page of the look up table to be initially accessed, and a second set of bits of the hash key further mapping to a selected entry of the look up table.

15. The apparatus of claim 14, wherein entries of the look up table further comprises:

a MAC address/VLAN pair and a unique value identifying a port to which the frame is to be sent by the forwarding engine.

16. The apparatus of claim 15 further comprising:

a comparison circuit arrangement,

the comparison circuit arrangement comparing the MAC address/VLAN pair from the selected entry of the look up table with a MAC address/VLAN pair from a received data packet, and the switch, in response to a match, using the port identified by the look up table entry to forward the received data packet;

the look up table handler, in response to the MAC address/VLAN pair not matching the table entry, accessing the next virtual page to locate the proper table entry.

17. A look up mechanism for a switch, the look up mechanism comprising:

a look up table;

a look up table handler coupled to the look up table;

at least one hashing element coupled to the look up table handler;

the look up table handler programmed to perform the steps of;

(A) establishing the look up table, configured as a plurality of pages, with each page containing a plurality of entries, each entry for storing address information including a media access control (MAC) address and a VLAN designation in addition to associated data that includes a unique index value identifying a port associated with that MAC address/VLAN pair;

(B) using the hashing element to hash a MAC address/VLAN pair received by the forwarding engine as a forwarding address to produce a hash key;

(C) deriving a virtual first page from said hash key for a particular MAC address/VLAN pair which virtual first page determine a physical page of the look up table to be initially accessed; and

(D) accessing the virtual first page and selecting an entry on the first virtual page identified by the hash key to retrieve the forwarding information.

18. A method for looking up forwarding information in a network switch comprising the steps of:

A) hashing a set plurality of fields of a received data packet to produce a hash key, the hash key having at least a first set of bits and a second set of bits;

B) mapping the first set of bits to a virtual first page of a look up table;

C) mapping the second set of bits to an entry in the virtual first page.

19. The method of claim 18 wherein the set plurality of fields further comprises:

a media access control (MAC) field and a virtual area network (VLAN) tag field.

20. The method of claim 18 wherein the first set of bits further comprises:

a three most significant bits of the hash key.

21. The method of claim 18 further comprising the steps of:

D) comparing the entry from the virtual first page with the set plurality of fields from the received data packet;

E) advancing to the next virtual page in response to the entry not matching the set plurality of fields in the received data packet;

F) returning a forwarding port in response to the virtual first page matching the set plurality of fields in the received data packet.

22. A computer-readable medium for practicing the method of claim 18.

23. Electromagnetic signals propagating over a computer network, the electromagnetic signals carrying information for practicing the method of claim 18.