Using consistent hashing for ECMP routing

Patent metadata

Field	Value
Publication number	US-9853900-B1
Application number	US-201715670055-A
Country	US
Kind code	B1
Filing date	Aug 7, 2017
Priority date	Aug 7, 2017
Publication date	Dec 26, 2017
Grant date	Dec 26, 2017

Abstract

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 and fanned out. A portion of the elements in the fanned out vector is pseudo-randomly masked. A flow of packets is transmitted to the first valid destination in the masked member vector.

First claim

The invention claimed is:

1. A method, comprising the steps of:
defining in a fabric of network entities a group of the entities;
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;
fanning out the permuted member vector to form a series of consecutive instances of the permuted member vector;
pseudo-randomly masking a portion of the elements of the fanned out member vector; and
transmitting a flow of packets to the valid destination represented by a first valid element of the masked 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 fanned out 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 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 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;
fanning out the permuted member vector to form a series of consecutive instances of the permuted member vector;
pseudo-randomly masking a portion of the elements of the fanned out member vector; and
transmitting a flow of packets to the valid destination represented by a first valid element of the masked 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 fanned out 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 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 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.

Assignees

• Mellanox Tech Tlv Ltd

Inventors

• Mula Liron
• Levy Gil
• Kfir Aviv

Classifications

• H04L41/0893

  Assignment of logical groups to network elements · CPC title

• H04L47/125 Primary

  by balancing the load, e.g. traffic engineering · CPC title

• H04L45/7453 Primary

  using hashing · CPC title

• H04L45/24 Primary

  Multipath · CPC title

• H04L45/245

  Link aggregation, e.g. trunking · CPC title