这里给出CS 144 Lab 6: building an IP router的翻译。

实验资料:

实验6:构建IP路由器

0. 合作政策

编程作业必须是你自己的工作:你必须编写你为编程作业提交的所有代码,但我们作为作业的一部分提供给你的代码除外。请不要复制和粘贴来自StackOverflow,GitHub或其他来源的代码。如果你的代码基于你在网上或其他地方找到的样例,请在提交的源代码中的注释中引用URL。

与他人合作:你不能把你的代码给别人看,也不能看别人的代码,更不能看往年的解决方案。你可以与其他学生讨论作业,但不要抄袭任何人的代码。如果你与其他学生讨论作业,请在你提交的源代码中的注释中列出他们的姓名。请参阅课程管理讲义了解更多详细信息,如果有任何不清楚的地方,请在Piazza上询问。

Piazza:请随时在Piazza上提问,但请不要发布任何源代码。

1. 概述

在本周的实验中,你将在现有的NetworkInterface基础上实现一个IP路由器,从而结束本课程。路由器有几个网络接口,可以在其中任何一个接口上接收互联网数据报。路由器的工作是根据路由表转发它得到的数据报:一个规则列表,它告诉路由器,对于任何给定的数据报:

  • 发送到哪个接口;
  • 下一跳的IP地址 ;

你的工作是实现一个路由器,它可以为任何给定的数据报计算出这两件事。(你不需要实现设置路由表的算法,例如RIP、OSPF、BGP或SDN控制器,只需要实现跟随路由表的算法)。

你对路由器的实现将使用带有新的Router类的Sponge库,以及在模拟网络中检查你的路由器功能的测试。实验6建立在你在实验5中对NetworkInterface的实现之上,但不使用你在实验0-4中实现的TCP栈。IP路由器不需要知道任何关于TCP、ARP或以太网的信息(仅限IP)。我们希望你的实现将需要大约25-30行的代码。

图1:路由器包含多个网络接口,可以在其中任何一个接口上接收IP数据报。路由器将接收到的任何数据报转发到相应出站接口上的下一跳,路由表告诉路由器如何做出这个决定。

2. 开始

  1. 请确保你已经提交了你在实验5中的所有解决方案。请不要修改libsponge目录顶层以外的任何文件,或者webget.cc。(请不要添加代码所依赖的额外文件。)否则,你可能会在合并实验6的启动代码时遇到麻烦。
  2. 在实验作业的存储库中,运行git fetch来检索实验作业的最新版本。
  3. 通过运行git merge origin/lab6-startercode,下载实验6的启动代码。
  4. build目录中,编译源代码:make(编译时可以运行make -j4以使用四个处理器)。
  5. build目录外,打开并开始编辑writeups/lab6.md文件。这是你实验报告的模板,将包含在你提交的内容中。

3. 实现路由器

在本实验中,你将实现一个Router类,它可以:

  • 跟踪路由表(转发规则或路由列表),并
  • 转发它收到的每个数据报:
    • 转发到正确的下一跳
    • 在正确的出站NetworkInterface

你的实现将被添加到router.hhrouter.cc骨架文件中。在你开始编码之前,请查看新的Router类的文档

下面是你要实现的两个方法,以及我们对每个方法的期望:

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

这个方法将一条路由添加到路由表中。你要在Router类中添加一个数据结构作为私有成员来存储这些信息。这个方法所要做的就是保存路由,以供以后使用。

路由的各个部分是什么意思?

路由是一个”匹配——行动”规则:它告诉路由器,如果一个数据报前往一个特定的网络(一个IP地址范围),并且如果该路由被选为最具体的匹配路由,那么路由器应该把数据报转发到特定接口上的特定下一跳。

“匹配”:数据报是前往这个网络的吗?route_prefixprefix_length共同指定了一个可能包括数据报目的地的IP地址范围(一个网络)。route_prefix是一个32位数字的IP地址。prefix_length是一个介于0和32(包括32)之间的数字;它告诉路由器路由前缀中有多少最高有效位是有效的。例如,要表达一个到网络”18.47.0.0/16”的路由(这与前两个字节为18和47的任何32位IP地址匹配),路由前缀将是305070080($18×2^{24}+47×2^{16}$),前缀长度是16。任何以”18.47.x.y”为目的地的数据报都会匹配。

“行动”:如果路由匹配并被选中,该怎么做。如果路由器直接连接到有关的网络,next_hop将是一个空的可选项;在这种情况下,next_hop是数据报的目标地址。但如果路由器是通过其他路由器连接到有关网络的,则next_hop将包含路径中下一路由器的IP地址。interface_num给出了路由器NetworkInterface的索引,它用来将数据报发送到下一跳。你可以用interface(interface_num)方法访问这个接口。

void route_one_datagram(InternetDatagram &dgram);

这里是橡胶与道路的交汇处。这个方法需要将数据报路由到下一跳,从适当的接口传出。它需要实现IP路由器的”最长前缀匹配”逻辑,以找到最佳路由,这意味着:

  • 路由器搜索路由表,以找到与数据报的目的地址相匹配的路由。我们所说的”匹配”是指目的地址的最高有效prefix_length比特与route_prefix的最高有效prefix_length比特相同的。
  • 在匹配的路由中,路由器选择具有最大prefix_length的路由,这就是最长前缀匹配路由。
  • 如果没有匹配的路由,路由器会丢弃数据报。
  • 路由器会递减数据报的TTL(生存时间)。如果TTL已经为零,或在递减后为零,路由器应该放弃该数据报。
  • 否则,路由器将修改后的数据报通过适当的接口(interface(interface_num).send_datagram())发送到适当的下一跳。

在这个互联网的设计中,有个优点(或至少是一种成功的抽象):路由器从不考虑TCP、ARP或以太网帧。路由器甚至不知道链路层是什么样子的。路由器只考虑互联网数据包,并且只通过NetworkInterface抽象与链路层进行交互。当涉及到”链路层地址是如何解决的?”或”链路层是否有自己的不同于IP的寻址方案?”或”链路层帧的格式是什么?”或”数据报的有效载荷是什么意思?”等问题时,路由器根本不关心。

4. 测试

你可以通过运行make checklab6来测试你的实现。这将在特定的模拟网络中测试路由器,如图2所示。

图2:应用/网络模拟器工具中使用的模拟测试网络,也是由make check lab6运行的。 (有趣的事实:uun网络是David Mazieres的互联网切片,于1993年分配whois工具或链接的网站可以用来查询谁控制了每个IP地址的分配)。

5. Q & A

  • 我应该用什么数据结构来记录路由表?

    由你决定! 但不需要太过疯狂。每个数据报需要做$O(N)$个工作是完全可以接受的,其中$N$是路由表的条目数。如果你想做一些更有效的事情,我们鼓励你在优化之前先得到一个有效的实现,并仔细记录和评论你选择的任何实现。

  • 如何将以地址对象形式出现的IP地址转换为可以写入ARP消息的32位原始整数?

    使用Address::ipv4_numeric()方法。

  • 如何将一个以原始32位整数形式出现的IP地址转换为一个地址对象?

    使用 Address::from_ipv4_numeric()方法。

  • 如何将一个$32$位IP地址的最高$N$位(其中$0\le N\le 32$) 与另一个32位IP地址的最重要的$N$位进行比较?

    这可能是这项任务中”最棘手”的部分,因为要让逻辑正确。也许值得在C++中写一个小的测试程序(一个简短的独立程序)或者在Sponge中添加一个测试,以验证你对相关的C++操作符的理解,并仔细检查你的逻辑。

    回顾一下,在C和C++中,将一个32位整数移位32位,可能会产生未定义行为。使用make_clean,然后在编译代码时打开sanitizer(cmake -DCMAKE_BUILD_TYPE=RelASan)以便在你提交之前尝试捕捉你的代码中任何未定义的行为。

    你可以通过在build目录中运行./apps/network simulator来直接运行路由器测试。

  • 如果路由器没有到目的地的路由,或者TTL为零,它是不是应该向数据报的源头发送一个ICMP错误信息?

    在现实生活中,是的,这将是有帮助的。但在这个实验里没有必要——丢弃数据报就足够了。(即使在现实生活中,也不是每个路由器都会在这些情况下向源头发送ICMP消息)。

  • 我如何运行本实验的测试套件?

    make check_lab6(两个测试)。或者你可以用make check运行整个测试套件(161个测试)。

  • 如果这个PDF出来后还有更多的FAQ,我在哪里可以看到?

    请定期查看网站(https://cs144.github.io/lab_faq.html)和Piazza。

6. 提交

  1. 在你的提交中,请只对libsponge顶层的.hh.cc文件进行修改。在这些文件中,请随意添加必要的私有成员,但请不要改变任何类的公共接口。
  2. 请不要添加额外的文件,自动打分器不会查看这些文件,你的代码可能无法编译。
  3. 在提交任何作业之前,请按顺序运行这些。
    • (a) make format(使编码风格正常化)
    • (b) git status(检查是否有未提交的修改,如果有,请提交!)
    • (c) make(确保代码可以编译)
    • (d) make check_lab6(确保自动测试通过)
  4. writeups/lab6.md中写一份报告。这个文件应该是一个大约20到50行的文件,每行不超过80个字符,以使其更容易阅读。该报告应包含以下部分。
    • (a) 程序结构和设计。描述你的代码中所体现的高层次结构和设计选择。你不需要详细讨论你从启动代码中继承了什么。借此机会突出重要的设计方面,并在这些方面提供更多的细节,以便你的评分助教理解。我们强烈建议你通过使用小标题和提纲,使这篇报告尽可能可读。请不要简单地将你的程序翻译成一段英文。
    • (b) 实现方面的挑战。描述你认为最麻烦的代码部分,并解释原因。反思一下你是如何克服这些挑战的,以及是什么帮助你最终理解了给你带来麻烦的概念。你是如何试图确保你的代码维护你的假设、不变式和先决条件的,你在哪些方面发现这很容易或很困难?你是如何调试和测试你的代码的?
    • (c) 剩余的错误。尽量指出并解释代码中仍然存在的任何错误(或未处理的边缘情况)。
  5. 在你的报告中,请同时填写这项任务花了你多少时间以及任何其他评论。
  6. 当准备提交时,请按照https://cs144.github.io/submit。在提交之前,请确保你已经提交了所有你想要的东西。
  7. 如果有任何问题,请尽快在周二晚上的实验课上告诉课程组成员,或者在Piazza上发帖提问。祝您好运!
  8. 还有:拍拍你们的肩膀。你们是第一个通过新的”模块化”CS144实验的班级,我们非常感谢你们对实验的耐心和所有有用的反馈。未来的学生将从你们的经验中受益。谢谢你们,祝你们有一个愉快的寒假! ——Keith, Nick, Sarah, Nick, Will, Alex, Emily, and Sadjad