Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-12-18
2001-09-18
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C370S401000
Reexamination Certificate
active
06292483
ABSTRACT:
BACKGROUND ART
Switched local area networks use a network switch for supplying data frames between network stations, where each network station is connected to the network switch by a media. The switched local area network architecture uses a media access control (MAC) enabling a network interface within each network node (including the switch) to access the media.
The network switch passes data frames received from a transmitting station to a destination station based on the header information in the received data frame, including source address and destination address. One possible arrangement for generating a frame forwarding decision may use the source address or destination address in a direct addressing scheme, where the network switch includes a table storing switching logic for a plurality of network addresses, and where the switching logic for the corresponding destination address is stored in a table address corresponding to the destination address. Such an arrangement, however, is not practical for a network where the source addresses or destination addresses may have a large variation in values. Moreover, it may be more difficult for the network switch to quickly scan a table for the referenced address, locate the address, and make a frame forwarding decision as the table grows with table entries storing address information, especially if the address information is stored in a sequential manner. Since multiple data frames may be received by the network switch simultaneously, the network switch needs to make frame forwarding decisions relatively quickly. Hence, storing address information in a sequential manner (i.e., arranged in an increasing order by either source address or destination address) becomes impracticable as the number of entries increases, since a row by row search for the appropriate address table entry may be too slow for making frame forwarding decisions for multiple received data frames.
One arrangement for improving the accessing of switching logic from a table involves hashing, where an address, such as the source address or destination address, is transformed into a key that will be used to access information from a table. A problem with using a hash function is that the hash function is permanently set in the network switch. Hence, network traffic over time may cause over-usage of certain entries in the address table of the network switch. Hence, the over-usage results in a loss of efficiency in accessing the appropriate address table entry, causing the switching engine in the network switch to suffer a loss of performance in the throughput in making frame forwarding decisions.
SUMMARY OF THE INVENTION
There is a need for an arrangement for accessing a table entry storing switching logic in a network switch that maintains a high throughput, regardless of the accumulation of table entries over time.
There is also a need for an arrangement for generating an index key for accessing a table entry using a hashing function, where the distribution of incoming network addresses over an address range is balanced to limit access time.
These and other needs are attained by the present invention, where the network switch includes a programmable hash function register, enabling the hash function to be selectively modified during network operation to maintain an even distribution of entries within a table.
According to one aspect of the present invention, 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 comprises 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. Use of a hash key to access a table entry for a corresponding address enables efficient allocation of table entries across the plurality of bin entries. Moreover, storing the user-selected hash function in a programmable register enables the hash key, and subsequently the address table bin structure, to be reconfigured upon a determination that a given bin entry has a number of table entries exceeding a prescribed value. Hence, the method enables efficient accessing of switching logic for a given address, where the hash key and the bin structure of the address table can be periodically modified to maintain an efficient address search structure, enabling the network switch to make frame forwarding decisions quickly for multiple received data packets.
Another aspect of the present invention provides a method for controlling access of a network address table storing switching logic 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. Monitoring the number of table entries for a bin entry ensures that the address table maintains an efficient distribution of entries, since replacement of the user-specified hash function essentially resets the table entry distribution before loss in address table access performance is encountered.
Still another aspect of the present invention provides 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, and 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. The programmable registers ensure that a network address table can be configured for optimum access for different network architectures and addressing schemes.
Another aspect of the present invention provides a system comprising 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, and 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
Advanced Micro Devices , Inc.
Nguyen Chau
Nguyen Phuongchau Ba
LandOfFree
Apparatus and method for generating an index key for a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for generating an index key for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for generating an index key for a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2544465