Hash equation for MAC addresses that supports cache entry tagging and virtual address tables

• US 6,230,231 B1
• Filed: 03/19/1998
• Issued: 05/08/2001
• Est. Priority Date: 03/19/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Miller, David S., DeLong, Kenneth J.
• Primary Examiner(s): Yoo, Do
• Assistant Examiner(s): Encarnacion, Yamir
• Application Number:
  US09/044,490
• Time in Patent Office: 1,146 Days
• Field of Search: 711/3, 711/200, 711/216
• US Class Current: 711/3
• 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 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A cache line index for an address cache entry is calculated by organizing an address such as a Media Access Control (“MAC”) address into a plurality of intermediate elements, barrel shifting the bits of at least one of the intermediate elements in accordance with predetermined criteria, and folding the intermediate address elements together with an exclusive-OR function. A Virtual Local Area Network (“VLAN”) index may also be included in cache line index calculation. The VLAN index enables segmentation of the cache into virtual tables. The tag portion of the cache entry includes a subset of the complete set of intermediate elements. The intermediate elements in the cache entry can be employed in conjunction with the cache line index to recover the original MAC address. Hence, the size of the tag portion of the address cache entry is reduced relative to the full MAC address without a reduction in the information content of the entry.

Claims

1. A method for calculating a cache line index into an address cache containing information used in the processing of network data units, comprising the steps of:

organizing an address into a plurality of intermediate elements, wherein said organizing includes performing a bit wise shift on at least one portion of said address, and employing a result of said bit wise shift as at least one of said plurality of intermediate elements; and

folding said intermediate elements together with an exclusive-OR function, wherein a result of said folding includes said cache line index, and where in the folding includes encompassing a predetermined one of the intermediate elements in the calculation of each bit of the cache line index, wherein the predetermined one of the intermediate elements includes bits more likely to differ in value between any two addresses than bits in other ones of the intermediate elements, wherein the encompassing of the predetermined one of the intermediate elements in the calculation of each bit of the cache line index provides more uniform distribution of cache line index values,

wherein only a subset of the intermediate elements are stored in a tag portion of a cache entry.

2. The method of claim 1 wherein the address is a Media Access Control address and there are four intermediate elements, and including the step of storing three of the intermediate elements in a tag portion of the cache entry.

3. The method of claim 2 wherein the index is 14 bits in length, and including the step of encompassing at least some of the lower 28 bits of the address in the calculation of each bit of the cache line index in said folding step.

4. The method of claim 3 including the step of storing first and second most significant bits of the cache line index in the tag portion of the entry.

5. The method of claim 4 including the step of organizing the address cache into a plurality of virtual tables.

6. The method of claim 5 wherein the virtual tables are indexed by a virtual local area network index, and including the step of combining the virtual local area network index with a portion of the Media Access Control address to provide one of the intermediate elements prior to said step of folding the intermediate elements with the exclusive-OR function.

7. The method of claim 4 including the step of recalculating the Media Access Control address from the cache line index and the three stored intermediate elements.

8. The method of claim 7 including the step of encompassing the first and second most significant bits of the cache line index stored in the tag portion of the entry in the step of recalculating the Media Access Control address.

9. A method for generating a cache line index associated with an address cache entry in an address cache from a Media Access Control address and a virtual local area network index value, comprising the steps of:

segmenting the Media Access Control address and virtual local area network index into a plurality of portions, said plurality of portions including a first portion, a second portion, a third portion and a fourth portion;

shifting the first portion by a first predetermined number of bits in a first predetermined direction to form a first intermediate element;

shifting the second portion by a second predetermined number of bits in a second direction to form a second intermediate element;

employing said third portion as a third intermediate element;

employing said fourth portion as a fourth intermediate element; and

performing a bit wise exclusive-OR operation on the first intermediate element, second intermediate element, third intermediate element and fourth intermediate element to produce a result, wherein the result includes the cache line index, and wherein the performing includes encompassing a predetermined one of the intermediate elements in the calculation of each bit of the cache line index, wherein the predetermined one of the intermediate elements includes bits more likely to differ in value between any two addresses than bits in other ones of the intermediate elements, wherein the encompassing of the predetermined one of the intermediate elements in the calculation of each bit of the cache line index provides more uniform distribution of information in the address cache,

wherein only a subset of the intermediate elements are stored in a tag portion of the cache entry.

10. The method of claim 9 including the step of storing three of the intermediate elements in a tag portion of the cache entry.

11. The method of claim 10 wherein the cache line index is 14 bits in length, and including the step of encompassing a different bit from each of the first element and second element in the calculation of each bit of a cache line index in said step of performing the bit wise exclusive-OR operation.

12. The method of claim 11 including the step of storing first and second most significant bits of the cache line index in a cache line index portion of a tag portion of the cache entry.

13. The method of claim 12 including the step of organizing the address cache into a plurality of virtual tables.

14. The method of claim 13 wherein the virtual tables are indexed by the virtual local area network index, and including the step of combining the virtual local area network index with a portion of the Media Access Control address to provide the fourth intermediate element prior to said step of performing said bit wise exclusive-OR operation.

15. The method of claim 12 including the step of recalculating the Media Access Control address from the tag portion of the cache entry.

16. The method of claim 15 including the step of encompassing the cache line index portion of the tag portion of the cache entry in the step of recalculating the Media Access Control address.