logo一只豆腐

cs144-sp23, Lab Checkpoint 5: building an IP router

  • HangX-Ma
  • May 30, 2023
  • Total 3884 words
  • About 11 mins
  • 0 views

记录 cs144 Spring-23 Lab5: building an IP router 的思路与实践难点。

1. 内容简述

IP router structure
IP router structure

Lab5 要求实现一个简易的路由器， 通常路由器会有多个网络接口， 能够从任意一个接口接收网络数据报。 路由器的作用就是将 datagrams 依据 路由表 进行转发， 路由表定义了路由转发的一些规则：

  • 确定转发的接口
  • 确定下一跳的 IP 地址

在 Lab5 中需要实现一个新的 Router 类， 该类能够 跟踪路由表信息 并且 将接收到的每个 datagram 通过正确的输出端 NetworkInterface 正确转发到下一跳 （hop）。 在项目指导书中明确解释了 route 的相关含义， 后续需要通过 IP 的最长前缀匹配来实现路由的功能， 这也是实验中最为棘手的部分。

2. IP Router 实现

  1. add_route： 调用该方法将路由信息添加到路由表中， 我们需要自己添加存储相关信息的数据结构。

     void add_route(uint32_t route_prefix, uint8_t prefix_length, 
                 std::optional<Address> next_hop, size_t interface_num);

    根据 add_route 所给的参数以及 wiki 中对 routing table 内容的描述， 我们需要自己创建如下的数据结构。

     // Routing table data structure
 using route_t = struct {
     uint32_t route_prefix;
     uint8_t prefix_length;
     std::optional<Address> next_hop;
     size_t interface_id;
 };
 std::list<route_t> routing_table_ {};

    wikipedia - Routing table

  2. route： 该方法需要对输入的 datagrams 进行路由， 将其通过正确的网络接口转发到下一跳， 这需要实现 “最长前缀匹配 （longest-prefix match）” 以找到最合适的路由方案， 该方法有如下细节需要实现：

    • 路由器需要搜索路由表找到匹配 datagrams 中的目的地址的那个路由。 这意味着目的地址的 prefix_length 需要与 route_prefix 的 prefix_length 完全一致。
    • 在匹配的路由方案中路由器选择 prefix_length 值最大的那个， 选中的就是满足 “最长前缀匹配” 的路由。
    • 如果没有匹配的路由信息， 则丢弃该项 datagram。
    • 每一跳的路由器都需要减少 datagrams 的 ttl。 如果 ttl 已经归零或者在本次减除后触及零的下界， 路由器同样需要丢弃该项 datagram。
    • 最终， 路由器需要将修改过的 datagram 通过合适的网络接口 （interface(interface num).send datagram()） 发送到下一跳。

    整个过程中， 路由器仅需要和 datagram 以及链接层的网络接口抽象进行交互， 完全不需要考虑 TCP， ARP 以及以太网帧， 较好实现了分层隔离， 降低了路由器的处理负担。

     void route();

3. 网络拓扑

Simulated router and interfaces topology
Simulated router and interfaces topology

4. 坑点记录

测试的时候有这样一条记录（就是第一个测试都没过啦）， 当时觉得很奇怪怎么会有 bad IPv4 datagram 的打印， 查看后是 InternetDatagram 的 parse 返回了错误。 于是我给 set_error 的部分都加上了打印才发现是 checksum 未匹配。 我还以为是 NetworkInterface 部分的接收部分没有写好， 调试了半天就想着要不要用 compute_checksum 在 recv_frame 中重新把 checksum 计算一下， 这时候突然发现这个函数的接口都是 const 类型， 并且结合 NetworkInterface 在 link layer 与 application 之间的情况， 以及错误是出现在以太网帧传输到 router 再转发出去的， 唯一有嫌疑的应当还是刚刚写的 Router 类。

在读 router.cc 代码考虑把 compute_checksum 加在哪里的时候我突然看到 ttl 的值被我更改了。 这不就是问题根源嘛， 我们更新了 InternetDatagram 的内容， 那么 checksum 也需要重新计算。

Testing traffic between two ordinary hosts (applesauce to cherrypie)...

Host applesauce trying to send datagram (with next hop = 10.0.0.1): 
    IPv4, len=2f, protocol=6, src=10.0.0.2, dst=192.168.0.2 
    payload="random payload: {613419936}"

Transferring frame from applesauce to router.eth0: 
    dst=ff:ff:ff:ff:ff:ff, src=16:4e:eb:3a:a2:3d, 
    type=ARP, payload: ARP: opcode=REQUEST, 
    sender=16:4e:eb:3a:a2:3d/10.0.0.2, target=00:00:00:00:00:00/10.0.0.1

Transferring frame from router.eth0 to applesauce: 
    dst=16:4e:eb:3a:a2:3d, src=02:00:00:dd:27:73, 
    type=ARP, payload: ARP: opcode=REPLY, 
    sender=02:00:00:dd:27:73/10.0.0.1, target=16:4e:eb:3a:a2:3d/10.0.0.2

Transferring frame from applesauce to router.eth0: 
    dst=02:00:00:dd:27:73, src=16:4e:eb:3a:a2:3d, 
    type=IPv4, payload: IPv4: IPv4, len=2f, protocol=6, 
    src=10.0.0.2, dst=192.168.0.2 payload="random payload: {613419936}"

Transferring frame from router.eth2 to cherrypie: 
    dst=ff:ff:ff:ff:ff:ff, src=02:00:00:a1:96:8d, type=ARP, 
    payload: ARP: opcode=REQUEST, 
    sender=02:00:00:a1:96:8d/192.168.0.1, target=00:00:00:00:00:00/192.168.0.2

Transferring frame from cherrypie to router.eth2: 
    dst=02:00:00:a1:96:8d, src=ea:80:f1:26:53:c8, 
    type=ARP, payload: ARP: opcode=REPLY, 
    sender=ea:80:f1:26:53:c8/192.168.0.2, target=02:00:00:a1:96:8d/192.168.0.1

Transferring frame from router.eth2 to cherrypie: 
    [ERROR]: 'IPv4Header::parse' Checksum is not matched
    dst=ea:80:f1:26:53:c8, src=02:00:00:a1:96:8d, 
    type=IPv4, payload: bad IPv4 datagram
    [ERROR]: 'IPv4Header::parse' Checksum is not matched
    [NetworkInterface ERROR]: 'recv_frame' IPV4 parse error



Error: Host cherrypie did NOT receive an expected Internet datagram: 
        IPv4, len=2f, protocol=6, src=10.0.0.2, dst=192.168.0.2

5. 测试结果

cs144@cs144-ubuntu22:~/minnow$ cmake --build build --target check5
Test project /home/cs144/minnow/build
    Start  1: compile with bug-checkers
1/3 Test  #1: compile with bug-checkers ........   Passed   44.90 sec
    Start 35: net_interface
2/3 Test #35: net_interface ....................   Passed    0.20 sec
    Start 36: router
3/3 Test #36: router ...........................   Passed    0.17 sec

100% tests passed, 0 tests failed out of 3

Total Test time (real) =  45.41 sec
Built target check5
Search