Hashing-based routing table management
First Claim
Patent Images
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 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 functions, 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 an address selected from the source address and the destination address, generate, 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, andbased on the determined routing information, forward 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.
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. 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.
-
Citations
19 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 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 functions, 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 an address selected from the source address and the destination address, generate, 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, forward 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. 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 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 functions, 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 an address selected from the source address and the destination address of the first frame, 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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
-
Specification