Forward citation
I'm really bored and speechless recently because of one thing
Now I feel the gap between our school and other schools. I really don't understand that some teachers allow me to skip classes. I can do my own work. As a result, the college remembers my name alone
I thought that the University credits were given by the teacher, the rules were given by the teacher, and the teacher decided how to manage them separately. What made me speechless was that the school committee needed to call the name again before each class. I really had a big question mark --
Everything needs to be solved, and everything will happen. No matter what comes out to block you, you should also continue to go towards the road you want to go. This is the summary of some recent events. I hope you can live smoothly in college, find a job in a big factory, and get your graduation certificate. Let's write it here first
Lab3 The TCP Sender
Get experimental documents + introduction to debugging methods
Give this out as usual
For the convenience of everyone, it's still the same. Post the document below to get the link
CS144 experiment document access link
CS144 Lab Assignments
Download this one below
Post the blog link of debugging methods as usual
Stanford University CS144 debugging method
1. Overview
I won't elaborate on the overview of the documents in the experiment. When you see this, I have completed the Lab and completed 100% phase. To be honest, I really don't know how much more difficult this Lab is than Lab2. My whole Lab took more than one day to do it. In fact, it took two days. However, the effective time of doing the Lab in these two days is only about one day --
I'm still worried about the reliability of Lab4, lab2 and lab3, but I think it's reasonable to change the code for so long. Although some variables are specially set for example, I think some are quite reasonable. Let's go according to the meaning of the document
The main purpose of Lab3 is to implement TCPSender. The following is a schematic diagram. Let's have a look. For the implementation details or precautions, I will describe too many and too complicated things in the following -- let's talk about it slowly
2. Getting started
As usual, enter the command git merge origin / lab3 startercode to get the file we want
Then we can try make check_ Lab3 see if it is successful ^ ^ this part should be over if there is no problem
1,How does the TCPSender know if a segment was lost? (how does the TCP sender know if a segment is lost?)
Here's the document to explain our Sender's retransmission mechanism. Next, in order to help many people without any ideas, hxd I'd better take the trouble to write it. It's really not easy to fully implement Lab3 --
We should set up a timer class. This implementation is still relatively simple. Then our system automatically gives us a timeout, which is the initial RTO. Then we need to store our packets. The timeout starts only for the first packet sent out. If there are still packets in the cache queue, it will be reset to continue timing and retransmission
Here is a mechanism involved. If the receiving window is sent to us by our Receiver, the WIN is 0, not the sending record window recorded by us is 0, then the time-out will not be doubled every time. If the WIN is not 0, the time-out will be doubled every time. Next, I'd like to paste my timeout class code to give you some inspiration and tips
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;}
};
You don't have to worry too much about the tick. Our test case is called automatically every other minute. The parameter value of each call is the interval of the last call. That time is not the exact time or the number of time ticks, so we can set our timeout function in the tick
3. Implementing the TCP sender
Let's introduce the functions we want to implement one by one
TCPSender(const size_t capacity, const uint16_t retx_timeout, const std::optional<WrappingInt32> fixed_isn)
Initial RTO and send are initialized_ The SIZE of the ISN input byte stream. I also initialized the timer in it
uint64_t bytes_in_flight() const
The number of bytes in transit, that is, the number of bytes that have not been confirmed
void fill_window() mainly needs to implement functions
Let's talk about the implementation details below. This function is not called actively. It is called by the test case. When our input window is 0, it will not be output, unless our output window is not 0 or the WIN sent by the Receiver to us is 0. We can temporarily send a byte as 1 to give the Receiver a chance to vacate Space to continue to accept
Also, our maximum payload is 1452 bytes, which is defined in other header files
We need to follow the following format for sending data here
For the first message, we need to create a new SYN message without data. The last message must be FIN message. If there is space, FIN message is sent together with data. If there is no space, it will be sent separately. Some details will be discussed later
void ack_received(const WrappingInt32 ackno, const uint16_t window_size)
Cumulatively confirm that the data packets have been accepted. Through this, you can also turn off the set timer or continue to reset after closing and then restart. Through this, the WIN of the receiver knows where the cumulatively accepted packets are now
void tick(const size_t ms_since_last_tick)
Through the number of ticks, the number in the open timer is subtracted from the number of ticks each time. If it is reduced to 0 or below, our retransmission will trigger the retransmission mechanism. As mentioned above, we won't talk about it in detail here
unsigned int consecutive_retransmissions() const
Return retransmission times
void send_empty_segment()
Only ACK packets are transmitted, but they are not put into the retransmission queue, because it is simple to not fill in the serial number
1. Theory of testing
The following figure can be used as a reference when you do it. It is still very useful. Before implementation, you must understand the functions clearly before typing the code
2. FAQs and special cases
In this part, I'll talk about FAQ + special circumstances + emphasized places. I'd better give you hxd a list
How do I "send" a segment?
We push packets into_ segments_ When out, we can think that our data has been sent out and the test cases are taken away at any time
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?
Here, I use the queue to store the retransmission queue. Because our data is referenced by an R-value, it is not really a copy. A real object is only read-only, so it won't waste a lot of space^^
What should my TCPSender assume as the receiver's window size before I've gotten an ACK from the receiver?
The initial byte can be set to 1 byte
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 only a part of a packet is confirmed, we think that the packet is not confirmed^^
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?
As like as two peas, we can send packets back to the same package as we send out.
Should I store empty segments in my "outstanding" data structure and retransmit them when necessary?
For the empty segment, for example, the end that only sends one ACK, that is, the segment that has no load (FIN SYN), we will not count and resend it. Because there is no serial number, the normal sequence will not be affected in our transmission
Well, let's talk about some points that need attention, mainly to help you save time for debugging. I'll write what I can think of myself
1. For Receiver Send WIN = 0 processing
I've been debugging this for a long time and haven't understood what it means. If the sending window is sent to 0 by ourselves, we won't send it anymore. However, if the Receiver sends us a message WIN=0, we need to pretend that our Receiver WIN = 1 is finished. Why do we need this WIN = 1? Because if WIN=0, we won't send it again, so it's very possible The Receiver can no longer accept our message, probably because WIN=0 is full of the subsequent packet cache - if we continue to contract, it may cause the cache to be extracted and continue to accept, making the WIN larger
2. Send the SYN FIN settings. I don't know why the settings here are set like this, but Lab4 may understand it later. If we haven't contracted, we need to send a SYN packet without data to the last packet. If there is still space, bring FIN. If not, wait for a new space to Send a FIN only packet
3, Timer problem here is also a point I have debugged for a long time. Here, we need to make it clear that if the timeout expires, the WIN of the other party we received last time = 0, our RTO timer time does not double, keep the original value unchanged, and resend. If it is because the window we sent is reduced to 0, it is not the same as accepting WIN = 0 above. Our and WIN are the same The same processing. The RTO here is not the initial RTO. The initial RTO is not modified. Our RTO is doubled every time it times out. It may happen that we receive the Receiver's packet WIN = 0 after timeout twice. Then the timeout RTO remains unchanged, which means not to restore to the initial RTO, but not to restore to the previously set RTO
That's all I can think of -- now I'll put the code directly
3. Final code implementation (tcp_sender.hh tcp_sender.cc)
Code implementation (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
Code implementation (tcp_sender.hh)
#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;
if(_segments_out.empty()) Segment.header().seqno = next_seqno();
else
{
WrappingInt32 seqno(_segments_out.back().header().seqno);
seqno = seqno + 1;
Segment.header().seqno = seqno;
}
_segments_out.emplace(Segment);
}
4. Compile and run the test case verification program (100% tests passed)
It's really not easy. After writing the blog, I'll go to breakfast later, and then come back to see Lab4. I hope the later experiment Goes Well. Hahaha, see you in the next chapter
