Kinnari's Blog

CS168 Proj1 - Traceroute

3 min

在 intro 中介绍了 TTL，而 traceroute 利用 TTL 来实现探测网络路径的功能。笼统来说就是从较小的 TTL 逐渐变大，传输一个 UDP-over-IP 的 packet（称为 probe），在中途某个 router 发现 TTL 失效后，再传回一个 ICMP 的 Time Exceeded 报文，从而得知经过了哪些 router。具体实现见 https://sp25.cs168.io/proj1/guide/#2-introducing-traceroute。

问题
  1. 网络是 best-effort 的，可能会丢包
  2. 多条路径

可以用重复探测（repeated probing）来解决。

问题

end hosts 可能不会返回消息，导致不知道是否成功到达目的地。 解决方法是故意访问无法访问的端口，使用 port unreachable 的 ICMP 报文来告知发送方。端口号 33434 常被设置为从不使用。

Proj1 就是用 python 来实现 traceroute 的功能。

Part A

Stage 1

traceroute 函数实现：

def traceroute(sendsock: util.Socket, recvsock: util.Socket, ip: str) \
        -> list[list[str]]:
    ttl = 30
    sendsock.set_ttl(ttl)
    sendsock.sendto("Potato".encode(), (ip, TRACEROUTE_PORT_NUMBER))
    if recvsock.recv_select():
        buf, addr = recvsock.recvfrom()
        print(f"Packet bytes: {buf.hex()}")
    return []

得到输出：

traceroute to cmu.edu (128.2.42.10)
Packet bytes: 4500003878084000e40199dd80022a0a0ab4d01e0303bb3b0000000045000022693b4000041188b10ab4d01e80022a0ae4de829a000eda39

给 https://hpd.gasmi.net/ 解码后得到：128.2.42.10 → 10.180.208.30 ICMP Destination unreachable (Port unreachable)

设置不同的 ttl 以得到不同的结果。

NOTE

这个实验里面的 routers 默认使用大端法，并且长度按照 header 和 payload 的总长度来计算。

Stage 2

上一个 stage 中实现了数据传输，这个 stage 负责实现数据的解析。只需要根据提示和 https://sp25.cs168.io/proj1/guide/#3-header-structure 实现 IPv4、UDP、ICMP 的 __init__ 函数即可。

class IPv4:
    def __init__(self, buffer: bytes):
        b = ''.join(format(byte, '08b') for byte in [*buffer])
        self.version = int(b[0:4], 2)
        self.header_len = int(b[4:8], 2) * 4
        self.tos = int(b[8:16], 2) 
        self.length = int(b[16:32], 2) 
        self.id = int(b[32:48], 2)
        self.flags = int(b[48:51], 2)  
        self.frag_offset = int(b[51:64], 2)
        self.ttl = int(b[64:72], 2)
        self.proto = int(b[72:80], 2)
        self.cksum = int(b[80:96], 2)
        self.src = '.'.join(str(int(b[i:i+8], 2)) for i in range(96, 128, 8))
        self.dst = '.'.join(str(int(b[i:i+8], 2)) for i in range(128, 160, 8))

class ICMP:
    def __init__(self, buffer: bytes):
        b = ''.join(format(byte, '08b') for byte in [*buffer])
        self.type = int(b[0:8], 2)
        self.code = int(b[8:16], 2)
        self.cksum = int(b[16:32], 2)

class UDP:
    def __init__(self, buffer: bytes):
        b = ''.join(format(byte, '08b') for byte in [*buffer])
        self.src_port = int(b[0:16], 2)
        self.dst_port = int(b[16:32], 2)
        self.len = int(b[32:48], 2)
        self.cksum = int(b[48:64], 2)

Stage 3

这个 stage 则将上两个 stage 的功能进行结合，实现一个基本的 traceroute！（异常处理在 part B 实现）

代码：

def traceroute(sendsock: util.Socket, recvsock: util.Socket, ip: str) \
        -> list[list[str]]:
    paths = []
    for ttl in range(1, TRACEROUTE_MAX_TTL+1):
        # init
        routers = []
        recv_ip = None
        for _ in range(PROBE_ATTEMPT_COUNT):
            sendsock.set_ttl(ttl)
            sendsock.sendto("Potato".encode(), (ip, TRACEROUTE_PORT_NUMBER))
            if recvsock.recv_select():
                _, addr = recvsock.recvfrom()
                recv_ip = addr[0]
                if recv_ip not in routers:
                    routers.append(recv_ip)
                if recv_ip == ip:
                    break
        # result
        paths.append(routers)
        util.print_result(routers, ttl)
        if recv_ip == ip:
            break
    return paths

完整输出

traceroute to cmu.edu (128.2.42.10)
 1: *
 2: 10.3.2.217
 3: 10.3.0.26
 4: 10.3.0.73
 5: 10.255.38.54
 6: 10.255.38.73
 7: 10.255.38.90
 8: 58.247.64.114
 9: 139.226.203.117
10: *
11: *
12: 219.158.5.158
13: 219.158.3.178
14: 219.158.117.2
15: *
16: *
17: *
18: *
19: *
20: *
21: *
22: ae26.mpr2.pit1.us.zip.zayo.com (64.125.22.103)
23: 209.249.178.189.IDIA-397525-ZYO.zip.zayo.com (209.249.178.189)
24: *
25: CORE2-BORDER-FW.GW.CMU.NET (128.2.5.68)
26: POD-D-CYH-9500-CORE2.GW.CMU.NET (128.2.255.13)
27: CMU-VIP.ANDREW.CMU.EDU (128.2.42.10)

Part B

To be done…

计算机网络