前言

merge lab2的初始代码，加入了如下文件

本题分为两部分：序号的转换和TCPReceiver

第零阶段：序号的转换

分析
从绝对序号（uint64_t）转化成TCP序号（uint32_t）比较简单，记为wrap函数
- 设绝对序号为n
  - 用static_cast将n转化为uint32_t，就会自动的取模
  - 然后加上isn的就是结果，也会自动取模
从TCP序号（uint32_t）转化成绝对序号（uint64_t）需要思考
- 由于TCP序号是循环的，所以1个TCP序号存在无数个对应的绝对序号
- 因此，我们需要提供1个叫做checkpoint的绝对序号
- 这个checkpoint是最近收到的报文段所携带的TCP序号转化成的绝对序号
- 我们的转化目标，就是转化到离checkpoint最近的绝对序号
由于TCP是乱序的，所以当前需要转化的TCP序号对应的绝对序号，可能比checkpoint大，也可能比checkpoint小
- 我们选择差的绝对值最小的那种
算法
- 使用wrap函数将checkpoint转化为TCP序号，记为c
- 计算n-c，记为offset1，对应比checkpoint大的情况
- 计算c-n，记为offset2，对应比checkpoint小的情况
- 如果offset1>offset2&&checkpoint>=offset2
  - 那么结果认为是checkpoint-offset2
- 如果offset1<offset2
  - 那么结果认为是checkpoint+offset2
    代码
```cpp
include “wrapping_integers.hh”

// Dummy implementation of a 32-bit wrapping integer

// For Lab 2, please replace with a real implementation that passes the // automated checks run by make check_lab2.

template void DUMMY_CODE(Targs &&… / unused /) {}

using namespace std;

//! 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) { // 这个是参考别人的，因为不太熟悉C++的数据类型与转换 return WrappingInt32{static_cast(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) { / 原理是虽然segment不一定按序到达，但几乎不可能出现相邻到达的两个segment序号差值超过INT32_MAX的情况，除非延迟以年为单位，或者产生了比特差错（后面的LAB可能涉及）。/ // checkpoint是上一个绝对序号 // 将checkpoint转化为WrappingInt32，记为c // n的绝对序号可能比c的绝对序号大，也可能是反过来，我们取差的绝对值更小的那种情况 WrappingInt32 c = wrap(checkpoint, isn); uint32_t offset1 = n.raw_value()-c.raw_value(); // n的绝对序号更大 uint32_t offset2 = c.raw_value()-n.raw_value(); // c的绝对序号更大 if (offset1>offset2&&checkpoint>=offset2) { return checkpoint-offset2; } else { return checkpoint+offset1; } }

// uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) { // uint32_t offset = n.raw_value() - isn.raw_value(); // uint64_t t = (checkpoint & 0xFFFFFFFF00000000) + offset; // uint64_t ret = t; // if (abs(int64_t(t + (1ul << 32) - checkpoint)) < abs(int64_t(t - checkpoint))) // ret = t + (1ul << 32); // if (t >= (1ul << 32) && abs(int64_t(t - (1ul << 32) - checkpoint)) < abs(int64_t(ret - checkpoint))) // ret = t - (1ul << 32); // return ret; // }

<a name="bhQlL"></a>
## 测试结果
![image.png](https://cdn.nlark.com/yuque/0/2021/png/3018011/1614583415694-7aa6f4fa-0b0a-47fb-b4fd-6de487a8e307.png#align=left&display=inline&height=224&margin=%5Bobject%20Object%5D&name=image.png&originHeight=224&originWidth=494&size=18860&status=done&style=none&width=494)
<a name="ykyvI"></a>
# TCPReceiver：第一阶段
<a name="u0pRt"></a>
## 分析
- 首先我删除了StreamReassembler的成员变量_next_index的使用
   - 用stream_out().bytes_written()来代替
   - 详细说明见[LAB1实现](https://www.yuque.com/milesgo/mfqmay/isnzhx?view=doc_embed)的第四阶段
- 这部分逻辑比较简单，这里就不再赘述了，可以参考代码及注释，以及后面的《问题一》、《问题二》小节
   - 因为最难的部分，报文段的组装逻辑已经写在了StreamReassembler中
   - 由于状态转化很简单，所以也没有额外用枚举来表示状态
<a name="rZblS"></a>
## 代码
```cpp
#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;
    bool _syn_received;
    bool _fin_received;
    WrappingInt32 _isn;
    // uint64_t abs_seqno();
  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), 
                                         _syn_received(false), _fin_received(false), _isn(0) {}
    //! \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 reassembled
    size_t unassembled_bytes() const { return _reassembler.unassembled_bytes(); }
    //! \brief handle an inbound segment
    void 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
#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;
// uint64_t TCPReceiver::abs_seqno() {
//     return stream_out().bytes_written()+1;
// }
void TCPReceiver::segment_received(const TCPSegment &seg) {
    if (stream_out().input_ended()) {  // 如果已经组装全部字节流数据，则直接返回，后面收到的报文段都是没有用的
        return;
    }
    if (!_syn_received) {  // 如果还未收到第一个SYN
        if (seg.header().syn) {
            _isn=seg.header().seqno;  //保存isn
            _syn_received=true;
            // 包含SYN的报文，同时也可能包含FIN（文档里说的）
            if (seg.header().fin) {
                stream_out().end_input();
            }
            return;  // SYN报文段不会携带数据
        } else {  // 如果报文段不带SYN，则出现错误
            stream_out().set_error();
            return;
        }
    } else {
        if (seg.header().syn) {   // 如果报文段带SYN，则出现错误
            stream_out().set_error();
            return;
        }
    }
    // 获取数据长度
    size_t data_length = seg.length_in_sequence_space();
    if (seg.header().fin) {
        data_length--;
    }
    // 获取第一个字节的字节流序号
    size_t abs_seqno = unwrap(seg.header().seqno, _isn, stream_out().bytes_written()+1);
    // 组装数据
    if (data_length>0) {
        _reassembler.push_substring(seg.payload().copy(), abs_seqno-1, seg.header().fin);
    }
}
optional<WrappingInt32> TCPReceiver::ackno() const { 
    if (!_syn_received) {
        return std::nullopt;
    }
    size_t abs_seqno = stream_out().bytes_written()+1;
    if (stream_out().input_ended()) {
        abs_seqno++;
    }
    return wrap(abs_seqno, _isn); 
}
size_t TCPReceiver::window_size() const { return stream_out().remaining_capacity(); }

测试结果

一下子过了92%的样例，还不错

问题一

在TCPReceiver::segment_received的最后，我对data_length进行了判断，只有当其长度大于0时，才调用_reassembler.push_substring；这样会有1个问题，如果到达了一个不带数据的FIN，则我们要调用ByteStream的end_input

所以这里可以不判断data_length，即使是空串，也调用push_substring，这样就可以让_reassembler帮我们调用end_input
也可以在这里加上单独的处理，手动调用end_input

问题二

在初始化状态（LISTEN）下，收到非SYN报文如何处理？
- 我目前是set_error
- 但是测试样例说是直接丢弃，仍然保持LISTEN状态
在初始化状态（LISTEN）下，收到带数据的SYN报文如何处理？
- 我目前是直接丢弃
- 但是测试样例说是也要算作字节流的一部分
在SYN_RECVz状态下，收到SYN报文如何处理？
- 我目前是set_error
- 测试样例没有报错，那么暂且这么认为

SYN报文段、SYN&FIN报文段、FIN报文段都可能携带数据

TCPReceiver: 第二阶段

修正了第一阶段最后提到的两个问题

代码

#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;
    bool _syn_received;
    bool _fin_received;
    WrappingInt32 _isn;
  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), 
                                         _syn_received(false), _fin_received(false), _isn(0) {}
    //! \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 reassembled
    size_t unassembled_bytes() const { return _reassembler.unassembled_bytes(); }
    //! \brief handle an inbound segment
    void 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
#include "tcp_receiver.hh"
#include <iostream>
// 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 (stream_out().input_ended()) {  // 如果已经组装全部字节流数据，则直接返回，后面收到的报文段都是没有用的
        return;
    }
    if (!_syn_received) {  // 如果还未收到第一个SYN
        if (seg.header().syn) {
            _isn=seg.header().seqno;  //保存isn
            _syn_received=true;
        } else {  // 如果报文段不带SYN，则直接丢弃
            return;
        }
    } else {
        if (seg.header().syn) {   // 如果报文段带SYN，则出现错误
            stream_out().set_error();
            return;
        }
    }
    // 获取第一个字节的字节流序号
    size_t abs_seqno = unwrap(seg.header().seqno, _isn, stream_out().bytes_written()+1);
    if (seg.header().syn) {  // 根据测试样例，SYN报文段也可能携带数据
        abs_seqno = unwrap(WrappingInt32(seg.header().seqno.raw_value()+1), _isn, stream_out().bytes_written()+1);
    }
    // 组装数据
    // 这里即使数据为空，我们也要push一个空串进去，以让Assembler帮我们调用_output.end_input()
    // 当然我们在这里调用也行
    _reassembler.push_substring(seg.payload().copy(), abs_seqno-1, seg.header().fin);
}
optional<WrappingInt32> TCPReceiver::ackno() const { 
    if (!_syn_received) {  // 如果还处于LISTEN状态
        return std::nullopt;
    }
    size_t abs_seqno = stream_out().bytes_written()+1;
    if (stream_out().input_ended()) {  // 如果input_ended()返回true，则说明已经收到FIN，且全部数据提交到流已经成功
        abs_seqno++;
    }
    return wrap(abs_seqno, _isn); 
}
size_t TCPReceiver::window_size() const { return stream_out().remaining_capacity(); }

CS144——计算机网络

LAB2实现

前言

第零阶段：序号的转换

分析

代码

include “wrapping_integers.hh”

测试结果

问题一

问题二

TCPReceiver: 第二阶段

代码

测试结果