Using consistent hashing for ECMP routing
View Patent ↗ECMP routing is carried out in fabric of network entities by representing valid destinations and invalid destinations in a group of the entities by a member vector. The order of the elements in the member vector is permuted. A portion of the elements in the permuted vector is pseudo-randomly masked. A flow of packets is transmitted to the first valid destination in the masked member vector.
1. A method, comprising the steps of:
defining in a fabric of network entities a group of the entities, wherein the network entities have a plurality of physical ports and are interconnected via a data network;
representing the group by a member vector having elements, including valid elements and invalid elements that respectively reference valid destinations and invalid destinations in the group;
permuting an order of the elements in the member vector to define a permuted member vector;
pseudorandomly masking a portion of the elements of the permuted member vector to define a masked permuted member vector; and
transmitting via the physical ports and the data network a flow of packets to the valid destination represented by a first valid element of the masked permuted member vector.
2. The method according to claim 1 , wherein the destinations are next hops in an equal cost multi-path (ECMP) group.
3. The method according to claim 1 , wherein the destinations are addresses in a link aggregation group (LAG).
4. The method according to claim 1 , wherein permuting an order comprises applying a hash function to a packet header and varying the order according to the hash function.
5. The method according to claim 1 , wherein masking comprises applying a masking hash function to the permuted member vector.
6. The method according to claim 1 , further comprising deleting one of the valid destinations from the group prior to representing the group by a member vector and redistributing the flow of packets to remaining valid destinations using the masked permuted member vector.
7. The method according to claim 6 , wherein redistributing the flow of packets comprises avoiding migrating flows of packets in the remaining valid destinations to other remaining valid destinations.
8. The method according to claim 1 , further comprising adding a new valid destination to the group prior to representing the group by a member vector redistributing the flow of packets to include the new valid destination using the masked permuted member vector.
9. The method according to claim 8 , wherein redistributing the flow of packets comprises avoiding migrating flows of packets in preexisting valid destinations to other preexisting valid destinations.
10. A system, comprising the steps of:
a fabric of network entities for communication of data packets, wherein the network entities have a plurality of physical ports and a memory storing a forwarding database, respectively; and
programmable hardware logic in the network entities configured for performing the steps of:
representing a group of the network entities by a member vector having elements, including valid elements and invalid elements in the forwarding database that respectively reference valid destinations and invalid destinations in the group;
permuting an order of the elements in the member vector to define a permuted member vector;
pseudo-randomly masking a portion of the elements of the permuted member vector to define a masked permuted member vector; and
transmitting a flow of packets to the valid destination represented by a first valid element of the masked permuted member vector.
11. The system according to claim 10 , wherein the destinations are next hops in an equal cost multi-path (ECMP) group.
12. The system according to claim 10 , wherein the destinations are addresses in a link aggregation group (LAG).
13. The system according to claim 10 , wherein permuting an order comprises applying a hash function to a packet header and varying the order according to the hash function.
14. The system according to claim 10 , wherein masking comprises applying a masking hash function to the permuted member vector.
15. The system according to claim 10 , wherein the hardware logic is configured for deleting one of the valid destinations from the group prior to representing the group by a member vector and redistributing the flow of packets to remaining valid destinations using the masked permuted member vector.
16. The system according to claim 15 , wherein redistributing the flow of packets comprises avoiding migrating flows of packets in the remaining valid destinations to other remaining valid destinations.
17. The system according to claim 10 , wherein the hardware logic is configured for adding a new valid destination to the group prior to representing the group by a member vector redistributing the flow of packets to include the new valid destination using the masked permuted member vector.
18. The system according to claim 17 , wherein redistributing the flow of packets comprises avoiding migrating flows of packets in preexisting valid destinations to other preexisting valid destinations.