实验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. 开始

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

3. 实现路由器

在本实验中，你将实现一个Router类，它可以：

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

你的实现将被添加到router.hh和router.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_prefix和prefix_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. 提交

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