ECMP, flow hashes, and collisions
Understand stable per-flow path selection without confusing equal-cost routes with equal utilization.
On this page
The question for today
What you’ll understand
- Explain why per-flow hashing can preserve a path while leaving load imbalanced.
- Calculate collision probability under an explicit independent uniform hash model.
- Separate flow-count distribution from byte-rate distribution.
Equal-cost multipath routing gives a forwarding decision several eligible next hops. A common design hashes selected flow-identifying fields so packets of a flow tend to choose the same next hop while the membership stays stable. That distributes decisions, not necessarily bytes. Two large transfers can collide on one path while other paths remain quiet. Treat the hash and traffic-size assumptions as part of the performance argument.
Stable flow selection has a purpose
Sending successive packets of a flow over paths with different delays can create reordering. Per-flow hashing avoids deliberate packet-by-packet striping by using a stable key, often derived from network and transport fields. The exact fields, tunnel handling, seed, and bucket mapping depend on the device. A fixed key with fixed forwarding membership normally selects the same next hop; a topology change or reconfiguration can invalidate that stability assumption.
Equal cost is a routing metric relationship, not a statement that paths have equal current queues or identical residual capacity. Two eligible paths may share a downstream bottleneck. An encapsulated workload may also expose too little key diversity if inner flow fields are not considered. Verify the actual packet headers and device hash behavior before assuming that opening many application requests creates equally many independent path choices.
Count imbalance and byte imbalance differ
If flows differ greatly in rate, equal flow counts can still give unequal utilization. A single long transfer can dominate a path containing many short requests. Across multiple stages, hash correlations may further concentrate traffic. The useful measurement is therefore per-link bytes, queue behavior, and flow completion under the relevant traffic matrix, not just the number of installed routes. Repeat tests with different flow keys and placements to reveal accidental favorable assignments.
Flowlets, adaptive routing, and endpoint multipathing can address some imbalance, but each has ordering, state, and feedback costs. A flowlet mechanism relies on a sufficient gap before moving traffic so earlier packets can drain; a universal gap is unsafe when path delay differences vary. Removing a next hop can remap active traffic. Distinguish a mechanism's intended balancing behavior from the transport's tolerance of reordering and from its measured response during membership changes.
Expose the random assumption in the lab
Use a test matrix with both many small flows and a small number of large synchronized flows. Record keys or reproducible key-generation rules, path membership, and observed link rates. A throughput drop that disappears when a source port changes is evidence for a hashing interaction, but still needs packet and forwarding confirmation. Keep routing failures separate from congestion: a path can be healthy and selected too often, or unavailable and still temporarily present in forwarding state.
In the probability lab, model each independent flow after the first as a success when it chooses the same one of four paths as that first flow. Reset, set both p=0.25 and n=3, predict mean 0.75 colliders and zero-collider probability 0.75³, then inspect. Play only highlights exact binomial outcomes; it does not sample a switch hash. The model ignores flow sizes, shared downstream links, correlated keys, and reassignment. Its independent uniform assumption is precisely the hypothesis being exposed.
Work it through
Four large flows do not ensure four used paths
Four equal-rate flows independently choose among four equal-capacity paths uniformly. Compute the probability that every flow chooses a different path.
The first flow may use any path. The second must avoid that path, giving probability 3/4; the third then has probability 2/4 of avoiding both occupied paths.
The fourth has probability 1/4 of selecting the remaining path. Multiply: 1×3/4×2/4×1/4=24/256=0.09375.
Thus at least one collision occurs with probability 1−0.09375=0.90625, or 90.625%. A collision is not automatically packet loss; its impact depends on rates, queues, and transport response.
With only a few large flows, a uniform hash can produce frequent collisions despite equal-cost path diversity.
The living notebook
Explore the model
Interactive lab · probability
Colliders with one reference flow
Reset, set p=0.25 and n=3, and predict mean 0.75 and P(K=0)=0.421875. These exact binomial probabilities assume independent uniform four-path choices relative to one reference flow; playback highlights outcomes without sampling actual hashes.
- Mean · np
- 5
- Variance · np(1−p)
- 2.5
- Total probability
- 1
These are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forAn independent hash model quantifies one collision event, not all path utilization or congestion.
Pause & reason
Check your understanding
Your turn
Try it yourself
Two independent equal-rate flows each send 60 Gbit/s and select uniformly among four 100 Gbit/s paths. Find their collision probability and the offered rate on their shared path when they collide.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Condition on the first choice, then compare offered rate with one path's capacity.
Compare with the solution
The second flow matches the first with probability 1/4=25%. In that event they offer 120 Gbit/s to one 100 Gbit/s path, exceeding its capacity by 20 Gbit/s before feedback. Other paths may be idle. This does not predict a fixed loss rate or completion time because queues and congestion control respond to the overload.
Keep the idea
Take it with you
- Stable per-flow hashes address ordering, not perfect byte balance.
- Collision calculations depend on explicit independence and uniformity assumptions.
- Measure bytes and queues across relevant paths and traffic keys.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.