Network unit including address hashing

• US 6,731,633 B1
• Filed: 04/25/2000
• Issued: 05/04/2004
• Est. Priority Date: 03/01/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Clifford, Neil J, OʼBrien, Eoin, Sohor, Annette E, OʼDonoghue, Derry M
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Mills, Donald L
• Application Number:
  US09/556,788
• Time in Patent Office: 1,470 Days
• Field of Search: 370/392, 370/395.32, 370/401, 370/466, 370/402, 370/389
• US Class Current: 370/392
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• 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
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A network unit includes a forwarding database which includes entries relating packet addresses to forwarding data and is operative to form linked chains of entries wherein the entries in a chain represent different packet addresses which are reduced by hashing to the same pointer for the database. A seed for a hashing algorithm is provided by a combination, such as an exclusive-OR combination, of part of an input address word and a selected word. Hashing is preferably performed in at least two cycles, wherein in one cycle a hash function is applied to a portion of the input address not including the part which is combined with the selected word to constitute a hash seed and in another (preceding) cycle a further part of the address and the aforementioned hash seed are subject the hash function. The selected word may be a software programmable mask and it is possible thereby to ensure a high degree of randomness in the hash seed and to reduce the incidence of convergence of different addresses to a common pointer.

Claims

1. Apparatus for reducing a first digital word to an output word of substantially lesser width in bits than the first digital word, said first digital word comprising mutually exclusive first and second parts each consisting of a different multiplicity of bits of the first digital word, said apparatus comprising:

means for providing an adjustable auxiliary word;

combinatorial logic for combining said auxiliary word with a portion of one of said mutually exclusive parts of said first digital word to provide a seed word;

a hashing stage for hashing said seed word and a selected part of the first digital word; and

a selector stage operative in one cycle to select for the hashing stage said seed word and said first part of the first word, said first part not including said portion, and operative in another cycle to select for the hashing stage said second part of said first word, said second part including said portion.

2. Apparatus according to claim 1 wherein said hashing stage has an input for receiving an output of the selector stage and a feedback word.

3. Apparatus according to claim 2 wherein said hashing stage provides a first output which constitutes said feedback word during said another cycle.

4. Apparatus according to claim 1 wherein said combinatorial logic provides exclusive-OR gating of bits of the auxiliary word with bits of said portion of said first digital word.

5. A network unit including:

a multiplicity of ports for receiving and forwarding addressed data packets;

a forwarding database which includes entries relating packet addresses to forwarding data; and

apparatus for receiving a packet address as a first digital word for reducing a first digital word to an output word of substantially lesser width in bits that the first digital word, said first digital word having a plurality of mutually exclusive parts, said apparatus comprising;

means for providing an adjustable auxiliary word;

combinatorial logic for combining said auxiliary word with a portion of one of said mutually exclusive parts of said first digital word to provide a seed word; and

means for hashing in successive cycles of operation said seed word with respective ones of said mutually exclusive parts of said first digital word to produce the said output word, only one of said mutually exclusive parts of said first digital word including said portion, said output word constituting a pointer to an entry in said forwarding database.

6. A network unit according to claim 5 wherein said database is operative to form linked chains of entries wherein the entries in a chain represent different packet addresses which are reduced by the means for hashing to the same output word and wherein the network unit includes means for detecting the existence of said linked chains to indicate a need to alter said adjustable auxiliary word.

7. A network unit according to claim 6 wherein said means for detecting is operative to alter said adjustable auxiliary word.

8. A network unit according to claim 5 wherein said portion consists of the sixteen least significant bits of a 48-bit media access control address, a first part consists of the sixteen most significant bits of said media access control address, and a second part consists of the thirty-two least significant bits of said media access control address, said auxiliary word being a 16-bit mask, and wherein said output word constitutes a 16-bit pointer.