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

实验资料:

实验2:TCP接收方

0. 合作政策

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

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

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

1. 概述

在实验0中,你实现了流控制字节流(ByteStream)的抽象。

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

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

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

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

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是:

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

英文原始部分:

在绝对序列号(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的连接问题)。

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

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

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

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

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

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

3.3 实现TCP接收方

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

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

首先,请回顾一下TCP段的格式。这是两个端点相互发送的数据报有效载荷的结构。ackno和窗口大小都是TCPSegment结构中的字段。请查阅TCPSegmenthttps://cs144.github.io/doc/lab2/class_t_c_p_segment.html)和TCPHeaderhttps://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_bytesstream_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上发表问题。祝你好运!