Traceroute the World

ICMP 一直是我最喜欢的协议，在没有机器/设备的登录权限的时候，ICMP (ping) 可以让我在 debug 的时候获得很多关键的信息：网络通不通，延迟多少，有没有环路，经过了哪些设备，等等。其中比较关键的机制，一个是 ping 工具，即 echo/reply 机制；另一个是在 TTL 耗尽的时候发回来 ICMP 错误信息¹，这是 traceroute 工具实现的基础原理。

在网上经常有人贴出来一些奇奇怪怪的 traceroute 结果²，有人找到很长的 traceroute 会很兴奋。所以…… 我想我们能不能用系统的方法找到 traceroute 比较长的 IP 呢？

虽然这个问题没有什么实际的意义，但是本文在探索这个问题的时候会遇到一些常见的技术，还是挺有意思的。

实验 traceroute 的起点，我们设置在新加坡。

新加坡是一个重要的交通枢纽。这是在写这篇文章的时候，新加坡附近起降的飞机（PS，新加坡的樟宜机场是我最喜欢的机场，如果你路过新加坡的话，建议给樟宜机场预留多 2 个小时的时间逛一逛）。

也是一个重要的海上枢纽。

在网络方面，新加坡也有丰富的海底光缆。

所以，预期最长的 hop 不会太高，现在世界的互联网越来越扁平了，一般一个互联网 IP 可以在 10-20 个 hop 触达。我用了一台 DigitalOcean 的机器来做这个实验，用它来 traceroute 1.1.1.1 只需要 8 跳，延迟在 1ms 左右。

回到本文的问题：找到一个 traceroute 最长的 IP，直观的方法就是 traceroute 每一个互联网的 IP。（本文只讨论 IPv4）

traceroute 对每一跳发 3 个包，超时时间 5s，最长 hop 尝试 30 跳。假设平均 15 跳完成，15 跳 × 3 探针 × ~100ms RTT = 5s，如果 IP ping 不通，那么 traceroute 可能要花 2min 以上。即使按照 5s 来算，我们 traceroute 整个互联网也需要：4,294,967,296 × 5 秒 = 21,474,836,480 秒 ≈ 680 年。如果开 1000 个并发，也需要 680 年 ÷ 1000 = 0.68 年 ≈ 248 天，大约8个月的时间。

怎样加快呢？

先来看一下现在的时间花在哪里了。traceroute 的逻辑是：对于目标 IP，发送 TTL=1 的包，等待回复，然后再重复 2 次；接下来换 TTL=2 的包，发送，等待回复，重复 3 次……

这样有两个问题：

1. 时间都在等待回复上了，效率太低；
2. 一个进程只能 trace 1 个目标 IP，如果开并发的话，会消耗很多 CPU 在 context switch 上，实际发出去的包非常少，CPU 使用率却很高；

对于本文的这个项目，我们是想找出来 traceroute 最长的一个 IP，而并不关心具体的路径。

要求高性能，我们换一个方式：不再使用发送——等待，我们设计两个程序，一个给所有的 IP 一起发送包，另一个监听收到的回应，如果是 ICMP 的 reply 包，就记录此 IP 可以 ping 通，如果收到其他的 ICMP 类型的包，直接丢弃即可。这样就完全没有等待时间了，而且之后两个程序，上下文切换的问题也解决了。

但是这就有了一个新的问题：我们怎么知道收到的包对应的 TTL 是多少呢？仅通过收到的 ICMP Time Exceeded 包是无法知道 TTL 消耗了多少的，怎么找到最长的 TTL 呢？

为了区分出来 TTL，我们分多轮进行扫描，先对所有的 IP 发送 TTL=1 的包，接收程序如果收到了 ICMP reply 的回应，说明这些 IP 在 TTL=1 的时候就能 ping 通，由于我们要找的是 TTL 越长越好，所以这些 IP可以直接淘汰了。接下来我们把 TTL=1 不能 ping 通的包，用 TTL=2 再发送一轮，如果能收到 ICMP reply，那么也可以淘汰了…… 假设我们在 TTL=30 的时候有一些 IP 能 ping 通，但是在 TTL=31 以及之后的时候没有任何 IP 可以 ping 通，那就说明这些 TTL=30 的 IP 就是胜者。

这样需要多久呢？

DigitalOcean 页面解释：All other Droplets have a maximum network throughput limit of 2 Gbps³. 每一个 ICMP 包的大小是：Ethernet 14 + IP 20 + ICMP 8 + payload 32 = 74 bytes，所以，理论上我们可以跑到：

2 Gbps ÷ (74 bytes × 8 bits) = 2,000,000,000 ÷ 592 ≈ 3,378,378 pps ≈ 3.4M pps

Ping 一次整个互联网只需要：

4,294,967,296 （2^32，所有的 IPv4 数量） ÷ 3,400,000 ≈ 1263 秒 ≈ 21 分钟

但是为了避免 overload 接受端（大量网段在同一个区域），以及中间设备可能存在的 conntrack，我们把速度限制在 100K pps，这样，只用了全速的 2.7%，ping 一次需要的时间是：

4,294,967,296 ÷ 100,000 ≈ 42,950 秒 ≈ 11.9 小时

对于我们的场景来说，也足够了。

第一个法宝：XDP

使用我们自己的方式来发送 ping 包并且能跳过不需要的 conntrack 功能，就需要使用 kernel bypass 技术：

• egress 使用 AF_XDP 直接发送；
• ingress 使用 XDP，attach BPF 程序到 eth0 网卡上，直接在网络收包的最前方进行处理；

在收包程序上，直接看这个 IP 是不是一个合法的 ICMP reply，如果是，就记录 ping 通，如果不是就放通或丢弃。

但是 XDP 是运行在 kernel 的程序，如何把 ICMP reply 里面的 IP 信息记录到文件中呢？

第二个法宝：ring buffer

Ring buffer⁴ 在网络领域是一个非常常用的数据结构，它本质上是一个 buffer，生产方可以往里面写，消费方从里面读，是两个指针。它天然适合网络的原因是，buffer 的 head 和 tail 是相接的，自然而然就可以实现「如果生产方生产的速度太快，丢弃（覆盖）最早到达并且还没有处理的包」。（对于 BPF ring buffer，如果用户态消费得不够快、buffer 没有剩余空间，新的记录会写入失败。）

使用 BPF ring buffer （BPF_MAP_TYPE_RINGBUF），作为 kernel space 和 user space 的桥梁——kernel 往这个 ring buffer 里面不断写入可以 ping 通的 IP，用户态读出来这个 IP 记录到文件中。

接下来我们看用户态的程序。怎么存储这些 IP 呢？

我们可以使用一个 txt 文件不断 append IP，但是这样查找起来的话就是 O(n) 了。（不过我们只需要最后的几个赢家，大部分情况不需要查找，所以……还好啦）。另一个方案是使用一个数据库，比如 sqlite，查找快，不过大量写入的时候就有瓶颈。

看起来用最简单的文本好一些。

如果按照一个 IP 一行的格式，xxx.xxx.xxx.xxx\n，一共是 16 bytes，16 bytes * 2^32 就是 64GiB （最坏的情况）。

ping 一次就需要 64GiB！这也太多了，作为一个 hobby project，我们的目标是使用一个 $5 的 DigitalOcean VPS 来完成这个任务，磁盘只有 25GiB，远远不够。

有哪些字符可以简化呢？乍一看，首先是每一个 IP 的一个点，以及，IP 的每一个段实际有效数据是 0-255，但是可以表示的容量是 0-999，所以有很大一部分空间浪费了。

诶等等，IP 不就是 4 个 bytes 吗？这样的话我们可以把 IP 转化成一个 32位的 int：

这样的话每 4 bytes 是一个 IP 总共是 16GiB，缩小了 4 倍！而且，4 bytes 里面每一个组合都是一个合法的 IP ，完全没有空间的浪费。

等等，「每一个组合都是一个合法的 IP」——那是不是就意味着，我们从 0 数到 2^32，每一个位置都有一个 IP？这样的话，可以让每一个位置的 bit 位，如果是 1，表示这个 IP 能够 ping 通，如果是 0，表示 ping 不通（默认，文件初始化为 0）。而这个 bit 所在的 index（比如，是文件的第 3232235521 比特位，就表示 192.168.0.1 这个 IP），就表示 IP。

第三个法宝：bitmap

恭喜我们自己！我们刚刚发明了 bitmap！

但是每次 seek 过去，把要写入的 bit 组合成一个 byte，调用 syscall write，这也太麻烦了！

第四个法宝：mmap

mmap 可以帮我们把文件映射到内存地址空间，我们只要操作内存就可以了，操作系统会在后台帮我们同步——定期把内存的修改写入到文件中。这可太方便了！

这样，我们 ping 一轮，就有一个 512 MiB（Exactly 512 MiB!） 的文件，里面存储了这一轮 ping 通的 IP。然后我们拿 bit 是 0 的 index 作为 IP，做下一轮的 ping，能通的 IP 会越来越少，直到得到一个冠军。

其实互联网大部分 IP 是 ping 不通的，尤其是我们刚开始使用比较小的 TTL。所以我们的文件的大部分内容都是 0，只有一小部分是 1，而且 1 的部分通常是连续的。因为 IP 是按连续的段分配给不通的组织，一般来说，一个段要么都可以通，要么都不通。

那么我们可以省略中间的 0 的部分吗？这样的话可以节省一大部分磁盘。

第五个法宝：Sparse file

答案是可以！这叫做 Sparse file，或者叫 file hole。比如我可以创建一个 10PB 的超大文件：

然后实际占用的空间，使用 du 查看，是 0：

使用非常简单，seek 到 EOF 以后的位置，随后再 write，中间没有写过的区域形成 hole （注意，不是 write 0）。

我们可以先用 ftruncate 调用，创建一个 sparse file，然后用 mmap 只修改需要写为 1 的部分，这样，其实只有 1 占用空间了。

将将将！

实际运行还有很多问题，比如 IP 不稳定，有时候回复 ping 有时候不回复有时候回复；有些 IP 使用另一个 IP 回复 ping；有些 IP 不减 TTL 导致产生无限环路，等等。

最后我找到 34 跳的就放弃了：

代码放在这里了：https://github.com/laixintao/traceroute-the-world 有兴趣的读者可以自己跑跑看。

代码是 AI 写的，但是这篇博客是我自己纯手写的。这年头能读的博客不多了，但是可以放心的是，这个博客不会有大批量 AI 生成的文字。

1. 参考 使用 mtr 检查网络问题，以及注意事项 ↩︎
2. 比如这里 https://www.reddit.com/r/ZiplyFiber/comments/15vvs4c/holy_traceroute_batman_this_has_to_be_a_new_record/， 以及这里 https://www.reddit.com/r/sysadmin/comments/2gxz4e/is_it_possible_to_find_the_worlds_longest_routes/ ↩︎
3. https://docs.digitalocean.com/products/droplets/details/limits/ ↩︎
4. https://en.wikipedia.org/wiki/Circular_buffer ↩︎

---