一事未毕，不启二事。 ——yangnanbei

Lab0 Warmup

https://cs144.github.io

1. check web_get

环境搭建

prepare：

如何检查环境设置是否到位呢？

我们可以尝试用telnet命令

telnet cs144.keithw.org http

观察到如下打印：

而后输入

GET /hello HTTP/1.1

Host: cs144.keithw.org

Connection: close

键入空格，告诉服务端http请求结束, 回显如下

根据教程配置好环境后，将github 仓库关联到本地上，以后提交代码用git push github

概述

lab0是一个热身，读一下框架的代码，构造一个request即可，而后将response回显，测试：

seems ok

自动测试一下：

通过

代码风格检查

注意！

交作业前，用

cmake --build build --target tidy

来检查代码风格

cmake --build build --target format

格式化代码

2. An in-memory reliable byte stream

概述

实现一个字节流，不用考虑线程安全

Your byte stream is for use in a single thread—you don’t have to worry about concurrent writers/readers, locking, or race conditions.

既然只是单线程的话，是比较好处理的，一开始没有明白每个函数要做什么，后面看了下测试用例才搞清楚。

这里选择下数据结构。首先尝试用deque去做缓存，但是性能比较差，最后使用的是 std::queue<string> 来做缓存结构。

如果是多线程的话，那要考虑什么呢？

• condition race — 存在race的数据都需要用原子变量声明及操作
• 可重入性
• buffer 考虑到性能应做成无锁队列
• …

测试

commit前记得规范下格式

cmake --build build --target tidy
cmake --build build --target format

提交完成

lab0 warm up 结束

Lab 1 Stitching substrings into a byte stream

概述

上图为官方提供的tcp模块化实现架构图，我们将分模块逐步实现tcp模块。在lab1 中我们要实现TCPReceiver 中的 Reassembler类，其作用是将收到的字节segment重组成有序的字节流传递给我们在lab0 中实现的BtyeStream。

• 蓝色部分：已经出buffer
• 绿色部分：经过reassembler的排序，已经放入buffer
• 红色部分：reassembler储存且需要排序的部分
• other：丢弃

遵循的原则

1. 当重排器意识到能写入buffer时，马上写入。

何时能写入？重排器缓存非空，从expect_index 到 可写入的index之前的所有数据都有序填充后，可写入。

2. 请记住，重排器是有容量上线的，以及，再判断是否可写入的时候，buffer可处理的部分也是有容量上线的(availble_size)。
3. 对于要处理的子串，如果buffer中已经有子串的前缀，则将这部分前缀截断。
4. eof判断，首先是这个子串要是eof串，然后当前的容量（重排器容量/buffer容量）能够处理子串的所有部分，才能认定为eof。

思路讨论

思考一下，我们会面对哪些情况？

我们现在已知的是：

• expect_index_： 重排器期望的index,index之前已经写入stream
• index：传入的字节流的首个index
• data_size: 传入的字节流长度，单位 byte

1. expect_index > index + data_size

• 直接drop，因为所有的数据都已经写入

2. index < expect_index < index + datasize

• 将重合的部分截断
• 处理截断后的数据

测试

cmake –build build –target check1

ok，lab1完成~

我是直接使用wsl作为实验环境的，所以重排器的性能看上去还可以，与最优实践肯定有些差距，若日后有闲暇再来优化。

lab2 the TCP receiver

概述

实现了重排器之后，我们现在要实现 tcp 接收端了~

接收端从发送端收到消息后，将其交给重排器，重排器会将数据写入buffer。同时，Receiver还需要通过send()接口向发送端发确认帧。

接收端需要告诉发送端

• 未被重排的第一个segment的索引，也即为所谓的 ack number or ackno. 这是接收端期望从发送端收到的第一个segment。
• ByteStream中的有效空间，即为所谓滑动窗口的 window size.

ackno 和 window size 共同描述了接收方滑动窗口的情况，同时发送方可以从这两者得出：发送方允许发送的索引范围。使用这种机制，接收方就能进行流量控制。我们可以称 ackno 为接收端期望的左边界，ackno + window size为接收端期望的右边界。

到目前为止，我们已经完成了重排器和字节流的构建，接下来接收端的实现更多的是工程问题而非算法问题了。重点在于，如何在流中表示数据的位置。

2.1 Translating between 64-bit indexes and 32-bit seqnos

思路讨论

根据手册中描述的，其中的一个难点在于。tcp协议预留给seqno的空间只有32bit大小，因为TCP协议不可能给出64位用来存放序列号，这太占用空间。我们可以通过 RFC 793 来确认tcp协议的字段

那么一共有三个要注意的点

1. 你的实现需要考虑32位整数的溢出情况。

毕竟32位整数的最大范围是4GB，若超过4GB，index会从0开始。而4GB的流是有可能出现的。

2. TCP seqno 开始于一个随机值。

考虑到鲁棒性以及减少部分场景可能存在的迷惑。TCP的开始seqno(ISN, Initial Sequence Number)是一个随机的32-bit number。

3. SYN包和FIN包也需要占用seqno哦

这里有一些别称，方便我们厘清概念：

• seqno：TCP头部填入的seqno，注意TCP有两个方向，每个方向都有自己的ISN和seqno。循环计数。
• absolute sequence number：从0开始，不会溢出(64 bit)。非循环计数。
• stream index：重排器中传入的索引，从0开始。非循环计数。

通过上图，我们很容易就能梳理出下列关系：

seqno = abs seqno + ISN

那么两种转化方式考虑如下：

1. 64bit -> 32 bit: 如上式
2. 32bit -> 64bit: 这里加一个入参 checkpoint 的概念
   1. checkpoint：最近一次convert得到的abs seqno, 本次convert得到的数应该尽量的与他接近(我们认为相邻两个seqno的差值不会超过int32Max)。
   2. 故而得到abs seqno，而后与checkpoint做比较，离得最近的为准。

测试

通过测试~

2.2 Implementing the TCP receiver

实现基于滑动窗口的tcp接收端。

解读一下TCPReceiver这个类，它以重排器为参数作为构造函数。我们不仅要接收由对端发来的数据，当然还要回复消息给对方，比如 ack 和 rst 消息。

思路讨论

我们一共要实现两个接口：Receive 和 Send。用这两个接口来实现一个具有流量控制和异常控制的滑动窗口机制。

在Receive中，注意要对特殊标志有特殊处理，如fin, ack, rst。

在Send中，实际上就是回复，我认为主要用来发送ack,rst和一些建议的消息。

要注意序列号的转化，以及我们传递给Reassembler的序列号要是abs seqno。

测试

调试调了得有快俩小时。

cmake –build build –target check2

通过~

lab3 the TCP sender

主要实现超时重传和拥塞控制

概述

先详细读一读实验指南吧

TCP是不稳定的网络环境中的可靠传输协议。通信的双方(peer)即使发送者，也是接收者。

TCP发送端的职责：

• 跟踪接收端的窗口状态（通过window size 和 ackno）
• 通过读ByteStream的状态在可以装填时装填window，创建并发送TCP segment，并且在需要时带上SYN和FIN flag。
• 跟踪outstanding segments,即为发送了但是还未被接收端ack。
• 超时后重传outstanding segments.

为什么我们要关注以上这些呢？

• 重传：基本原则是，若接收端允许我们发送，我们就发送。且我们应持续重传outstanding segments.这被称为ARQ(Atumic Repeat Request)。
• 感谢我们之前的工作，我们知道了接收端只要收到每个index tagged byte至少一次，而无关收到的顺序，它就能重新组建byte stream, 所以我们发送端就需要确认接收端至少要收到每单位一次。

TCP Sender怎么知道segment丢失了？

我们有一个tick方法, 表示超时的时间。如果我们最早发送的segment在达到超时时间后还是没有得到ack，那么我们就需要重传了。

1. 每过去几个ms，tick方法就会被调用来告诉你过去了多久。我们可以通过它来记录TCP Sender存活的时间。由于已经提供了tick方法，大伙儿就不要再从其他途径来获取时间了。
2. TCP Sender被构建的时候，是有个参数能够传入RTO(retransmission timeout)的. 当然，RTO是会随着时间调整的，但是初始值不会变化。initial_RTO_ms 是该初始值。
3. 我们还需要实现重传的定时器timer,一个可以在特定时间或者RTO过期的时候发出告警的定时器。我们需要基于tick来实现相关逻辑。
4. 我们需要在发送带有数据的segment时启动timer，这样在RTO之后它就能过期。
5. 当所有发送的segment都被ack后，停止RTO timer.
6. 如果调用了 tick 函数且重传定时器已超时：
   1. 重传 TCP 接收方尚未完全确认的最早（序列号最小）的段。我们需要在某些内部数据结构中存储未确认的段，以便能够做到这一点。
   2. 如果窗口大小不为零：
      1. 记录连续重传的次数，并将其递增，因为我们刚刚重传了某些内容。我们的TCP Connection 将使用此信息来判断连接是否无望（连续重传次数过多）并需要终止。
      2. 将 RTO 的值加倍。这被称为“指数退避”——它会减慢糟糕网络中的重传速度，以避免进一步阻塞网络。
   3. 重置重传计时器并启动它，使其在 RTO 毫秒后到期（请注意，我们可能刚刚将 RTO 的值加倍了！）
7. 当接收方给发送方发送一个确认号ackno，表明成功接收了新的数据（该确认号反映的绝对序列号大于任何之前的确认号）时：
   1. 将重传超时（RTO）时间重置为其“初始值”。
   2. 如果发送方有任何未确认的数据，则重新启动重传计时器，使其在 RTO 毫秒后到期（以当前 RTO 值为准）。
   3. 将“连续重传次数”的计数重置为零。

不好意思，刚才说了这么多，一下子晕过去了~

我们来实现TCP发送端吧~！

实现TCP发送端

我们需要实现几个方法

• void push( const TransmitFunction& transmit ):
  • 尽可能往window里填充segment，使用transmit方法来发送segment.
  • 我们需要保证所有装填的TCP Sender Messages都在window的容量内，尽可能装填，但是不要超过TCPConfig::MAX_PAYLOAD_SIZE.
  • 可以通过sequence_length方法获取已经占据的seq数。注意SYN和FIN也占据一个seq哦
• void receive( const TCPReceiverMessage& msg ):
  • 从接收端收到消息，左端是ackno,右端是ackno + window size, 注意收到消息后我们就知道被ack的边界了：ackno 是被ack的最大seqnum.
• void tick( uint64_t ms_since_last_tick, const TransmitFunction& transmit ):
  • 过去的时间~ 再次提醒不要使用其他任何的时间源
• TCPSenderMessage make_empty_message() const:
  • 需要发送一个正确设置seqno的zero-lengthmessage.
  • 不占用实际的seqno？所以不用跟踪它为outstanding.

思路讨论

实验手册讲的还是蛮清晰的，那么开始（面向测试）编程吧~

测试

cmake –build build –target check3