3 ms·

Consider a case where you have a router balancing over four links. It chooses which link based on a hash of some information from the packet. Now imagine you

Consider a case where you have a router balancing over four links. It chooses which link based on a hash of some information from the packet. Now imagine you have four more routers on each of those links, hashing out over four more links. So you have a tree with 16 outputs. If the second-tier router uses the same hash algorithm as the first one, all the packets it receives will hash to the same link, because it's doing the same calculation as the router before it. Thus the 2nd tier of four routers will only use 4 of their outputs, instead of all 16.

sleepydog 8y ago
Thank you for this explanation, I understand now. Originally I thought you would want all routers in the path to hash the same flow the same way, but didn't think about how it interacts with layers of routers. On first guess, I would think a per-device salt is another way to address polarization. What are other ways?
- bogomipz 8y ago
  >"Originally I thought you would want all routers in the path to hash the same flow the same way," This is actually what you do want.
  - toast0 8y ago
    The problem is if all of the equipment hashes the same way, many of your links will be underutilized. If A has a link to B1 and B2, and each of B1 and B2 have two links to C, and everything hashes the same, there will only be two possible paths to C, instead of the four you should have. Ex: if packet hashes to 0, it goes to B1, and then over the 0 link to C. If packet hashes to 1, it goes to B2 and over the 1 link to C. If the Bs hash on different values than A (including if they have a different salt), you'll have better distribution on the B to C links, and actually be able to hit all 4 paths.
  - sleepydog 8y ago
    The property you want is that all packets for a given flow take the same path through the network (absent topology changes), to minimize out-of-order packets and ease troubleshooting. A1 +- B1 +- C1 | `- C2 | `- B2 +- C3 `- C4 In this example, if all routers compute the same hash value for a given packet, links B1 -> C2 and B2 -> C4 never get used, for any flows. So all you really need is for each router to make a consistent decision about packets in the same flow. They don't have to use the exact same hashing function. In addition to the cumulus networks link provided in the GP, it looks like Cisco gear also has a per-device salt: https://www.cisco.com/c/en/us/support/docs/ip/express-forwarding-cef/116376-technote-cef-00.html#anc5 https://www.cisco.com/c/en/us/support/docs/ip/express-forwar... Note that this has nothing to do with endpoint selection, just the intermediate hops. Edit: I'm also leaving out how the final modulo can produce different selections between layers. So in practice, if you have layers that are different sizes you'd get better utilization. That seems like a fragile thing to depend upon, though.
    - bogomipz 8y ago
      >"So all you really need is for each router to make a consistent decision about packets in the same flow." Indeed this is what I was trying to articulate but maybe I didn't do a good job of that. I mentioned somewhere else you can also just change the hash at each tier in your network - add IP protocol in one, don't use IP protocol in another. This should achieve the same as adding a "seed." to a router's hash.
- mcpherrinm 8y ago
  Per device salt is the usual way. See https://docs.cumulusnetworks.com/plugins/servlet/mobile#content/view/8358175 https://docs.cumulusnetworks.com/plugins/servlet/mobile#cont... for some example documentation (ctrlf hash seed). Or you can change the inputs to the hash function (eg, one tier hashes on source is and the other doesn't) but that's more troublesome.
bogomipz 8y ago
I think you are describing a CLOS(spine and leaf) network data center topology here. >"Now imagine you have four more routers on each of those links, hashing out over four more links. So you have a tree with 16 outputs." I'm not really understanding this as a link exists exactly between only two routers do you mean "path" instead? >"If the second-tier router uses the same hash algorithm as the first one, all the packets it receives will hash to the same link, because it's doing the same calculation as the router before it. And this is kind of the tax of flow based preservation which is fine compared to the price of TCP reordering no? Efficient hash-based ECMP utilization is going to be a function of the distribution of source IP and port in the 5 tuple used in hashing. You can see this outside of EMCP for example when running LVS with the hashing algo and you have customers that are all behind the same NAT box. But also there's nothing stopping you from using different hashing on your spine tier than you do on your leaf tier. You could assign a 4 tuple on one and a 5 tuple on the other. At any rate a common CLOS ECMP design with BGP is to put each ToR switch in its own ASN and then load balance across ASNs. So using your example and a 3 tier CLOS network. If Tier 2 had the 16 outputs then the a router should ECMP over the 16 different ToR ASNs to the destination.
- tatersolid 8y ago
  Pedantic: Clos isn’t an acronym and only the first letter should be capitalized. It’s a non-blocking switched network named after its inventor, Charles Clos.
- sleepydog 8y ago
  > And this is kind of the tax of flow based preservation which is fine compared to the price of TCP reordering no? Efficient hash-based ECMP utilization is going to be a function of the distribution of source IP and port in the 5 tuple used in hashing. mcpherrinm's example is worse than what I think you're suggesting. Because a given second-tier router will only receive packets that hash to a specific set of values, if that router has the same number of downstream links that the first tier router had, it will send all packets it receives to the same link, ignoring other links. Which is a terrible trade-off for avoiding OOO packets. The more reasonable trade-off is giving up on utilizing all routers for a single flow, to avoid OOO packets.
deleted 8y ago
[deleted]

sleepydog 8y ago

Thank you for this explanation, I understand now. Originally I thought you would want all routers in the path to hash the same flow the same way, but didn't think about how it interacts with layers of routers. On first guess, I would think a per-device salt is another way to address polarization. What are other ways?

bogomipz 8y ago
>"Originally I thought you would want all routers in the path to hash the same flow the same way," This is actually what you do want.
- toast0 8y ago
  The problem is if all of the equipment hashes the same way, many of your links will be underutilized. If A has a link to B1 and B2, and each of B1 and B2 have two links to C, and everything hashes the same, there will only be two possible paths to C, instead of the four you should have. Ex: if packet hashes to 0, it goes to B1, and then over the 0 link to C. If packet hashes to 1, it goes to B2 and over the 1 link to C. If the Bs hash on different values than A (including if they have a different salt), you'll have better distribution on the B to C links, and actually be able to hit all 4 paths.
- sleepydog 8y ago
  The property you want is that all packets for a given flow take the same path through the network (absent topology changes), to minimize out-of-order packets and ease troubleshooting. A1 +- B1 +- C1 | `- C2 | `- B2 +- C3 `- C4 In this example, if all routers compute the same hash value for a given packet, links B1 -> C2 and B2 -> C4 never get used, for any flows. So all you really need is for each router to make a consistent decision about packets in the same flow. They don't have to use the exact same hashing function. In addition to the cumulus networks link provided in the GP, it looks like Cisco gear also has a per-device salt: https://www.cisco.com/c/en/us/support/docs/ip/express-forwarding-cef/116376-technote-cef-00.html#anc5 https://www.cisco.com/c/en/us/support/docs/ip/express-forwar... Note that this has nothing to do with endpoint selection, just the intermediate hops. Edit: I'm also leaving out how the final modulo can produce different selections between layers. So in practice, if you have layers that are different sizes you'd get better utilization. That seems like a fragile thing to depend upon, though.
  - bogomipz 8y ago
    >"So all you really need is for each router to make a consistent decision about packets in the same flow." Indeed this is what I was trying to articulate but maybe I didn't do a good job of that. I mentioned somewhere else you can also just change the hash at each tier in your network - add IP protocol in one, don't use IP protocol in another. This should achieve the same as adding a "seed." to a router's hash.
mcpherrinm 8y ago
Per device salt is the usual way. See https://docs.cumulusnetworks.com/plugins/servlet/mobile#content/view/8358175 https://docs.cumulusnetworks.com/plugins/servlet/mobile#cont... for some example documentation (ctrlf hash seed). Or you can change the inputs to the hash function (eg, one tier hashes on source is and the other doesn't) but that's more troublesome.

bogomipz 8y ago

I think you are describing a CLOS(spine and leaf) network data center topology here. >"Now imagine you have four more routers on each of those links, hashing out over four more links. So you have a tree with 16 outputs." I'm not really understanding this as a link exists exactly between only two routers do you mean "path" instead? >"If the second-tier router uses the same hash algorithm as the first one, all the packets it receives will hash to the same link, because it's doing the same calculation as the router before it. And this is kind of the tax of flow based preservation which is fine compared to the price of TCP reordering no? Efficient hash-based ECMP utilization is going to be a function of the distribution of source IP and port in the 5 tuple used in hashing. You can see this outside of EMCP for example when running LVS with the hashing algo and you have customers that are all behind the same NAT box. But also there's nothing stopping you from using different hashing on your spine tier than you do on your leaf tier. You could assign a 4 tuple on one and a 5 tuple on the other. At any rate a common CLOS ECMP design with BGP is to put each ToR switch in its own ASN and then load balance across ASNs. So using your example and a 3 tier CLOS network. If Tier 2 had the 16 outputs then the a router should ECMP over the 16 different ToR ASNs to the destination.

tatersolid 8y ago
Pedantic: Clos isn’t an acronym and only the first letter should be capitalized. It’s a non-blocking switched network named after its inventor, Charles Clos.
sleepydog 8y ago
> And this is kind of the tax of flow based preservation which is fine compared to the price of TCP reordering no? Efficient hash-based ECMP utilization is going to be a function of the distribution of source IP and port in the 5 tuple used in hashing. mcpherrinm's example is worse than what I think you're suggesting. Because a given second-tier router will only receive packets that hash to a specific set of values, if that router has the same number of downstream links that the first tier router had, it will send all packets it receives to the same link, ignoring other links. Which is a terrible trade-off for avoiding OOO packets. The more reasonable trade-off is giving up on utilizing all routers for a single flow, to avoid OOO packets.

deleted 8y ago

[deleted]