6 ms·

If you're doing multi-tier ECMP with the same hashing algorithm at each tier, using TTL can ensure you don't get polarization issues. Though there's plenty of

If you're doing multi-tier ECMP with the same hashing algorithm at each tier, using TTL can ensure you don't get polarization issues. Though there's plenty of other ways to avoid polarization, this works out of the box. I have heard fastly competitors tut-tut their use of anycast as potentially unreliable in the face of issues like this.

greglindahl 8y ago
"this works out of the box" seems a bit of an odd thing to say when it's not working for significant edge cases. Maybe "it worked when we first tested it" is better? :-)
- p1necone 8y ago
  I dunno, in my experience anything that "works right out of the box" usually misses a bunch of edge cases (possibly necessarily/by definition). The description seems apt to me.
bogomipz 8y ago
What is "polarization" here? I am not familiar with this term applied to routing? Oscillating between different available paths?
- zkms 8y ago
  > Oscillating between different available paths? The term for unwanted oscillation between different paths is, IIRC, "flapping". However, when working with ECMP (equal-cost multi path), you actually do want to use all your paths (hence "equal cost") simultaneously (for load-balancing purposes, say). "Polarisation" refers to the unwanted condition when the hash algorithm that decides which path a flow/packet takes is not properly distributing flows/packets across links, leading to underutilisation and/or overutilisation of links/routes.
  - bogomipz 8y ago
    Sure, I meant when the same 5 tuple is oscillating between different paths which really should not happen. You mentioned there were plenty other ways to avoid polarization. I would be curious to hear what those are.
    - alecbenzer 8y ago
      New to most of this but couldn't you just salt the hashes being used per-router?
      - bogomipz 8y ago
        Yeah I think you could seed each router's hashing with something unique like a mac address hardware ID but you could also just use different hashing at each tier in your network like using source IP + dest IP on one tier and source IP + dest IP + IP protocol on another tier. This should achieve the same result.
        alecbenzer 8y ago
        Yeah but then you need to keep coming up with new ways of hashing things as you add tiers. It's easier to generate a new salt than it is to figure out a new but still-valid way of hashing the packets.
        bogomipz 8y ago
        Practically speaking this isn't an issue though. You don't see many spine and leaf networks that are deeper than 3 tiers(edge, distribution, ToR) which means one link upstream and one down. It's not like people build networks arbitrarily deep.
- mcpherrinm 8y ago
  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.

greglindahl 8y ago

"this works out of the box" seems a bit of an odd thing to say when it's not working for significant edge cases. Maybe "it worked when we first tested it" is better? :-)

p1necone 8y ago
I dunno, in my experience anything that "works right out of the box" usually misses a bunch of edge cases (possibly necessarily/by definition). The description seems apt to me.

bogomipz 8y ago

What is "polarization" here? I am not familiar with this term applied to routing? Oscillating between different available paths?

zkms 8y ago
> Oscillating between different available paths? The term for unwanted oscillation between different paths is, IIRC, "flapping". However, when working with ECMP (equal-cost multi path), you actually do want to use all your paths (hence "equal cost") simultaneously (for load-balancing purposes, say). "Polarisation" refers to the unwanted condition when the hash algorithm that decides which path a flow/packet takes is not properly distributing flows/packets across links, leading to underutilisation and/or overutilisation of links/routes.
- bogomipz 8y ago
  Sure, I meant when the same 5 tuple is oscillating between different paths which really should not happen. You mentioned there were plenty other ways to avoid polarization. I would be curious to hear what those are.
  - alecbenzer 8y ago
    New to most of this but couldn't you just salt the hashes being used per-router?
    - bogomipz 8y ago
      Yeah I think you could seed each router's hashing with something unique like a mac address hardware ID but you could also just use different hashing at each tier in your network like using source IP + dest IP on one tier and source IP + dest IP + IP protocol on another tier. This should achieve the same result.
      - alecbenzer 8y ago
        Yeah but then you need to keep coming up with new ways of hashing things as you add tiers. It's easier to generate a new salt than it is to figure out a new but still-valid way of hashing the packets.
        bogomipz 8y ago
        Practically speaking this isn't an issue though. You don't see many spine and leaf networks that are deeper than 3 tiers(edge, distribution, ToR) which means one link upstream and one down. It's not like people build networks arbitrarily deep.
mcpherrinm 8y ago
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.