Apparatus and method for generating an index key for a network switch routing table using a programmable hash function

• US 6,292,483 B1
• Filed: 12/18/1997
• Issued: 09/18/2001
• Est. Priority Date: 02/14/1997
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Kerstein, Denise
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Nguyen, Phuongchau Ba
• Application Number:
  US08/992,795
• Time in Patent Office: 1,370 Days
• Field of Search: 370/389, 370/392, 370/400-405, 709/201, 709/232, 709/242, 709/243, 709/250
• US Class Current: 370/389
• CPC Class Codes: G06F 13/1605 based on arbitration arbitration in handling access to a common bus or bus system G06F13/36
• CPC Class Codes: G06F 13/24 using interrupt G06F13/32 takes precedence
• CPC Class Codes: G11C 11/412 using field-effect transistors only
• CPC Class Codes: H04L 12/1863 comprising mechanisms for improved reliability, e.g. status reports arrangements for detecting or preventing errors by carrying supervisory signal the return channel H04L1/16
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 12/4645 Details on frame tagging routing of packets H04L45/00; support for virtual LAN H04L49/354
• CPC Class Codes: H04L 12/467 Arrangements for supporting untagged frames, e.g. port-based VLANs
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/255 Control mechanisms for ATM switching fabrics
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3054 Auto-negotiation, e.g. access control between switch gigabit interface connector [GBIC] and link
• 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]
• CPC Class Codes: H04L 49/40 : Constructional details, e.g. power supply, mechanical construction or backplane
• CPC Class Codes: H04L 49/50 : Overload detection or protection within a single switching element
• CPC Class Codes: H04L 49/552 : by ensuring the integrity of packets received through redundant connections
• CPC Class Codes: H04L 49/555 : Error detection
• CPC Class Codes: H04L 49/90 : Buffering arrangements
• CPC Class Codes: H04L 49/901 : using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9047 : including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9063 : Intermediate storage in different physical parts of a node or terminal
• CPC Class Codes: H04L 49/9073 : Early interruption upon arrival of a fraction of a packet
• CPC Class Codes: H04L 49/9078 : using an external memory or storage device
• CPC Class Codes: H04L 49/9084 : Reactions to storage capacity overflow
• CPC Class Codes: H04Q 2213/1316 : Service observation, testing
• CPC Class Codes: H04Q 2213/13162 : Fault indication and localisation
• CPC Class Codes: H04Q 3/54591 : Supervision, e.g. fault localisation, traffic measurements, avoiding errors, failure recovery, monitoring, statistical analysis

Abstract

A network switch configured for switching data packets across multiple switch ports uses programmable hash functions to generate a hash key for each network address to access an address table storing switching logic. The address table is configured to include a programmable number of bin entries, where each bin entry is configured to reference a plurality of address table entries storing the switching logic information for respective network addresses. The address of an incoming data packet is used to generate a hash key that references a selected one of the bin entries. The switching logic for the corresponding address is then obtained by accessing the appropriate table entry referenced by the selected bin entry. If the number of table entries for a given bin exceeds a prescribed threshold, an external host reprograms the network switch to use another hash key to maintain an efficient access throughput of the address table. Use of programmable hash keys also enables the host processor to use different hash key polynomials for different network configurations to optimize the table access throughput.

Claims

1. A method for determining a network switch output port for transmission of a data packet having an address and having been received by a network switch, comprising:

storing a user-selected hash function in a programmable register;

generating a hash key for the received data packet in response to the user-selected hash function and the corresponding address;

accessing a selected bin entry from a plurality of bin entries in an address table based on the hash key, each bin entry configured to reference a corresponding plurality of table entries, each table entry configured for identifying the output port for a corresponding address; and

determining the output port from one of the table entries of the selected bin entry based on the address.

2. The method of claim 1, wherein the storing step comprises storing a bit pattern in the programmable register, each bit of the bit pattern corresponding to a coefficient of a corresponding polynomial value.

3. The method of claim 2, wherein the generating step comprises supplying the address as a bit stream to a hash function circuit responsive to the bit pattern, the hash function circuit outputting a hash-generated polynomial.

6. The method of claim 1, further comprising:

determining a number of table entries for at least one of the bin entries; and

selectively storing a second user-selected hash function in the programmable register based on said number of table entries exceeding a prescribed value, the generating step generating a new hash key in response to the second user-selected hash function stored in the programmable register.

7. The method of claim 6, further comprising storing a plurality of available hash functions in a nonvolatile memory, the selectively storing step comprising loading one of the available hash functions into the programmable register.

8. The method of claim 1, wherein the storing step comprises:

storing a plurality of available hash functions in a nonvolatile memory; and

selectively loading one of the available hash functions into the programmable register in response to the address table encountering a prescribed condition.

9. The method of claim 8, further comprising detecting as said prescribed condition the number of table entries for one of the bin entries exceeding a prescribed value.

10. The method of claim 1, further comprising:

clearing the address table;

storing a new user-selected hash function in the programmable register; and

assigning a new table entry in the address table to a second selected bin entry in response to generating a second hash key for an address specified in the new table entry.

4. A method for determining a network switch output port for transmission of a data packet having an address and having been received by a network switch, comprising:

storing a user-selected hash function in a programmable register;

generating a hash key for the received data packet in response to the user selected hash function and the corresponding address;

accessing a selected bin entry from a plurality of bin entries in an address table based on the hash key, each bin entry configured to reference a corresponding plurality of table entries, each table entry configured for identifying the output port for a corresponding address; and

determining the output port from one of the table entries of the selected bin entry based on the address, wherein

the storing step comprises storing a bit pattern in the programmable register, each bit of the bit pattern corresponding to a coefficient of a corresponding polynomial value,

the generating step comprises supplying the address as a bit stream to a hash function circuit responsive to the bit pattern, the hash function circuit outputting a hash-generated polynomial,

the storing step further comprises storing a polynomial enable value in a polynomial enable register, the polynomial enable value specifying a number of the bits in the hash key, and

the generating step comprises generating the hash key in response to the hash-generated polynomial and the polynomial enable value.

5. The method of claim 4, wherein the polynomial value corresponds to an addressable range of the bin entries.

11. A method for controlling access of a network address table storing switching data for a plurality of network addresses, comprising:

storing a first number in a first programmable register, the first number specifying an addressable range of bin entries in the address table, each bin entry configured to reference a corresponding group of table entries for respective network addresses;

storing a second number specifying a user-specified hash function in a second programmable register, the hash function configured to map a network address value to one of the bin entries;

monitoring for at least one bin entry a number of the corresponding table entries; and

replacing the second number in the second programmable register with a third number specifying a second user-specified hash function in response to the number of table entries exceeding a prescribed threshold.

12. The method of claim 11, wherein the replacing step comprises:

clearing the network address table;

selectively loading the third number from a plurality of stored available hash functions into the second programmable register; and

loading the network address table with new table entries based on the a new hash fiction determined by said third number.

13. The method of claim 11, further comprising storing a plurality of the user-specified hash functions in a nonvolatile memory, the replacing step including selecting one of the user-specified hash functions as the second user-specified hash function.

14. The method of claim 11, wherein the replacing step comprises:

clearing the network address table;

selectively loading the third number from a plurality of stored available hash functions into the second programmable register; and

causing a controller accessing the network address table using the hash function specified by the second programmable register to store learned addresses in the network address table.

15. A network switch configured for outputting a data packet having an address, comprising:

a first programmable register for storing a first number specifying an addressable range of bin entries;

a network address table for storing the addressable range of bin entries, each bin entry configured to reference at least one table entry and each table entry configured for storing switching data including an output port of the network switch for a corresponding address;

a second programmable register for storing a second number specifying a user-specified hash function;

a hash key generator configured to map the address of the data packet to one of the bin entries according to the user-specified hash function specified by the second number, the hash key generator outputting a hash key for addressing the one bin entry and having a number of bits based on the first number.

16. The network switch of claim 15, wherein the hash key generator comprises:

a hash function circuit configured for generating a hash-generated polynomial for the address of the data packet according to the user-specified hash function in response to the second number; and

a logic circuit for outputting a portion of said hash-generated polynomial as said hash key in response to the first number.

17. The network switch of claim 15, wherein each bin entry is configured to reference a plurality of table entries using a link-list chain, wherein said each bin entry and each table entry includes a next-entry pointer segment, the next-entry pointer segment indicating one of another chain entry and an end-of-chain designation.

18. A system comprising:

a network switch configured for outputting a data packet having an address, comprising;

(1) a first programmable register for storing a first number specifying an addressable range of bin entries,

(2) a network address table for storing the addressable range of bin entries, each bin entry configured to reference at least one table entry and each table entry configured for storing switching data including an output port of the network switch for a corresponding address,

(3) a second programmable register for storing a second number specifying a user-specified hash function, and

(4) a hash key generator configured to map the address of the data packet to one of the bin entries according to the user-specified hash function specified by the second number, the hash key generator outputting a hash key for addressing the one bin entry and having a number of bits based on the first number; and

a host processor configured for monitoring for at least one bin entry a number of the corresponding table entries, the host processor selectively reprogramming the second programmable register with a second number specifying another user-specified hash function in response to the number of table entries exceeding a prescribed threshold.

19. The system of claim 18, further comprising a nonvolatile memory storing a plurality of hash configuration values specifying respective available hash functions, the host processor selectively storing one of the hash configuration values in said second programmable register as said second number in response to the number of table entries exceeding the prescribed threshold.

20. The system of claim 18, further comprising a memory controller configured for clearing the network address table in response to the reprogramming of at least one of the first and second programmable registers.