计算机网络-CS144-lab3

实现 TCPSender
- 发送新segment : fill_window() when 上层有数据 && receive_window有空间
  - fill_window 负责一直向后走发送新数据. 更新send_window
  - 重传的部分交由tick()来做
- 定时器超时重传 : tick()
  - 更新send_window ; 重启定时器 ; 超时重传 , RTO加倍
  - Retransmission Timer [RFC]
- 收到ACK报文 : ack_received()
  - 更新rwnd , sender自动继续发送fill_window.(因为rwnd可能变大)
我们Sender并没有实现快速重传(可以不实现，易知不影响其正确性，仍然可以可靠传输)
有趣的是我们Sender并没有实现拥塞控制，但TCP仍然可以正常运行.
- 原因如下 : 拥塞控制只是为了TCP的公平性，使得其不会无节制的占用带宽. 如我们的信道中有两条TCP连接，若都实现了拥塞控制，那么最终二者所占带宽会向y=x收敛.
- 而为了保证己方Sender可以和对端Receiver正常交互，我们只需要保证：
  - 每个字节都令对方接受到并返回ACK : 重传保证
  - 对端receiver不会由于己方发送过快而导致receiver buf缓存溢出
    - 这通过流量控制就解决了.

背景

lab0中, 我们实现了bytestream
lab1 和 lab2中, 我们实现了StreamReassembler 和 TCPReceiver : 将通过不可靠的datagrams传送来的segment 重组到 bytestream中
lab3中, 我们将实现tcp connection的另一端 : TCPSender：TCPSender 将 outbound bytestream 转化成不可靠datagrams的负载内容
lab4中，我们将组装lab0123 来实现tcp：一个包含 TCPSender 和 TCPReceiver 的 tcp connection。我们将使用lab4实现的tcp 去和互联网上真实的server进行通信

TCP Sender 概述

TCP 协议是一个在不可靠的 datagram之上传输可靠的流量控制的字节流的协议。
参与TCP连接的双方都同时扮演了sender和 receiver的角色。
本周，我们将实现 TCP Sender。TCPSender 负责读取 outbound bytestream ，并将 stream转化成将要发出的一系列 tcp segment。（在对端，TCP receiver 将这些 segment(those that arrive—they might not all make it)重组为原先的字节流，并发送ack 和 window size 给sender。）
TCP sender 和 receiver 各自负责 TCP segment的一部分.
- TCP Sender 添写 lab2 中 TCP receiver 相关的所有字段 sequence number , syn , fin , payload (其他的在wrap in ip , unwrap in ip)
- TCP Sender 只读取 receiver 填写的字段 : ackno , window size

TCPSender 责任

TCP Sender 负责
关注 receiver window , 处理传入的 ackno 和 window size
填充receiver window : 在可能的时候通过读取outbound bytestream ，创建 tcp segment(include syn , fin) 并发送。TCP Sender应当持续发送segment 直到 receiver window满了或者 bytestream 空了。（没有可发送的segment，即 no data payload(bytestream.eof()) && no flags)
outstanding segment : 关注sent but not acked 的segment，我们称之为 outstanding segment（未完成的segment，就是之前学的send window).
重传 outstanding segment 当超时（从发送之后开始计时）
我为什么要做这个？
- 基本原理是 automatic repeat request(ARQ) : (fill window)sender发送任何receiver允许发送的segment，并且持续重传segment，直到receiver ack了每个segment。
- TCP sender 将流切分成segment，并在receiver允许的范围内尽可能地发送他们。
- 由之前实现易知, tcp receiver 可以重组至少接收到一次的byte；那么Sender需要保证receiver对于每个byte都至少接收到了一次

TCPSender如何知道 segment lost

TCPSender 如何知道一个segment丢失了 ? (即发送方没有接收到接收方发送的对该segment的ack)
TCPSender 将会持续发送一堆segment,每个segment都包含了来自outbound bytestream的substring，每个segment都有一个seqno作为下标来代表其在字节流中的位置,并且用SYN flagstream的开始,FIN flag标记stream的结束。
除了发送segment，TCPSender还需要关注 outstanding segment 直到其被 ack。
TCP Sender也会周期性的调用tick方法，标记着时间的流逝。
TCP Sender负责查询所有outstanding segment 然后决定最老的outstanding segment是否已经超时（长时间没被ack,outstanding for too long）。（这句话就是说在tick的时候如果定时器超时（全局只有一个最老的outstanding segment的定时器））
- 如果是，则重传该分组
Here are outstanding for too long的含义
- These are based on a simplified version of the “real” rules for TCP: RFC 6298, recommendations 5.1 through 5.6. The version here is a bit simplified, but your TCP implementation will still be able to talk with real servers on the Internet
- 你将要实现如下逻辑，有一点详细，但我们不希望你过于教条或者面向case编程。（感觉就是这意思）。lab3将给你一些合理的测试。lab4会给全部测试
我为什么要做这个 ?
- 总体目标是让sender及时检测到segment丢失并需要重新发送。
- 超时时间很重要：你不会希望发送方在重传segment之前等待过长时间（因为这样延迟了字节流向发送方），但是你也不会想重传一个即将收到ack的segment，因为这样会浪费宝贵的网络流量。（重传出去的这个segment就相当于没用了，因为之前发送的该segment的ack马上就收到，而之后再收到的重传的segment的ack就没用了，因为segment已经被ack了，已经不在send_window中了）
1. 每隔一些微秒，TCPSender 就会调用 tick(elapsed_milliseconds)，来告知tcp sender 举例上次调用tick已经过去了多长时间(elapsed_milliseconds)。
- 使用tick来维护TCPSender处于活跃状态的总微秒数。不要调用syscall 如 time,clock function. tick 是我们操作时间流逝的唯一途径。这使得事情具有确定性和可测试性。
1. TCPSender 在构建是就会初始化 retransmission timeout (RTO) 的初始值(initial retransmission timeout)
- RTO是超时时间。RTO的值会随着超时次数变化，但是初始值不变。
1. 你将实现重传定时器retransmission timer : 一个可以计时 RTO时间时钟。当RTO过去之后，alarm goes off 报警。我们强调通过tick method来获取时间流逝的概念而非通过获取真实的时间。
1. 每次发送segment时（nonzero length in sequence space），不管是第一次发送该报文还是重传该报文，如果timer没有启动，那么启动timer，这样RTO之后，timer就会expire过期(感觉可以理解成报警）。
1. 当所有的outstanding data都被ack了，那么停止 retransmission timer
1. 调用tick , timer过期
- a. 重传outstanding segment中最早发送的segment(lowest sequence number)。
```
为实现此功能，你需要用一个数据结构来存储这些outstanding segment
```
- b. if receiver window size != 0
  - i. 关注consecutive retransmissions，当重传sth时 ++cnt。
    - 你的TCP连接将使用该信息，来决定一条连接是否已经没有希望，需要被放弃.(当重传次数cnt过多时)
  - ii. RTO *= 2 , 减缓了我们在糟糕的网络上进行重传，以免进一步把事情搞糟(拥塞控制这就是 ?)
- c. 重置timer 并启动timer，使其在RTO之后过期（注意RTO可能翻倍）
- 可以看到，在tick函数的具体实现里，基本就是完全照着这abc三步做的

1. 当发送端接收了接收方发送的确认新数据的ackno时（ackno比之前接收到的ackno都要大）（就是说ackno确认了outstanding的segment(即send window中的segment)）
- a. 重置RTO = initial(我的实现是将RTO交给timer保管)
- b. 如果TCP Sender有任何outstanding segment，那么重启timer
- c. 重置consecutive retransmissions = 0

Retransmission Timer [RFC]

RFC 中共识的 TCP retransmission timer 实现

1. Managing the RTO Timer
- An implementation MUST manage the retransmission timer(s) in such a
  way that a segment is never retransmitted too early, i.e., less than
  one RTO after the previous transmission of that segment.
- The following is the RECOMMENDED algorithm for managing the
  retransmission timer:
- (5.1) Every time a packet containing data is sent (including a
```
 retransmission), if the timer is not running, start it running
 so that it will expire after RTO seconds (for the current value
 of RTO).
```
- (5.2) When all outstanding data has been acknowledged, turn off the
```
 retransmission timer.
```
- (5.3) When an ACK is received that acknowledges new data, restart the
```
 retransmission timer so that it will expire after RTO seconds
 (for the current value of RTO).
```
- When the retransmission timer expires, do the following:
  - (5.4) Retransmit the earliest segment that has not been acknowledged
    by the TCP receiver.
  - (5.5) The host MUST set RTO <- RTO * 2 (“back off the timer”). The
    maximum value discussed in (2.5) above may be used to provide
    an upper bound to this doubling operation.
  - (5.6) Start the retransmission timer, such that it expires after RTO
    seconds (for the value of RTO after the doubling operation
    outlined in 5.5).
  - (5.7) If the timer expires awaiting the ACK of a SYN segment and the
    TCP implementation is using an RTO less than 3 seconds, the RTO
    MUST be re-initialized to 3 seconds when data transmission
    begins (i.e., after the three-way handshake completes).

State

next_seqno_abs : sender要发送的下一个字节的绝对索引，syn和fin也会占据一个字节。
bytes_in_flight : bytes sent but not acked

State
- 为了测试你的代码，test会期待你的sender经历一系列状态：从发送第一个syn报文，到发送所有数据，到发送fin报文，以及最终获得fin的ack。我们不认为你需要设计更多的变量来追踪这些状态。这些状态被简单的定义在tcp sender的接口中。但是为了让你理解test的输出，这里有一个tcpsender在stream的生命中的演化图。你不必要担心error state 或者 rst flag 直到lab4
CLOSED : waiting for stream to begin
- next_seqno_absolute() = 0
- 字节流中还没有任何字节，连最一开始的syn segment也没有发送
SYN_SENT : stream started but nothing acked
- sender发送了第一个syn报文(可能携带数据)(可能也接着发送了其他带data得segment)，但是sender还没有收到receiver对该syn报文的ack
- next_seqno_absolute() == bytes_in_flight() && next_seqno_absolute() > 0
  - next_seqno_absolute() == bytes_in_flight() : syn 和 data segment 都在 send_window中
  - next_seqno_absolute() > 0 : 至少有一个syn了
SYN_ACKED : stream outgoing
- sender已经接收到了 syn 的 ack，那么syn就不会在bytes_in_flight中占据字节了（即不会在send window中占据字节了），但是syn仍然一直占据着abs_seqno空间里的0号位置。故会next_seqno_abs > bytes_in_flight）
- next_seqno_absolute() > bytes_in_flight() && not stream_in().eof()
  - next_seqno_absolute() > bytes_in_flight() : syn 不在 send_window中 (即syn已经acked)
  - not stream.eof() : stream还没到结尾
SYN_ACKED (also) ： stream outgoing (stream has reached EOF , but FIN flag hasn’t been sent yet)
- sender的stream已经到eof了，但是sender还没有发送FIN seg
- outbound_stream.eof() && next_seqno_absolute() < outbound_stream.bytes_written() + 2;
- 那么sender应该何时发送fin seg :
  - 在sender 处于syn_acked(also)状态时，且此时接受窗口的大小还能装下当前seg(syn + data)附带上一个fin flag,那么，发送fin segment
FIN_SENT : stream finished(FIN sent) but not fully acked
- sender 已经发送了 fin segment 但是还没有接收到 fin segment的ack
- 也即 sender 已经将outbound stream的字节全部发送出去，并发送了代表关闭的fin seg ，但是sender还没有收到receiver对outbound stream中的所有字节的确认（因为fin还没被确认）
- bytes_in_flight() > 0 && outbound_stream.eof() && next_seqno_abs() == outbound_stream.bytes_written() + 2 && bytes_in_flight() > 0
  - bytes_in_flight() > 0 : 至少有一个fin segment sent but not acked
  - outbound_stream.eof() : 好理解，outbound已经走到了eof
  - next_seqno_abs() == outbound_stream.bytes_written() + 2 : 已经发送了fin
    - next_seqno_abs = fin seq + 1。
    - 好比outbound_stream发送了abcdef,那么下标为
      - //// 0 1 2 3 4 5 6 7 8///
      - //// syn a b c d e f fin ////
      - 易知 next_abs_seq = 8
      - 同时，outbound_stream.bytes_written() = 6 , 因为bytestream 并不会将 syn fin 作为占据stream_idx的字节。故+2 = next_seqno_abs

FIN_ACKED : stream finished fully acked
- outbound_stream的字节已经全部被acked
- outbound_stream.eof() && next_seq_abs = outbound_stream.bytes_written() + 2 && bytes_in_flight() == 0
  - outbound_stream.eof() : outbound_stream已经走到of
  - next_seq_abs = outbound_stream.bytes_written() + 2 : sender已经发送fin
  - bytes_in_flight() == 0 : sender没有sent but not acked 的segment（ -> fin segment已经被acked）

TCPSender 实现

We’ve discussed the basic idea of what the TCP sender does (given an outgoing ByteStream, split it up into segments, send them to the receiver, and if they don’t get acknowledged soon enough, keep resending them). And we’ve discussed when to conclude that an outstanding segment was lost and needs to be resend.

TCPsender 主要关注以下几类事件

发送新segment : fill_window() when 上层有数据 && receive_window有空间
定时器超时重传 : tick()

收到ACK报文 : ack_received()

维护receive_window
新ackno : 更新recv_window

老ackno : 我的实现是忽略·

event: data received from application above 
  create TCP segment with sequence number NextSeqNum 
  if (timer currently not running) 
    start timer pass segment to IP 
  NextSeqNum = NextSeqNum + length(data) 

event: timer timeout 
  retransmit not-yet-acknowledged segment with smallest sequence number 
  start timer 

event: ACK received, with ACK field value of y 
  if (y > SendBase) { 
    SendBase = y
    if (there are currently not-yet-acknowledged segments) 
      start timer 
  }

接口如下。这四个接口每个都可能以发送tcp segment作为结尾

重要成员

约定outstanding segment : segment sent but not acked
约定超时时间：在重传一个outstanding segment之前所等待的时间。（从该segment被发送出去之后开始计时）
约定rwnd : receive_window_size
约定 earliest outstanding segment : 最早发送的outstanding segment，即 send_window的左边界的segment的timer。
约定：携带数据的segment：即占据了sequence num的分组，即syn + payload + fin 不为空

_next_seqno{0}
- 含义：sender将要发送的下一个byte 在字节流中的 abs_seqno
- _next_seqno 是单增的，只从stream中读取新数据来发送，而不管需要超时重传的数据。
约定 : send_window(中科大郑老师这么叫的，不过书上和rfc似乎没有这种叫法hhh)
- 即将 bytes_in_flight 的 bytes 都称为落在 send_window中的bytes
- 即将 outstanding segment 都称为落在send_window中的segment
- [last_ackno , _next_seqno)
- bytes sent but not acked : sebder已经发送但还没被接收到ack确认的字节
- 随着sender接收到的ack_no的增大，send_window的左端也随之增大
- 随着sender发送新segment(_next_seqno增大)，send_window的右端也随之增大
- 实现
  - deque<TCPSegment> _send_window{}

std::queue _segments_out{};
- sender发送segment：将 segment 压入queue
size_t _receive_window_size{1}
- sender认为receive_window_size
- rwnd初始化为1（在还没有接收到接收方的任何ack报文时）
  - 原因？：我觉得为了使得sender可以发送出第一个SYN报文？不然会一直等待
  - 或许rfc中有
unsigned int _initial_retransmission_timeout
- retransmission timer for the connection
Timer _timer
- TCPSender全局只有一个定时器
- 该timer监测：earliest outstanding segment
- 该timer超时，重传earliest outstanding segment
- sender的使用者通过tick()来使用_timer
ByteStream _stream
- outgoing stream of bytes that have not yet been sent
uint64_t _consecutive_retransmissions_cnt;
- 对于同一分组的重传次数
enum State { ERROR = 0, CLOSED , SYN_SENT, SYN_ACKED_1,SYN_ACKED_2,FIN_SENT,FIN_ACKED,};
- 见State

fill_window

fill_window含义: 从outbound_stream中读取新数据（还没发送过的数据），依据receive_window大小，尽可能多的发送出去。该方法并不负责重传segment，重传segment由tick方法负责。
fill_window 到什么时候停止发送 segment ?
- 只要同时满足AB两个条件，就一直发送segment
  - (as long as there are new bytes to be read and space available in the window.)
  - A. 还有segment可以发送
    - payload!=0 (outbound_bytestream 中还有可读字节) + 需要发送 syn / fin flag
  - B. receive_window还有空间
在正确的时刻发送syn和fin flag
- 发送syn flag
  - TCP Sender 处于 CLOSED 状态 : 字节流中还没有任何字节，连最一开始的syn segment也没有发送
- 发送fin flag
  - TCP Sender 处于 SYN_ACKED_2 状态 : TCP Sender的stream已经到eof了，但是TCP Sender还没有发送FIN seg

发送segment : _segment_out.push(seg)
start timer : 如果没有开启定时器（send_window empty之后第一次发送数据），那么重新开启定时器
更新_next_seqno
- _next_seqno含义：将要发送的下一个byte 在字节流中的 abs_seqno
- _next_seqno 是单增的，只从stream中读取新数据来发送，而不管需要超时重传的数据。
- 代表sender将要发送到第几个字节了。
当sender收到receiver声明的rwnd = 0时，sender应当保持发送1byte的segment给receiver
- 代码体现：调用fill_window时，若receive_window_size = 0 , 则 fill_window() 先将其视为1。
- 为什么sender要发送1 byte的segment？
  - 其实感觉就是一个探测报文的作用，sender为了及时获知receiver的receive_window是否有了空闲空间。
    - 如果receiver没有空闲空间，那么sender发送的这个segment就被receiver丢弃，且sender也不会收到任何报文
    - 如果receiver有空闲空间，那么就会接收该探测segment到receive_window中，且发送一个携带了receive_window_size的ack segment给sender。sender得知rwnd之后，会fill_window。
  - 既然是为了起到探测报文的作用，自然发送的大小越小越好，所以其payload = 1byte。
- 如《自顶向下》中所说
  - 假设receiver 的 receive_window_size = 0, 在将rwnd告知sender后，还要假设receiver没有任何数据要发送给sender。此时，考虑发生什么情况：
  - 因为TCP中，receiver只在有数据或者有确认要发送时，才会给sender发送segment，因此在receiver将接收缓存清空的过程中以及清空后，receiver不会给sender发送任何带有rwnd新值的报文。
  - 那么 sender就永远也无法得知 receiver的 receive_window中有空闲空间了(rwnd!=0)，那么sender就被阻塞而永远也不会发送新数据。（如fill_window中，如果按照receive_window_size = 0来运行，那么不会发送数据）。
  - 为解决该问题，TCP规范中要求：当sender认为receiver的receive_window_size = 0时，sender继续发送只有1个byte数据的报文段，这些segment最终会被receiver确认（因为receiver的receve_window迟早会出现空闲空间），receiver会向sender发送对该1byte的segment的ack segment（其中会有新的receive_window_size）

fill_window核心逻辑:

1. 计算 remaining_recv_window，然后开始发送segment，直到消耗完recv_window_space
1. 创建tcp segment
- syn + payload from bytestream + fin
3.1 发送tcp segment
- _segments_out.push(seg);
3.2 存入send_window
- _send_window.push_back(seg);
1. start timer if need

update vars such as_next_seqno

//  try to send segment to fill the receive window
void TCPSender::fill_window() 
{
    //  1. 计算 remaining_recv_window
    size_t remaining_recv_window_sz = _receive_window_size == 0 ? 1 : _receive_window_size;
    if(bytes_in_flight() > remaining_recv_window_sz)
        return ;
    remaining_recv_window_sz -= bytes_in_flight();
    //  开始发送segment
    while(remaining_recv_window_sz > 0)     //  check B
    {
        //  2. build tcpsegment
        TCPSegment seg;
            seg.header().seqno = next_seqno();
            //  syn flag
            if(state() == State::CLOSED)    //  remain_recv_window_sz >= 1 （肯定的）
                seg.header().syn = true;

            //  payload
            size_t payload_sz = min({TCPConfig::MAX_PAYLOAD_SIZE,remaining_recv_window_sz - seg.header().syn,_stream.buffer_size()});
            seg.payload() = _stream.read(payload_sz);       
            
            //  fin flag
            //  疑问a
            if(state() == SYN_ACKED_2 && remaining_recv_window_sz > payload_sz + seg.header().syn)
                seg.header().fin = true;

        //  check A : 如果这个segment 既没有 flag 如 syn fin；又没有 payload 则 不必发送该seg
        if(seg.length_in_sequence_space() == 0)
            break;

        //  3.1 send seg !
        _segments_out.push(seg);
        
        //  3.2 update send_window
        _send_window.push_back(seg);

        //  4. 如果这是 send_window empty之后 第一次发送数据（装入数据到_send_window）。
        if(!_timer.active())
        {
            _timer.reset();
            _timer.start(_initial_retransmission_timeout);
        }

        //  5.  update
        //  update _next_seq
        _next_seqno += seg.length_in_sequence_space();
        //  update receive_window_size
        remaining_recv_window_sz -= seg.length_in_sequence_space();
    }
}

- remaining_recv_window_sz -= bytes_in_flight() : 
- 如sender给receiver分别发送a b c 3个segment(已知receive_window = 3).receiver接收到了a之后，给sender发送ack segment，（abs_ackno = 1 , rwnd = 2),那么ack_received会更新rwnd，并且调用fill_window。易知fill_window会依照rwnd的大小，继续从bytestream读取新数据发送,那么实际上，虽然sender收到的rwnd=2，但是sender不能直接使用，还要减去bytes_in_flight，这些byte，sent but not acked，receiver稍后就会对他们ack，存入receive_window. sender发送新segment时，这些新segment在recv_window所占的空间应当在bc之后，故应当将recv_window - bytes_in_flight。获取当sender继续发送数据时，应当认为recv_window是多大。
- if(bytes_in_flight() > remaining_recv_window_sz) return ;
- 此时receive_window没有空闲空间，无法发送，返回即可。
- 由于我们ack_received 没有实现将segment拆开了acked，也即更新了recv_window（减小），但是send_window中的字节并没有移除，故可能会出现recv_window < bytes_in_flight的情况，无法成功的remaining_recv_window_sz -= bytes_in_flight() = 0(溢出)，所以需要特判返回。
- 如果实现了则应当不需要。
- In fact , the receive_window is full now , but because of our sender implementation , we can't acked part of the segment , so we can't bascially remaining_recv_window_sz -= bytes_in_flight() to get 0 . Instead, we should return now

ack_received

void ack received( const WrappingInt32 ackno, const uint16 t window size)
- 含义:(何时调用) sender收到了包含 ackno 和 rwnd 的 segment
- 更新sender看到的receive_window_sz
- sender 查询send_window中所有segment，并移除其中被ackno确认的segment
  - 什么样的segment才是被ackno确认的segment？
    - segment.abs_seqno + seg.length <= abc_ackno
    - 我们的实现中，sender 认为 segment只能被完整的确认，而不能部分确认。也即如下，sender发送了”abc”segment，receiver分别返回了ack_for_a , ack_for_b , ack_for_c，那么对于我们实现的sender,收到的ack_for_a 和 ack_for_b 都是无用的，只有收到了ack_for_c时，sender会知道receiver确认了”abc”segment，将其从send_window中移除。
    - 以下摘自指导书
      - 我应该怎么做，如果有一个ack报文只确认了某个outstanding segment的一部分?我应该将该segment进行切割吗？将确认的字节切割出去？
      - 一个TCP Sender 可以做到这点，不过就这个类的目的而言，没有必要这么花哨。
      - 将每个segment视为一个整体都outstanding,直到她完全被一个ack确认（直到它每个字节的seqno都小于收到的ack）

TCP Sender 需要查询outstanding segment的集合，并且移除其中 seqno < ack的 segment
TCP Sender 需要再次fill window 如果receive window中有新的空间

核心逻辑：核心代码见下

0. update window_size
1. 检验ackno是否合法
2. 从send_window中移除被acked的segment
3.1 为send_window中的新的 earliest outstanding segment 计数 _consecutive_retransmissions_cnt = 0;
3.2 为send_window中的新的 earliest outstanding segment 开启 timer

4. fill_window(起到自动响应receiver，sender继续发送的作用) : 因为更新了rwnd 且 bytes_in_flight可能也减少了。

void TCPSender::ack_received(const WrappingInt32 ackno, const uint16_t window_size) 
{ 
    //  0. 
    _receive_window_size = window_size;
    uint64_t abs_ackno = unwrap(ackno,_isn,_next_seqno);
    //  ...
    //  1. some check for ackno

    //  2. remove acked seg from window
    //  remove acked seg from the send_window  
    for(deque<TCPSegment>::iterator iter = _send_window.begin();iter!=_send_window.end();)
    {
        uint64_t abs_idx = unwrap(iter->header().seqno,_isn,_next_seqno);
        uint64_t len = iter->length_in_sequence_space();
        if(abs_idx + len <=  abs_ackno)     //  如果对于abs_idx < abs_ackno , abs_idx + len > abs_ackno的情况呢 ? 该如何处理 ?
        {
            seg_acked = true;
            iter = _send_window.erase(iter);
        }
        else
        {
            ++iter;
        }
    } 
    //  ...
    //  3.1 上一个计时重传的分组被移除 故 下一个重新计数
    _consecutive_retransmissions_cnt = 0;
    //  3.2 如果send_window中还有未发送的分组 则 为send_window新的最左侧分组开启timer
    if(!_send_window.empty())
    {
        _timer.reset();
        _timer.start(_initial_retransmission_timeout);
    }
    //  否则关闭老timer
    else
    {
        _timer.reset();
    }

    //  4. 因为更新了rwnd 且 bytes_in_flight可能也减少了。 故 接着从next_seqno发送新分组  
    fill_window();
}

tick

void TCPSender::tick(const size_t milli_secs)

sender 每过milli_secs 就调用一次tick，代表时间流逝.

核心逻辑：

如果超时

a. 重传earliest outstanding segment。
b. if receive_window_size != 0 (我目前也不知道为什么必须rwnd!=0)
- 对于rwnd == 0时不double rwnd 可能是为了
- i. 关注consecutive retransmissions，当重传sth时 ++cnt。
  - 你的TCP连接将使用该信息，来决定一条连接是否已经没有希望，需要被放弃.(当重传次数cnt过多时)
- ii. RTO *= 2 , 减缓了我们在糟糕的网络上进行重传，以免进一步把事情搞糟
c. 重置timer 并启动timer，使其在RTO之后过期（注意RTO可能翻倍）

可以看到，在tick函数的具体实现里，基本就是完全照着这abc三步做的

void TCPSender::tick(const size_t ms_since_last_tick) { 
    if(!_timer.active())        
        return ;
    if(_timer.elapse(ms_since_last_tick))
    {
        TCPSegment & oldest_seg = _send_window.front();
        uint64_t timeout = _timer.initial_alarm();
        //  b. 
        if(_receive_window_size > 0)
        {
            timeout <<= 1;
            ++_consecutive_retransmissions_cnt;         
        }
        //  c. 
        _timer.reset();
        _timer.start(timeout);
        //  a. 超时重传
        _segments_out.push(oldest_seg);
    }
}

超时重传相关FAQ
- 如果我发送了三个独立的segment，其payload分别为”a”, “b”, “c”,并且他们还都没被acked，那么稍后当我重传a的时候，我需要将abc三个segment拼接成一个大的segment吗？还是说我需要分别的独立的传输每个segment？
  - TCP Sender可以做到这点，但是就这个类的目的而言，没有必要这么花哨
  - 只需要独立的关注每个segment即可，并且当timer到期的时候，重传最早的outstanding segment。
- 我需要在数据结构中存储empty segment，然后在必要的时候重传他们吗？
  - 不需要。只有携带了数据(consume some length in sequence space)的segment需要被关注是否重传的
  - 一个没有占据seqno的segment(no payload, SYN, or FIN),不需要被记录或者重传。

流量控制 flow-control

一言以蔽之：receiver 通过将 recv_window （ackno + recv_window_size)发送给 sender , 来告知sender自己可接收的字节下标范围,sender通过receive_window,来获知自己还能发送多少字节.

背景: 当TCP连接的 receiver 接收到正确的、按序的字节后，就将数据放入接收缓存（receiver 的 bytestream）。相关联的应用进程会从该缓存中读取数据，但不必是数据刚一到达就立即读取。事实上，接收方应用也许正忙于其他服务，甚至要过很长时间之后才读取该数据。如果某应用程序读取数据时相对缓慢。而sender发送的太快太多，发送的数据会从接受缓存溢出。

我所实现的receiver接收缓存溢出 情况.

约定接收缓存 : bytestream(顺序) + recv_window(乱序)

receiver接收缓存溢出实现 : bytestream_size + recv_window_size == capacity —> 最终会变成bytestream_size == capacity,(接收缓存中只有bytestream而没有recv_window的空间了)，那么再来的data就会全部落入接收缓存之外(first_unacceptable之外),也即被discarded.

receiver_code
size_t StreamReassembler::cached_into_receiving_window(const string &data, const size_t index,bool &non)
    if (index >= first_unacceptable()) {
        non = true;
        return 0;  //  nothing
    }

flow-control 流量控制
- TCP为其应用程序提供了流量控制服务，目的：避免Receiver的接收缓存溢出
- 也即流量控制是一个速度匹配服务 , 通过遏制sender，来让sender和发送速率和receiver的接收速率相匹配
流量控制实现途径 : receive_window
- ackno + recv_window_size
- sender通过ack报文维护 (recv_window) recv_window_size
- 实现核心：sender 在整个 TCPConnection 中，始终保证send_window_size <= recv_window_size。
  - recv_window(recv_window_size + ackno) 即 receiver 可以接收的字节的范围
  - sender 所能发送的字节范围被限制在recv_window中.
- 1
  2
  3
  4
  5
  6
  7
  8
  fill_window()
  {
  while(recv_window_size > 0)
  {
  // send segment from _next_seqno
  // update recv_window_size
  }
  }
关于receive_window具体含义可见 lab2 blog

拥塞控制 Congestion Control

可以看到，TCPSender并没有实现TCP拥塞控制算法
- 根本就没维护拥塞窗口cwnd变量，只有一个接收窗口rwnd
- 那就更没有慢启动,拥塞避免,拥塞控制,快速恢复
我们只实现了一种形式受限的拥塞控制
- 对于同一报文段 , 每次Timer超时之后 , RTO翻倍

case

fin 占据 receive_window seqno空间

发送syn
发送abc

发送fin

{
    TCPConfig cfg;
    WrappingInt32 isn(rd());
    const size_t rto = uniform_int_distribution<uint16_t>{30, 10000}(rd);
    cfg.fixed_isn = isn;
    cfg.rt_timeout = rto;

    TCPSenderTestHarness test{"Don't add FIN if this would make the segment exceed the receiver's window", cfg};        
        //  sender.fill_window(); 发送syn报文 
    test.execute(ExpectSegment{}.with_no_flags().with_syn(true).with_payload_size(0).with_seqno(isn));
        //  check 刚才发送的报文 : seq(isn) + syn + payload(0)
        //  [0](isn)  1  2  3  4
        //  syn 
    test.execute(WriteBytes("abc").with_end_input(true));
        //  sender.stream_in().write(std::move(_bytes));    sender.stream_in().end_input();     sender.fill_window();     
        //  [0]  1  2  3  4
        //  syn  
        //  in stream wait for send : a b c fin   
    test.execute(AckReceived{WrappingInt32{isn + 1}}.with_win(3));
    test.execute(ExpectState{TCPSenderStateSummary::SYN_ACKED});
    test.execute(ExpectSegment{}.with_payload_size(3).with_data("abc").with_seqno(isn + 1).with_no_flags());
        // sender.ack_received(_ackno, _window_advertisement.value_or(DEFAULT_TEST_WINDOW));
        //  0   [1  2  3]  4
        //  syn  a  b  c
        //  in stream wait for send : fin   
    //  ack for a
    test.execute(AckReceived{WrappingInt32{isn + 2}}.with_win(2));
    test.execute(ExpectNoSegment{});
    //  ack for b
    test.execute(AckReceived{WrappingInt32{isn + 3}}.with_win(1));
    test.execute(ExpectNoSegment{});
    //  ack for c
    test.execute(AckReceived{WrappingInt32{isn + 4}}.with_win(1));
    test.execute(ExpectSegment{}.with_payload_size(0).with_seqno(isn + 4).with_fin(true));
        // sender.ack_received(_ackno, _window_advertisement.value_or(DEFAULT_TEST_WINDOW));
        //  0   1  2  3  [4]
        // syn  a  b  c  fin
        //  in stream wait for send
}

FAQ

FAQ and sepcial cases
- 我该如何既发送segment，又追踪该segment作为outstanding segment，以便我知道稍后将要重传该segment ？我是否需要为每个segment做一份拷贝?可那样的话不会很浪费吗？
  - 不会。虽然TCPSegment在send_window和segments_out中会有两个副本，但是由TCPSegment实现可知，其payload的实现是Buffer，Buffer中保存的是对string payload的引用。（std::shared_ptr<std::string> _storage{};）。故不必担心会真实的拷贝一份payload。代价不是太大。

receiver reassembler 看来 SYN 和 FIN就不占据 recv_window 空间
在sender看来 SYN和FIN就占据 recv_window 空间
因为reassembler使用的是stream_idx 发送时sender使用的是seqno
他们之间通过wrap进行转化见 lab2