standford cs144计算机网络Lab1-实现字节流重组器

书接上回打开终端在项目目录之中输入git checkout -b mylab1 origin/lab1-startercode可以获取纯净的lab1原始代码建立属于你的lab1的分支就可以在操作台上面写代码了。通过git merge mylab0将上一个实验的实现内容合并到当前分支本实验依赖lab0实现的Bytestream。初始化构建方法mkdir build cd build cmake .. make -j4一、实验任务和原理计算机网络采用分层设计底层服务通常只提供较低的可靠性保障。以网络层的IP协议为例它仅承诺“尽最大努力”交付数据包但数据包在实际传输过程中可能面临丢失、乱序、重复或内容损坏等问题。而上层的应用程序总是希望看到一条可靠的、连续并且顺序正确的数据流TCP则是其中的经典案例他在底层网络只提供“尽最大努力”的数据包传输服务之上为通信双方提供可靠的字节流服务能够让通信双方看到可靠有序的字节流。在lab1中我们将实现streamReassembler模块实现TCP能够将字节流片段拼接成为可靠的连续的原始流的能力。streamReassembler主要需要我们完成保存乱序的片段去除重合和重叠片段将他们重新组装成为正确的顺序并且写入我们在lab0之中实现的bytesteream之中。在本实验之中会出现以下核心接口需要我们完成设计// Construct a StreamReassembler that will store up to capacity bytes. StreamReassembler(const size_t capacity); ​ // Receive a substring and write any newly contiguous bytes into the stream, // while staying within the memory limits of the capacity. Bytes that would // exceed the capacity are silently discarded. // // data: the substring // index indicates the index (place in sequence) of the first byte in data // eof: the last byte of this substring will be the last byte in the entire stream void push_substring(const string data, const uint64_t index, const bool eof); ​ // Access the reassembled ByteStream ByteStream stream_out(); ​ // The number of bytes in the substrings stored but not yet reassembled size_t unassembled_bytes() const; ​ // Is the internal state empty other than the output stream? bool empty() const;这些提供的接口也就是stream_reassembler的函数成员作为公共成员向外提供操作。头文件之中给定的私有成员ByteStream _output; //! The reassembled in-order byte stream size_t _capacity; //! The maximum number of bytes_output是内部输出的有序字节流_capacity是可容纳的最大容量。实验handout也对capacity这个成员变量做出了相关的解释。capacity不仅单纯限制缓存的接收到的乱序数据也包括ByteStream当前保存的还没被读走的数据是对内存使用的限制所以存在以下关系ByteStream 中尚未读取的字节数 StreamReassembler 中未组装字节数 capacity可以接收的窗口范围通常是[first_unassembled, first_unacceptable)其中first_unassembled 已经成功写入 ByteStream 内容的下一个字节下标 first_unacceptable first_unassembled 剩余可用容量凡是落在这个范围之外的字节都应该丢弃。图示如下需要处理的关键场景按序到达push_substring(ab, 0) 立即写入 outputoutput 中有 ab push_substring(cd, 2) 紧接着output 中变成 abcd这是最简单的情况当前期待的下一个字节刚好达到乱序到达空洞push_substring(b, 1) 还没收到 index0 的字节先存起来output 为空 push_substring(a, 0) 现在 0 和 1 都有了组装 ab 写入 output这里需要一个数据结构来暂存早到的片段重叠片段push_substring(abc, 0) output: abc push_substring(bcd, 1) bc 与已有数据重叠d 是新的 → output: abcd push_substring(cdef, 2) cd 重叠ef 是新数据 → output: abcdef新到达的片段可能出现部分或者全部和已经存储或者已经输出的数据重叠在这里需要精准的裁剪重复片段push_substring(abcd, 0) output: abcd push_substring(abcd, 0) 完全相同应被忽略unassembled_bytes 不变 push_substring(ab, 0) 是已有数据的前缀子集应被忽略重复片段是不应该被重复写入的容量限制capacity 2 push_substring(ab, 0) → output 有 ab占满容量 push_substring(cd, 2) → 超出容量cd 被丢弃或部分丢弃总容量等于bytestream之中未读的字节加上未组装暂存的字节超出的部分应该按照要求丢弃。eof处理push_substring(b, 1).with_eof(true) 虽然 eoftrue但 index0 还是空洞 push_substring(a, 0) 现在 ab 写入并且此时才设置 output 的 EOF即使eoftrue也必须要等到前面的所有字节都按照顺序写入值得注意的是测试样例里面存在大规模随机测试样例考验我们对于数据结构存储的选择。以上这些场景在给定的测试框架之中都有相关的测试样例我们选取的数据结构以及实现的方案需要成功处理所有的样例。二、数据结构选取和设计方案需要实现的核心文件是stream_reassembler.hh和stream_reassembler.cc头文件之中增加需要的成员变量并且在实现文件之中将给定的函数声明按照要求实现。在数据结构选型上直观的思路是采用std::set或std::map这类有序关联容器来存储乱序到达的子串及其索引。这两者的底层实现均为红黑树插入与查找操作的时间复杂度为O(log n)且每个节点需要额外存储父指针、颜色等信息内存开销显著。虽然这种方案在处理稀疏数据时足够灵活但对于大规模数据流场景性能瓶颈不容忽视。相比之下std::deque结合滑动窗口的设计更为高效它避免了std::vector在头部操作时频繁的数据搬移和内存重分配同时相较于红黑树结构std::deque的插入和随机访问均为O(1)常数时间且内存布局更加紧凑更适合处理高吞吐量的字节流重组任务。在这里主要给出std::deque的实现办方法以及对比std::deque和std::set两者在跑测试的时候耗时上的对比。在这里偏向选取std::deque是因为lab0在实现bytestream的时候也是选择的std::deque这样体现了一致性设计和逻辑对称的美感因为通过阅读handout可以明显感受到bytestream和这里缓冲滑动窗口在逻辑上其实是连续的参考capacity的图示数据从网络流动到应用程序其实更加自然。在数据结构的选取之中实验的handout存在以下一段提示这一段话直观的意思理解就是在实际接收substring缓冲区里面我们不能存储相互重叠的子字符串简单来说先接收到了2~4的字符此时又传过来了3~5的字符串我们不能存储两个而只需要在第一个字符串里面补充第二次新出现的字符即可。以下是我选取的数据结构ByteStream _output; //! The reassembled in-order byte stream size_t _capacity; //! The maximum number of bytes size_t _unassembled_start; //! The first index of the unassembed byte (beginning of the window) size_t _unassembled_size; //! The size of the unassembled bytes bool _eof; //! Whether the end of the stream has been reached size_t _eof_index; //! The index of the end of the stream std::dequechar _buffer; //! The buffer of sliding window std::dequebool _filled; //! Whether the buffer has been filled特别需要注意的是在实际的窗口滚动的时候我们都是遵循的左闭右开的规则比如_unassembled_start是第一个可以接受重组字符串的索引位置也就是说该位置当前没有字符在缓冲区可以放置后续传来的字符而_eof_index代表右侧的窗口末端这个位置是能接受的流末端的下一个字符这个索引位置被_capacity_限制是不能放置字符的。三、代码实现和测试下面是我stream_reassembler.hh的实现#include stream_reassembler.hh #include algorithm #include string // Dummy implementation of a stream reassembler. // For Lab 1, please replace with a real implementation that passes the // automated checks run by make check_lab1. // You will need to add private members to the class declaration in stream_reassembler.hh template typename... Targs void DUMMY_CODE(Targs ... /* unused */) {} using namespace std; StreamReassembler::StreamReassembler(const size_t capacity) : _output(capacity) , _capacity(capacity) , _unassembled_start(0) , _unassembled_size(0) , _eof(false) , _eof_index(0) , _buffer(capacity, \0) , _filled(capacity, false) {} //! \details This function accepts a substring (aka a segment) of bytes, //! possibly out-of-order, from the logical stream, and assembles any newly //! contiguous substrings and writes them into the output stream in order. void StreamReassembler::push_substring(const string data, const size_t index, const bool eof) { if (eof) { _eof true; _eof_index index data.size(); } if (_capacity 0) { if (_eof _unassembled_start _eof_index) _output.end_input(); return ; } const size_t first_unacceptable _unassembled_start _output.remaining_capacity(); const size_t data_end index data.size(); const size_t start max(index, _unassembled_start); const size_t end min(data_end, first_unacceptable); if (start end) { for (size_t pos start; pos end; pos) { const size_t offset pos % _capacity; if (!_filled[offset]) { _buffer[offset] data[pos - index]; _filled[offset] true; _unassembled_size; } } } string assembled; while (_filled[_unassembled_start % _capacity]) { const size_t offset _unassembled_start % _capacity; assembled.push_back(_buffer[offset]); _filled[offset] false; _unassembled_start; --_unassembled_size; } if (!assembled.empty()) _output.write(assembled); if (_eof _unassembled_start _eof_index) _output.end_input(); } size_t StreamReassembler::unassembled_bytes() const { return _unassembled_size; } bool StreamReassembler::empty() const { return _unassembled_size 0; }相关解释实际传输之中有可能最末端的substring先到而前半段还没有传输到位此时先到的应该先确定到缓冲区_buffer之中并且标记_eoftrue末端_eof_index也可以算出来if (eof) { _eof true; _eof_index index data.size(); }计算可接收窗口的参数const size_t first_unacceptable _unassembled_start _output.remaining_capacity();这里这么写比较直观实际上bytestream对象_output和streamReassembler的对象构造的时候的capacity是一样的二者的底层都是std::deque实际计算可接收区间公式为_first_unassembled_capcity-_output.size()这里把他简化了而已。求片段和窗口的交集需要下面的参数const size_t start max(index, _unassembled_start); const size_t end min(data_end, first_unacceptable);起点的位置应该是当前substring的索引和可接收位置更靠后的索引值终点位置应该是first_unacceptable和substring的末端更靠前的索引毕竟超过限制的部分是需要丢弃的。当第一个可接收位置被标记成为true的时候就可以开始考虑往bytestream里面写入了同时窗口可以开始在前端收缩。这里重组缓存区域可能其中会有几段区域都有连续重组数据整体窗口连不起来但只要存在连续的前缀就可以写入bytestrem并且向后移动窗口。只有 ByteStream 中的数据被上层读走接收窗口才会继续向后扩大体现了滑动窗口随着数据被消费而不断推进的思想。考虑用一个临时string类型变量将缓存之中的字符流变成连续的字符串这里考虑到lab0之中实现的bytestream真实的写入接口传递的也是string类型确保类型一致。最后只有确认收到了 EOF并且 EOF 之前的所有字节都已经连续组装完成才结束输出流。其实换一句话说收到 EOF 是一个事件EOF 前的数据全部组装完成才是转换条件最终的状态变化就是关闭bytestream想清楚这些问题其实也很容易理解代码的原理。测试结果如下可以看到全部的测试点其实都在半秒钟之内跑完了证明选取std::deque是一种效率比较高的选择。而使用std::set实际上速度就会稍微慢一点这篇博客给出了std::set的解决方案【计算机网络】Stanford CS144 Lab Assignments 学习笔记 - 康宇PL 。cmake命令默认构建的是release版本可以使用cmake .. -DCMAKE_BUILD_TYPEDebug进行显式的调试具体可以参考实验手册提供的调试方法。四、复盘通过 CS144 Lab 1我们可以对 TCP 接收端的数据重组机制有更加具体的认识。网络传输并不能保证数据报按顺序到达还可能出现丢失、重复和乱序因此接收端需要根据每段数据的索引将零散片段重新拼接成连续、有序的字节流并在确认下一个字节后尽快写入ByteStream。实现StreamReassembler的过程看似类似经典的区间合并问题实际上还要同时考虑重叠数据去重、容量限制和实时输出。例如两个片段部分重叠时重复字节不能被再次保存或计入unassembled_bytes()否则不仅统计结果会出错也会使capacity失去限制内存使用的意义。这里的容量同时约束已经写入但尚未读取的字节以及收到但尚未组装的字节因此程序必须根据当前可用空间裁剪新片段丢弃已经输出的旧数据和超出接收窗口的数据对TCP滑动窗口和容量管理的理解进一步加深。实验中最容易出错的是各种边界情况例如空字符串、完全重复、前后部分重叠、一个新区间覆盖多个旧区间以及前方缺口补齐后连续输出多个缓存片段。EOF 的处理同样需要严格的状态管理收到携带 EOF 的片段只代表已经知道整个流的结束位置并不表示可以立即关闭输出流只有 EOF 之前的全部字节都已经连续组装完成才能调用end_input()。在性能方面大规模随机测试要求实现不能反复扫描全部数据应借助合理的数据结构将主要处理过程控制在O(n)或O(n log n)范围内。整个实也可以体会到单元测试不仅是验证程序的工具还可以帮助理解需求通过分别分析有序、乱序、重叠、容量和 EOF 等测试场景能够逐步明确程序必须维持的不变量。总体来看Lab 1 不只是完成了一次字符串拼接任务更重要的是可以训练对于可靠传输、容量管理、区间算法、状态机、边界条件和测试驱动开发的综合理解。