CS144计算机网络 Lab2

一、简介

这里记录了笔者学习 CS144 计算机网络 Lab2 的一些笔记 - TCP接收方实现 TCPReceiver

CS144 Lab2 实验指导书 - Lab Checkpoint 2: the TCP receiver

个人 CS144 实验项目地址 - github

二、环境配置

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

1
git merge origin/lab2-startercode

之后重新 make 编译即可。

三、TCPReceiver 简述

在 Lab2,我们将实现一个 TCPReceiver,用以接收传入的 TCP segment 并将其转换成用户可读的数据流。

TCPReceiver 除了将读入的数据写入至 ByteStream 中以外,它还需要告诉发送者两个属性

  • 第一个未组装的字节索引,称为确认号ackno,它是接收者需要的第一个字节的索引。
  • 第一个未组装的字节索引第一个不可接受的字节索引之间的距离,称为 窗口长度window size

ackno 和 window size 共同描述了接收者当前的接收窗口。接收窗口是 发送者允许发送数据的一个范围,通常 TCP 接收方使用接收窗口来进行流量控制,限制发送方发送数据。

总的来说,我们将要实现的 TCPReceiver 需要做以下几件事情:

  • 接收TCP segment
  • 重新组装字节流(包括EOF)
  • 确定应该发回给发送者的信号,以进行数据确认和流量控制

四、索引转换

TCP 报文中用来描述**当前数据首字节的索引(序列号 seqno)**是32位类型的,这意味着在处理上增加了一些需要考虑的东西:

  • 由于 32位类型最大能表达的值是 4GB,存在上溢的可能。因此当 32位的 seqno 上溢后,下一个字节的 seqno 就重新从 0 开始。

  • 处于安全性考虑,以及避免与之前的 TCP 报文混淆,TCP 需要让每个 seqno 都不可被猜测到,并且降低重复的可能性。因此 TCP seqno 不会从 0 开始,而是从一个 32 位随机数起步(称为初始序列号 ISN)。

    而 ISN 是表示 SYN 包(用以表示TCP 流的开始)的序列号。

  • TCP 流的逻辑开始数据包逻辑结束数据包各占用一个 seqno。除了确保接收到所有字节的数据以外,TCP 还需要确保接收到流的开头和结尾。 因此,在 TCP 中,SYN(流开始)和 FIN(流结束)控制标志将会被分别分配一个序列号(SYN标志占用的序列号就是ISN)。

    流中的每个数据字节也占用一个序列号。

    但需要注意的是,SYN 和 FIN 不是流本身的一部分,也不是传输的字节数据。它们只是代表字节流本身的开始和结束。

字节索引类型一多就容易乱。当前总共有三种索引:

  • 序列号 seqno。从 ISN 起步,包含 SYN 和 FIN,32 位循环计数
  • 绝对序列号 absolute seqno。从 0 起步,包含 SYN 和 FIN,64 位非循环计数
  • 流索引 stream index。从 0 起步排除 SYN 和 FIN64 位非循环计数。

这是一个简单浅显的例子,用于区分开三种索引的区别:

image-20211107105751818

序列号和绝对序列号之间相互转换稍微有点麻烦,因为序列号是循环计数的。在该实验中,CS144 使用自定义类型 WrappingInt32 表示序列号,并编写了它与绝对序列号之间的转换。

但这个需要我们自己实现,天下没有免费的午餐(笑)

这个实现稍微有点麻烦,而且实现的时候也最好避免各类循环,减少使用条件判断的次数,以提高执行效率。

我的实现如下所示,相关细节以注释形式写入至代码中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//! Transform an "absolute" 64-bit sequence number (zero-indexed) into a WrappingInt32
//! \param n The input absolute 64-bit sequence number
//! \param isn The initial sequence number
WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
return WrappingInt32{isn + static_cast<uint32_t>(n)};
}

//! Transform a WrappingInt32 into an "absolute" 64-bit sequence number (zero-indexed)
//! \param n The relative sequence number
//! \param isn The initial sequence number
//! \param checkpoint A recent absolute 64-bit sequence number
//! \returns the 64-bit sequence number that wraps to `n` and is closest to `checkpoint`
//!
//! \note Each of the two streams of the TCP connection has its own ISN. One stream
//! runs from the local TCPSender to the remote TCPReceiver and has one ISN,
//! and the other stream runs from the remote TCPSender to the local TCPReceiver and
//! has a different ISN.
uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
// 32位的范围
const constexpr uint64_t INT32_RANGE = 1l << 32;
// 获取 n 与 isn 之间的偏移量(mod)
// 实际的 absolute seqno % INT32_RANGE == offset
uint32_t offset = n - isn;
/// NOTE: 最大的坑点!如果 checkpoint 比 offset 大,那么就需要进行四舍五入
/// NOTE: 但是!!! 如果 checkpoint 比 offset 还小,那就只能向上入了,即此时的 offset 就是 abs seqno
if(checkpoint > offset) {
// 加上半个 INT32_RANGE 是为了四舍五入
uint64_t real_checkpoint = (checkpoint - offset) + (INT32_RANGE >> 1);
uint64_t wrap_num = real_checkpoint / INT32_RANGE;
return wrap_num * INT32_RANGE + offset;
}
else
return offset;
}

四、TCPReceiver 实现

1. 要求

需要实现一些类成员函数

  • segment_received(): 该函数将会在每次获取到 TCP 报文时被调用。该函数需要完成:

    • 如果接收到了 SYN 包,则设置 ISN 编号。

      注意:SYN 和 FIN 包仍然可以携带用户数据并一同传输。同时,同一个数据包下既可以设置 SYN 标志也可以设置 FIN 标志

    • 将获取到的数据传入流重组器,并在接收到 FIN 包时终止数据传输。

  • ackno():返回接收方尚未获取到的第一个字节的字节索引。如果 ISN 暂未被设置,则返回空。

  • window_size():返回接收窗口的大小,即第一个未组装的字节索引第一个不可接受的字节索引之间的长度。

这是 CS144 对 TCP receiver 的期望执行流程:

image-20211107122822566

2. 具体实现

思路

对于 TCPReceiver 来说,除了错误状态以外,它一共有3种状态,分别是:

  • LISTEN:等待 SYN 包的到来。若在 SYN 包到来前就有其他数据到来,则必须丢弃
  • SYN_RECV:获取到了 SYN 包,此时可以正常的接收数据包
  • FIN_RECV:获取到了 FIN 包,此时务必终止 ByteStream 数据流的输入。

在每次 TCPReceiver 接收到数据包时,我们该如何知道当前接收者处于什么状态呢?可以通过以下方式快速判断:

  • 当 isn 还没设置时,肯定是 LISTEN 状态
  • 当 ByteStream.input_ended(),则肯定是 FIN_RECV 状态
  • 其他情况下,是 SYN_RECV 状态

Window Size 是当前的 capacity 减去 ByteStream 中尚未被读取的数据大小,即 reassembler 可以存储的尚未装配的子串索引范围。

ackno 的计算必须考虑到 SYN 和 FIN 标志,因为这两个标志各占一个 seqno。故在返回 ackno 时,务必判断当前 接收者处于什么状态,然后依据当前状态来判断是否需要对当前的计算结果加1或加2。而这条准则对 push_substring 时同样适用。

源码实现

类声明:

1
2
3
4
5
6
7
8
9
10
11
12
13
class TCPReceiver {
WrappingInt32 _isn;
bool _set_syn_flag;

//! Our data structure for re-assembling bytes.
StreamReassembler _reassembler;

//! The maximum number of bytes we'll store.
size_t _capacity;

public:
...
}

方法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* \brief 当前 TCPReceiver 大体上有三种状态, 分别是
* 1. LISTEN,此时 SYN 包尚未抵达。可以通过 _set_syn_flag 标志位来判断是否在当前状态
* 2. SYN_RECV, 此时 SYN 抵达。只能判断当前不在 1、3状态时才能确定在当前状态
* 3. FIN_RECV, 此时 FIN 抵达。可以通过 ByteStream end_input 来判断是否在当前状态
*/

void TCPReceiver::segment_received(const TCPSegment &seg) {
// 判断是否是 SYN 包
const TCPHeader &header = seg.header();
if (!_set_syn_flag) {
// 注意 SYN 包之前的数据包必须全部丢弃
if (!header.syn)
return;
_isn = header.seqno;
_set_syn_flag = true;
}
uint64_t abs_ackno = _reassembler.stream_out().bytes_written() + 1;
uint64_t curr_abs_seqno = unwrap(header.seqno, _isn, abs_ackno);

//! NOTE: SYN 包中的 payload 不能被丢弃
//! NOTE: reassember 足够鲁棒以至于无需进行任何 seqno 过滤操作
uint64_t stream_index = curr_abs_seqno - 1 + (header.syn);
_reassembler.push_substring(seg.payload().copy(), stream_index, header.fin);
}

optional<WrappingInt32> TCPReceiver::ackno() const {
// 判断是否是在 LISTEN 状态
if (!_set_syn_flag)
return nullopt;
// 如果不在 LISTEN 状态,则 ackno 还需要加上一个 SYN 标志的长度
uint64_t abs_ack_no = _reassembler.stream_out().bytes_written() + 1;
// 如果当前处于 FIN_RECV 状态,则还需要加上 FIN 标志长度
if (_reassembler.stream_out().input_ended())
++abs_ack_no;
return WrappingInt32(_isn) + abs_ack_no;
}

size_t TCPReceiver::window_size() const { return _capacity - _reassembler.stream_out().buffer_size(); }

测试结果就不贴了,不同的机器上跑所消耗的时间是不一样的,没什么可比性。

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

请我喝杯咖啡吧~