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.
Huh? No you would never want to use "all" routers for a single flow anyway. Each router just needs to make a deterministic selection for each packet. The alternative to a hash based scheme would be per packet load balancing which is practically never used b/c it gives you TCP packet reordering.
>"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"
No it would not be a terrible trade off. Optimizing for maximum link utilization only matters if you have congestion in your network and even then ECMP is congestion agnostic. In reality your leaf network has less downstream link that it has upstream. A common topology is 4x4x2 where each leaf node has two downstream links to two ToR switches.
>"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.