Lab2 TCPReceiver

前置学习

Overview

承上启下

在前两个实验中，我们可以说只是做了点算法上的抽象工作，跟TCP协议还是没什么显著的关系的。但来到了本次实验，一切就都不一样了。

依然还是这张图。相信此时做过前两个实验之后，看到这张图就会有了不一样的发现。

我们对TCP协议的实现是由内向外的，先实现里面再实现最外层。前两节实验，我们由内而外实现了ByteStream和StreamReassembler；在这次实验中，我们会实现更外层一点的TCPReceiver。

根据我们前两次实验内容，我们可以知道，TCPReceiver的功能之一就是，将数据包TCPSegment拆分成一个个data，并且通过seq生成出这些data的index，然后传递给StreamReassembler。

由外而内

TCPConnection

在说明TCPReceiver的其他功能前，不妨先从外面的TCPConnection说起，由外而内回忆一下整个TCP协议过程。

这期间最关键需要理解的，是SYN FIN ACK ack seq这些东西究竟是什么东西。

对象说明

seq

seq用来标识字节流中某个字节的序号，在TCP报文中，它表示的是该报文携带的数据的第一个字节的序号。

与我们在Lab1实现的StreamReassembler的参数index相比，它有三方面不同：

seq为32位，index为64位

当一个字节流的数据超过2^32字节（实际上比这少就会环绕）时，seq就会产生环绕。如，当前seq为0xFFFFFFFF，则下一个seq就是0x00000000。
seq不从0开始，index从0开始

为了确保传输过程中的安全性，一个字节流的起始seq不为0，而是一个随机数，称其为ISN。
seq有不携带数据的两个逻辑报文SYN和FIN，index没有

SYN

SYN是TCP“三握手”中服务器端接收到的来自客户端的第一个报文。它是TCP报文中的一个标识位：

它用以标识数据传输的开始，并且携带seq最初随机的序号ISN。

除了确保收到所有字节的数据外，TCP必须确保也能收到流的开始和结束

这个说得非常好，完美解释了为什么需要占据一个seqno

ACK

ACK也是一个标识位，它代表当前报文是一个确认收到的报文ACK，也即报文中的ackno值有效。

ack

ack表示当前endpoint【包括客户端和服务器端】希望接收到的下一个数据流的起始字节的seq。

关于seq和ack，听起来还是有点抽象，不如以连接释放图中ack和seq的值变化为例来说明。

为什么一开始seq=u，ack=v，但下一个就是seq=v，ack=u+1？

这是因为，ack和seq的语义对于客户端和服务器端都是不变的。ack为已经收到的数据的seq+1表示第一个应该接收的值，seq为已经发送的数据的seq+1表示已经发送的值。并且还需要意识到，图中其实有两个数据流（一个是C→S，另一个是S→C），也即有两套seq和ack。

ack

服务器从客户端接收信号。ack表示服务器希望接收到的下一个序列号，也即为它从客户端收到的数据的seq+1。

对于此情况，虽然终止报文不携带数据，但其依然占据一个序列号seq。

因而服务器的ack=u+1.

seq

服务器向客户端发送数据。ack表示客户端希望接收到的下一个序号，因而服务器端就应该发送ack这个序号的数据，也即v。

FIN

FIN也是一个标识位，标识着数据传输的结束

接收报文类型

因而，从图中可以看出，TCP连接中大概会收到以下几类报文：

特殊报文
1. SYN = 1
  1. C的连接请求携带了ISN
  2. S的连接请求确认，ACK = 1，携带了S的ISN
2. ACK = 1
  
  额我觉得这是TCPSender管的。这大概是Connection知道了之后通知下TCPSender吧，应该跟我们这次实验没关系
3. FIN = 1
普通的数据

TCPReceiver的作用

我们的TCPReceiver需要负责TCP协议中部分关键对象的管理。我们需要生成ackno以及拥塞窗口大小；我们需要接收SYN和FIN等信号；我们需要对seq进行处理，将其变为StreamReassembler所想要的index。

总结TCPReceiver的作用

处理数据

把Internet过来的一个个TCP报文变成一个个小data，小data再由整流器整流为完整的data，外界再通过socket从ByteStream读取完整的data。
反馈信息

向发送方反馈自己当前的一些状态信息，如拥塞窗口的大小以及ack等。
1. ackno
  
  本质上是“index of the first unassembled byte”
2. window size
  
  本质上是“the distance between the first unassembled index and the first unacceptable index”
也即，ackno为拥塞窗口的左端点，ackno+window_size为拥塞窗口的右端点

64-bit indexes ←→ 32-bit seqnos

从Overview中可以看出来，至关重要的一点就是，将环绕的32bit的seq转化为我们在StreamReassembler中使用的index。

我们不妨再引入一个中间变量abstract seqno。则seqno、abstract seqno、stream index三者关系如下图：

显然从seqno转化为abstract seqno更加复杂。因而，我们要做的第一个实验部分就是实现这个转化。

我们需要实现类WrappingInt32。它的wrap函数将64位的abstract seqno转化为32位的seqno，它的unwrap将32位的seqno转化为64位的abstract seqno。

感想

64-bit indexes ←→ 32-bit seqnos

这个实验完美地触及到了我的雷点：对这种环绕来环绕去的东西非常头疼……因而昨天晚上做的时候晕晕乎乎的什么也思考不了，今天过来边画了下图才知道要怎么做。

wrap很简单我就不说了。对于unwrap，我的做法是，先让checkpoint和n-isn都处在同一个区间（红圈）内【也即都让它们对2^32取余】，再通过几个东西之间的关系来确定最终的res是否需要+-HEAD_ONE：

【蓝线表示n-isn，橙线表示红圈区间的中点】

具体的就不多说了。直接看下面的代码，多画画图就能明白了。

TCPReceiver

心得

我一开始头晕晕地去写，对很多地方产生了疑问，激情地写下了一些消极的话语。刚刚出去吹了会儿风回来，bug全都改对了，于是狂喜着把消极的话语全部删掉了（）

怎么说呢，我的错误发生是因为我没有意识到sponge的TCP也许算是一个“简化版”。

在学习本章内容之前，我特地先去回顾了下TCP协议的全过程，并且所有的SYN，FIN等等等概念都是按照网上的概念来的。因而我在面对自己的错误时真的是一脸懵逼……好在，吹完风之后我还是及时醒悟了。

思路还是很简单的，细节也不像Lab1那样那么多那么破防，就是一些奇奇怪怪的恶心小毛病太多了，导致我出错频频，并且都是些很sb的问题，让人直接心态爆炸。

先不吐槽了，接下来就来讲讲总体的思路，以及我产生疑惑的一些地方吧。

思路

基本流程

得益于Lab1那个复杂算法的健壮性和多功能性，我们对TCPReceiver的实现就可以变得更加简洁。我们不再需要关心报文是否能够被成功接收、报文是否重叠等等等。我们仅需对SYN和FIN这样的报文做特殊的参数处理，将seqno转化为index，然后直接传入我们的StreamReassembler中就行了。

也即，基本流程为：

如果收到SYN报文，则对一些参数进行初始化，并且标记数据传输开始信号syn为true
如果syn为true，则计算index后传入整流器
判断是否需要加上FIN报文的比特位

一些细节

SYN和FIN各占一个seqno

// SYN
    if(!syn&&header.syn){ // is the first packet
        // ...
        isn = header.seqno;
        seqno = seqno + 1; // plus one to skip the SYN byte
        // ...
    }
// FIN
	if(header.fin)      fin = true; // 这个一定要写在上面那个if的后面
	// ...
	if(_reassembler.empty() && fin){
    	ack += 1;
    }

SYN很直观，没什么好说的。

FIN比较烧。之所以不是这么写：

1
2
3

if(header.fin){
   	ack += 1;
   }

也即一发现FIN报文到了就++，是因为可能会发生这种情况：

也即FIN报文虽然到了，但是中间有一段数据还没到，ack应该等于中间那段数据的开头，你这时候想要跳过FIN而把ack+1那肯定是不对的。

也因而，我们需要记录fin是否有过，并且仅当：

1	bool StreamReassembler::empty() const { return buffer.empty()&&is_eof; }

成立时，才能表示数据传输真正结束，让ack++。

以abstract seqno的形式保存ackno

说实话我一开始ackno的数据结构是WrappingInt32。为了这么搞，我还得特地维护一个checkpoint变量用来做unwrap的参数，然后ackno也不能用_reassembler.get_left_bound()来获取，总之就搞得非常非常麻烦。这时候我不小心【是故意的还是不小心的？】看到了感恩的代码，对其用abstract seqno保存ackno这个想法大为赞叹，于是就果断地沿用了（）果然设计思想方面我还是有很大不足啊。

疑惑

关于特殊报文

我一开始被这个图以及百度得到的结果受影响：

认为SYN报文不能携带数据【同理FIN也是】，因而在最初实现的时候看到test case人都麻透了开始怀疑人生……

不过这也怪我没有意识到实验和业界可能是不一样的，但指导书也没说SYN和FIN到底会不会携带数据……emm，我感觉这一点做得不够详细，也许可以改进一下。

关于window size的定义

我现在还是搞不懂这东西究竟是什么玩意……

指导书上是这么说的：

the distance between the “first unassembled” index and the “first unacceptable” index.

This is called the “window size”.

所谓的“first unassembled”正是ackno。而，我正是理解错了所谓“first unacceptable” 的意思，才导致我想了好久好久都没想出来，最后看了答案被薄纱到现在。

看到这个“first unacceptable” ，我的第一反应就是，维护一个变量right_bound，当packet过来的时候，如果packet的index范围(seqno + data.length())比right_bound大就更新。我认为这才叫做“first unacceptable”。但其实！我会这么想是因为我英语不好……

“first unacceptable” ，unacceptable，意为无法接受的，也就是说，它跟容量有关。第一个无法接受的，就是第一个超出容量的。而结合我们上面的那张图：

可以看出，事实上window size就是黑框部分，也即紫框部分减去绿色部分，也即ByteStream的remaining_capacity()……

而我以为它是还未收到的的意思，故而才理解成了上面那样。

看来英语不好也是原罪23333

代码

64-bit indexes ←→ 32-bit seqnos

//! 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) {
    uint32_t tmp = (n & TAIL_MASK);
    return isn + tmp;
}

//! 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) {
    uint32_t tmp_n = n.raw_value() - isn.raw_value();
    uint64_t res = (checkpoint & HEAD_MASK);
    uint32_t tmp_cp = (checkpoint & TAIL_MASK);

    res |= tmp_n;
    if(tmp_cp < FLAG){
        if(tmp_n > tmp_cp + FLAG){
            if(res >= HEAD_ONE) res -= HEAD_ONE;
        }
    }else if(tmp_cp > FLAG){
        if(tmp_n < tmp_cp - FLAG)       res += HEAD_ONE;
    }
    return res;
}

TCPReceiver

头文件

class TCPReceiver {
    StreamReassembler _reassembler;

    size_t _capacity;
    uint64_t ack = 0;
    WrappingInt32 isn = WrappingInt32(0);

    bool syn = false;
    bool fin = false;
// ...

具体实现

void TCPReceiver::segment_received(const TCPSegment &seg) {
    TCPHeader header = seg.header();
    WrappingInt32 seqno = header.seqno;
    string data = seg.payload().copy();
    size_t index = 0; // the param of the reassembler
    
    // LISTENING -> SYN_SENT
    if(!syn&&header.syn){ // is the first packet
        _reassembler.set_is_eof();// reset the eof flag
        fin = false;// reset the fin flag
        isn = header.seqno;
        seqno = seqno + 1; // plus one to skip the SYN byte
        syn = true;// mark the start of the byte stream
    }
    
    // must keep after the last if branch to avoid the case "flag = SF"
    // FIN_RECEIVED
    if(header.fin)      fin = true; 
    if(syn){
        uint64_t abs_seqno = unwrap(seqno,isn,ack);
        index = abs_seqno - 1;
        if (abs_seqno != 0)// write into the assembler
        	_reassembler.push_substring(data,index,header.fin);
        ack = _reassembler.get_left_bound() + 1;
        
        if (_reassembler.stream_out().input_ended() && fin)
            ack += 1;// plus one to skip the FIN byte
    }
}
optional<WrappingInt32> TCPReceiver::ackno() const {
    if(syn)     return wrap(ack,isn);
    else        return {};// empty
}

size_t TCPReceiver::window_size() const {
        return stream_out().remaining_capacity();
}