Hashing-based routing table management

• US 9,215,172 B2
• Filed: 02/27/2013
• Issued: 12/15/2015
• Est. Priority Date: 08/29/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Basso, Claude, Shedivy, David A., Verrilli, Colin B., Walk, Bruce M., Wind, Daniel
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): Rahman, M Mostazir
• Application Number:
  US13/778,671
• Publication Number:
  US 20140064093A1
• Time in Patent Office: 1,021 Days
• Field of Search: 370/392
• US Class Current: 1/1
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

Techniques are provided for hash-based routing table management in a distributed network switch. A frame having a source address and a destination address is received. If no routing entry for the source address is found in a routing table of a switch module in the distributed network switch, routing information is determined for the source address and a routing entry is generated. The routing table is modified to include the routing entry and based on a set of hash functions.

Claims

1. A computer-implemented method for hash-based routing table management in a distributed network switch comprising a plurality of switch modules including a first switch module, the computer-implemented method comprising:

receiving, by the first switch module, a first frame having a source address and a destination address, wherein the first switch module comprises a plurality of bridge elements and a first routing table, wherein the first routing table is shared among the plurality of bridge elements in the first switch module and includes a plurality of sets of buckets, each bucket storing a plurality of routing entries, wherein each set of buckets is associated with a respective hash function of a plurality of distinct hash function, at least one hash function of which is selected based on a hash property comprising at least one of an avalanche property, an intra-hash collision property, an inter-hash collision property, and an inter-subgroup distribution property;

upon determining that the first routing table does not include any routing entry for a selected address comprising an address selected from the source address and the destination address, generating, in the first routing table, a routing entry for the selected address, based on routing information determined for the selected address and based further on at least one hash function of the plurality of hash functions, the routing entry having a routing key included within a header of the first frame, wherein the routing key includes Layer-2 routing information comprising a virtual local area network (VLAN) tag, a logical network (LN) identifier, and a media access control (MAC) address; and

based on the determined routing information, forwarding the first frame to a second switch module of the distributed network switch, the second switch module having a second routing table, wherein the second switch module is configured to, upon determining that the second routing table does not include any routing entry for the selected address, generate, in the second routing table, a routing entry for the selected address.

2. The computer-implemented method of claim 1, wherein each bucket in each set of buckets is identifiable by a bucket identifier that is distinct within the respective set of buckets, wherein the first routing table is modified, comprising:

generating, using the hash function associated with each set of buckets, a respective hash value based on the routing key included within the header of the first frame;

identifying, within each set of buckets, a candidate bucket having a bucket identifier matching the hash value generated using the hash function associated with the respective set of buckets;

determining a least-full bucket among the identified candidate buckets; and

inserting the generated routing entry into the determined least-full bucket.

3. The computer-implemented method of claim 2, wherein the least-full bucket is selected from one of:

(i) the candidate bucket having a smallest count of valid routing entries and (ii) the candidate bucket having a smallest count of valid routing entries and belonging to the set of buckets having a smallest count of valid routing entries;

wherein inserting the generated routing entry into the determined least-full bucket comprises;

upon determining that the least-full bucket is full, discarding the routing entry in the least-full bucket to make room for the generated routing entry, without reinserting the discarded routing entry into any of the plurality of sets of buckets.

4. The computer-implemented method of claim 1, wherein each set of buckets is stored in a respective hash table of the first routing table.

5. The computer-implemented method of claim 1, wherein each bucket in each set of buckets is identifiable by a bucket identifier that is distinct within the respective set of buckets.

6. The computer-implemented method of claim 1, wherein the first routing table is modified.

7. The computer-implemented method of claim 1, wherein the generated routing entry is inserted in to a least-full bucket selected from a plurality of identified candidate buckets.

8. The computer-implemented method of claim 7, wherein each candidate bucket is identified based on the respective candidate bucket having a bucket identifier matching a hash value generated using the hash function associated with a respective set of buckets of the respective candidate bucket.

9. The computer-implemented method of claim 8, wherein inserting the generated routing entry into the selected least-full bucket comprises:

upon determining that the least-full bucket is full, discarding the routing entry in the least-full bucket to make room for the generated routing entry, without reinserting the discarded routing entry into any of the plurality of sets of buckets.

10. The computer-implemented method of claim 1, wherein at least one hash function is selected based on the hash function avalanche property.

11. The computer-implemented method of claim 1, wherein at least one hash function is selected based on the intra-hash collision property.

12. The computer-implemented method of claim 1, wherein at least one hash function is selected based on the inter-hash collision property.

13. The computer-implemented method of claim 1, wherein a routing entry, selected based on an aging criterion, is discarded.

14. The computer-implemented method of claim 13, wherein the selected routing entry is discarded if the first routing table satisfies a fullness condition.

15. The computer-implemented method of claim 1, wherein the routing entry in the second routing table and for the selected address is generated based on routing information determined for the selected address.

16. The computer-implemented method of claim 15, wherein the routing entry in the second routing table and for the selected address is generated based further on at least one hash function associated with the second routing table.

17. The computer-implemented method of claim 1, wherein the plurality of hash functions includes at least two of the avalanche property, the intra-hash collision property, the inter-hash collision property, and the inter-subgroup distribution property.

18. The computer-implemented method of claim 1, wherein the plurality of hash functions includes at least three of the avalanche property, the intra-hash collision property, the inter-hash collision property, and the inter-subgroup distribution property.