CS144 - lab 1

date

Nov 29, 2022

slug

cs144-lab1

status

Published

简介

本次lab 对应到 week 3。

week 3 的 slide 讲的都是包交换（packet switching）技术，这里记录一下基本概念：

包交换技术

数据从http ⇒ tcp ⇒ ip层层封装然后交给路由器转发到目的地

Delay

使用路由交换技术不可避免的延迟：

链接上固定的传播延迟。 Propagation delay along the links (fixed)
数据打包的固定延迟。Packetization delay to place packets onto links (fixed)
路由器数据包缓冲区中的排队延迟. Queueing delay in the packet buffers of the routers (variable)

缓冲区

网络环境是有波动的，如下图：

发送的bytes和时间的曲线可能会产生波动，为此缓冲区可以缓解这些波动带来的影响。缓冲区可以将部分数据缓存起来，避免丢失。

这次lab的任务是完成StreamReassembler部分

同时说明了我们每个 lab 需要做的任务

2 Getting started

这边要求我们合并远程的 lab1-startercode 代码再继续工作。

我一开始没搞清楚这个 lab 的 git 分支逻辑，然后尝试了几次才搞清楚。

这个 lab 的每一个分支都对应一个lab

我们每完成一个分支，都要保存下来，然后在完成的工作基础上合并新的labx-startercode 进行开发。

比如说我自己的仓库有 master，我开了一个 lab0 的分支，然后完成了 lab0 的测试。

接着我从 lab0 checkout 出来一个 lab1 的分支，然后 merge lab1-startercode 到这个新的 lab1 分支上，完成 lab1 的任务，以此类推

示意图大概就是这样

当然这是我自己的 git 风格，你可以在原始的 master 上进行迭代开发，而我习惯每进行一个 lab 都创建一个新的分支

ok，搞定之后我们看需求

3 Putting substrings in sequence

在 lab1 和 lab2 我们将要实现 TCP receiver，它能够接受数据报文并且将它们转换为可靠的字节流供应用程序从 socket 中读取数据。

TCP sender 将字节流分割为多个 segments，每个子串最大长度不超过 1460 bytes。网络是不稳定的，可能会产生乱序、丢失、重复提交等这些工作。receiver 必须要充足这些 segments 以实现可靠的字节流（reliable byte stream）

本次 lab 的工作就是实现 StreamReassmbler

接收 substrings，包括了组成 string 的 bytes，还有 string 在 stream 中的唯一 index。这些数据可能是乱序的，需要我们组装起来

使用 ByteStream 作为输出，有序的把 bytes 写入到 ByteStream 中

然后文档也给出了需要实现的接口，同时强调了 StreamReassmbler 实现的是 TCP 的可靠性：从任意字节数据中恢复出原有的数据流，用此来对抗网络波动产生的丢失、复制等结果。

接口说明在stream_reassembler.hh

3.1 What’s the “capacity”?

主要是定义了 capacity 的含义：

一方面是限制了 ByteStream 的大小

另一方面限制了从 substrings 中读取的最大 bytes 数

比如下面这种图

蓝色部分指的是已经处理完的数据，绿色部分指的是在 ByteStream 中的数据，红色部分指的是还没有放入 ByteStream 的部分，后面的部分就是还没开始处理的数据

分析和设计

我们最终要设计的结构如下所示：

有一个 buffer 帮助我们缓存不能立即放入 ByteStream 的数据

一个 ByteStream 供读写

特别的我们需要注意这种情况：

假设我们读入 5 和 6，那么后面的三个 bytes 也应该一并放入 ByteStream 中

然后我们需要合并 buffer 中的 bytes，例如：

如果某次输入中带有10、11，例如 index = 7，data = “aaaa”，那么 7 ~ 12 的数据应该立即合并

实验结果

第一次尝试

第一个版本，用 set 来标记出现过的 index，用 map 来作为缓冲区，每次push_substring的时候都先往 map 里面放，然后再尝试从 map 里面取 byte 放到 ByteStream 里面

虽然通过了本地测试，但是性能比较糟糕。

首先是按照 byte 插入 buffer 性能太低了，然后用 set 标记使用过的 index 是没有必要的，因为最终表示的字节流是一致的，我当时写的时候没有注意到这一点

第二次尝试

经过第一次尝试，现在问题清晰很多了，问题本质就是一个算法问题：

对于一大段的 bytes，有多个切片（线段），切片之间可能重叠，每次输入会提供一个切片和起点，对于能够立即写入的切片，应该马上写入到 ByteStream 中，不能写入的切片应该暂存，但是需要丢弃容量之外的 bytes。

显然我们从线段的角度考虑更优，这里的线段可能会重叠、乱序、重复，但是它们表示的 bytes 都是一致的，这个性质很重要。

对于这个角度，我最先想到用堆来处理，每次都把一个 node: <index, slice> 放置到堆中，然后尝试将堆顶写入到 ByteSteam 中。但是用堆经过若干次插入后可能会变得很冗余，也就是线段重叠的部分会很多，这是不符合设计的（lab1 的 FAQs 也有说明）。

于是可以在堆上进一步尝试，我们根据 node 的 index 作为第一索引，存放到一个有序的数据结构中，我们对这个数据结构的要求是：node 之间没有重叠的部分。

那么在 push_substring 的时候，对于当前的 node，我们可以检查它前后的 node 是否能合并，如果能合并则消除重叠部分，直到不能合并为止。这样能够保证数据结构中的 node 都是无重叠的。显然用二叉排序树能够很好的满足我们的要求，还可以用二分来加快查找过程。在 cpp 里面，set 的底层是红黑树，使用起来很方便。

这个核心数据结构想明白之后，接下来的实现就简单了。

push_substring的流程