CS144计算机网络 Lab1

一、简介

这里记录了笔者学习 CS144 计算机网络 Lab1 的一些笔记 - 流重组器 StreamReassembler

CS144 Lab1 实验指导书 - Lab Checkpoint 1: stitching substrings into a byte stream

个人 CS144 实验项目地址 - github

PS: 在做 CS144 前,最好先学一手计网理论,或者读读我之前写的笔记

二、实验结构

这幅图完整的说明了CS144 这门实验的结构:

image-20211105142904316

其中, ByteStream 是我们已经在 Lab0 中实现完成的。

我们将在接下来的实验中分别实现:

  • Lab1 StreamReassembler:实现一个流重组器,一个将字节流的字串或者小段按照正确顺序来拼接回连续字节流的模块
  • Lab2 TCPReceiver:实现入站字节流的TCP部分。
  • Lab3 TCPSender:实现出站字节流的TCP部分。
  • Lab4 TCPConnection: 结合之前的工作来创建一个有效的 TCP 实现。最后我们可以使用这个 TCP 实现来和真实世界的服务器进行通信。

该实验引导我们以模块化的方式构建一个 TCP 实现。

流重组器在 TCP 起到了相当重要的作用。迫于网络环境的限制,TCP 发送者会将数据切割成一个个小段的数据分批发送。但这就可能带来一些新的问题:数据在网络中传输时可能丢失、重排、多次重传等等。而TCP接收者就必须通过流重组器,将接收到的这些重排重传等等的数据包重新组装成新的连续字节流。

三、环境配置

当前我们的实验代码位于 master 分支,而在完成 Lab1 之前需要合并一些 Lab1 的依赖代码,因此执行以下命令:

1
git merge origin/lab1-startercode

之后重新 make 编译即可。

四、如何调试

先 cmake && make 一个 Debug 版本的程序。

所有的评测程序位于build/tests/中,先一个个手动执行过去。

若输出了错误信息,则使用 gdb 调试一下。

五、StreamReassembler 实现

1. 要求

在我们所实现的流重组器中,有以下几种特性:

  • 接收子字符串。这些子字符串中包含了一串字节,以及该字符串在总的数据流中的第一个字节的索引

    是不是有TCP那味了 :-) 感兴趣可以看看真实世界中的 TCP 报文段结构 - Kiprey Blog

  • 流的每个字节都有自己唯一的索引,从零开始向上计数。

  • StreamReassembler 中存在一个 ByteStream 用于输出,当重组器知道了流的下一个字节,它就会将其写入至 ByteStream中。

需要注意的是,传入的子串中:

  • 子串之间可能相互重复,存在重叠部分

    但假设重叠部分数据完全重复。

    不存在某些 index 下的数据在某个子串中是一种数据,在另一个子串里又是另一种数据。

    重叠部分的处理最为麻烦。

  • 可能会传一些已经被装配了的数据

  • 如果 ByteStream 已满,则必须暂停装配,将未装配数据暂时保存起来

除了上面的要求以外,容量 Capacity 需要严格限制:

image-20211107124153476

为了便于说明,将图中的绿色区域称为 ByteStream,将图中**存放红色区域的内存范围(即 first unassembled - first unacceptable)**称为 Unassembled_strs。

CS144 要求将 ByteStream + Unassembled_strs 的内存占用总和限制在 Reassember 中构造函数传入的 capacity 大小。因此我们在构造 Reassembler 时,需要既将传入的 capacity 参数设置为 ByteStream的缓冲区大小上限,也将其设置为first unassembled - first unacceptable的范围大小,以避免极端情况下的内存使用。

注意:first unassembled - first unacceptable的范围大小,并不等同于存放尚未装配子串的结构体内存大小上限,别混淆了。

Capacity 这个概念很重要,因为它不仅用于限制高内存占用,而且它还会起到流量控制的作用(见 lab2)。

2. 实现思路

总体上,现阶段的要求还是比较简单的,但是,这里面需要考虑到相当多的情况。

在具体说明处理情况之前,我们先简单定义几个变量来指示当前状态:

  • _next_assembled_idx:下一个待装配的字节索引
  • _unassemble_strs: 一个字节索引到数据子串的 map 映射
  • _eof_idx: 指示哪个字节索引代表 EOF

以下是具体需要考虑的情况

  1. index <= _next_assembled_idx && index + data.size() > _next_assembled_idx

    1
    2
    3
    4
    5
    index    _next_assembled_idx   index+data.size()   
    V V V
    --+-----------------------------------+-----------------------------
    |///////////////|///////////////////|
    --+-----------------------------------+-----------------------------

    这种情况可以先截断掉

    • 前面已经装配过的那部分数据
    • 后面与已经存入 _unassembled_strs 的数据重合的那部分数据

    这样截断是为了让每次装配进的数据与存入 _unassembled_strs 的数据不产生重合,简化处理逻辑。

    之后就可以直接装配,无需任何额外处理。

    如果装配不下,即 _output 已满,那么就必须先放入待装配队列 _unassembled_strs 中,等待装配。

  2. index > _next_assembled_idx

    这种情况是需要认真考虑的,因为这种情况可能会与一些已经保存起来的未装配子串重合,导致大量的内存占用以及无用的轮询处理。对于传入数据的始末位置,分别有好几种情况。

    为了便于说明,我们将_unassembled_strs中比 index 小且距离最近的那部分数据,称作 up_data, 其起始位置称为 up_idx。
    down_data 和 down_idx 同上,指的是在 _unassembled_strs中比当前传入 index 大且距离最近的那部分数据与起始位置。

    up 指的是数据前面的那个方向,down 是数据后面的那个方向。

    首先是传入数据头部位置的情况:

    1. 若 up_idx + up_data.size() <= index, 则说明当前传入 data 没有与已经保存的上一个子串重叠。这种无需处理

      1
      2
      3
      4
      5
      _next_assembled_idx  up_idx                  index  
      V V up_data.size V
      ----------+------------+------------------+---+-----------------...
      | |++++++++++++++++++| |\\\\\\\\\\\\\\\\\...
      ----------+------------+------------------+---+-----------------...
    2. 若 up_idx + up_data.size() > index, 则说明传入数据前半部分重合,需要进行截断,同时在截断后更新当前 index。

      截断前:

      1
      2
      3
      4
      5
      6
      7
      _next_assembled_idx  up_idx       up_idx+up_data.size     
      V V V
      ----------+------------+-----------+------+-----------------...
      | |+++++++++++|+/+/+/|\\\\\\\\\\\\\\\\\...
      ----------+------------+-----------+------+-----------------...
      A
      index

      截断后:

      1
      2
      3
      4
      5
      6
      7
      _next_assembled_idx  up_idx       up_idx+up_data.size     
      V V V
      ----------+------------+------------------+-----------------...
      | |++++++++++++++++++|\\\\\\\\\\\\\\\\\...
      ----------+------------+------------------+-----------------...
      A
      new_idx

    而对于传入数据尾部位置的情况,情况又有所不同:

    1. 若 index + data.size() <= down_idx,则说明当前数据的后半部分没有重合,此时无需进行任何处理。

      1
      2
      3
      4
      5
       index      index+data.size  down_idx
      V V V
      ---+---------------+------------+------------------...
      |///////////////| |++++++++++++++++++...
      ---+---------------+------------+------------------...
    2. 若 index + data.size() > down_idx,则说明后半部分重合。但后半部分重合又有两种情况

      1. index + data.size() < down_idx + down_data.size(),这种就是常规情况的部分重合,截断掉重合部分即可

        截断前:

        1
        2
        3
        4
        5
        6
        7
         index              index+data.size   
        V V
        ---+---------------+-------+------------+-----...
        |///////////////|+/+/+/+|++++++++++++| ...
        ---+---------------+-------+------------+-----...
        A A
        down_idx down_idx+down_data.size

        截断后

        1
        2
        3
        4
        5
        6
        7
         index       index+data.size   
        V V
        ---+------------------------------------+-----...
        |///////////////|++++++++++++++++++++| ...
        ---+------------------------------------+-----...
        A A
        down_idx down_idx+down_data.size
      2. index + data.size() < down_idx + down_data.size(),这种是完全重合:当前传入的 data 完全覆盖下一个保存的data,此时将下一个 data 丢弃。

        注意,若存在完全覆盖的情况,则需要重复检测 index + data.size 的位置与丢弃下一个data后,新的下一个data末尾位置。因为可能当前传入的 data 会同时覆盖好几个保存的 data。

        处理前:

        1
        2
        3
        4
        5
        6
        7
         index                          index+data.size   
        V V
        ---+-----+--------------------+---------+-----+------...
        |/////|/+/+/+/+/+/+/+/+/+/+|/////////| |++++++...
        ---+-----+--------------------+---------+-----+------...
        A A
        down_idx down_idx+down_data.size

        处理后:

        1
        2
        3
        4
        5
        6
        7
         index                          index+data.size   
        V V
        ---+------------------------------------+-----+------...
        |////////////////////////////////////| |++++++...
        ---+------------------------------------+-----+------...
        A
        新的 down_idx

上面所描述的处理方式可以很好的保证,_unassembled_strs 中的各个子串之间互不重叠,提高了内存利用效率。这是一种用时间换空间的方式,因为个人认为,从不可靠网络中获取到的数据是相当宝贵的,与降低处理时间相比,会更加宝贵一点。

EOF 的实现需要严格按照实验指导书来。当传入的 eof 参数为真时,表示当前传入的数据子串的最后一个字节将是整个流中的最后一个字节,这并不意味着这是最后一次调用 reassembler 来传入子串,因此需要额外将这个 eof_idx 保存,并在 reassemble 后判断一下是否到达 EOF 位置。

3. 具体实现

实现的代码已经上传到github上

以下是测试结果,总测试时间低于0.5s,还可以。

image-20211107094807715

  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2020-2024 Kiprey
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~