Sliced routing table management

• US 9,124,527 B2
• Filed: 08/29/2012
• Issued: 09/01/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/597,784
• Publication Number:
  US 20140064277A1
• Time in Patent Office: 1,098 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/44 Distributed routing
• 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, where the routing table is divided into slices of buckets, then 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 and properties of the slices.

Claims

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

a non-transitory computer-readable medium having computer-readable program code embodied therewith, the computer-readable program code executable by one or more computer processors to;

receive, 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 distinct hash functions and is divided into a plurality of slices of buckets, each slice having a respective property and including one or more buckets, each bucket storing one or more routing entries, wherein each slice of each set of buckets is accessible in parallel;

upon determining that the routing table in the first switch module does not include any routing entry for an address selected from the source address and the destination address of the first frame, generate, in the 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 and at least one property of the respective properties of the plurality of slices, wherein the generated routing entry stores a routing key included within a header of the first frame; and

forward the first frame based on the determined routing information and to a second switch module of the distributed network switch, the second switch module having a routing table, wherein the second switch module is operable to, upon determining that the routing table in the second switch module does not include any routing entry for the selected address, generate, in the routing table in the second switch module, 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 associated with the routing table of the second switch module.

2. The computer program product of claim 1, wherein access to the plurality of slices of each set of buckets is managed by an arbiter component of the routing table of the first switch module, wherein each slice of each set of buckets is identified via a predefined subset of bits of hash function output, wherein access to each slice of each set of buckets is monitored by the arbiter component, wherein the respective properties of the plurality of slices are updated based on the monitored access.

3. The computer program product of claim 2, wherein each set of buckets is stored in a respective hash table of the routing table in the first switch module, 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;

wherein each slice includes an array data structure, wherein each hash function is selected based on;

(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-slice distribution property of the respective hash function.

4. The computer program product of claim 3, wherein the respective property of each slice of the plurality of slices comprises an access frequency property of the respective slice, wherein each bucket in each set of buckets is identifiable by a bucket identifier that is distinct within the respective set of buckets, and wherein the computer-readable program code is further executable to modify the routing table of the first switch module, 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;

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

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.

5. The computer program product of claim 4, 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 the computer-readable program code is further executable to insert the generated routing entry into the determined bucket, comprising;

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.

6. The computer program product of claim 1, wherein access to the plurality of slices of each set of buckets is managed by an arbiter component of the routing table of the first switch module.

7. The computer program product of claim 1, wherein each slice of each set of buckets is identified via a predefined subset of bits of hash function output.

8. The computer program product of claim 1, wherein access to each slice of each set of buckets is monitored by an arbiter component of the routing table of the first switch module, wherein the respective properties of the plurality of slices are updated based on the monitored access.

9. The computer program product of claim 1, wherein each set of buckets is stored in a respective hash table of the routing table in the first switch module.

10. 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 operable 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 set of buckets is associated with a respective hash function of a plurality of distinct hash functions and is divided into a plurality of slices of buckets, each slice having a respective property and including one or more buckets, each bucket storing one or more routing entries, wherein each slice of each set of buckets is accessible in parallel;

upon determining that the routing table in the first switch module does not include any routing entry for an address selected from the source address and the destination address of the first frame, generating, in the 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 and at least one property of the respective properties of the plurality of slices, wherein the generated routing entry stores a routing key included within a header of the first frame; and

forwarding the first frame based on the determined routing information and to a second switch module of the distributed network switch, the second switch module having a routing table, wherein the second switch module is operable to, upon determining that the routing table in the second switch module does not include any routing entry for the selected address, generate, in the routing table in the second switch module, 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 associated with the routing table of the second switch module.

11. The system of claim 10, wherein access to the plurality of slices of each set of buckets is managed by an arbiter component, wherein each slice of each set of buckets is identified via a predefined subset of bits of hash function output, wherein access to each slice of each set of buckets is monitored by the arbiter component of the first switch module, wherein the respective properties of the plurality of slices are updated based on the monitored access.

12. The system of claim 11, wherein each set of buckets is stored in a respective hash table of the routing table in the first switch module, 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;

wherein each slice includes an array data structure, wherein each hash function is selected based on;

(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-slice distribution property of the respective hash function.

13. The system of claim 12, wherein the respective property of each slice of the plurality of slices comprises an access frequency property of the respective slice, wherein each bucket in each set of buckets is identifiable by a bucket identifier that is distinct within the respective set of buckets, and wherein the operation further comprises modifying the routing table of the first switch module, 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;

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

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.

14. The system of claim 13, 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.

15. The system of claim 10, wherein access to the plurality of slices of each set of buckets is managed by an arbiter component of the routing table of the first switch module.

16. The system of claim 10, wherein each slice of each set of buckets is identified via a predefined subset of bits of hash function output.

17. The system of claim 10, wherein access to each slice of each set of buckets is monitored by an arbiter component of the routing table of the first switch module, wherein the respective properties of the plurality of slices are updated based on the monitored access.

18. The system of claim 10, wherein each set of buckets is stored in a respective hash table of the routing table in the first switch module.

19. A computer program product to increase access bandwidth of a routing table by distributing lookup hits in the routing table across hash tables and slices, the computer program product comprising:

a non-transitory computer-readable medium having computer-readable program code embodied therewith, the computer-readable program code executable by one or more computer processors to;

provide the routing table, wherein the routing table is shared between a plurality of bridge elements of a first switch module of a plurality of switch modules in a distributed network switch, wherein the routing table is divided into a plurality of hash tables accessible in parallel, each hash table having a distinct hash function, wherein at least one hash function is selected based on a predefined set of hash properties, wherein each hash table is divided into a plurality of slices accessible in parallel, each slice including one or more buckets, each bucket adapted to store one or more routing entries;

receive a first frame having a source address and a destination address; and

facilitate, at least in part, even distribution of a plurality of subsequent lookup hits expected to occur for a plurality of routing entries, by preemptively causing insertion of the plurality of routing entries based on a predefined set of insertion properties, comprising;

upon determining that the routing table does not include any routing entry for an address selected from the source address and the destination address of the first frame, generating, in the 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 and at least one insertion property of the predefined set of insertion properties, wherein the generated routing entry stores a routing key included within a header of the first frame; and

forward the first frame based on the determined routing information and to a second switch module of the distributed network switch, the second switch module having a routing table, wherein the second switch module is operable to, upon determining that the routing table in the second switch module does not include any routing entry for the selected address, generate, in the routing table in the second switch module, 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 associated with the routing table of the second switch module.

20. The computer program product of claim 19, wherein access to the plurality of slices of each set of buckets is managed by an arbiter component of the routing table of the first switch module.

21. The computer program product of claim 19, wherein each slice of each set of buckets is identified via a predefined subset of bits of hash function output.

22. The computer program product of claim 19, wherein access to each slice of each set of buckets is monitored by an arbiter component of the routing table of the first switch module, wherein the respective properties of the plurality of slices are updated based on the monitored access.

23. A system to increase access bandwidth of a routing table by distributing lookup hits in the routing table across hash tables and slices, the system comprising:

one or more computer processors;

a memory containing a program which, when executed by the one or more computer processors, is operable to perform an operation comprising;

providing the routing table, wherein the routing table is shared between a plurality of bridge elements of a first switch module of a plurality of switch modules in a distributed network switch, wherein the routing table is divided into a plurality of hash tables accessible in parallel, each hash table having a distinct hash function, wherein at least one hash function is selected based on a predefined set of hash properties, wherein each hash table is divided into a plurality of slices accessible in parallel, each slice including one or more buckets, each bucket adapted to store one or more routing entries; and

receiving a first frame having a source address and a destination address;

facilitating, at least in part, even distribution of a plurality of subsequent lookup hits expected to occur for a plurality of routing entries, by preemptively causing insertion of the plurality of routing entries based on a predefined set of insertion properties, comprising;

upon determining that the routing table does not include any routing entry for an address selected from the source address and the destination address of the first frame, generating, in the 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 and at least one insertion property of the predefined set of insertion properties, wherein the generated routing entry stores a routing key included within a header of the first frame; and

forwarding the first frame based on the determined routing information and to a second switch module of the distributed network switch, the second switch module having a routing table, wherein the second switch module is operable to, upon determining that the routing table in the second switch module does not include any routing entry for the selected address, generate, in the routing table in the second switch module, 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 associated with the routing table of the second switch module.

24. The system of claim 23, wherein access to the plurality of slices of each set of buckets is managed by an arbiter component of the routing table of the first switch module.

25. The system of claim 23, wherein each slice of each set of buckets is identified via a predefined subset of bits of hash function output.