计算机网络CS144-Lab2

TCP Receiver

Index和Seqno的转换

为了节省在TCP Header当中的空间,在StreamReassembler里面写的index虽然是一个uint64_t的类型,但是在实际的Header中是使用一个uint32_tseqno来进行标记位置的。对于uint32_tseqnouint64_tindex的相互转换则是通过以4GiB (2^32 bytes)为一个长度进行取模来实现。

同时为了提高TCP本身的安全性,并且确保每次获得的segments数据段都是来自于本次连接的,因此提出了ISN(Initial Sequence Number)的概念,即本次链接是从序号为isn开始作为seqno进行通信,大于isnseqno所代表的index是本次链接所需要的数据段,早于isnseqno则是来自于上一次连接的老数据段,并不需要处理。

如果想要将uint32_tseqno转为一个uint64_t则需要一个checkpoint作为定位,这个checkpoint在实现中就是最后一个重新组装后的字符位置

按lab2的原文:In your TCP implementation, you’ll use the index of the last reassembled byte as the checkpoint.

通过寻找距离checkpoint最近的seqno就可以定位到本来需要插入的seqno位置了

代码思路

对于将uint32_t转为uint64_t的代码实现很简单,只需要将uint64_tindex加上isn的值之后对2^32进行取模就行了,具体代码实现如下

1
2
3
4
WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
uint64_t result = (n + isn.raw_value()) % (static_cast<uint64_t>(UINT32_MAX) + 1);
return WrappingInt32(static_cast<uint32_t>(result));
}

而对于将wrap后的seqno转回index,我直接通过类似分类讨论的枚举找到了四个临界点,只需要判断checkpoint相对于临界点的位置就可以得到答案。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
const uint64_t L = (1ul << 32);
const uint64_t a = (checkpoint / L) * L - isn.raw_value() + n.raw_value();
if (checkpoint > a + (L * 3) / 2) {
return a + 2 * L;
} else if (checkpoint > a + L / 2) {
return a + L;
} else if (checkpoint < L) {
return n.raw_value() < isn.raw_value() ? a + L : a;
} else {
return checkpoint < a - L / 2 ? a - L : a;
}
}
详细思路点这里(硬分类,感觉好蠢,但是有效.jpg)
通解推导
checkpoint > L

由以下公式

(index+isn)modL=seqno\left ( index+isn \right )\mod{ L } = seqno

通过推导可以得到

index=seqno+kLisnindex = seqno + k * L - isn

因此如果需要得到离checkpoint最近的index就只需要找到合适的k即可,在这里不妨设

m=checkpoint/Lm = checkpoint / L

m作为一个附近值,通过画图可以知道,在一般情况下,答案一定在checkpoint附近的三个区间内

k的范围

seqno - isn > 0

在这种情况下,checkpoint的前中后三个区间都存在,只要列举并讨论范围就很简单了

seqno - isn为正数的时候,index可能的一个取值会落在第②个区间上,有

index=mL+seqnoisnindex'' = m * L + seqno - isn

此时第①区间和第③区间上的index可以分别表示为

index=indexLindex=index+Lindex' = index'' - L \\\\ index''' = index'' + L

index'index''index'''的中间值进行判断,很容易得到以下规律

a=mL+seqnoisnL=UINT32_MAX+1{checkpoint<aL/2index=a-LaL/2checkpoint<a+L/2index=aa+L/2checkpointindex=a+L\begin{array}{l} 令a = m*L+seqno-isn \\\\ L = UINT32\_MAX+1 \\\\ \left \{\begin{matrix} checkpoint < a - L/2 & \text{index=a-L}\\\\ a-L/2\leq checkpoint< a+L/2 & \text{index=a}\\\\ a+L/2\leq checkpoint & \text{index=a+L} \end{matrix}\right. \end{array}

注:此时checkpoint一定小于 a+L,因为a+L属于第③区间,而checkpoint在第②区间内

seqno - isn < 0

此时因为是从m*L的位置向前移动,所以相比于上面,三个可能是答案的index的分布则改为了

index=mL+seqnoisnindex=index+Lindex=index+2Lindex' = m * L + seqno - isn \\\\ index'' = index' + L \\\\ index''' = index' + 2 * L

所以很容易得到以下结果

a=mL+seqnoisnL=UINT32_MAX+1{checkpoint<a+L/2index=aa+L/2checkpoint<a+3L/2index=a + La+3L/2checkpointindex=a+2*L\begin{array}{l} 令a = m*L+seqno-isn \\\\ L = UINT32\_MAX+1 \\\\ \left \{\begin{matrix} checkpoint < a + L/2 & \text{index=a}\\\\ a+L/2\leq checkpoint< a+(3*L)/2 & \text{index=a + L}\\\\ a+(3*L)/2\leq checkpoint & \text{index=a+2*L} \end{matrix}\right. \end{array}

将以上两种规律整合,我们很容易可以得到以下通解

a=mL+seqnoisnL=UINT32_MAX+1{checkpoint<aL/2index=a-LaL/2checkpoint<a+L/2index=aa+L/2checkpoint<a+3L/2index=a + La+3L/2checkpointindex=a+2*L\begin{array}{l} 令a = m*L+seqno-isn \\\\ L = UINT32\_MAX+1 \\\\ \left \{\begin{matrix} checkpoint < a - L/2 & \text{index=a-L}\\\\ a-L/2\leq checkpoint< a+L/2 & \text{index=a}\\\\ a+L/2\leq checkpoint< a+(3*L)/2 & \text{index=a + L}\\\\ a+(3*L)/2\leq checkpoint & \text{index=a+2*L} \end{matrix}\right. \end{array}

特殊情况
checkpoint < L

checkpoint < L的时候,通解中对于a - L的一部分(即checkpoint < a + L)就不适用了,不过分析起来也很简单,由于有

(index+isn)modL=seqno\left ( index+isn \right )\mod{ L } = seqno

所以当seqno小于isn的时候,答案一定在下一个区间,因此答案即L - isn + seqno,当seqno大于isncheckpoint < a + L,所以答案一定为a

所以就可以得到上述代码了。

TCP 段接收处理

这部分代码逻辑完成的是tcp握手中对于tcp段的接受处理。

我自己增加的私有成员和用途大致为:

  • _is_syn: 判断链接是否建立
  • _isn: 存入第一次建立连接时接受的seqno来初始化
  • _is_fin: 用于判断结束输入的报文是否传入

对于acknocheckpoint的实现机制是:

  • ackno: 本质上就是返回已经整合好的数据量,也就是bytes_streambytes_written(),同时建立连接后一定存在syn所以可以直接加一,之后只需要判断fin是否到达并且整合完毕,然后再次加一即可。
  • checkpoint: 和ackno差别不大,只需要直接返回已经写入完成的字符个数即可

知道了上述几个逻辑以后就只需要通过调整简单的逻辑flag加上lab1里面的push_substring来对payload()进行整合就可以通过了。

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
void TCPReceiver::segment_received(const TCPSegment &seg) {
// 等待并处理第一个syn链接
if (not _is_syn && seg.header().syn) {
_is_syn = true;
_isn = seg.header().seqno;
_reassembler.push_substring(seg.payload().copy(), 0, seg.header().fin);
} else if (not _is_syn) {
return;
}

// checkpoint的位置就是已经写入完成的字符的数量
// In your TCP implementation, you’ll use the index of the last reassembled byte as the checkpoint.
uint64_t checkpoint = _reassembler.stream_out().bytes_written();

// 将内容写入reassembler,判断!=0的原因是为了忽略那些小于等于seq的错误TCP段
uint64_t stream_index = unwrap(seg.header().seqno, _isn, checkpoint);
if (stream_index != 0) {
_reassembler.push_substring(seg.payload().copy(), stream_index - 1, seg.header().fin);
}

// 标志结尾的TCP段是否送达
if (seg.header().fin) {
_is_fin = true;
}
}

optional<WrappingInt32> TCPReceiver::ackno() const {
WrappingInt32 result = _isn + _is_syn + _reassembler.stream_out().bytes_written();
if (_is_fin && _reassembler.unassembled_bytes() == 0) {
result = result + _is_fin;
}
return _is_syn ? optional<WrappingInt32>(result) : nullopt;
}

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

这里有一个让我感觉很疑惑的点就是在单元测试中存在两种测试样例,这里做个记录,后面如果知道了原因就来解决一下

  • 存在同时携带SYNFIN报文,按照正常的TCP握手感觉这是不合理的
  • 在接受SYN的同时会接受一部分的Data进行处理,按正常的TCP也是不会这么做的

计算机网络CS144-Lab2
https://halc.top/p/4e68707
作者
HalcyonAzure
发布于
2022年11月22日
许可协议