CS144 Lab2翻译

这里给出CS 144 Lab 2: the TCP receiver的翻译，因为做Lab的时候发现要反复阅读讲义，但直接看英语还是有点效率过低，所以索性翻译一遍。

实验资料：

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

实验2：TCP接收方

0. 合作政策

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

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

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

1. 概述

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

在实验1中，你创建了一个模块，该模块接受一系列从同一字节流中提取的子字符串，并将它们重新组装回原始ByteStream，同时将其内存消耗限制在给定的数量（容量capacity）。

现在，在实验2中，你将实现TCP中处理入站字节流的部分：TCPReceiver。在编写StreamReassembler和ByteStream时，你已经完成了其中大部分的“算法”工作；本周主要讨论如何将这些类连接到TCP格式。这将涉及到考虑TCP如何表示每个字节在流中的位置——即所谓的”序列号”。TCPReceiver负责告诉发送方

• (a) 它能够成功地组装多少入站字节流（这被称为“确认(ack)”）。
• (b) 发送方现在被允许发送的字节范围（“流控制窗口”）。

下周，在实验3中，你将实现TCP中处理出站字节流的部分：TCPSender。最后，在第4个实验中，你将结合前几个实验的工作，创建一个有效的TCP实现：一个包含TCPSender和TCPReceiver的TCPConnection。你将用它来与世界各地的真实服务器进行对话。

2. 开始

你的TCPreciver实现将使用与实验0和1中使用的相同的Sponge库，以及其他类和测试。为了开始进行作业：

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

3. 实验2：TCP接收方

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

本周，你将实现TCP的“接收方”部分，负责接收TCP段（实际的数据报有效载荷），重新组装字节流（包括它的结束，当它发生时），并决定应该发送回发送方的确认和流量控制信号。

为什么要这样做？这些信号对于TCP在不可靠数据报网络上提供流控制、可靠字节流服务的能力至关重要。在TCP中，确认(acknowledgment)意味着，“接收方需要的下一个字节的索引是什么，这样它才能重新组装更多的ByteStream？”这告诉发送方它需要发送或重新发送哪些字节。

流量控制意味着，“接收方感兴趣并愿意接收哪些索引范围”（通常作为其剩余容量的函数）。这会告诉发送方允许发送多少。

3.1 序列号

作为热身，我们需要实现TCP表示字节流中每个字节的索引的方法。上周你创建了一个StreamReassembler，它可以重新组装子串，其中每个单独的字节都有一个64位的索引，从0开始，流中的每个字节序列号按序增加1。在TCP中，每个字节在数据流中的索引用一个32位的“序列号”（seqno）表示，这就增加了一些复杂性：

1. 开始和结束都算作序列中的一个位置：除了确保收到所有字节的数据外，TCP必须确保也能收到流的开始和结束。因此，在TCP中，SYN（数据流的开始）和FIN（数据流的结束）标志都被分配了序列号。这些计数都在序列中占据一个位置。数据流中的每个字节也在序列中占据一个位置。

2. 32位封装的序列号：在我们的StreamReassembler中，索引总是从0开始，并且有64位，我们不必担心用完所有可能的64位索引。然而，在TCP中，传输的序列号是32位，如果数据流足够长的话，序列号就会循环。(TCP中的数据流可以任意长——通过TCP发送的ByteStream的长度没有限制，所以循环是很常见的）。

3. TCP序列号不从零开始：为了提高安全性和避免不同连接之间的混淆，TCP试图确保序列号不能被猜到，而且不太可能重复。因此，一个流的序列号不从零开始。流中的第一个序列号通常是一个随机的32位数字，称为初始序列号（ISN）。这是代表SYN（流的开始）的序列号。其余的序列号在这之后表现正常，例如，第一个字节的数据将有ISN+1的序列号，第二个字节的数据将有ISN+2，等等。

这些序列号是“真正的”序列号：在每个TCP段的头部中传输的实际32位数值。谈论“绝对序列号”（它总是从零开始，并且不被封装）和“流索引”（你在StreamReassembler中使用的：一个从零开始的数字，代表流中第一个实际字节）的概念有时也很有帮助。

为了使这些区别具体化，考虑只包含三个字母的字符串”cat”的字节流。如果SYN的seqno为$2^{32-2}$，那么每个字节的seqnos、absoluteseqno和streamindex是：

$$\begin{array}{r|c|c|c|c|c} \text { element } & \text { SYN } & \text { c } & \text { a } & \text { t } & \text { FIN } \\ \hline \text { seqno } & 2^{32}-2 & 2^{32}-1 & 0 & 1 & 2 \\ \hline \text { absolute seqno } & 0 & 1 & 2 & 3 & 4 \\ \hline \text { stream index } & & 0 & 1 & 2 & \end{array}$$

下图显示了TCP中涉及的三种不同类型的索引：

$$\begin{array}{l|l|l} \text { 序列号(Sequence Numbers) } & \text { 绝对序列号(Absolute Sequence Numbers) } & \text { 流索引(Stream Indices) } \\ \text { • 从ISN开始 } & \text { • 从0开始 } & \text { • 从0开始 } \\ \text { • 包括SYN/FIN } & \text { • 包括SYN/FIN } & \text { • 不包括SYN/FIN } \\ \text { • } 32 \text { 比特,封装 } & \text { • } 64 \text { 比特,没有封装 } & \text { • } 64 \text { 比特,没有封装 } \\ \text { • "seqno" } & \text { • "absolute seqno" } & \text { • "stream index" } \end{array}$$

英文原始部分：

$$\begin{array}{l|l|l} \text { Sequence Numbers } & \text { Absolute Sequence Numbers } & \text { Stream Indices } \\ \text { • Start at the ISN } & \text { • Start at 0 } & \text { • Start at 0 } \\ \text { • Include SYN/FIN } & \text { • Include SYN/FIN } & \text { • Omit SYN/FIN } \\ \text { • } 32 \text { bits, wrapping } & \text { • } 64 \text { bits, non-wrapping } & \text { • } 64 \text { bits, non-wrapping } \\ \text { • "seqno" } & \text { • "absolute seqno" } & \text { • "stream index" } \end{array}$$

在绝对序列号(absolute seqno)和流索引(stream index)之间的转换是很容易的，只要加减一就可以了。不幸的是，在序列号(seqno)和绝对序列号(absolute seqno)之间的转换有点困难，混淆这两者会产生棘手的错误。为了系统地防止这些bug，我们将用一个自定义类型来表示序列号：WrappingInt32，并编写它与绝对序列号（用uint64_t表示）之间的转换。

（WrappingInt32是包装类型的一个示例：一种包含内部类型（在本例中为uint32_t）但提供不同函数/运算符集的类型。）

我们已经为你指定了这个类型，并提供了一些辅助函数（见wrapping_integers.hh），你将在wrapping_integers.cc中实现转换：

1. WrappingInt32 wrap(uint64_t n, WrappingInt32 isn)

   转换$\mathrm{absolute\ seqno\to seqno}$。给出一个绝对序列号（$n$）和一个初始序列号（$isn$），产生$n$的（相对）序列号。

   1. uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint)

      转换$\mathrm{seqno\to absolute\ seqno}$。给定一个序列号（$n$），初始序列号（$isn$），和一个绝对检查点（checkpoint）序列号，计算与$n$对应的最接近checkpoint的绝对序列号。

      （注意：checkpoint是必需的，因为任何seqno对应于许多absolute seqnos。例如，序列号“17”对应于绝对序列号17，但也对应于$2^{32}+17$，或$2^{33}+17$，或$2^{34}+17$，等等。checkpoint有助于解决这种歧义性：它是一个最近解封装的absolute seqno，这个类的用户知道它接近于这个seqno的所需解封装的absolute seqno。在你的TCP实现中，你将使用最后一个重新组装的字节的索引作为checkpoint）。

      提示：最清晰/最简单的实现将使用wrapping_integers.hh中提供的辅助函数。wrap/unwrap操作应该保留偏移量——两个相差17的seqnos将对应于两个同样相差17的绝对seqnos。

      因此，请尝试

      • (a) 封装checkpoint；
        • (b) 在封装的空间中计算$n$和checkpoint之间的差异；
        • (c) 在未封装的空间中加入该差异；
        • (d) 处理underflow（负数）结果；

你可以通过运行WrappingInt32测试来测试你的实现。在build目录中，运行ctest -R wrap。

3.2 什么是可接受的字节的”窗口”？

祝贺你获得了正确的封装逻辑！在我们深入研究TCPReceiver的实现之前，让我们讨论一下接收方流控窗口的概念。

这里的想法是，TCPReceiver要告诉TCPSender它感兴趣并愿意接受的字节索引的连续范围（或“窗口”）。(而且，我们要清楚：你的TCPReceiver将把你的StreamReassembler作为一个成员，并使用它来完成繁重的工作。本周主要是关于StreamReassembler与TCP的连接问题）。

接收方这样做是为了实现流量控制。TCPReceiver的StreamReassembler将忽略任何会超过其内存使用限制（容量）的字节。通过告诉发送方允许和不允许发送的数据范围，接收方可以防止发送方浪费精力，并使发送方的发送速度不超过应用程序从重新组装的ByteStream中的读取速度。（记住，ByteStream本身可以是任意长的terabytes, exabytes, yottabytes，但是接收方的内存使用，包括StreamReassembler和它正在重构的ByteStream，都受容量限制。只有当应用程序从接收方的ByteStream中读取并弹出一些数据时，发送方才会被允许发送更多的流）。

所以“窗口”指的是当前接收方可以接受的字节索引或序列号的范围。

窗口的下边缘（有时称为”左”边）称为ackno：它是TCPReceiver还不知道的第一个字节的索引（因此希望能找出）。例如，假设接收方收到一个序列号为24的SYN，然后是序列号为25、26、27和35的四个字节的数据。ackno将是28：它是接收方尚未能重新组合的第一个字节的序列号。

窗口的上边缘（或“右”边）是TCPReceiver不愿意接受的第一个索引。

窗口的大小是上边缘减去下边缘。

你的接收方负责计算任何给定点的ackno（窗口的下边缘）和窗口大小（窗口的上边缘和下边缘之间的差值）。这些最终将被放在从接收方发送到发送方的TCPSegments中。在实际中，你的接收方将宣布一个窗口大小，该窗口大小等于它的容量减去它的StreamReassembler的ByteStream中持有的字节数。

3.3 实现TCP接收方

在本实验的其余部分，你将实现TCPReceiver。它将

• (1) 从它的对等方接收段，
• (2) 使用你的StreamReassembler重新组装ByteStream，并计算
• (3) 确认号(ackno)，和
• (4) 窗口大小。

首先，请回顾一下TCP段的格式。这是两个端点相互发送的数据报有效载荷的结构。ackno和窗口大小都是TCPSegment结构中的字段。请查阅TCPSegment（https://cs144.github.io/doc/lab2/class_t_c_p_segment.html）和TCPHeader（https://cs144.github.io/doc/lab2/struct_t_c_p_header.html）的文档。你可能对length_in_sequence_space()方法感兴趣，它计算出一个段占据多少个序列号（包括SYN和FIN各占一个序列位置，以及有效载荷的每个字节）。

接下来，我们来谈谈你的TCPReceiver将提供的接口：

// Construct a `TCPReceiver` that will store up to `capacity` bytes
TCPReceiver(const size_t capacity); // implemented for you in .hh file

// Handle an inbound TCP segment
//
// returns `true` if any part of the segment was inside the window
bool segment_received(const TCPSegment &seg);

// The ackno that should be sent to the peer
//
// returns empty if no SYN has been received
//
// This is the beginning of the receiver's window, or in other words,
// the sequence number of the first byte in the stream
// that the receiver hasn't received.
std::optional<WrappingInt32> ackno() const;

// The window size that should be sent to the peer
//
// Formally: this is the size of the window of acceptable indices
// that the receiver is willing to accept. It's the difference between
// (a) the sequence number of the end of the window (the first index that
//     won't be accepted by the receiver) minus
// (b) the sequence number of the beginning of the window (the ackno).
//
// Operationally: it's the capacity minus the number of bytes that the
// TCPReceiver is holding in the byte stream.
size_t window_size() const;

// number of bytes stored but not yet reassembled
size_t unassembled_bytes() const; // implemented for you in .hh file

// Access the reassembled byte stream
ByteStream &stream_out(); // implemented for you in .hh file

TCPReceiver是围绕你的StreamReassembler建立的。我们已经在.hh文件中为你实现了构造函数，unassembled_bytes和stream_out方法。下面是你要做的其他事情：

3.3.1 segment received()

这是一个主要的工作方法！TCPReceiver::segment received()将在每次从对等方接收到新段时被调用。

这个方法需要：

• 必要时设置初始序列号。第一个到达的、设置了SYN标志的段的序列号是初始序列号。为了在32位封装的seqnos/acknos和它们的绝对等价物之间保持转换，你需要跟踪这一点。(注意，SYN标志只是头部中的一个标志。同样的段也可以携带数据，甚至可以设置FIN标志）。
• 将任何数据或流结束标记推送给StreamReassembler。如果在TCPSegment的头中设置了FIN标志，这意味着流以有效负载的最后一个字节结束，它相当于一个EOF。
• 确定该段的任何部分是否落在窗口内。如果段的任何部分落在窗口内，这个方法应该返回true，否则返回false。（如果是false，说明TCPSender在某种程度上被混淆了，需要对该窗口进行纠正。）我们的意思是：一个段占据了一个序列号范围——从它的序列号开始，长度等于它的length_in_sequence_space()（这反映了SYN和FIN各占一个序列号，以及有效载荷的每个字节的事实）。如果一个段所占的任何一个序列号都在接收方的窗口内，那么这个段是可以接受的（该方法应返回true）。
  有一些特殊情况：
  • 如果ISN还没有被设置，则如果（且仅当）设置了SYN位，则段是可接受的。
  • 如果窗口的大小为零，则应将其大小视为一个字节，以确定窗口的第一个和最后一个字节。（这个可接受性的定义是对RFC 793第25至26页中的定义的轻微调整。）
  • 如果段在序列空间中的长度为零（例如，只有一个没有有效负载且没有SYN或FIN标志的裸确认），则其大小应视为一个字节，以确定其占用的第一个和最后一个序列号。

3.3.2 ackno()

返回一个可选的<WrappingInt32>，包含接收方尚未知道的第一个字节的序列号。这就是窗口的左边缘：接收方感兴趣的第一个字节。如果ISN还没有被设置，返回一个空的可选值。

3.3.3 window size()

有关窗口大小的定义，请参见§§3.2。

4. 开发和调试建议

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

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

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

   来配置，然后使用GNU调试器（gdb）。

5. 提交

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

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

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

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

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