【计算机网络】CS144 Lab 2：the TCP receiver_综合

1 概述

在lab0中，我们实现了流控制的字节流(ByteStream)。
在lab1中，我们创建了一个模块，该模块接受一系列子字符串，这些子字符串都是从相同的字节流中摘录的，并将它们重新组装回原始的字节流，同时将其内存消耗限制在给定的数量(容量)。
现在，在lab2中，我们将实现处理入站字节流的TCP部分:tcprecreceiver。当你编写StreamReassembler和ByteStream时，你已经完成了其中涉及的大部分算法工作;本周主要是关于将这些类连接到TCP格式。这将涉及到TCP如何表示每个字节在流中的位置——称为“序列号”，tcprecreceiver负责告诉发送方(a)它已经成功组装了多少入站字节流(这被称为“确认”)和(b)发送方现在允许发送的字节范围(“流量控制窗口”)。
下周，在lab3中，我们将实现处理出站字节流的TCP部分:TCPSender。最后，在lab4中，我们将结合前面的工作来创建一个工作的TCP实现:一个包含TCPSender和tcprecreceiver的TCPConnection。

2 准备开始

在sponge目录下运行

git fetch
git merge origin/lab1-startercode

得到lab1的源码
在build目录下make，出错：在这里插入图片描述
参考，需要安装libpcap-dev

sudo apt-get install libpcap-dev

再make就编译成功了

3 Lab 2：TCP接收器

本周，我们将实现TCP的”receiver”部分，负责接收TCP段(实际的数据报有效负载)，重新组装字节流(包括它的结束，当它发生时)，并确定应该发回给发送者的信号，以进行确认和流控制。
确认的意思是，接收方需要的下一个字节的索引是什么，以便重新组装更多的字节流?这告诉发送方它需要发送或重发哪些字节。
流量控制意味着，接收方感兴趣和愿意接收什么范围的索引?”(通常作为剩余容量的函数)。这告诉发送者它允许发送多少

3.1 序列号

当SYN随机为2^32-2时以下三者的数值以及区别：
在这里插入图片描述

可以看到，absolute seqno和stream index之间相互转换很容易，只需要+1或者-1就好了。但是absolute seqno与 seqno之间相互转换比较麻烦，实验准备了这两者相互转换的数据类型和函数（ wrapping integers.hh），具体实现需要我们自己动手（wrapping integers.cc）

分析：
(1)从 seqno转成absolute seqno

WrappingInt32 wrap(uint64_t n, WrappingInt32 isn);

absolute seqno从ISN开始，则seqno=isn+absolute seqno
(2)从absolute seqno转成 seqno

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint);

参数：
n:seqno
isn:ISN
checkpoint:最近的absolute seqno
根据上面的seqno=isn+absolute seqno，我们可以推出absolute seqno=seqno-isn。但是absolute seqno与isn都是无符号32位，seqno是无符号64位，转换结果不唯一。比如seqno=4，isn=2，absolute seqno可能为4-2=2或者4+2³²-2=2³²+2，或者2³³+2……我们想要的是与check point最接近的转换结果，如果check point=1，那么我们想要的结果就是absolute seqno=2。
可以用上面实现的函数将checkpoint转化为WrappingInt32 checkpoint_seqno，差值seqno-checkpoint_seqno加在checkpoint上
比如上面例子里的check point=1，则checkpoint_seqno=isn+check point=2+1=3，差值=seqno-checkpoint_seqno=4-3=1，再将差值加在checkpoint上，得到absolute seqno=差值+checkpoint=1+1=2。
注意差值+checkpoint可能是负数，所以还要absolute seqno=absolute seqno>0?absolute seqno:absolute seqno+(1UL<<32)

//! 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(static_cast<uint32_t>(n) + isn.raw_value()); }//! 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) {
    // STEP ranges from -UINT32_MAX/2 to UINT32_MAX/2// in most cases, just adding STEP to CHECKPOINT will get the absolute seq// but if after adding, the absolute seq is negative, it should add another (1UL << 32)// (this means the checkpoint is near 0 so the new seq should always go bigger// eg. test/unwrap.cc line 25)int32_t steps = n - wrap(checkpoint, isn);int64_t res = checkpoint + steps;return res >= 0 ? res : res + (1UL << 32);
}

3.2 什么是可接收字节的窗口？

流量控制窗口：目前接收方可以接收的字节索引范围
窗口的左边缘称为ackno，它是TCPReceiver不知道的第一个字节的索引(因此希望找到)。
窗口的右边缘是TCPReceiver不愿意接受的第一个索引

3.3 实现TCPReceiver

在本实验的剩余部分中，您将实现tcprecreceiver。它将(1)从它的对等端接收片段，(2)使用你的StreamReassembler重新组装字节流，并计算(3)确认号(ackno)和(4)窗口大小。

3.3.1 segment_received()

这是最主要的方法!每次从对等端收到一个新的段时，tcprecreceiver::segment received()将被调用。

如果需要的话，设置初始序列号。具有SYN标志集的第一个到达的段的序列号是初始序列号。为了在32位封装的seqnos/acknos和它们的绝对等价项之间进行转换，您需要跟踪它。(注意SYN标志只是报头中的一个标志。同样的段也可以携带数据，甚至可以设置FIN标志。)
将任何数据或流结束标记推入StreamReassembler。如果
FIN标志在TCPSegment的头中设置，这意味着流以有效负载的最后一个字节结束，相当于EOF
确定段的任何部分是否落在窗口内。如果段的任何部分落在窗口内，该方法将返回true，否则返回false下面是我们的意思:一个段占用一个序列编号|的范围——这个范围从它的序列号开始，长度等于它在序列空间()中的长度。(这反映了SYN和FIN每个计数为一个序列号以及有效负载的每个字节这一事实)。段是可以接受的(并且该方法应该返回true)如果它占用的任何序列号落在接收方的窗口内。

3.3.2 ackno()

返回窗口的左边缘:接收者想要接收的第一个字节。如果尚未设置ISN，则返回一个空的可选值

3.3.3 window_size()

容量-TCPReceiver在字节流中持有的字节数
代码参考自千裡

stream_reassembler.hh

uint64_t getter_head_index() const {
     return _first_unassembled; }

tcp_receiver.hh

#ifndef SPONGE_LIBSPONGE_TCP_RECEIVER_HH
#define SPONGE_LIBSPONGE_TCP_RECEIVER_HH#include "byte_stream.hh"
#include "stream_reassembler.hh"
#include "tcp_segment.hh"
#include "wrapping_integers.hh"#include <optional>//! \brief The "receiver" part of a TCP implementation.//! Receives and reassembles segments into a ByteStream, and computes
//! the acknowledgment number and window size to advertise back to the
//! remote TCPSender.
class TCPReceiver {
    //! Our data structure for re-assembling bytes.StreamReassembler _reassembler;//! The maximum number of bytes we'll store.size_t _capacity;//0:listen 1:syn_recv 2:fin_recvuint64_t _state = 0;uint32_t _isn = 0;bool _syn = false;bool _fin = false;public://! \brief Construct a TCP receiver//!//! \param capacity the maximum number of bytes that the receiver will//! store in its buffers at any give time.TCPReceiver(const size_t capacity) : _reassembler(capacity), _capacity(capacity) {
    }//! \name Accessors to provide feedback to the remote TCPSender//!@{
    //! \brief The ackno that should be sent to the peer//! \returns empty if no SYN has been received//!//! This is the beginning of the receiver's window, or in other words, the sequence number//! of the first byte in the stream that the receiver hasn't received.std::optional<WrappingInt32> ackno() const;//! \brief The window size that should be sent to the peer//!//! Operationally: the capacity minus the number of bytes that the//! TCPReceiver is holding in its byte stream (those that have been//! reassembled, but not consumed).//!//! Formally: the difference between (a) the sequence number of//! the first byte that falls after the window (and will not be//! accepted by the receiver) and (b) the sequence number of the//! beginning of the window (the ackno).size_t window_size() const;//!@}//! \brief number of bytes stored but not yet reassembledsize_t unassembled_bytes() const {
     return _reassembler.unassembled_bytes(); }//! \brief handle an inbound segmentvoid segment_received(const TCPSegment &seg);//! \name "Output" interface for the reader//!@{
    ByteStream &stream_out() {
     return _reassembler.stream_out(); }const ByteStream &stream_out() const {
     return _reassembler.stream_out(); }//!@}
};#endif // SPONGE_LIBSPONGE_TCP_RECEIVER_HH

tcp_receiver.cc

#include "tcp_receiver.hh"// Dummy implementation of a TCP receiver// For Lab 2, please replace with a real implementation that passes the
// automated checks run by `make check_lab2`.template <typename... Targs>
void DUMMY_CODE(Targs &&... /* unused */) {
    }using namespace std;void TCPReceiver::segment_received(const TCPSegment &seg) {
    if (_state == 2) return;//payload中实际上并不包含syn和fin//size_t length_space; //seg 序列长度 //绝对序列号，同时作为下一次seg的checkpoint，用于将相对序列号转换成绝对序列号//使用abs_seq确定checkpoint实际上,窗口不能太大否则checkpoint不好确定了static size_t abs_seqno = 0;size_t length = seg.length_in_sequence_space();if (seg.header().syn == true) {
     if (_syn == true)   //重复建立链接，丢弃return;_syn = true;_isn = seg.header().seqno.raw_value();_state = 1;abs_seqno = 1;  //记录checkpoint,seg中第一个字节数据的绝对序号length--;//length_space = seg.length_in_sequence_space() - 1; //序列长度，不包括synif (seg.length_in_sequence_space() - 1 == 0) //只有synreturn;} else if (!_syn) {
     //尚未建立连接就开始传送数据，丢弃return;} else {
    //拆包成绝对地址（64位 初始位是0），同时获得该seg的indexabs_seqno = unwrap(WrappingInt32(seg.header().seqno.raw_value()), WrappingInt32(_isn), abs_seqno);//length_space = seg.length_in_sequence_space();}if (seg.header().fin) length--;// //处理超出窗口的和ackno之前的if (abs_seqno >= _reassembler.getter_head_index() + 1 + window_size())return;if (seg.header().fin) _fin = true;// if (abs_seqno + length <= _reassembler.getter_head_index() + 1)// return;//seq syn fin都已经处理。 最后处理payload//abs_seqno -> index _reassembler.push_substring(seg.payload().copy(), abs_seqno - 1, _fin);if (_reassembler.stream_out().input_ended())_state = 2;return;
}optional<WrappingInt32> TCPReceiver::ackno() const {
     if (_state == 1) {
    //把64位绝对位置+ISN打包成32位相对位置//index ->-> abs_seq ->-> seq// +1 wrapreturn wrap( _reassembler.getter_head_index() + 1, WrappingInt32(_isn));} else if (_state == 2){
    return wrap( _reassembler.getter_head_index() + 2, WrappingInt32(_isn));} else {
    return nullopt;}
}size_t TCPReceiver::window_size() const {
     //容量(buffer的最大长度) - 已经重组排好序的部分(buffer_size)，把ressemble理解成对bytetream的一层封装 return {
     _capacity - _reassembler.stream_out().buffer_size()};
}