Stanford University CS144 Lab3 The TCP Sender

---

前引

---

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

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

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

---

Lab3 The TCP Sender

---

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

---

还是老样子把这个给出来

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

下载下面的这个即可

---

老样子 贴一下调试方法的博客链接
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(测试理论)

---

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

---

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 TCPSenderTCPSender(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 receivedvoid 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 possiblevoid fill_window();//! \brief Notifies the TCPSender of the passage of timevoid 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 rowunsigned 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 sentuint64_t next_seqno_absolute() const {
     return _next_seqno; }//! \brief relative seqno for the next byte to be sentWrappingInt32 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 哈哈哈 那各位下一章再见啦