CS144学习（2）TCP协议实现
Lab1-4 分别是完成⼀个流重组器，TCP接收端，TCP发送端，TCP连接四个部分，将四个部分组合在⼀起就是⼀个完整的TCP端了。之后经过包装就可以进⾏TCP的接收和发送了。 代码全部在上了。
Lab1 流重组器
这⼀个实验是要实现⼀个流重组器，传⼊数据的⽚段以及起始位置，之后对其进⾏重组，并尽快将以及重组完成的数据输出。
这⾥我使⽤的是红⿊树来实现，也就是C++的std::set来实现。将未重组完成的碎⽚保存在红⿊树中，当新碎⽚到达时就尽可能地将该碎⽚与已有的碎⽚进⾏合并，保证红⿊树中没有重叠的碎⽚。
这⼀个实验的问题就是要考虑的情况有很多，当⽤lower_bound()到插⼊位置后，要对前⾯和后⾯的碎⽚判断能否合并，合并的情况也有很多种，包括部分重叠、正好接上、完全覆盖等情况；⽽且⼀个新的碎⽚可能会⼀次覆盖掉很多碎⽚。这⼀部分代码我写的⽐较混乱，因为写完之后测试发现有情况没考虑到，然后就只能打补丁，于是就越来越混乱了。
⽽尽快输出这个条件还是很容易的，如果当前到达碎⽚能够直接输出的话，就再判断⼀下树中第⼀个碎⽚能否输出，因为前⾯保证了不会有重叠碎⽚，所以可以只对第⼀个碎⽚进⾏判断。
Lab2 TCP接收端
这个实验是基于上⼀个的流重组器来实现⼀个TCP接收端，这⼀个还是⽐较简单的。就是前⾯流重组器的⼀些BUG可能会在这个实验⾥⾯被检测到，要回去改代码。
⾸先是实现⼀个WrappingInt32，因为TCP的序号是32位的，并且是可能发⽣溢出的，⽽在流重组器⾥⾯使⽤的序列号是64位，因此需要实现函数来进⾏转换，将64位的相对序列号根据ISN转换成32位的绝对序列号。
#include "wrapping_integers.hh"
using namespace std;
WrappingInt32 wrap(uint64_t n, WrappingInt32 isn) {
uint64_t res = isn.raw_value() + n;
return WrappingInt32{static_cast<uint32_t>(res)};
}
uint64_t abs(uint64_t a, uint64_t b) {
if (a > b) {
return a - b;
} else {
return b - a;
}
}
uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
uint64_t pre = checkpoint & 0xffffffff00000000;
uint64_t num;
if (n.raw_value() >= isn.raw_value()) {
num = n.raw_value() - isn.raw_value();
} else {
num = 0x0000000100000000;扫把头
num += n.raw_value();
num -= isn.raw_value();
}
uint64_t a = pre + num;
uint64_t b = a + 0x0000000100000000;
uint64_t c = a - 0x0000000100000000;
// b a c
if (abs(a, checkpoint) < abs(b, checkpoint)) {
if (abs(a, checkpoint) < abs(c, checkpoint)) {
return a;
} else {
return c;
}
} else {
return b;
}
}
最后就是对流重组器进⾏⼀下包装，计算出ackno和window_size提供给后⾯使⽤，处理⼀下SYN和FIN标记就⾏了。
#include "tcp_receiver.hh"
using namespace std;
void TCPReceiver::segment_received(const TCPSegment &seg) {
if (!_isn.has_value()) {
if (seg.header().syn) {
_isn = seg.header().seqno + 1;
} else {
std::cerr << "Error: connection not build" << std::endl;
return;
}
}
bool eof = seg.header().fin;
std::string&& payload = std::string(seg.payload().str());
if (seg.header().seqno == _isn.value() - 1 && !seg.header().syn && _pect() < 0x0000ffff) {
// wrong packet seqno == isn
return;
}
uint64_t index = unwrap(seg.header().seqno + (seg.header().syn ? 1 : 0), _isn.value(), _pect());
_reassembler.push_substring(payload, index, eof);
}
optional<WrappingInt32> TCPReceiver::ackno() const {
if (_isn.has_value()) {
return { wrap(_pect(), _isn.value()) + (_reassembler.stream_out().input_ended() ? 1 : 0) };
} else {
return std::nullopt;
}
}
size_t TCPReceiver::window_size() const {
return _capacity - _reassembler.stream_out().buffer_size();
}
Lab3 TCP发送端
在这个实验⾥⾯就要考虑到TCP的⼀些细节了，包括SYN和FIN包的发送，ACK的处理，超时重传的实现了。 SYN包
之前我还在考虑客户端和服务端的SYN包应该是不同的，应该如何处理；⽽实际上两个包是相同的，都是携带SYN和初始序列号，不同的地⽅就是服务端的SYN要同时对客户端
的SYN的包进⾏ACK。但ACK的处理是在TCP连接部分进⾏处理的，也就是说在TCP发送端⾥，只要发出⼀个SYN包就⾏了，剩下的不需要考虑。
⽽应该在什么时候发出SYN包呢，⼀开始我是在构造函数中就构造⼀个SYN包放到发送队列⾥⾯。这个做法在这个实验的测试⾥⾯是没有问题的，但是对于下⼀个实验就有问题了。因为服务端⼀开始是处于LISTEN状态，⽽这个状态下不应该有包被发出。因此，SYN包的发送应该放在fill_window()函数中，如果没有发送过SYN包，就先将SYN包发送出去。
对于⼀个最简单的SYN包，就只需要将SYN位置1，设置初始序列号seqno就⾏了。注意SYN是要占⽤⼀个序列号的。
FIN包
当发送流被⽤户程序结束后，就可以发送FIN包来关闭⼀个⽅向的连接了。这⼀个包的发送还是⽐较简单的，只要在fill_window中判断是否结束就⾏了。FIN包是可以和数据包⼀起发送的，在发送数据时发现流结束了，就将该数据包的FIN标志置1就⾏了。FIN也是要占⽤⼀个序列号的。当收到对⽅对FIN包的ACK后，就说明顺利关闭了。 ACK的处理
ACK数据会通过ack_received函数来通知发送端，当收到⼀个ACK后，就可以将发送窗⼝向右滑动，注意判断⼀下ACK是不是之前的ACK，避免窗⼝左移。最后将所有被ACK了的包从等待确认的队列中移除就⾏了。
重传
在这个实验⾥⾯只要求实现的是超时重传机制，但我也加⼊了快速重传机制。理论上当⼀个包超时之后就要对其进⾏重传，也就是每个包都要有定时器来负责重传，⽽这样的代价是很⾼的。因此，实现中是对每个TCP连接设置⼀个定时器，当时间超过RTO后进⾏重传，定时器的规则如下：
当发送⼀个包并且定时器为关闭状态：打开定时器
当发送⼀个包并且定时器为打开状态：不做任何修改
当收到⼀个ACK并且所有包都被ACK了：关闭定时器
当收到⼀个ACK并且仍有包未被ACK：重开定时器
超时重传使⽤的是指数退避算法，当进⾏了⼀次超时重传后，下⼀次超时的时间就会翻倍，也就是1RTO，2RTO，4RTO，8RTO…
当定时器超时后，就需要对包进⾏重传，在本实验⾥⾯只要重传第⼀个包就⾏了。这种⽅法的缺点就是后⾯丢失的包也要等到第⼀个被ACK了才能重发，时间会⽐较长。另⼀种选择是重传所有包，⽽这种的缺点就是会加⼤⽹络负担。因此，为了解决这种问题，就引⼊了其他的机制。
快速重传
快速重传是指当收到三个重复ACK（不包括第⼀次ACK）的时候，就⽴即进⾏重传，这种⽅法是数据驱动⽽不是时间驱动，可以避免超时重传的速度较慢的问题。⽽这仍然存在是重传⼀个还是所有的问题。
SACK
SACK也就是选择重传机制，接收端通过SACK来确认已收到的⽚段，从⽽对重传算法进⾏优化，可以不⽤对所有包进⾏重传。
⽽SACK存在接收⽅Reneging的问题，即接收⽅有权把已经SACK的数据给丢弃。这种丢弃是不被⿎励但还是可能发⽣的。因此，发送⽅不能完全依赖SACK，还是要依赖ACK，并维护定时器，如果后续的ACK没有增长，那么还是要对已经SACK的数据进⾏重传。同时，接收端也永远不能把SACK的包标记为ACK。
#include "tcp_sender.hh"
#include "tcp_config.hh"
#include <random>
#include <cassert>
using namespace std;
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) { }
uint64_t TCPSender::bytes_in_flight() const {
return _next_seqno - _expect_ack;
}
void TCPSender::fill_window() {
if (!_syn_sent) {
TCPSegment seg;
seg.header().syn = true;
seg.header().seqno = wrap(0, _isn);
_segments_out.push(seg);
_seg_not_ack.push(seg);
_next_seqno = 1;
_retrans_timer = _tick + _initial_retransmission_timeout;
_syn_sent = true;
}
uint64_t remain = _window_size - bytes_in_flight();
bool send = false;
if (_expect_ack != 0) {
// SYN received
while (remain > 0 && _stream.buffer_size() > 0) {
// send segment
uint64_t send_bytes = min(remain, TCPConfig::MAX_PAYLOAD_SIZE);
string payload = _ad(send_bytes);
TCPSegment seg;
seg.header().seqno = wrap(_next_seqno, _isn);
莫氏变径套seg.payload() = move(payload);
_next_seqno += seg.length_in_sequence_space();
remain = _window_size - bytes_in_flight();
if (_f() && remain > 0 && !_fin_sent) {
seg.header().fin = true;
_next_seqno += 1;
_fin_sent = true;
}
_segments_out.push(seg);
_seg_not_ack.push(seg);
send = true;
}
}
if (_f() && remain > 0 && !_fin_sent) {
// send FIN
TCPSegment seg;
seg.header().fin = true;
seg.header().seqno = wrap(_next_seqno, _isn);
_segments_out.push(seg);
_seg_not_ack.push(seg);
_next_seqno += 1;
_fin_sent = true;
send = true;
}
if (send && _retrans_timer == 0) {
// open timer
_retrans_timer = _tick + _initial_retransmission_timeout;
_consecutive_retransmissions = 0;
_rto_back_off = 0;
}
}
void TCPSender::ack_received(const WrappingInt32 ackno, const uint16_t window_size) {
_window_size = window_size;
_do_back_off = 1;
if (_window_size == 0) {
_window_size = 1;
_do_back_off = 0;
}
uint64_t ack = unwrap(ackno, _isn, _expect_ack);
if (ack <= _next_seqno && ack > _expect_ack) {
if (ack == _expect_ack) {
_same_ack++;
} else {
_same_ack = 0;
}
_expect_ack = ack;
if (bytes_in_flight() == 0) {
// close timer
_retrans_timer = 0;
_consecutive_retransmissions = 0;
_rto_back_off = 0;
} else {
/
/ reopen timer
_retrans_timer = _tick + _initial_retransmission_timeout;
_consecutive_retransmissions = 0;
_rto_back_off = 0;
}
}
// remove all acked packets
while (!_seg_pty()) {
TCPSegment seg = _seg_not_ack.front();
if (seg.length_in_sequence_space() + unwrap(seg.header().seqno, _isn, _expect_ack) <= _expect_ack) {
_seg_not_ack.pop();
} else {
break;
}
}
// faster retransmit
if (_same_ack == 3 && !_seg_pty()) {
// cout << "!! FASTER RETRANSMIT" << endl;
_same_ack = 0;
TCPSegment seg = _seg_not_ack.front();
_segments_out.push(seg);
_consecutive_retransmissions += 1;
_rto_back_off += _do_back_off;
_retrans_timer += _initial_retransmission_timeout << _rto_back_off;
}
}
void TCPSender::tick(const size_t ms_since_last_tick) {
_tick += ms_since_last_tick;
if (!_seg_pty() && _tick >= _retrans_timer) {
// retransmit the first packet
// cout << "retransmit" << endl;
TCPSegment seg = _seg_not_ack.front();
_segments_out.push(seg);
_consecutive_retransmissions += 1;
_rto_back_off += _do_back_off;
废旧电路板提金技术
_retrans_timer = _tick + (_initial_retransmission_timeout << _rto_back_off);
}
}
unsigned int TCPSender::consecutive_retransmissions() const { return _consecutive_retransmissions; }
void TCPSender::send_empty_segment() {
TCPSegment seg;
seg.header().seqno = wrap(_next_seqno, _isn);
_segments_out.push(seg);
}
Lab4 TCP连接
这个实验就是将之前的发送端和接收端组合起来，成为⼀个完整的TCP peer。
主要的⼯作就是将发送的数据从发送端的队列中取出，再放到发送队列中去；发送ack包进⾏确认；对RST进⾏处理；对连接的关闭和TIME_WAIT状态进⾏处理。
js防水涂膜当调⽤connect函数时，就可以调⽤fill_window⽣成SYN包，然后发送出去。
当收到⼀个包之后，就将对于信息交给发送端和接收端进⾏处理，然后进⾏ACK，当发送队列有包时直接附带ACK就⾏了，如果没有就要⽣成⼀个空包进⾏ACK，注意当接收的包只是⼀个ACK包⽽没有任何数据的话就不要进⾏ACK。当接收端收到所有数据以及FIN包之后就会关闭接收端的输⼊流。
当连接的输⼊流关闭，就可以调⽤发送端的end_input和fill_window来⽣成FIN包并发送。
连接的关闭
TCP连接的关闭分为两种情况，主动关闭和被动关闭。
当发送流先结束时，就要进⾏主动关闭，发送FIN进⼊FIN_WAIT_1状态，收到ACK后进⼊FIN_WAIT
_2状态，当收到对⽅的FIN包并进⾏ACK之后，就进⼊TIME_WAIT状态，在TIME_WAIT状态下要等待2MSL（Linux中⼀般为60s）才能释放连接。
TIME_WAIT状态的⽬的就是保证最后⼀个ACK包被对⽅接收到，因为不会对ACK进⾏ACK，就只能使⽤这种⽅式。如果ACK没有被对⽅接收到，那么对⽅就会重发FIN包，这时候就可以再次进⾏ACK。如果直接释放⽽不进⾏TIME_WAIT的话，那么下⼀个使⽤该端⼝的连接就可能会收到上⼀个连接重传的FIN包，从⽽导致混乱。
当对⽅先关闭时就是被动关闭，当收到FIN并ACK后，就进⼊CLOSE_WAIT状态。等到发送流结束后，发送FIN进⼊LAST-ACK状态，收到对⽅ACK后就可以关闭连接了，当被动关闭时，就不需要TIME_WAIT了。
#include "tcp_connection.hh"
#include <iostream>
using namespace std;
void TCPConnection::send_all_segments() {
dvrsif (_closed) return;
while (!_sender.segments_out().empty()) {
TCPSegment& seg = _sender.segments_out().front();
if (_receiver.ackno().has_value()) {
seg.header().ack = true;
seg.header().ackno = _receiver.ackno().value();
}
size_t max_win = numeric_limits<uint16_t>().max();
seg.header().win = min(_receiver.window_size(), max_win);
_segments_out.push(seg);
_sender.segments_out().pop();
}
if (_sender.stream_in().eof() && _sender.bytes_in_flight() == 0 && _receiver.stream_out().input_ended()) {
if (_linger_after_streams_finish) {
_time_wait = true;
}
}
}
size_t TCPConnection::remaining_outbound_capacity() const {
return _sender.stream_in().remaining_capacity();
}asdl
size_t TCPConnection::bytes_in_flight() const {
return _sender.bytes_in_flight();
}
size_t TCPConnection::unassembled_bytes() const {
return _receiver.unassembled_bytes();
}
size_t TCPConnection::time_since_last_segment_received() const {
return _ticks - _last_ack_time;
}
void TCPConnection::segment_received(const TCPSegment &seg) {
if (!_syn_sent && !seg.header().syn) return;
if (seg.header().rst) {
// reset connection
_sender.stream_in().set_error();
_receiver.stream_out().set_error();
_linger_after_streams_finish = false;
}
_last_ack_time = _ticks;
_receiver.segment_received(seg);
_sender.ack_received(seg.header().ackno, seg.header().win);
_sender.fill_window();
_syn_sent = true;
if (_receiver.stream_out().input_ended() && !_sender.stream_in().eof()) {
// passive close
_linger_after_streams_finish = false;
}
if (!_receiver.ackno().has_value()) {
return; // no need for ack
}
if (_sender.segments_out().empty()) {
// generate an empty segment to ack
if (_receiver.stream_out().input_ended() && !seg.header().fin) {
// no need to ack, server closed and seg not fin
