Sliced routing table management with replication

• US 8,867,550 B2
• Filed: 02/27/2013
• Issued: 10/21/2014
• Est. Priority Date: 08/29/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shedivy, David A., Verrilli, Colin B., Walk, Bruce M., Wind, Daniel, Bawsso, Claude
• Primary Examiner(s): Grey, Christopher
• Assistant Examiner(s): Rahman, M Mostazir
• Application Number:
  US13/778,450
• Publication Number:
  US 20140064092A1
• Time in Patent Office: 601 Days
• Field of Search: 370/395.31, 370/395.32
• US Class Current: 370/395.31
• 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 by a switch module having bridge elements and a routing table divided into slices of buckets, each slice having a respective property and including one or more buckets. If a routing entry for the source address is found in a first slice of a first set of buckets of the routing table responsive to a lookup request for the source address, and the property of the first slice satisfies a replication condition, then the routing entry is replicated to a second set of buckets of the routing table.

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 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 routing table, wherein the routing table in the first switch module is shared among the plurality of bridge elements in the first switch module and includes a plurality of sets of buckets, wherein each set of buckets is associated with a respective hash function of a plurality of hash functions, wherein each set of buckets is divided into a plurality of subgroups of buckets, each subgroup having a respective property determined over a configurable time duration;

upon determining, responsive to an initial lookup request for the source address, that the routing table does not include any routing entry for the source address, generating a routing entry for the source address in a first subgroup of a first set of buckets of the routing table, without replicating the routing entry to any other set of buckets of the routing table, the routing entry including a replication flag;

upon accessing the routing entry for the source address in the first subgroup of the first set of buckets of the routing table responsive to a first subsequent lookup request for the source address, and determining that the property of the first subgroup satisfies a replication condition comprising the property exceeding a configurable threshold measure, replicating the accessed routing entry to at least a second subgroup of a second set of buckets of the routing table, different from the first set, wherein the routing entry is not replicated to any set of buckets upon determining that the first subgroup does not satisfy the replication condition;

resolving a second subsequent routing entry lookup request via access requests to the routing entry and the replicated routing entry, respectively, wherein granting of a first of the access requests causes dropping of a second of the access requests, wherein a newly generated routing entry is subsequently inserted into the second set at an existing entry according to a predetermined priority policy favoring an invalid entry over a replicated entry and favoring the replicated entry over an oldest entry; and

upon accessing a routing entry for the destination address in a given subgroup of a given set of buckets of the routing table responsive to a lookup request for the destination address, and determining that the property of the given subgroup satisfies the replication condition, replicating the accessed routing entry to at least a set of buckets of the routing table, different from the given set of buckets.

2. The computer-implemented method of claim 1, wherein at least a first bridge element of the plurality of bridge elements has an associated set of caches, wherein the set of caches is modified upon accessing the generated routing entry in the modified routing table responsive to the first subsequent lookup request for the source address.

3. The computer-implemented method of claim 1, wherein each bridge element of the plurality of bridge elements has a respective, associated set of caches, wherein each set of caches includes a source address lookup cache and a destination address lookup cache.

4. The computer-implemented method of claim 3, wherein each lookup cache of each bridge element stores up to a predefined count of routing entries previously requested by and resolved for the respective bridge element.

5. The computer-implemented method of claim 4, further comprising:

forwarding the first frame based on routing information determined for the destination address;

receiving, by the first switch module, a second frame having an address selected from the source address and the destination address of the first frame;

accessing the set of caches of the first bridge element to identify the routing entry for the address of the second frame, without accessing the routing table in the first switch module, wherein accessing the routing table incurs a higher performance cost than accessing the set of caches; and

forwarding the second frame based on the routing entry included in the set of caches of the first bridge element.

6. The computer-implemented method of claim 4, wherein each lookup cache of the first bridge element is configured to be invalidated upon each of:

(i) routing information of any valid routing entry is modified;

(ii) receiving an indication that a flush operation is requested by a master controller component of the distributed network switch; and

(iii) a threshold duration of time has elapsed since a last invalidation of the respective lookup cache.

7. The computer-implemented method of claim 6, wherein the lookup cache is not flushed upon an aging out of each routing entry in the routing table, wherein routing entries to be inserted into the set of caches need not be compared prior to insertion.

8. The computer-implemented method of claim 1, wherein access to the plurality of subgroups of each set of buckets is managed by an arbiter component of the routing table, wherein each subgroup of each set of buckets is identified via a predefined subset of bits of hash function output, wherein access to each subgroup of each set of buckets is monitored by the arbiter component, wherein the respective properties of the plurality of subgroups are updated based on the monitored access.

9. The computer-implemented method of claim 1, wherein each hash function is distinct, wherein each bucket stores a plurality of routing entries, wherein each set of buckets is stored in a respective hash table of the routing table in the first switch module.

10. The computer-implemented method of claim 1, wherein the generated routing entry further includes a routing key included within a header of the first frame.

11. The computer-implemented method of claim 10, 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.

12. The computer-implemented method of claim 1, wherein the routing table is configured to provide parallel access to each subgroup of each set of buckets, wherein each subgroup includes an array data structure.

13. The computer-implemented method of claim 1, wherein each hash function is selected based on at least one of:

(i) an avalanche property of the respective hash function;

(ii) an intra-hash collision property of the respective hash function;

(iii) an inter-hash collision property of the respective hash function; and

(iv) an inter-subgroup distribution property of the respective hash function.

14. The computer-implemented method of claim 1, wherein the respective property of each subgroup of the plurality of subgroups comprises an access frequency property of the respective subgroup, wherein each bucket in each set of buckets is identifiable by a bucket identifier that is distinct within the respective set of buckets.

15. The computer-implemented method of claim 14, wherein the generated routing entry further includes a routing key included within a header of the first frame, wherein modifying the routing table comprises:

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;

upon determining that an access frequency mode is enabled, determining a bucket among the identified candidate buckets, belonging to a least-frequently accessed subgroup;

upon determining that the access frequency mode is disabled, determining one of;

(i) a least-full bucket among the identified candidate buckets and (ii) a least-full bucket among the identified candidate buckets and belonging to a least-full set of buckets of the plurality of sets of buckets, upon determining a presence of multiple least-full buckets; and

inserting the generated routing entry into the determined bucket.

16. The computer-implemented method of claim 15, 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.

17. The computer-implemented method of claim 16, wherein inserting the generated routing entry into the determined bucket comprises:

upon determining that the least-full bucket is full, discarding a 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.

18. The computer-implemented method of claim 17, wherein discarding the routing entry comprises:

upon determining that a routing entry is more aged than other routing entries in the same set of buckets as the routing entry, selecting the determined routing entry to be discarded; and

upon determining that a plurality of routing entries is more aged than other routing entries in the same set of buckets as the plurality of routing entries, randomly selecting a routing entry from the determined plurality of routing entries, to be discarded.

19. The computer-implemented method of claim 1, wherein the plurality of switch modules further includes a second switch module comprising a plurality of bridge elements and a routing table.

20. The computer-implemented method of claim 19, further comprising:

receiving the first frame by the second switch module;

upon determining that the routing table in the second switch module does not include any routing entry for the source address, determining routing information for the source address;

generating a routing entry for the source address, based on the routing information determined for the source address; and

modifying the routing table in the second switch module based on the plurality of hash functions, to include the routing entry generated for the source address.