Kentik - Network Observability
More episodes
Telemetry Now  |  Season 1 - Episode 32  |  March 12, 2024

Using Paris Traceroute for Modern Load-Balanced Networks

Play now


Traditional traceroute is a widely used and very useful tool, but it struggles to accurately trace load-balanced networks. In this episode, Dr. Justin Rohrer joins us to talk about Paris traceroute, an extension of traditional traceroute, and how it's used to trace paths on a network that uses flow-based load balancing, or in other words, most of the internet. Learn more about Paris traceroute in Phil's blog post, The Power of Paris Traceroute for Modern Load-Balanced Networks.


If you're a network engineer or just work in tech in pretty much any capacity, you're probably already familiar with trace route.

A mechanism that we use to trace the path between a source and destination over a network. And that sounds straightforward enough, but the way that we do networking today, especially when you take the public internet into account poses some challenges to trace route. Or what I'm gonna call in this episode legacy or traditional trace route.

With me today is doctor Justin Rohrer, a subject matter expert on Paris traceroute, a newer version of traceroute that you might not be familiar with. So today's episode is gonna be a little in the weeds, which is just the way I like it, and I hope that you do too. My name is Philip Dhruvasse, and this is telemetry.

Justin, thank you so much for joining me today. I know that, trace route is something that's very familiar to most network engineers, and and really to a lot of people working in tech in general help desks, assist admins, all that. Three years and years and years, So I I really, am interested in talking about this newer version of trace route, Paris trace route, what problems it solves, why it's necessary today, And, and I I do appreciate you bringing your subject matter expertise to the show today. So thanks very much.

Yeah. It's no problem at all.

I'm gonna have to be Justin, before we get started, can you give us a little bit about your background, maybe even your formal education, and what you specialized in?

Right. So my PhD is actually actually an electrical engineering.

I That's what I did as an undergrad, and kind of worked my way up the stack over time. I was always really interested in networking, but, when I was starting to look at graduate school, the hot thing was optical networking, is a very, you know, physical sciences oriented, approach. And then, as time went on, I became more and more interested in the science of network resilience and survivability, and a lot of that, comes into play with software stacks and the interaction between the layering of the protocols and things like this. So, by the time I finished my PhD, I ended up working as a professor in computer science for over a decade and, teaching, you know, networking from the software side of things rather than from the, hardware side of things.

Oh, interesting. I I didn't know that you were a professor. I mean, I knew you were in academia for a long time. Anyone who's getting a PhD, especially in the sciences, is gonna be in academia for a long time, but I didn't know that you were a teacher as a professor. So that's pretty interesting.

Also interesting something that you mentioned is that you are approaching networking from the software side of things. And, you know, without giving away your age, that that happened years ago. Right? And so it's just so interesting to me that we're talking about, you know, approaching networking in the context of soft where infrastructure is code and all these things today.

Right? Like it's some new thing. But years and decades ago, VLANs were invented, which is a a construct written in in software for networking. So I don't know.

It's just interesting to me that we we really kind of been talking about this stuff for years and even decades anyway.

So anyway, let's focus on today's episode, a discussion of trace route. And specifically Paris Trace route.

Now, I'm not gonna give you a definition of trace route per se because, I think most of our audience is familiar with tools like ping and trace route. Again, that exist on most systems out there from networking devices to most operating systems as well.

But, let's start with a quick recap of what trace route is, and I guess I'll use the term traditional trace route, legacy trace route. What do you think, Justin?

Yeah. I think traditional trace route is good.

Sometimes we could call it legacy traceroute, but it's not like it's deprecated in any way. It's it's still the tool that's on all these systems.

Right. So legacy in the sense that there are new versions, but not legacy in the sense that it's completely deprecated and is already replaced on all systems everywhere with some other more modern, maybe better solution. Now we are gonna talk a more about a more, modern solution Paris Trace route. But it's important to understand that that is not installed everywhere. So folks are still relying very much on traditional or legacy traceroute in their day to day network operations. So in that light, Justin, can you give us a little bit of a background, technical explanation of how traceroute works and what we use it for?

Right. It's kind of filling in a gap in IP, where we don't have any instrumentation about the path that traffic flows over from end to end just natively in IP protocol. And so it's it's a little bit of a hack that, uses the IP TTL field in the header to try and interrogate the different hops on and so it starts with a low value of that TTL so that it will expire at the first hop, and it'll get back an error message essentially from that router, which is the ICMP time exceeded message. And then it will send a packet that expires at the second hop, and it'll get that same message back hopefully, and then construct the path in terms of the IP addresses that send the Trace strat application, these ICMP messages.

Right. So a hack, not in the sense that we're just hobbling together random technologies haphazardly, but we're using technology and mechanisms and information that wasn't necessarily intended to do what we're doing in this case with trace route to solve that particular problem But as as I guess engineers do, right? You use what you have in order to solve the problem at hand. So in this case, we're using things like ICMP and TTL messages and and and all that information that we, that we have available to us to then trace a path, which is a, something that's lacking inherently in IP. Right?

Exactly. Yeah. It's a hack in the, the traditional terms of, you know, using things expediently, not, for nefarious purposes. And, the, you know, that's not what the ICMP time exceeded messages were intended for. They're intended to expire packets that might have gotten stuck in a routing loop or something like that.

I guess the other thing to mention here is that, traceroute sends UDP packets by default, at least on on Linux and BSD systems, it's sending out UDP packets, and but it can be done with you know, TCP send messages or ISMP ping packets, Windows uses the ISMP ping packets by default. So any of these can be used because they're just expiring based on this field in the IP header.

Okay. So we have trace route that has not been hobbled together, but it is kind of a hack again, using the technology that we have at hand to solve a problem.

So with the advent of newer forms of trace route like parris trace route, again, the topic of today's episode. Does that mean that trace route is just completely dysfunctional, broken, and we needed a solution to fix it? Or a solution rather to replace it entirely. I mean, it is everywhere on pretty much every operating system, every network device, and I have used it extensively over the course of many years of my career. I would say decades now. Right?

I so I guess I want to mention a couple things that it, that it does well first because, It's not like you have to completely replace traditional traceroute with Paris traceroute.

It can answer questions for you like just how far away is this destination? You know, am I going to my ISP to reach something or, you know, one ASA, or am I going across you know, the country, the internet, you know, just to get a notion of how many hop star it does, it works just fine for that. If you don't, like, care, very specifically about which hops are in the path and just want to get this general notion of distance. It does fine for that. Also, you know, probably the most common thing I use it for is I can't reach something and I wanna know where the path is broken. Like, is the traffic getting out of my house? Is it getting out of my data center, right, is it getting out of my ISP, that kind of notion of, just in broad terms where is the path broken?

Okay. So so trace route, traditional trace route. I'm not gonna use the term legacy because as you said, we're still using it. It's still very useful.

So maybe not legacy. But I think we can say traditional trace route as compared to newer forms is still very, very ubiquitous. It's very commonly used out there and very useful to us Now I know that there are ways to trace path in, layer two, but here we're talking primarily about layer three, hop by hop, where are my packets going, assuming that those hops, especially if they're out there on the public internet, like ISPs, are returning that information to us. Okay.

Traditional trace route is still very useful. We get that. Where does it fall short such that we need something new like Paris trace route?

Yeah. So then where you run into issues is when you want to know specifically what path am I taking and characteristics of that path, and it involves load balancing.

And, Okay.

Well, not to cut you off, but it sounds like load balancing is primary driver here. Load balancing is where traditional trace route is lacking. A general inability to be able to trace paths, when there is layer three, I assume load balancing occurring.

But what are the technical reasons for that? Why can't traditional tracer out handle that?

The reason technical reasons that this becomes an issue for traditional traceroute is that it has to encode a sequence number in each packet it sends so that when it gets the ISMP responses back, They have a snippet of that original packet, including the sequence number, and it can match up the responses with the packet that was sent. In the ICMP header, there's a field for the sequence number, and, in the UDP header, there's no sequence number, and so it instead encodes the sequence number in the destination port and then in the TCP header, it can use the sequence number.

So that's not an issue for TCP, but for UDPNISMP, using those fields, causes routers to think these packets are part of separate flows. And so when the router goes to do flow based load balancing, it doesn't keep the packets together on the same path, so one packet may go down, one load balanced path, the next packet goes down a different one. And when Traceroute puts these responses back together. It says, Oh, here is the path, and it it says there's links effectively between these interfaces that may not exist. Alright.

And that's assuming both paths are the same length. You may just get kind of a random assortment of of hops that are actually different paths, and don't actually have links to each other.

In the cases of, of unbalanced load balancing, which kind of an oxymoron, but where the load balance has our different lengths, It can actually look like you've got a loop in the path. You might see the same hop appear multiple times. And when you're trying to diagnose something, right? This looks like, oh, I've got a routing problem here when Actually, it's just load balancing. It's all working correctly.

But traditional traceroute made the wrong inferences for you.

Okay. So you're getting, either, completely imaginary links. You're getting maybe, indication of a routing loop that doesn't exist. We wanna know if there are routing loops, of course. And and and, you know, trace route is one of the first things that I'll do to look at that and see if the IP address is basically flipped back and forth back and forth. But, ultimately, there might be something that in the results that indicates that and it doesn't exist at all. So so trace route, when we're talking about the context of load balancing typically flow bay flow based load balancing in particular, is potentially inaccurate.

So how do we solve for this? We have Paris Trace route And when I say Paris Trace wrote, I mean Paris as in the city, p a r I s.

First introduced around, I think, two thousand six is when the first papers came out, and named after the city of Paris because the authors were working in and through several universities in the city of Paris and then in the suburbs, just south of Paris.

And then some subsequent talks were given in Munich and other cities in Europe, to socialize the technology. But ultimately, that's what we're talking about as far as the origin and that time period. So around two thousand six, two thousand seven, Now how does Paris trace route differ from trace route? How does it solve the problem for us?

Right. So in the the cases where the paths are load balanced. And by the way, we see load balancing in about sixty five percent of all paths on the internet. So it's very prevalent.

And of those about ninety eight percent are flow based. So this is very applicable to the pattern I should see in the internet.

Basically, the goal of Paris trace route is to keep the headers consistent across all the probe packets, such that they're all treated as part of the same flow.

So they got creative in where to put the sequence numbers so that it doesn't change, for example, in UDP, it doesn't change the destination port number it's included, somewhere else in the header. I'm forgetting off the top of my head, but the key is that it maintains the specific, header fields that are used to define a flow by routers doing flow based load balancing. Those fields, by the way, are the source and destination IP address, the protocol, and the source destination port number.

And, and typically it's just using byte offsets and looking at a hash of that. And so, certain of the ICMP headers will also get caught up in those, by offsets. And that includes the ICMP header checksum.

So you can't change anything in ICMP header that would change the checksum. Otherwise, it'll get treated as different flows.

So they do some some magic to still be able to encode the sequence number, but, add other data in the header so that the checks and voice comes out the same Okay.

I understand. So the real issue here is that trace route or at least the the packets that trace route uses in its probes operate differently on the network than regular application traffic does. So application traffic is gonna be load balanced, at least by flow, by pinning that flow using sequence numbers and check sums and whatever else to particular links and particular paths, whereas trace route is just sending packet by packet for their probes. And so it's not being pinned to anything.

There's no there's no concept of sending everything down the same path for the multiple probes that trace route is gonna use. They're in giving us the problem of imaginary links, false links, routing loops that might not even be there. And and ultimately the in accuracy that we get in flow based load balancing or rather flow based load balance networks and trying to use trace route on them. Right.

Yeah. So by keeping all the paths within a given traceroute, or sorry, all the packets within a given traceroute on the same path, Then if you see two interfaces next to each other, you can reasonably infer that there really is a link there that they didn't go down different paths.

Along the way, it also solves that problem of having the perceived routing loops because if your packets took the longer path, they all took the longer path. And so your responses all come back in a reasonable sequence.

Okay. So what we're doing here is we're keeping our sequence numbers among all of our, path probes used by trace route consistent. So that way, that forwarding decisions are are made such that they all, all the probes go down the same path.

Whether that's using sequence numbers, check some, or whatever other mechanisms.

But, really, the underlying technology doesn't really differ that much. I mean, we're still sending out, probes to get back time exceeded messages.

And, and really it operates very similar, if not the same as traditional trace route does. So Paris trace route does not really differ that much from traditional trace route in that sense. Does it?

It does not, and it can still use UDP TCP or ICMP. All the tools that I'm aware of support all three of those packet types.

So then if Paris Trace route gives us all the same information that we get in traditional trace route except it solves those inaccuracies that we have on flow based load balance networks, which as you said before is like everything on the internet. Right? Wouldn't it make sense to just replace trace route everywhere with with this new modern Paris trace route? And just just use that moving forward as everywhere that we can.

You could, if you wanted to go to the trouble of installing it everywhere that you want to use it, but I don't think it's necessary.


It's more being aware of. I'm trying to use this for a use case that, I could inaccurate information from tree straw. So, really, I should go install one of these tools that runs the Paris version and, and use it in those cases.

Now when I actually run it in experiment with it. I'm getting multiple responses back. I'm not just getting, you know, one one particular response per probe or per run. I'm getting multiple, results in the output. And I'm not exactly sure why. Can you explain what that means?

I so I I think you're referring to getting the three different timings per hop. The idea there is that it's, it's just so common for either one of these packets to get lost, especially, because ICMP responses have to be handled by the router CPU typically. They're not a fast path response. And so if that CPU is busy, it may just not respond, to a particular packet or, it could just be general congestion or whatever losing packets. On the internet, there's no, you know, reliability here for retransmissions.

So part of it is for that.

It's also the case that when you're looking at latencies and trying to get a trying to correlate latency to distance, you want the lowest value, right? You can never, you can never beat the speed of light, but your latencies can be highly affected by congestion and buffering on the path. And so if you get three samples back, you can just say, well, the lowest one is the closest correlation to distance, and that might be the one you want.

Alright. So what we're talking about right now is sort of testing or monitoring. I'm not sure which term to use a production network. But we're not using production traffic.

It's not like we're looking at an end user's application traffic and then determining what the latency is or what the what the path is that that application traffic is taking. These are test probes, whether it's trace route or Paris trace route. So this is this is artificial traffic. I mean, it's real traffic.

It's on a production network, but it's not an end user's traffic. So it's passive in that sense. And I guess this is the difference between active and passive monitoring, active and passive testing, And I noticed in our show notes and in some of the literature, from you, actually, you use the term active and passive measurement. You use the term measurement specifically.

So I I do wanna understand why, but can you explain a little bit about the difference between active and passive monitoring and then and then, of course, measurement.

Right. Yeah, I use the term measurement because I I do think of of Paris as a a measurement tool in terms of measuring topology, right, some some flavor of topology.

And in, passive measurements, we're just collecting data, whether it's, you know, Pcap, we're collecting raw traffic, or you're collecting your net flow, sampled traffic or even pulling SMM SMP to get counters that are passively collected as traffic flows through an interface and, you know, in the control plane, we have BGP looking glasses where we collect routing information.

From the internet. So those are all the things where we're not injecting traffic into the network as part of the measurements. And then, Tracer out, of course, falls into the the active category where we're injecting that traffic. And, in in, you know, when you run one traceroute, you generate something like, you know, maybe fifty packets.

Right? It's a very small number of packets that you hope is not affecting anything in your network. Right? If your network changes its behavior based on fifty packets, you're really info.

But in aggregate, if you are trying to do really large scale measurements, you know, you wanna see how the whole internet gets to your AS, for example, you might need to run a hundred million trace drops. And at that point, you can really start affecting things. And, An example of that comes into play with something called ICMP rate limiting.

So routers by default will have a a rate limit of how many ICMP responses they can generate. And if you're doing high volume trace route, it's, pretty easy to induce the routers to hit those limits. And stop responding to you. And so then you have trace routes where you're getting a bunch of stars back, right? And so now you can no longer infer that part of the path. It may also be, you know, viewed poorly by, service providers that you're causing this load on their CPUs and and causing those, routers to stop sending the ICMP messages that they should be.

So that's something to be really aware of when scaling up active measurements.

Yeah. That makes sense. I mean, really it's just basic math. When you have a very small sample size, a small dataset, there's a potential for inaccurate results.

So you use a larger dataset, a larger sample size. In this case, with trace route, paris trace route, you send out more probes and you get hopefully more accurate results. But when you in inundate the network with a a huge number of probes, there is a potential of some of those devices in the path presumably routers dropping your traffic or just skewing the results themselves. Like you're you're adversely affecting latency because you're inundating a production network with with more packets with traffic.

So let me ask you, Justin. What are the limit tations of Paris trace route. I mean, what I just explained was more of an operational, thing, not necessarily a deficiency in the in the mechanism itself, But you tell me, what are the limitations of Paris Trace route?

So the main limitation that comes out of of just running you know, like a single Paris tree trout versus a single traditional tree trout is that the Paris tree trout by keeping all the packets on the same path through load balancing actually hides that load balancing from you, right? So you you can't tell where load balancing might be happened. Might be happening.

Where traditional traceroute with those three responses, oftentimes you'll notice that at a given hop, you got different answers. Because those paths are different paths. And so it's, in one hand, telling you something incorrect about what's linked to what? But it gave you that hint that, yeah, there's load balancing around these hops.

And maybe you, you know, maybe you care about that.

So for Paris Trace to do something similar, you need to run it a bunch of times, basically, with different flow identifiers.

And so there's kind of an add on on top of Paris traceroute called MPA traceroute. Which can do this, but it becomes far more expensive in terms of the number of packets you're sending to interrogate a specific path.

So is then that's just the the way to solve for that limitation, just send out more packets, more probes.

And in this case, you mentioned MDA Paris Trace Round Right.

I mean, if you just run Paris with its default settings, it's not gonna do any of that for you. And so it'll just look like there's a single path to anywhere.

Alright. So this variation of Paris traceroute called MDA traceroute, you mentioned, the multipath detection algorithm. Right? That sends, a lot more probes to factor in for possible load balancing.

Right? And I get it. And so by sending more probes, you can vary the flow identifiers. I think you mentioned and you can trace those multiple paths more accurately.

So it sounds like the underlying mechanism with even MDA, the MDA version or variation of Paris Trace route is also the same where it's using some of the same underlying or the same underlying technology. Right? Is it is it any different? That's my first question.

And then my follow-up question of that is should we therefore be seeking to install Paris Trace route and it's variations everywhere and using that as our primary method, especially as network engineers and network operators.

Oh, no. No. The the hot by hot mechanisms are the same using ICMP and it's already part of the IP stack everywhere.

What I meant by that is more if you're, trace routing from different servers, in your infrastructure, you would need to install it in those places as opposed to traditional trace route that's probably already there and whatever distribution you're using.

And then if you are trace routing from routers, you may not even have the option to install Paris trace route.

Yeah. So so that doesn't sound like a limitation of Paris trace route to me because it's more of a, more of an adoption problem. I mean, there's nothing technically deficient there with trace route in that sense, at least. It's really a matter of, operating systems out there both in compute and network devices not supporting it, or you have to go and manually install it, which is a operational problem.

Right? And, and so we use traditional tracer out everywhere. It's everywhere. It's commonly installed, and so we rely on that at first.

And then when we need something like Paris Trace route, we install it where we can, and where we install it is on the sending device. It's on the device that's generating that Paris tracer out traffic, those probes. And so whether that's on some kind of a compute node, your operating system in front of you or, or network devices themselves.

So, Justin, what would be your advice, your recommendation, to those that are managing networks right now and wanna improve their strategy of how they can trace application traffic over the network, especially over the public internet. So for those engineers, like network engineers, network security, maybe, cloud engineers as well, those working in in operations, what would your advice be to them?

Yeah. Certainly, if if Tracehot is part of your regular, operations and troubleshooting and everything, it's worth having that tool in the toolkit as you were talking about, you know, experimenting with it, it's worth mentioning that there's, at least three different, you know, software packages that implement Parastrace route. And so at Kentech, we use the scamper package, and that's out there readily available. I I put the link in the document to that one. I think that one's the most widely used by folks doing kind of the large scale measurement projects, and then there's also the Yarp implementation, which is for doing very large scale, you know, like if you have a thousand or a hundred thousand destinations that you want to trace route to all at once, kind of like the z map of of trace route.

That's the one that I've used the most in the past.

But these tools are all, you know, have their strengths and weaknesses and are worth playing with.

Yep. That makes sense. So ultimately, the encouragement is to install it where you can when you can, perhaps starting on the computer sitting in front of you right now, and, and just get familiar with it and experiment and see the kind of results that you can get back and how Paris Trace route operates and maybe eventually add it to your overall network operations strategy.

So Justin, this has been a very interesting episode. I love getting into the weeds on this kind of stuff, so I appreciate you joining me today and for bringing us your subject matter expertise. And I will make sure to link in the show notes on the website the various resources that we alluded to today. So if folks wanna reach out to you with a question or a comment of some sort, how can they find you online?

Yeah. You can, Google my name. Some version of, of, site or social media will come up my kentech email is j roar at kentech dot com, so you can reach me that way.

Great. And that's rohrer spelled r o h r e r. So j ror at kentech dot com.

And you could still find me online on Twitter at network underscore fill. My blog network fill dot com, and you can search my name in LinkedIn and, some other various social media as well. LinkedIn being kind of the primary these days. Now, if you would like to be a guest on telemetry now or if you have an idea for an episode, I'd love to hear from you. You can reach out to us at telemetry now at pentic dot com, and, we'll start a conversation there.

So for now, thanks very much for listening. See you soon.

About Telemetry Now

Do you dread forgetting to use the “add” command on a trunk port? Do you grit your teeth when the coffee maker isn't working, and everyone says, “It’s the network’s fault?” Do you like to blame DNS for everything because you know deep down, in the bottom of your heart, it probably is DNS? Well, you're in the right place! Telemetry Now is the podcast for you! Tune in and let the packets wash over you as host Phil Gervasi and his expert guests talk networking, network engineering and related careers, emerging technologies, and more.
We use cookies to deliver our services.
By using our website, you agree to the use of cookies as described in our Privacy Policy.