CS144-2

CS144-2

检查
在实验2之前,要保证之前的实验1已经通过测试
cmake --build build --target check 1如果出现如下就可以继续实验了

获取实验文件
git fetch来检索实验分配的最新版本
git merge origin/check2-startercode然后同步这次的实验代码
在这一部分中,你需要实现TCPReceiver,和一个wrapping_integers这是我们整个实验中的端口的服务端和绝对/相对序列号的转换
在这实验之前,你需要了解报文中的确认号(ackno),序列号(seqno)以及连接请求(SYN)和断开请求(FIN),了解这些就足以应对这个实验。
你需要知道的是以上四个量在传递过程中的值的变化,最好是自己尝试画出来

实验开始
首先这一部分难的地方并不在于去理解发送中的状态更新,而是在于如何在适当的时刻去利用相对位置和绝对位置这两个状态,而且要实现这两个转换个,如果在实现了转换的部分,同时如果这个在收发过程想明白,那么这个实验容易通过的。

首先你需要知道,当2的32次方超过就会溢出,如果是无符号型就会回滚到0,所以我们需要利用这一点,直接强转,让绝对位置变成相对位置。我当时对于unwrap的实现思路是算出有多少个循环(也就是2^32有多少个)然后把检查点左边的和右边的最近求出来,比较一下距离谁近就可以了。

关于这一部分,我之前的思路是直接用相对位置来比较检查点的距离,然后直接加上循环几圈,但是后面出现了端点是检查点的情况,以及端点是序列号的情况,这导致后面一直出现边界问题,所以倒不如直接求出来两个绝对位置,然后求他们到检查点的距离来得要巴适。

对于这一部分如果不清楚的话我们可以做一道题

时钟问题:一台机器每个一段时间都会记录累计的工作总小时数 m,每一个人只知道最后记得的工作时间在24刻度的时钟的 n 刻度上,小明现在只知道 n 和 m 如何求出总的工作实际数 g?

(m-n)%24就是求出从 n 到 m 有多少个完整的周期,然后 24 x (m-n)%24+n 就是最后的结果

换而 lab 2言之 (m-n)>>32<<32+n

这一部分可以琢磨一下,我当时琢磨了两天(泪目),当然实现起来还是以上的扩展版本,要多注意边界问题。

其次是你需要知道的结构体,第一个是TCP应答消息,第二个是TCP的发送消息

然后需要好好思考这些结构体的成员变量如何联系到本次实验的主题,以及如何在调用函数的时候用到他们,同时需要按F12去查看对应的成员变量类型是否有成员函数,清楚了这些函数作用可以极大减少代码量,这需要你自己去发现,因为这部分文档中也并没有直接给出来,估计故意是让大家思考的。

清楚其结构才能明白如何调用函数头文件中的辅助函数。 我实现的过程也是很曲折的,一步一步整理思路,然后去调用F12去看代码实现,具体的思路过程可以看我粘贴在文末的代码注释,在此之前建议自己思考,这个思考过程才是提升自己的最好方式。 接下来我复制文档的一部分(偷个懒) 在 64 位索引和 32 位 seqno 之间转换 作为热身,我们需要实现 TCP 的索引表示方式。上周你创建了一个重组器,它重新组装子字符串,每个独立的字节有一个 64 位的流索引,流中的第一个字节的索引总是零。一个 64 位的索引足够大以至于我们可以把它当作永不溢出。 2^64 是真的大 然而,在 TCP 头中,空间是宝贵的,并且流中的每个字节的索引不是用 64 位索引表示,而是用 32 位的“序列号”,或者“seqno”表示。这添加了三个复杂点: - 1.你的实现需要计划 32 位整数的环绕。 TCP 中的流可以任意长——TCP 可以发送的 ByteStream 的长度没有限制。但是 2^32 字节只有 4 GiB,这并不大。一旦一个 32 位序列号计数到 2^32 - 1,流中的下一个字节将有序列号零。 - 2.TCP 序列号从一个随机值开始:为了避免对早先在同一端点之间的连接的旧段产生混乱,TCP 试图确保序列号不能被猜测并且不太可能重复。因此,一个流的序列号不会从零开始。流中的第一个序列号是一个被称为初始序列号(ISN)的随机 32 位数。这是表示“零点”或 SYN(流的开始)的序列号。其余的序列号在此后表现正常:数据的第一个字节将有 ISN+1(mod 2^32)的序列号,第二个字节将有 ISN+2(mod 2^32)的序列号,等等。 - 3.逻辑开始和结束每个占用一个序列号:除了确保收到所有的数据字节,TCP 还确保字节流的开始和结束可靠地被接收。因此,在 TCP 中,SYN(stream-beginning)和 FIN(stream-ending)控制标志被分配序列号。每个序列号占用一个序列号。(SYN 标志占用的序列号是 ISN。)流中的每个数据字节也占用一个序列号。记住,SYN 和 FIN 并不是流本身的一部分,它们不是“字节”——他们表示字节流本身的开始和结束。

tcp_receiver.cc

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "tcp_receiver.hh"

using namespace std;

void TCPReceiver::receive( TCPSenderMessage message, Reassembler& reassembler, Writer& inbound_stream )
{
/*
需要使用到的有inser函数

Reassembler::insert( uint64_t first_index, string data, bool is_last_substring, Writer& output )

绝对序号,data,是不是最后一个数据包,output系统
而output是一个Writer类型,需要外界提供,所以目光在inbound_stream
message.payload是数据字段
所以写出来应该是
reassembler.insert(message.seqno,message.payload,message.FIN,inbound_stream)
但是应该分别为连接请求和确认和中间段包,和挥手包四种可能
而reassembler.insert(message.seqno,message.payload,message.FIN,inbound_stream)
已经包涵了FIN包的处理,以及SYN包的空包处理,也就是说,需要关心的也就first_index这个接口
当SYN=1时是SYN包,此时没有数据,且设定了初始的绝对位置,此时应该是不需要传递到insert中的
当SYN=0时是中间段,此时的seqno就是我们的数据index
*/
//此处我不知道SYN如果多发了几次要怎么处理,然后还是不同的情况下,一般来说一个是再开一个线程
//如果此时我们的SYN包接受到,那么我们保存我们已经接受到SYN包,保存一下状态,以及初始的序列号
if(message.SYN){
//如果接收到了就保存这个状态
SYN_received=true;
//第一次开启的时候会记录一下零点的位置
zero_point=message.seqno;
FIN_received=message.FIN;
}

abs_seq=message.seqno.unwrap( zero_point, inbound_stream.bytes_pushed() );
//排除掉我们可能出现的SYN情况,FIN包他本身就可以处理
if(SYN_received){
//insert接受的是下一个abs_seq的下标,而abs_seq是依据当前流系统接收的包,拆包后的长度-1是因为只改变index后的数据,以及是否是SYN包是为了包涵当开头时,是0,没有向前的下标了
reassembler.insert( abs_seq+ message.SYN - 1,message.payload,message.FIN,inbound_stream);
if(FIN_received){
//后面可以用作半退出状态去接收数据
half_close=true;
}
}
}

TCPReceiverMessage TCPReceiver::send( const Writer& inbound_stream ) const
{
/*
这里就应该发送SYN包和ACK包,问题是要一起发送还是发送两次?
看了一下结构体确实是需要发送两次,但是他返回的就一种,那算了,就返回ACK包就行了
直接通过返回来返回给对方?
窗户应该设置多大?
那么我认为inbound_stream似乎没有什么用
然而是用来获取检查点的
*/
//由于我们一次连接只需要对SYN响应一次,所以我们响应过一次就设置为false防止误用,这条废除,因为后续连接需要保存syn
TCPReceiverMessage message_ACK;
//SYN包:
uint64_t res = inbound_stream.available_capacity();
message_ACK.window_size = res > UINT16_MAX ? UINT16_MAX : res;
if(!SYN_received){
return message_ACK;
}

//这一步网上看到的是用inbound_stream.bytes_pushed当做要装包的数据,我寻思难道不是seqno?
//这是因为seq插入后,不一定是完全的包,我们会经历合并等等操作,最后返回的应该是我们接受到的有效长度,所以用的是inbound_stream.bytes_pushed()
//+1是为了当有效长度的一个确认,然后是否是FIN包,我们也需要确认如果是最后一个包,我们分别需要对其seq确认,和FIN包确认,
//正版的是分开两次确认不知道为什么这两必须是同时合并一步确认
message_ACK.ackno=temp.wrap( inbound_stream.bytes_pushed() + 1 + inbound_stream.is_closed(), zero_point );
return message_ACK;
}



tcp_receiver.hh
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
#pragma once

#include "reassembler.hh"
#include "tcp_receiver_message.hh"
#include "tcp_sender_message.hh"

class TCPReceiver
{
public:
TCPReceiver():SYN_received(false),half_close(false),FIN_received(false),zero_point(0),temp(0),abs_seq(0){}

/*

TCPReceiver接收TCPSenderMessages,将它们的有效载荷插入到正确的流索引的Reassembler中。
*/
void receive( TCPSenderMessage message, Reassembler& reassembler, Writer& inbound_stream );

/* TCPReceiver将TCPReceiverMessages发送回TCPSender。 */
TCPReceiverMessage send( const Writer& inbound_stream ) const;
private:
//是不是正在连接中
bool SYN_received;
//是不是完成了半关闭
bool half_close;
//用来标记结束
bool FIN_received;
//为ack数做准备
//初始的绝对长度
Wrap32 zero_point;
Wrap32 temp;
uint64_t abs_seq;
};

</div>
wrapping_integers.cc
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "wrapping_integers.hh"

#include <cstdlib>

#include <algorithm>

using namespace std;

Wrap32 Wrap32::wrap( uint64_t n, Wrap32 zero_point )

{

return Wrap32 { zero_point + static_cast<uint32_t>(n) };

}

//zero_point 是uint32_t类型

uint64_t Wrap32::unwrap( Wrap32 zero_point, uint64_t checkpoint ) const

{

//求出序列号的循环中的绝对位置

uint64_t abs_seqno = static_cast<uint64_t>( this->raw_value_ - zero_point.raw_value_ );

if (abs_seqno>checkpoint)

{

return abs_seqno;

}

//这里checkpoint>>32求出的是检查点的2的32次倍数,而checkpoint-abs_seqno求出的是从序列号到checkpoint的距离的周期数,相当于把abs_seqno置原点,重新求周期,求一个,从而和检查点处于同一个周期内

//其实最重要的是吧检查点和序号的周期全部拿走,让其余检查点共处一个相对周期

uint64_t cycle=((checkpoint-abs_seqno)>>32);

uint64_t r=static_cast<uint64_t>((1ull<<32)*(cycle+1)+abs_seqno);

uint64_t l=static_cast<uint64_t>((1ull<<32)*cycle+abs_seqno);

if(checkpoint-l>r-checkpoint){

return r;

}else{

return l;

}

}

/*

但是只需要相对的位置就可以了,因为假设我们的周期只有一个,那么检查点的相对序列和当前相对序列的距离如果大于周期的一半,

说明checkpoint更加接近另一个循环的点,而我们求的是向下取整的cycle,

所以我们后续去加上cycle的时候,是在检查点左侧最近的位置,

而如果我们的序列号相对位置是大于周期一半的话,

由于题目是说要求检查点最近的点,

那么肯定就是在检查点右边最近的,

也就是我们当前的绝对序列号的下一个周期,

所以要进位

由于相对周期要判断的条件太多,还不如选择暴力的最后判断,况且性能还行,就不需要这样做了

*/

wrapping_integers.hh
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
#pragma once

#include <cstdint>

/*

Wrap32类型代表一个32位无符号整数,该整数:
从一个任意的"零点"(初始值)开始,并且
当达到2^32 - 1时,回到零。
*/


class Wrap32
{
protected:
uint32_t raw_value_ {};

public:
explicit Wrap32( uint32_t raw_value ) : raw_value_( raw_value ) {}

/* 构造一个 Wrap32,给定一个绝对序列号 n 和零点。*/
static Wrap32 wrap( uint64_t n, Wrap32 zero_point );

/*

unwrap方法返回一个绝对序列号,该序列号将包装到这个Wrap32,给定零点
以及一个"检查点":接近期望答案的另一个绝对序列号。
有许多可能的绝对序列号都包装到同一个Wrap32。
unwrap方法应该返回最接近检查点的那个。
*/

uint64_t unwrap( Wrap32 zero_point, uint64_t checkpoint ) const;

Wrap32 operator+( uint32_t n ) const { return Wrap32 { raw_value_ + n }; }
bool operator==( const Wrap32& other ) const { return raw_value_ == other.raw_value_; }
};