Stanford University CS144 Lab3 The TCP Sender

清疚 2022-09-12 03:48 144阅读 0赞

### 文章目录 ###

*   *  前引
     *  Lab3 The TCP Sender
     *   *  获取实验文档+调试方法介绍
         *  1、Overview(总览)
         *  2、Getting started(开始)
         *   *  1、How does the TCPSender know if a segment was lost?(TCP发送器如何知道一个段是否丢失?)
         *  3、Implementing the TCP sender(实现TCP发件器)
         *   *  1、Theory of testing(测试理论)
             *  2、FAQs and special cases(FAQS和特殊情况)
             *  3、最终代码实现(tcp\_sender.hh tcp\_sender.cc)
             *   *  代码实现(tcp\_sender.hh)
                 *  代码实现(tcp\_sender.cc)
             *  4、编译运行 测试用例检验程序 (100% tests passed)

--------------------

## 前引 ##

--------------------

**真的很烦 很无语 最近因为一件事情**  
**现在我才感觉的到 我们学校与其他学校的差距啊 我真的没搞懂 有些课老师都允许我不上课了 我可以自己去忙自己的 结果学院这边还单独来记我的名字**

**我寻思着 上大学 学分是老师在给 课是老师在上 规则是老师在定 怎么这边还能再单独分出来管理 而且最让我无语的是 每节课上课前 学委还需要再单独点一次名字 我真的一个大大的问号 - -**

**什么事情都需要去解决 什么事情都会发生 无论什么事情出来阻拦 自己也应该向着自己想走的路继续走下去 这些就当最近发生的一些事情的总结 希望后面自己能够顺顺利利的在大学生活下去 在大厂找到工作 顺顺利利的拿到毕业证吧 就先写到这里**

--------------------

## Lab3 The TCP Sender ##

--------------------

### 获取实验文档+调试方法介绍 ###

--------------------

**还是老样子把这个给出来**

**为了方便大家 还是一样下面贴一下文档获取链接吧  
CS144实验文档获取链接**  
**[CS144 Lab Assignments][]**

**下载下面的这个即可**  
![在这里插入图片描述][15965bc3bf1e4b8e900f6bfb6fa85d16.png]

--------------------

**老样子 贴一下调试方法的博客链接**  
**[Stanford University CS144 调试方法][Stanford University CS144]**

--------------------

### 1、Overview(总览) ###

--------------------

**关于实验中的文档中的总览我就不详细说了 当你看到这段话的时候 我已经完成了这个Lab 完成了`100%`的`phase` 说实话真的这个`Lab`的点真的不知道比`Lab2`困难了多少 我整个`Lab`大概花了一天多的时间来做 其实是两天 但是呢这两天在做`Lab`的有效时间只有大概一天左右 - -**

**我现在还是很担心`Lab4` 我的`Lab2` `Lab3`是否还能够可靠 但是我觉得改了这么久 我也觉得代码还能地方还是很合理的 尽管有一些地方的变量是为了过示例而专门设置的 但是我觉得有些还是挺有道理了 就按照文档的意思走吧**

**我们`Lab3`主要就是要实现`TCPSender` 下面是示意图大家看看就好 对于实现细节 或者注意事项我在下面会写 真的太多太杂了 - - 下面慢慢讲**

--------------------

### 2、Getting started(开始) ###

--------------------

**老样子 路径`sponge` 输入命令`git merge origin/lab3-startercode` 就得到我们要的文件啦**

**然后我们可以尝试一下`make` `make check_lab3` 看一下是否获取成功 ^^ 应该这部还是没有问题的 那这部分就过啦**

--------------------

#### 1、How does the TCPSender know if a segment was lost?(TCP发送器如何知道一个段是否丢失?) ####

--------------------

**这里就到了文档来解释我们`Sender`的重传机制了 下面为了帮助到很多一点思路都没有`hxd` 我还是不厌其烦的写一下吧 这个`Lab3`真的完全实现出来真的还是相当不轻松的 - -**

**我们应该设置一个定时器类 这个实现还是比较简单的 然后我们的系统自动给了我们一个超时时间 就是初始的`RTO` 然后我们需要把我们的数据包储存起来 超时器只为第一个发出去的包开始 如果被接受了 缓存队列中还有包的话就又重新设置 继续开始计时重发**

**这里就涉及了一个机制了 如果接受窗口 即是我们的`Receiver`方发给我们的`WIN`为`0` 不是我们这边记录的发送记录窗口为`0`哈 那么每次超时就不设置双倍时间了 如果不是`WIN`为`0`的话 就每超时一次 就翻倍时间一次 下面还是贴一下 我的超时器类代码吧 给大家一点灵感和提示**

class Retransmission_timer
    { 
        private:
          unsigned int origin_time;
          unsigned int now_time;
          unsigned int left_time;
          bool running = false;
        public:
          Retransmission_timer(unsigned int time):origin_time(time),now_time(time),left_time(time){ }
          void start() {  running = true;}
          void reset() {  now_time = origin_time;left_time = origin_time;running = false;}
          void resume() {  left_time = now_time;running = false;}
          void powtime() { now_time *= 2;left_time = now_time;running = false;}
          void decline(unsigned int time) 
          { 
              if(left_time <= time) left_time = 0;
              else left_time -= time;
          }
          bool is_running() { return running;}
          bool expire() const { return left_time == 0;}
    };

--------------------

**对于`tick`的话 大家不用太担心 这个是我们的测试用例自动隔一会就调用 每次调用的参数数值就是上一次调用的`tick`的间隔 那个时间不是准确的时间 就是时间滴答数 所以我们就在`tick`中 进行我们的超时器函数设定即可**

--------------------

### 3、Implementing the TCP sender(实现TCP发件器) ###

--------------------

**下面就挨个挨个介绍一下我们要实现的函数吧**

**`TCPSender(const size_t capacity, const uint16_t retx_timeout, const std::optional<WrappingInt32> fixed_isn)`**

> 初始化了 初始的RTO 我们初始的SEND\_ISN 输入字节流的SIZE 我还顺带在里面初始化了定时器

--------------------

**`uint64_t bytes_in_flight() const`**

> 还在运送中的字节数 即还没确认的字节数

--------------------

**`void fill_window()` 主要需要实现函数**

> 实现细节的话 在下面说吧 这个函数这里我还是说一下 这个不是我们主动调用的函数 是测试用例调用的 我们的输入窗口为0的时候就不输出了 除非我们的输出窗口不为0 或者Receiver 发送给我们的WIN为0 我们可以暂时把其当作1 发送一个字节来让Receiver有机会可以空出空间来继续接受  
> 还有我们的有效载荷最大为1452字节 在其他头文件定义了的  
> 我们这里发送数据的格式 就需要按照下面的来走了

> 第一个报我们需要创建一个新的SYN报文没有数据 最后一个报文必须是FIN报文 如果还有空间的话 FIN报文是和数据一起发送出去的 如果没有空间的话就单独再发了 还有一些细节后面再说了

--------------------

**`void ack_received(const WrappingInt32 ackno, const uint16_t window_size)`**

> 累计确认已经接受好的数据包 通过这个也可以把设置的定时器关闭 或者在关闭后 继续重设置后再重启 通过这个知道 接收方的WIN 也知道了现在累积接受到哪里了

--------------------

**`void tick(const size_t ms_since_last_tick)`**

> 通过tick数 每次就通过tick减去打开的定时器里面数 如果减到0或者以下之后 我们的重传器即触发了 重传机制在上面已经说过了 这里就不详细说了

--------------------

**`unsigned int consecutive_retransmissions() const`**

> 返回重传次数

--------------------

**`void send_empty_segment()`**

> 传输空包 仅有ACK的 但不放入重传队列中 因为没有填写序列号 比较简单 就不说了

--------------------

#### 1、Theory of testing(测试理论) ####

--------------------

**下面这个图 大家做的时候可以多作参考 还是很有用的 实现前一定把功能了解清楚之前再敲代码**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

#### 2、FAQs and special cases(FAQS和特殊情况) ####

--------------------

**这部分我就说一下 FAQ + 特殊情况 +强调说明的地方的吧 还是给各位hxd排排雷**

--------------------

**`How do I “send” a segment?`**

> 我们把数据包推入 **\_segments\_out**了 就可以任认为我们的数据已经发出去了 测试用例随时都在取走

--------------------

**`Wait, how do I both “send” a segment and also keep track of that same segment as being outstanding, so I know what to retransmit later? Don’t I have to make a copy of each segment then? Is that wasteful?`**

> 这里的话 我存储重传队列就是还是用的queue来存储的 因为我们的数据用的是右值引用 所以不是真的copy了一个真的对象 仅是只读的 所以不会浪费很多空间^^

--------------------

**`What should my TCPSender assume as the receiver’s window size before I’ve gotten an ACK from the receiver?`**

> 最初始的字节设置为1字节即可

--------------------

**`What do I do if an acknowledgment only partially acknowledges some outstanding segment? Should I try to clip off the bytes that got acknowledged?`**

> 如果只确认了一个数据包的一部分 我们认为没有确认那个数据包 ^^

--------------------

**`If I send three individual segments containing “a,” “b,” and “c,” and they never get acknowledged, can I later retransmit them in one big segment that contains “abc”? Or do I have to retransmit each segment individually?`**

> 我们重传数据包 不需要累积到一起 就按照和发送出的包一模一样的传出去即可

--------------------

**`Should I store empty segments in my “outstanding” data structure and retransmit them when necessary?`**

> 对于空段 例如只发送一个ACK的端 即没有(FIN SYN)还有没有载荷的段 我们一律不计入和重发 因为没有序列号 所以在我们的传输中并不影响正常序列

--------------------

**好了 下面讲一些点需要注意的 主要是为了帮各位节省时间调试 我把我自己能够想到的写出来**

> 1、对于Receiver Send WIN = 0的处理  
> 我在这上面真的调试了很久 一直没有懂什么意思 我们如果发送窗口被我们自己发到0了 我们就不再发了 但是如果是Receiver 给我们发的报文 WIN=0 则我们需要假装我们的Receiver WIN = 1 发完也就完了 那为什么需要这个WIN = 1呢 因为如果WIN = 0我们就不再发了 那么很有可能接收方再也接受不来我们的消息了 可能因为WIN = 0 堵满的是之后的包缓存 - - 我们如果继续发包 可能就会导致缓存能够提取出来 继续接受 使WIN变大

--------------------

> 2、发送关于 SYN FIN的设定 这里我进行了二次编辑 其实这里就是三次握手的一部分了 我很早之前还以为三次握手会有三次SYN 结果刚刚又去仔细搜了一下才知道是只有两次SYN M 一次是客户端向服务器发出第一次SYN 第二次是服务器向客户端发出第二次SYN N ACK M+1 然后最后一次握手就是客户端向服务器发出ACK N+1了 此时就建立好了连接在那一次中我们也可以发出我们的数据报了

--------------------

> 3、定时器问题 这里也是一个我调试了很久的点 这里我们需要明确的就是 如果超时了 我们最后一次接收到的对方的WIN = 0 我们的RTO定时器 时间不翻倍 保持原值不变 重新发送 如果是因为我们发送出去的窗口减到0了 是不和上面的接受WIN = 0一样的 我们这个和还有WIN是一样的处理 这里的RTO不是初始RTO 初始RTO是不修改的 每超时一次我们的RTO就翻倍一次 每超时一次就翻倍一次 可能会出现情况 我们超时两次后 接收到Receiver的包WIN = 0 那么之后超时 RTO不变 不变的意思不是恢复到初始RTO 而是不翻倍 恢复到之前设定的RTO的意思

**我能想到的就是那么多 - - 下面我就直接放代码了**

--------------------

#### 3、最终代码实现(tcp\_sender.hh tcp\_sender.cc) ####

--------------------

##### 代码实现(tcp\_sender.hh) #####

--------------------

#ifndef SPONGE_LIBSPONGE_TCP_SENDER_HH
    #define SPONGE_LIBSPONGE_TCP_SENDER_HH
    
    #include "byte_stream.hh"
    #include "tcp_config.hh"
    #include "tcp_segment.hh"
    #include "wrapping_integers.hh"
    
    #include <functional>
    #include <queue>
    
    class Retransmission_timer
    { 
        private:
          unsigned int origin_time;
          unsigned int now_time;
          unsigned int left_time;
          bool running = false;
        public:
          Retransmission_timer(unsigned int time):origin_time(time),now_time(time),left_time(time){ }
          void start() {  running = true;}
          void reset() {  now_time = origin_time;left_time = origin_time;running = false;}
          void resume() {  left_time = now_time;running = false;}
          void powtime() { now_time *= 2;left_time = now_time;running = false;}
          void decline(unsigned int time) 
          { 
              if(left_time <= time) left_time = 0;
              else left_time -= time;
          }
          bool is_running() { return running;}
          bool expire() const { return left_time == 0;}
    };
    
    //! \brief The "sender" part of a TCP implementation.
    
    //! Accepts a ByteStream, divides it up into segments and sends the
    //! segments, keeps track of which segments are still in-flight,
    //! maintains the Retransmission Timer, and retransmits in-flight
    //! segments if the retransmission timer expires.
    class TCPSender { 
      private:
        WrappingInt32 _isn;
        std::queue<TCPSegment> _segments_out{ };
        std::queue<TCPSegment> _rtsms_queue{ };
        unsigned int _initial_retransmission_timeout;
        ByteStream _stream;
        Retransmission_timer timer;
        uint64_t _next_seqno{ 0};
        uint64_t _recv_seqno{ 0};
        uint64_t _bytes_in_flight = 0;
        size_t recver_window_size = 1;
        uint16_t consecutive_retransmissions_times = 0;
        size_t plus_num = 0;
        bool syn_sent = false,syn_recved = false,fin_sent = false,window_size_zero = false;
      public:
        //! Initialize a TCPSender
        TCPSender(const size_t capacity = TCPConfig::DEFAULT_CAPACITY,
                  const uint16_t retx_timeout = TCPConfig::TIMEOUT_DFLT,
                  const std::optional<WrappingInt32> fixed_isn = { });
    
        //! \name "Input" interface for the writer
        //!@{ 
        ByteStream &stream_in() {  return _stream; }
        const ByteStream &stream_in() const {  return _stream; }
        //!@}
    
        //! \name Methods that can cause the TCPSender to send a segment
        //!@{ 
    
        //! \brief A new acknowledgment was received
        void ack_received(const WrappingInt32 ackno, const uint16_t window_size);
    
        //! \brief Generate an empty-payload segment (useful for creating empty ACK segments)
        void send_empty_segment();
    
        //! \brief create and send segments to fill as much of the window as possible
        void fill_window();
    
        //! \brief Notifies the TCPSender of the passage of time
        void tick(const size_t ms_since_last_tick);
        //!@}
    
        //! \name Accessors
        //!@{ 
    
        //! \brief How many sequence numbers are occupied by segments sent but not yet acknowledged?
        //! \note count is in "sequence space," i.e. SYN and FIN each count for one byte
        //! (see TCPSegment::length_in_sequence_space())
        size_t bytes_in_flight() const;
    
        //! \brief Number of consecutive retransmissions that have occurred in a row
        unsigned int consecutive_retransmissions() const;
    
        //! \brief TCPSegments that the TCPSender has enqueued for transmission.
        //! \note These must be dequeued and sent by the TCPConnection,
        //! which will need to fill in the fields that are set by the TCPReceiver
        //! (ackno and window size) before sending.
        std::queue<TCPSegment> &segments_out() {  return _segments_out; }
        //!@}
    
        //! \name What is the next sequence number? (used for testing)
        //!@{ 
    
        //! \brief absolute seqno for the next byte to be sent
        uint64_t next_seqno_absolute() const {  return _next_seqno; }
    
        //! \brief relative seqno for the next byte to be sent
        WrappingInt32 next_seqno() const {  return wrap(_next_seqno, _isn); }
        //!@}
    };
    
    #endif // SPONGE_LIBSPONGE_TCP_SENDER_HH

--------------------

##### 代码实现(tcp\_sender.cc) #####

--------------------

#include "tcp_sender.hh"
    #include "tcp_config.hh"
    #include <random>
    
    // Dummy implementation of a TCP sender
    
    // For Lab 3, please replace with a real implementation that passes the
    // automated checks run by `make check_lab3`.
    
    template <typename... Targs>
    void DUMMY_CODE(Targs &&... /* unused */) { }
    
    using namespace std;
    
    //! \param[in] capacity the capacity of the outgoing byte stream
    //! \param[in] retx_timeout the initial amount of time to wait before retransmitting the oldest outstanding segment
    //! \param[in] fixed_isn the Initial Sequence Number to use, if set (otherwise uses a random ISN)
    TCPSender::TCPSender(const size_t capacity, const uint16_t retx_timeout, const std::optional<WrappingInt32> fixed_isn)
        : _isn(fixed_isn.value_or(WrappingInt32{ random_device()()}))
        , _initial_retransmission_timeout{ retx_timeout}
        , _stream(capacity)
        , timer(retx_timeout)
        { }
    
    uint64_t TCPSender::bytes_in_flight() const
    { 
        return _bytes_in_flight;
    }
    
    void TCPSender::fill_window()
    { 
        if(fin_sent) return;
        while(true)
        {  
            size_t ready2send_size = min(_stream.buffer_size(),min(max(recver_window_size,plus_num),TCPConfig::MAX_PAYLOAD_SIZE));
            size_t fin_sent_size = max(recver_window_size,plus_num);
            if(plus_num) plus_num = 0;
            if(!syn_sent || ready2send_size || (_stream.eof() && !fin_sent && fin_sent_size))
            { 
                TCPSegment Segment;
                if(!syn_sent)
                { 
                    Segment.header().syn = true;
                    syn_sent = true;
                    ready2send_size  = 0;
                }
                
                if(!_stream.eof())
                { 
                    string ready2sent = _stream.read(ready2send_size);
                    Segment.payload() = move(ready2sent);
                }
                
                if(_stream.eof() && !fin_sent && fin_sent_size >= Segment.payload().size() + 1)
                { 
                    Segment.header().fin = true;
                    fin_sent = true;
                }
                
                uint32_t payload_size = Segment.length_in_sequence_space();
                if(_segments_out.empty()) Segment.header().seqno = next_seqno();
                else
                { 
                    WrappingInt32 seqno(_segments_out.back().header().seqno);
                    seqno = seqno + payload_size;
                    Segment.header().seqno = seqno;
                }
                if(recver_window_size >= payload_size) recver_window_size -= payload_size;
                else	recver_window_size = 0; 
                
                _bytes_in_flight += payload_size;
                _next_seqno += payload_size;
                _segments_out.emplace(Segment);
                _rtsms_queue.emplace(Segment);
                if(_rtsms_queue.size() && !timer.is_running()) timer.start();
            }
            else break;
        }
    }
    
    //! \param ackno The remote receiver's ackno (acknowledgment number)
    //! \param window_size The remote receiver's advertised window size
    void TCPSender::ack_received(const WrappingInt32 ackno, const uint16_t window_size) 
    { 
        auto tmp_seqno = unwrap(ackno,_isn,_next_seqno);
        if(tmp_seqno < _recv_seqno) return;
        
        if(ackno == _isn + 1) syn_recved = true;    
        if(syn_recved)
        { 
    	_recv_seqno = unwrap(ackno,_isn,_next_seqno);
    	while(true)
    	{ 
    	    if(_rtsms_queue.empty() || unwrap(_rtsms_queue.front().header().seqno+_rtsms_queue.front().length_in_sequence_space()-1,_isn,_next_seqno) >= _recv_seqno)
    	        break;
    	    _bytes_in_flight -= _rtsms_queue.front().length_in_sequence_space();
    	    _rtsms_queue.pop();
    	    consecutive_retransmissions_times = 0;
    	    timer.reset();
    	    if(!_rtsms_queue.empty()) timer.start();  
    	}
    	
            if(static_cast<int>(window_size) >= _bytes_in_flight)
                recver_window_size = static_cast<int>(window_size) - _bytes_in_flight; 
            else   recver_window_size = 0;
            window_size_zero = (static_cast<int>(window_size) == 0);
            if(window_size_zero) plus_num = 1;
        }
    }
    
    //! \param[in] ms_since_last_tick the number of milliseconds since the last call to this method
    void TCPSender::tick(const size_t ms_since_last_tick)
    { 
        if(!timer.is_running()) return;
        timer.decline(ms_since_last_tick);
        if(timer.expire())
        { 
            ++consecutive_retransmissions_times;
            if(window_size_zero) timer.resume();
            else timer.powtime();
            timer.start();
            _segments_out.emplace(_rtsms_queue.front());
        }
    }
    
    unsigned int TCPSender::consecutive_retransmissions() const
    { 
        return consecutive_retransmissions_times;
    }
    
    void TCPSender::send_empty_segment()
    { 
        TCPSegment Segment;
        _next_seqno += 1;
        _segments_out.emplace(Segment);
    }

--------------------

#### 4、编译运行 测试用例检验程序 (100% tests passed) ####

--------------------

**实属不容易啊 把博客写完了待会去吃早饭了 然后回来看看`Lab4`这块硬骨头 希望后面的实验Goes Well 哈哈哈 那各位下一章再见啦**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[CS144 Lab Assignments]: https://cs144.github.io/
[15965bc3bf1e4b8e900f6bfb6fa85d16.png]: /images/20220828/f5753799eeda481fb84d3de5ba2ec52e.png
[Stanford University CS144]: https://love6.blog.csdn.net/article/details/120408368
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/230964e8de4546c5908915767282e83b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/0b6ff9072c5d4428a42cf8e14c9e5f73.png