Computer-based system for validating hash-based table lookup schemes in a network switch

• US 6,757,742 B1
• Filed: 05/25/2000
• Issued: 06/29/2004
• Est. Priority Date: 05/25/2000
• Status: Expired due to Term

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Viswanath, Somnath
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): Duong, Oanh
• Application Number:
  US09/577,491
• Time in Patent Office: 1,496 Days
• Field of Search: 709/102, 709/220, 709/213, 709/245, 709/246, 370/255, 370/466, 370/469, 370/423, 370/229, 370/389, 370/422
• US Class Current: 709/246
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 61/10 of different types
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories

Abstract

A computer-based system is configured for generating a first data structure having entries representing respective network nodes having layer 2 and layer 3 network addresses. The system generates a second data structure, having a plurality of data packet headers, by selecting source and destination pairs from the first data structure and combining the respective layer 2 and layer 3 network addresses from the respective selected source and destination pairs with randomly-generated numbers representing layer 3 payload data. The second data structure is supplied to a switch model configured for parsing the layer 3 network addresses according to selected hash functions. Hence, the computer-based system is able to evaluate the selected hash functions based on a time-independent analysis, eliminating the necessity of building an actual network in hardware or simulating network traffic over a period of time.

Claims

1. A method in a computer system, the method comprising:

generating and storing on a tangible medium a first data structure having entries, each entry representing a network node and having a corresponding layer 2 network address and a corresponding layer 3 network address;

generating a second data structure having a plurality of data packet headers, by selecting selected entries from the first data structure as source and destination pairs and combining the layer 2 network addresses and layer 3 network addresses for the source and destination pairs with respective randomly-generated numbers representing layer 3 payload data to form the data packet headers; and

evaluating a hash function by supplying the second data structure to a switch model configured for parsing at least a portion of the data packet headers according to the hash function, and monitoring results of the parsing by the hash function.

2. The method of claim 1, further comprising evaluating a plurality of selected hash functions by supplying the second data structure to switch models configured for parsing at least a portion of the data packet headers according to the respective hash functions.

3. The method of claim 1, wherein the step of generating and storing a first data structure includes storing in each entry a MAC address for the layer 2 network address, and an IP address having a prescribed network identifier and subnetwork identifier based on a prescribed network representation.

4. The method of claim 1, further comprising generating within the switch model a hash table, configured for storing a plurality of hash key signatures, by executing the hash function on the at least a portion of prescribed network addresses, the evaluating step including correlating hash key values, generated by the hash function based on the data packet headers, to the hash key signatures stored in the hash table.

5. The method of claim 4, wherein the step of generating a hash table includes generating a plurality of the hash tables within the switch model, each hash table configured for storing a corresponding plurality of hash key signatures according to a corresponding hash function, the evaluating step further including evaluating each of the hash functions based on the data packet headers.

6. The method of claim 4, wherein the evaluating step further includes determining a table efficiency of the hash table relative to the data packet headers.

7. The method of claim 4, wherein the evaluating step further includes determining a memory utilization of the hash table relative to the data packet headers.

8. A computer-based system comprising:

a controller for generating and storing on a tangible medium a first data structure having entries, each entry representing a network node and having a corresponding layer 2 network address and a corresponding layer 3 network address, the controller configured for generating a second data structure having a plurality of data packet headers, by selecting selected entries from the first data structure as source and destination pairs, and combining the layer 2 network addresses and layer 3 network addresses for the selected source and destination pairs with respective randomly-generated numbers representing layer 3 payload data to form the data packet headers;

a switch model configured for parsing at least a portion of the data packet headers according to at least one hash function; and

an evaluation module configured for evaluating the at least one hash function by supplying the second data structure to the switch model and monitoring results of the parsing by the hash function.

9. The system of claim 8, wherein the evaluation module is configured for evaluating a plurality of selected hash functions by supplying the second data structure to the switch model, configured for parsing at least a portion of the data packet headers according to the respective hash functions.

10. The system of claim 8, wherein the controller is configured for storing in each entry a MAC address for the layer 2 network address, and an IP address having a prescribed network identifier and subnetwork identifier based on a prescribed network representation.

11. The system of claim 8, wherein the switch model includes a hash generator configured for generating a hash table, configured for storing a plurality of hash key signatures, by executing the hash function on the at least a portion of prescribed network addresses, the evaluation module configured for correlating hash key values, generated by the hash function based on the data packet headers, to the hash key signatures stored in the hash table.

12. The system of claim 11, wherein the controller includes a random number generator configured for generating a payload for the data packet headers.

13. The system of claim 11, wherein the evaluation module is configured for determining a table efficiency of the hash table relative to the data packet headers.

14. The system of claim 11, wherein the evaluation module is configured for determining a memory utilization of the hash table relative to the data packet headers.

15. A computer readable medium having stored thereon sequences of instructions for evaluating a hash function, the sequences of instructions including instructions for performing the steps of:

generating and storing on a tangible medium a first data structure having entries, each entry representing a network node and having a corresponding layer 2 network address and a corresponding layer 3 network address;

generating a second data structure having a plurality of data packet headers, by selecting selected entries from the first data structure as source and destination pairs, and combining the layer 2 network addresses and layer 3 network addresses for the source and destination pairs with respective randomly-generated numbers representing layer 3 payload data to form the data packet headers; and

evaluating a hash function by supplying the second data structure to a switch model configured for parsing at least a portion of the data packet headers according to the hash function, and monitoring results of the parsing by the hash function.

16. The medium of claim 15, further comprising instructions for performing the step of evaluating a plurality of selected hash functions by supplying the second data structure to switch models configured for parsing at least a portion of the data packet headers according to the respective hash functions.

17. The medium of claim 15, wherein the step of generating and storing a first data structure includes storing in each entry a MAC address for the layer 2 network address, and an IP address having a prescribed network identifier and subnetwork identifier based on a prescribed network representation.

18. The medium of claim 15, further comprising instructions for performing the step of generating within the switch model a hash table, configured for storing a plurality of hash key signatures, by executing the hash function on the at least a portion of prescribed network addresses, the evaluating step including correlating hash key values, generated by the hash function based on the data packet headers, to the hash key signatures stored in the hash table.

19. The medium of claim 18, wherein the step of generating a hash table includes generating a plurality of the hash tables within the switch model, each hash table configured for storing a corresponding plurality of hash key signatures according to a corresponding hash function, the evaluating step further including evaluating each of the hash functions based on the data packet headers.

20. The medium of claim 18, wherein the evaluating step further includes determining a table efficiency of the hash table relative to the data packet headers.

21. The medium of claim 18, wherein the evaluating step further includes determining a memory utilization of the hash table relative to the data packet headers.

22. A system comprising:

a controller configured for generating and storing on a tangible medium a first data structure having entries, each entry representing a network node and having a corresponding layer 2 network address and a corresponding layer 3 network address, the controller configured for generating a second data structure having a plurality of data packet headers, by selecting selected entries from the first data structure as source and destination pairs, and combining the layer 2 network addresses and layer 3 network addresses for the selected source and destination pairs with respective randomly-generated numbers representing layer 3 payload data to form the data packet headers;

a hash function portion configured for parsing at least a portion of the data packet headers according to at least one hash function; and

an evaluation module configured for evaluating the at least one hash function by supplying the second data structure to the hash function portion and monitoring results of the parsing by the hash function.

23. The system of claim 22, wherein the evaluation module is configured for evaluating a plurality of selected hash functions by supplying the second data structure to the hash function portion, configured for parsing at least a portion of the data packet headers according to the respective hash functions.

24. The system of claim 22, wherein the controller is configured for storing in each entry a MAC address for the layer 2 network address, and an IP address having a prescribed network identifier and subnetwork identifier based on a prescribed network representation.

25. The system of claim 22, wherein the hash function portion includes a hash generator configured for generating a hash table, configured for storing a plurality of hash key signatures, by executing the hash function on the at least a portion of prescribed network addresses, the evaluation module configured for correlating hash key values, generated by the hash function based on the data packet headers, to the hash key signatures stored in the hash table.

26. The system of claim 25, wherein the controller includes a random number generator configured for generating a payload for the data packet headers.

27. The system of claim 25, wherein the evaluation module is configured for determining a table efficiency of the hash table relative to the data packet headers.

28. The system of claim 25, wherein the evaluation module is configured for determining a memory utilization of the hash table relative to the data packet headers.