Sliced routing table management with replication
First Claim
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 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
13 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 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. - View Dependent Claims (2, 3, 4, 5, 6, 12)
-
-
7. 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 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. - View Dependent Claims (8, 9, 10, 11, 13)
-
Specification