Sliced routing table management with replication

• US 9,210,083 B2
• Filed: 04/01/2014
• Issued: 12/08/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:
  US14/242,455
• Publication Number:
  US 20140211806A1
• Time in Patent Office: 616 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 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 non-transitory computer-readable medium containing a program which, when executed, performs an operation for hash-based routing table management in a distributed network switch comprising a plurality of switch modules including a first switch module, the operation 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 bucket stores a plurality of routing entries, wherein each set of buckets is associated with a respective hash function of a plurality of hash functions, each hash function of which is distinct, wherein each set of buckets is divided into a plurality of subsets of buckets, each subset of which is accessible in parallel and has a respective property, wherein at least one of the plurality of hash functions 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, 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 subset 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 routing key included within a header of the first frame, the routing key having routing information including a virtual local area network (VLAN) tag, a logical network (LN) identifier, and a media access control (MAC) address; and

upon accessing the routing entry for the source address in the first subset 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 subset satisfies a replication condition, replicating the accessed routing entry to at least a second subset 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 subset does not satisfy the replication condition.

2. The non-transitory computer-readable storage medium of claim 1, wherein the respective property of each subset is determined over a configurable time duration, wherein the routing entry further includes a replication flag, wherein the replication condition comprises the property exceeding a configurable threshold measure.

3. The non-transitory computer-readable medium of claim 2, wherein the operation further comprises:

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 subset 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 subset 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.

4. The non-transitory computer-readable medium of claim 3, 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;

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, 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 non-transitory computer-readable medium of claim 4, wherein the operation further comprises:

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 non-transitory computer-readable medium of claim 5, 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;

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;

wherein access to the plurality of subsets of each set of buckets is managed by an arbiter component of the routing table, wherein each subset of each set of buckets is identified via a predefined subset of bits of hash function output, wherein access to each subset of each set of buckets is monitored by the arbiter component, wherein the respective properties of the plurality of subsets are updated based on the monitored access.

7. The non-transitory computer-readable medium of claim 6, wherein the respective property of each subset of the plurality of subsets comprises an access frequency property of the respective subset, wherein each bucket in each set of buckets is identifiable by a bucket identifier that is distinct within the respective set of buckets, 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 subset;

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.

8. The non-transitory computer-readable medium of claim 7, 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 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;

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.

9. The non-transitory computer-readable medium of claim 8, wherein the plurality of switch modules further includes a second switch module comprising a plurality of bridge elements and a routing table, wherein the operation further comprises:

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.

10. The non-transitory computer-readable medium of claim 1, wherein the respective property of each subset is determined over a configurable time duration.

11. The non-transitory computer-readable medium of claim 1, wherein the routing entry further includes a replication flag.

12. The non-transitory computer-readable medium of claim 1, wherein the replication condition comprises the property exceeding a configurable threshold measure.

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

one or more computer processors;

a memory containing a program which, when executed by the one or more computer processors, is configured to perform an operation 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 bucket stores a plurality of routing entries, wherein each set of buckets is associated with a respective hash function of a plurality of hash functions, each hash function of which is distinct, wherein each set of buckets is divided into a plurality of subsets of buckets, each subset of which is accessible in parallel and has a respective property, wherein at least one of the plurality of hash functions 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, 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 subset 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 routing key included within a header of the first frame, the routing key having routing information including a virtual local area network (VLAN) tag, a logical network (LN) identifier, and a media access control (MAC) address; and

upon accessing the routing entry for the source address in the first subset 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 subset satisfies a replication condition, replicating the accessed routing entry to at least a second subset 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 subset does not satisfy the replication condition.

14. The system of claim 13, wherein the respective property of each subset is determined over a configurable time duration.

15. The system of claim 13, wherein the routing entry further includes a replication flag.

16. The system of claim 13, wherein the replication condition comprises the property exceeding a configurable threshold measure.

17. A computer-implemented method of 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 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 bucket stores a plurality of routing entries, wherein each set of buckets is associated with a respective hash function of a plurality of hash functions, each hash function of which is distinct, wherein each set of buckets is divided into a plurality of subsets of buckets, each subgroup of which is accessible in parallel and has a respective property, wherein at least one of the plurality of hash functions 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, 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 routing key included within a header of the first frame, the routing key having routing information including a virtual local area network (VLAN) tag, a logical network (LN) identifier, and a media access control (MAC) address; and

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, 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.

18. The computer-implemented method of claim 17, wherein the respective property of each subset is determined over a configurable time duration.

19. The computer-implemented method of claim 17, wherein the routing entry further includes a replication flag.

20. The computer-implemented method of claim 17, wherein the replication condition comprises the property exceeding a configurable threshold measure.