CS144 Lab 1

Lab Checkpoint 1: stitching substrings into a byte stream

Checkpoint1 spec

This checkpoint contains a “hands-on” component and an implementation component.

hands-on部分是今年新加的，需要加入Stanford内部网络才能做，因此跳过

在Lab1中，我们需要实现一个TCP接收端的重组器(Reassembler)，用来将TCP接收到的乱序的子字符串(substring)重组成原本的字节流，按照正确的顺序推送(push)到我们在Lab0实现的ByteStream中，供TCP的customer读出。

Implementation: putting substrings in sequence

Why we need to implement the TCP receiver's reassembler? What does it do?

The TCP receiver needs to handle duplication and reordering of segments, so it needs to have the ability to stitch arbitrary excerpts of the byte stream(unordered substrings) back into the original ordered stream.

To achieve this, the TCP receiver needs a reassembler to reassemble out-of-order byte stream.

The reassembler buffers unordered substrings that fit within the stream's available capacity until earlier gaps get filled in, discards substrings that lie beyond the stream's available capacity and push ordered substrings to the ByteStream. As the reader pops bytes from the ByteStream, the stream's sliding window slides across the stream and the reassembler can accept further bytes.

My Solution

这个lab的关键是理解上图的TCP Receiver's sliding window。我建议自己理解后手动画一遍图再开始coding:

当Reassembler接收到一个新的substring的时候，他要怎么做？

根据上图，ByteStream的buffer空间（绿色区域）和Reassembler的internal storage空间（红色空间）合并起来是一个大小始终为capacity的sliding window。TCP的customer每从ByteStream中读出一个byte，sliding window就向右slide一个byte，Reassembler就可以接收更远一个byte。

当Reassembler新收到一个substring，他需要将substring在红色区域(available capacity)的部分先写入Reassembler的internal storage。因此首先，我们需要知道红色区域的上下界。

提示：红色区域的起始位置是Reassembler正在等待的next byte，想想这与ByteStream有什么联系？

应该用什么data structure来表示Reassembler's internal storage？

Reassembler需要存储接收到的substring，以及substring在stream中的位置(index)，因此我选择用一个map来存储<key = first_index, value = substring>。每次Reassembler接收到一个substring，截取substring在红色区域的部分插入map中，然后用一个merge_substrings函数来合并相邻或重叠的substrings。每次插入map以及合并后，检查map中的第一个元素的key是否是Reassembler正在等待的next byte，如果是，就将对应的substring push到ByteStream中。

Debugging Advice

1. To test your code:

cmake --build build --target check1

2. You may sometimes need to use the move() function to pass an object that can’t be copied.

If you get your builds stuck and aren’t sure how to fix them, you can erase your build directory and build again

rm -rf build
cmake -S . -B build

Finish!

All tests in check1 pass!