CS144 Lab3翻译

这里给出CS 144 Lab 3: the TCP sender的翻译。

实验资料：

• https://www.cnblogs.com/kangyupl/p/stanford_cs144_labs.html
• https://kangyupl.gitee.io/cs144.github.io/
• https://gitee.com/kangyupl/sponge

实验3：TCP发送方

0. 合作政策

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

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

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

1. 概述

在实验0中，你实现了流控制字节流（ByteStream）的抽象。

在实验1和2中，你实现了将不可靠数据报中的段转换为传入字节流的工具：StreamReassembler和TCPReceiver。

现在，在实验3中，你将实现连接的另一端：一个将出站字节流转换为不可靠数据报中发送段的工具。

最后，在第4个实验中，你将结合前几个实验的工作，创建一个工作的TCP实现：TCPConnection，其中包含TCPSender和TCPReceiver。你将用它来与世界各地的真实服务器进行对话。

2. 开始

你对TCPSender的实现将使用与你在实验0-2中使用的相同的Sponge库，并有额外的类和测试。为了开始进行作业：

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

3. 实验3：TCP发送方

TCP是一个协议，通过不可靠的数据报可靠地传输一对流量控制字节流（每个方向一个）。双方参与TCP连接，并且每一方同时充当“发送方”（其自身的传出字节流）和“接收方”（传入字节流）。双方被称为连接的“端点”或“对等点”。

本周，你将实现TCP的“发送方”部分，负责读取ByTestStream（由某些发送方应用程序创建并写入），并将流转换为一系列传出TCP段。在远程端，TCP接收方（重要的是要记住，接收方可以是有效TCP接收方的任何实现，而不一定是你自己的TCPReceiver。互联网标准最有价值的一点是，它们在端点之间建立一种通用语言，否则（指的是没有通用语言的情况），这些端点的行为可能会非常不同。）将这些段（那些到达的段，它们不一定都能到达）转换回原始字节流，并将确认和窗口发送回发送方。

TCPSender将负责：

• 跟踪接收方的窗口（处理传入的确认号（ackno）和窗口大小（window size）） ；
• 尽可能通过读取ByTestStream、创建新的TCP段（包括SYN和FIN标志，如果需要），填充窗口，并发送它们；
• 跟踪哪些段已经发送但尚未被接收方确认——我们称之为“未完成的”段；
• 如果发送后经过足够的时间但尚未确认，则重新发送未完成的段；

为什么要这样做？基本原则是发送接收方允许我们发送的任何内容（填充窗口），并不断重传，直到接收方确认每段内容，这称为“自动重复请求”（ARQ）。发送方将字节流分成若干段，并在接收方窗口允许的范围内发送它们。感谢你上周的工作，我们知道，只要远程TCP接收方至少收到一次带有索引标记的字节，就可以重构字节流，而无论其顺序如何。发送方的工作是确保接收方至少获得每个字节一次。

3.1. TCPSender应在何时断定某个段丢失并再次发送？

你的TCPSender将发送一组TCPSegments。每个将包含来自传出ByTestStream的一个子字符串（可能为空），用序列号索引以指示其在流中的位置，并在流的开头用SYN标志标记，在流的结尾用FIN标志标记。

除了发送这些段外，TCPSender还必须跟踪其未完成的段，直到它们占用的序列号被完全确认。TCPSender的所有者将定期调用TCPSender的tick方法，以指示时间的流逝。TCPSender负责查看其未完成的TCPSegments集合，并确定最早的已发送的段是否在未完成的情况下因为时间过长而未被确认（即，未确认其所有序列号）。如果是，则需要重新传输（再次发送）。

以下是“由于太长时间未完成”的含义规则。（这些是基于TCP“真实”规则的简化版本：RFC 6298，建议5.1至5.6。这里的版本有点简化，但是你的TCP实现仍然能够与Internet上的真实服务器进行通信。）你将要实现的逻辑非常详细，但我们不希望你担心隐藏的测试用例试图绊倒你，或将其视为SAT上的文字问题。本周我们将为你提供一些合理的单元测试，完成整个TCP实现后，在实验4中进行更全面的集成测试。只要你100%通过了这些测试，并且你的实现是合理的，就没事了。

为什么要这样做？总的目标是让发送方及时检测到段丢失并需要重新发送的情况。重发前的等待时间是很重要的：你不希望发送方等待太长的时间来重发一个网段（因为这会延迟流向接收应用程序的字节），但你也不希望它重新发送一段如果发送方再等一段时间就会被确认的信息，这会浪费互联网的宝贵容量。

1. 每隔几毫秒，你的TCPSender的tick方法就会被调用一次，它的参数是告诉你自上次调用该方法以来已经过了多少毫秒。使用参数可以维护TCPSender已激活的总毫秒数的概念。请不要试图从操作系统或CPU调用任何“time”或“clock”函数——tick方法是你唯一访问时间流逝的方法。这样可以保持事物的确定性和可测试性。
   1. 当构建TCPSender时，会给它一个参数，告诉它重传超时（retransmission timeout, RTO）的“初始值”。RTO是在重新发送一个未完成的TCP段之前要等待的毫秒数。RTO的值会随时间变化，但“初始值”保持不变。启动代码将RTO的“初始值”保存在一个名为_initial_retransmission_timeout的成员变量中。
   2. 你将实现重传计时器timer：一个可以在某个时间启动的警报，一旦RTO过期，警报就会熄灭（或”过期”）。我们强调，这种时间流逝的概念来自于被调用的tick方法，而不是通过获取一天中的实际时间。
   3. 每次发送包含数据（在序列空间中长度非零）的段（不管是第一次还是重传），如果timer没有运行，就启动它，使它在RTO毫秒后失效（对于RTO的当前值）。
2. 当所有未完成的数据都被确认后，关闭重传计时器。

3. 如果tick被调用，并且重传计时器已经过期：

   • (a) 重传TCP接收方尚未完全确认的最早（最低序列号）段。你需要在一些内部数据结构中存储未发送的段，以便能够做到这一点。
   • (b) 如果窗口大小为非零：
     • i. 跟踪连续重新传输的次数，并增加它，因为你刚刚重新传输了一些内容。你的TCPConnection将使用这些信息来决定连接是否无望（连续重传次数过多）并需要中止。
     • ii. 将RTO的值增加一倍。（这被称为“指数回退”——它会减慢糟糕网络上的重传速度，以避免进一步堵塞工作。我们将在稍后的课堂上了解更多有关这方面的内容。）

   • (c) 启动重传timer，使其在RTO毫秒后过期（对于前一个要点中概述的加倍操作后的RTO值）。

     1. 当接收方给发送方确认成功接收新数据的ackno时（该ackno反映了一个大于之前的任何ackno的绝对序列号）。

   • (a) 将RTO调回其“初始值”。

   • (b) 如果发送方有任何未完成的数据，重新启动重传timer，使其在RTO毫秒后失效（对于RTO的当前值）。
   • (c) 将“连续重传”的计数重设为零。

你可能希望在单独的类中实现重传计时器的功能，这取决于你自己。如果需要，请将其添加到现有文件（tcp_sender.hh和tcp_receiver.hh）。

3.2. 实现TCP发送方

Ok！我们已经讨论了TCP发送方所做的基本概念（给定一个传出的ByteStream，把它分割成若干段，发送给接收者，如果它们没有很快得到确认，就继续重新发送）。我们还讨论了何时得出结论：未完成的段已经丢失，需要重新发送。

现在是你的TCPSender将提供的具体接口的时候了。有四个重要的事件需要它来处理，每一个事件都可能最终发送一个TCPSegment：

1. fill_window：TCPSender被要求填充窗口：它从其输入的ByteStream中读取并以TCPSegments的形式发送尽可能多的字节，只要窗口中有新的字节要读取和可用空间。你要确保你发送的每一个TCPSegment都能完全放入接收方的窗口中。使每个单独的TCPSegment尽可能大，但不能大于TCPConfig::MAX_PAYLOAD_SIZE（1452字节）所给的值。你可以使用TCPSegment::length_in_sequence_space()方法来计算一个段所占用的序列号的总数。你的TCPSender维护着一个名为_next_seqn的成员变量，它存储着从零开始的发送的绝对序列号。对于你发送的每一个段，你都要让_next_seqno增加段的长度，以便知道下一段的序列号。
2. ack_received：从接收方收到一个确认信息，包括窗口的左边缘（= ackno）和右边缘（= ackno + window size）。TCPSender应该查看其未完成的段的集合，并删除任何现在已被完全确认的段（ackno大于该段中的所有序列号）。如果打开了新空间（指窗口变大），TCPSender可能需要再次填充窗口。如果ackno无效，即确认发送方尚未发送的数据，则此方法返回false。
3. tick：经过的时间；TCPSender将检查重传计时器是否已过期，如果是，则以最低的序列号重传未发送的段。（重要的是，重新传输的决定不必看接收方的窗口：该段在第一次发送时落在窗口内，并且尚未确认，因此现在仍在接收方的窗口内。接收方不应该“收缩”窗口的右边缘，你可以假设右边缘始终保持不变或向右移动。）
4. send_empty_segment：TCPSender应该生成并发送一个在序列空间中长度为零的TCPSegment，并将序列号正确设置为_next_seqno。如果所有者（你下周要实现的TCPConnection）想发送一个空的ACK段，这很有用。这种段（不携带数据，不占用序列号）不需要作为”未完成”来跟踪，也不会被重传。

为了完成实验3，请查看文档中的完整接口，网址是https://cs144.github.io/doc/lab3/class_t_c_p_sender.html，并在tcp_sender.hh和tcp_sender.cc文件中实现完整的TCPSender公共接口。我们预计你会想添加私有方法和成员变量，可能还有一个辅助类。

3.3. 常见问题和特殊情况

• 如何“发送”一个片段？

  把它push到_segments_out队列中。就你的TCPSender而言，当你把它push到这个队列时，就认为它已经发送了。很快，所有者就会出现并pop它（使用公共的segments_out()访问器方法），并真正发送它。

• 等等，我如何既“发送”一段，又将同一段记录为未完成，以便我知道以后重新传输什么？那我不是要给每个网段做一个副本吗？这是不是很浪费？

当你发送一个包含数据的段时，你可能想把它push到_segments_out队列中，同时在内部的数据结构中保留一个副本，让你跟踪未完成的网段，以便可能的重传。这并不是很浪费，因为段的有效载荷被存储为引用计数的只读字符串（一个Buffer对象）。所以不用担心，它实际上并没有复制有效载荷数据。

• 在我从接收方得到ACK之前，我的TCPSender应该假定接收方的窗口大小是多少？

一个字节。

• 接收方告诉我它的窗口大小是零字节。我是否应该被卡住，不再发送任何数据？

  否。如果接收方告诉你它的窗口长度是零字节，请将该信息保存为任何其他窗口使用（advertisement），因为它对3.1中描述的重传行为很重要。但当需要填充窗口时，请将窗口大小设置为一个字节。这被称为“零窗口探测”——这是一种定期探测接收方的方式，看看自从我们上次听到他们的消息后，他们是否碰巧在窗口中开辟了一些更多的空间。最坏的情况是，接收方会忽略你的一个字节段。（在一个更适合生产的TCP实现中，零窗口探测行为会更复杂一些，但也不会过于复杂。）

• 如果确认仅部分确认某些未完成的部分，我该怎么办？我是否应该尝试删除已确认的字节？

  TCP发送方可以这样做，但就课程而言，没有必要搞得太复杂。在完全确认之前，将每个段视为完全未完成——它所占用的所有序列号都小于ackno。

• 如果我发送了三个包含 “a”、”b “和 “c “的独立段，但它们从未被确认，我可以在以后将它们重新传送到一个包含 “abc “的大段吗？还是我必须单独重发每个段？

  再说一遍：TCP发送方可以做到这一点，但就本课程而言，没有必要搞得太花哨。只要单独跟踪每个未处理的段，当重传计时器到期时，再次发送最早的未处理段。

• 我应该在“未处理”数据结构中存储空段，并在必要时重发它们吗？

不，只有那些传递一些数据的网段（即在序列空间中消耗一些长度的网段）才应该被追踪为未完成的网段，并可能被重传。一个空的ACK不需要被记住，也不需要被重传。

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

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

4. 开发和调试建议

1. 在tcp_sender.cc文件中实现TCPSender的公共接口（以及你想要的任何私有方法或函数）。你可以在tcp_sender.hh中向TCPSender类添加任何你喜欢的私有成员。

2. 你可以用make check lab3测试你的代码（编译后）。

3. 请重新阅读Lab 0文档中关于”使用Git”的部分，并记住将代码保存在Git仓库中，它是在master分支上分发的。使用好的提交消息进行小规模的提交，这些消息可以识别更改的内容以及更改的原因。

4. 请努力使你的代码对将对其进行风格评分的CA来说可读。对变量使用合理而清晰的命名规则。使用注释来解释复杂或微妙的代码片段。使用”防御性编程”——明确地检查函数的先决条件或不变量，如果有什么问题，就抛出一个异常。在设计中使用模块化识别常见的抽象和行为，并在可能的情况下将其分解。重复的代码块和庞大的函数将使你很难理解代码。

5. 也请遵守Lab 0文件中描述的 “现代C++”风格。cppreference网站（https://en.cppreference.com）是一个很好的资源，尽管你不需要C++的任何复杂功能来做这些实验。（你有时可能需要使用move()函数来传递一个不能被复制的对象）。

6. 如果你得到一个segmentation fault，那么一定是出了问题！我们希望你的写作风格是使用安全的编程实践，使分段故障极不寻常（不使用malloc()，不使用new，不使用指针，在你不确定的地方进行安全检查，抛出异常，等等）。要进行调试，可以使用cmake配置构建目录

   -DCMAKE BUILD TYPE=RelASa

   使编译器的”净化器”能够检测内存错误和未定义行为，并在它们发生时给你一个漂亮的诊断。你也可以使用valgrind工具。你还可以用

   cmake .. -DCMAKE BUILD TYPE=Debug

   记住只在调试时使用这些设置，因为它们会大大降低程序的编译和执行速度。恢复到“Release”模式的最可靠/最愚蠢的方法是阐述build目录并创建一个新（build）目录。

5. 提交

1. 在你的提交中，请只对libsponge顶层的.hh和.cc文件进行修改。在这些文件中，请随意添加必要的私有成员，但请不要改变任何类的公共接口。
2. 在提交任何作业之前，请按顺序运行这些。
   • (a) make format（使编码风格正常化）
   • (b) git status（检查是否有未提交的修改，如果有，请提交！)
   • (c) make（确保代码可以编译）
   • (d) make check_lab3（确保自动测试通过）

3. 在writeups/lab3.md中写一份报告。这个文件应该是一个大约20到50行的文件，每行不超过80个字符，以使其更容易阅读。该报告应包含以下部分。

   • (a) 程序结构和设计。描述你的代码中所体现的高层次结构和设计选择。你不需要详细讨论你从启动代码中继承了什么。借此机会突出重要的设计方面，并在这些方面提供更多的细节，以便你的评分助教理解。我们强烈建议你通过使用小标题和提纲，使这篇报告尽可能可读。请不要简单地将你的程序翻译成一段英文。
   • (b) 实现方面的挑战。描述你认为最麻烦的代码部分，并解释原因。反思一下你是如何克服这些挑战的，以及是什么帮助你最终理解了给你带来麻烦的概念。你是如何试图确保你的代码维护你的假设、不变式和先决条件的，你在哪些方面发现这很容易或很困难？你是如何调试和测试你的代码的？
   • (c) 剩余的错误。尽量指出并解释代码中仍然存在的任何错误（或未处理的边缘情况）。

4. 在你的报告中，请同时填写这项任务花了你多少时间以及任何其他评论。

5. 当准备提交时，请按照https://cs144.github.io/submit。在提交之前，请确保你已经提交了所有你想要的东西。
6. 如果有任何问题，请在周二晚上的实验课上尽快告诉课程组成员，或者在Piazza上发表问题。祝你好运!