Implementing Paris Traceroute in Rust: Tracing Paths Through Load Balancers

Standard traceroute is broken on modern networks.

If you've ever run traceroute to debug a connectivity issue and seen wildly inconsistent hops, you've hit this problem. The culprit: Equal-Cost Multi-Path (ECMP) routing.

The Problem

ECMP load balancers distribute traffic across multiple paths based on flow identifiers — typically a hash of source IP, destination IP, source port, and destination port. Traditional traceroute changes the destination port (or ICMP sequence number) for each probe, which means each probe can take a completely different path through the network.

The result? A traceroute that shows hops from multiple physical paths stitched together into one nonsensical output.

Paris Traceroute

In 2006, Augustin et al. published "Avoiding traceroute anomalies with Paris traceroute" at IMC. The key insight: keep flow identifiers constant across all probes so they all traverse the same path.

For UDP probes, this means:

• Same source port
• Same destination port
• Vary the TTL (and checksum) only

For ICMP, it's trickier — ICMP echo requests don't have ports. Paris Traceroute manipulates the ICMP checksum field to maintain a constant value that ECMP routers hash on.

Implementing in Rust

I couldn't find a pure-Rust implementation, so I built one in multiprobe.

The core concept is a FlowId that stays constant:

rust
pub struct FlowId {
    pub src_port: u16,
    pub dst_port: u16,
    pub identifier: u16,
}

impl FlowId {
    pub fn udp(src: u16, dst: u16) -> Self {
        Self { src_port: src, dst_port: dst, identifier: 0 }
    }
}
When sending probes, we only vary the TTL:


let trace = Probe::paris("example.com")
    .flow_id(FlowId::udp(33434, 33434))
    .max_hops(30)
    .send().await?;

for hop in &trace.hops {
    println!("{:2}. {:15} {:.2}ms", 
        hop.ttl, 
        hop.addr.map(|ip| ip.to_string()).unwrap_or("*".into()),
        hop.rtt.as_secs_f64() * 1000.0);
}
Detecting Load Balancing
Once you can trace a single path consistently, you can also detect load balancing by sending probes with different flow IDs and comparing the paths:


let paths = discover_paths("example.com", 6, &Default::default()).await?;
println!("Found {} distinct paths", paths.len());
If you get multiple distinct paths, you've found an ECMP load balancer.

Results
With Paris Traceroute, you get:

Consistent paths through ECMP networks
Accurate hop-by-hop latency measurements
Load balancer detection (per-flow vs per-packet)
Try It

[dependencies]
multiprobe = "0.1"
crates.io
GitHub
docs.rs
References
Augustin, B., et al. "Avoiding traceroute anomalies with Paris traceroute." IMC 2006.
RFC 1191: Path MTU Discovery
Questions or feedback? Open an issue on GitHub or find me on [platform].

Comments

[Baptiste Le Bouquin]

The ECMP problem is exactly why I stopped trusting visual traceroute years ago. The hops stitching paths from different flows together is infuriating — you fix an issue with one probe, and the "next hop" is meaningless on the next run because the flow hash changed.

The multi-path approach you describe is the key insight: if you can force probes to stay on a single flow by keeping source/dest port constant, the topology becomes readable again. I've seen this bite hardest through load balancers and anycast front-ends where the hash input varies per packet.

One thing I'd love to read more about: how do you handle reverse-path asymmetry when the return traffic leaves on a different ECMP path than the probe went in on? Do you report both directions, or just the forward? That's usually where my traces fall apart in real troubleshooting. Nice to see Rust getting serious network tooling here.

[Biplab]

Great point - yeah, reverse-path asymmetry is the elephant in the room here. Right now multiprobe only sees the forward direction. The ICMP TTL Exceeded comes back on whatever path the router chooses, which could be totally different ECMP branches.
Honestly, properly solving this is hard without a cooperating endpoint. You'd need something on the other side sending probes back, or at minimum echoing timestamps so you can compare. I've thought about adding a server component for exactly this. For anycast troubleshooting specifically, I've had better luck just running traces from multiple vantage points rather than trying to infer the reverse path from one spot. Curious if you've found anything that works better?
This is on my list for future work - would love to hear what you'd want from a bidirectional mode if I built one.