TCP的核心算法在lwip中的实现

2019-07-14 12:55发布

      lwip是瑞士计算机科学院的一个开源的TCP/IP协议栈实现.   LwIP是Light Weight (轻型)IP协议,有无操作系统的支持都可以运行。LwIP实现的重点是在保持TCP协议主要功能的基础上减少对RAM 的占用,一般它只需要几百字节的RAM和40K左右的ROM就可以运行,这使LwIP协议栈适合在低端的嵌入式系统中使用。       本文主要讨论TCP的核心协议(滑动窗口、拥塞控制、慢启动、快速重传、快速恢复、Nagle 算法、捎带 ACK等 )在lwip中的实现。       lwip中负责TCP会话管理的核心数据结构是tcp_pcb 1、   滑动窗口 1.1 发送窗口的使用:         网络数据到达时: 更新 pcb->snd_wnd         网络数据发送时: // 发送数据大小不能超过发送窗口和拥塞窗口的最小值。 wnd =MIN pcb->snd_wnd pcb->cwnd );         if len (待发送数据包) > wnd { 暂不发送; }        1.2 接收窗口的使用:               网络数据到达时:                      pcb->rcv_wnd -= len               应用层读取数据时:                      pcb->rcv_wnd += len               rcv_wnd 被调整时:                   u32_t new_right_edge = pcb->rcv_nxt + pcb->rcv_wnd;                   if(new_right_edge>=pcb->rcv_ann_right_edge + MIN((TCP_WND/2), pcb->mss))                  {// 数据被应用层程序取走,调大接收窗口大小,接收窗口右边沿向右移动。                          pcb->rcv_ann_wnd = pcb->rcv_wnd;                  } else {// 设置接收窗口大小为 0                          if (pcb->rcv_nxt >= pcb->rcv_ann_right_edge) {                                pcb->rcv_ann_wnd = 0;                   } else {// 调小接收窗口大小,接收窗口右边沿不动。                             pcb->rcv_ann_wnd = pcb->rcv_ann_right_edge - pcb->rcv_nxt;                   }               2、   RTT 估计开启和关闭 2.1 RTT 估计的开启 RTT 估计的时机:说在内核没有进行 rtt 估计时,且不处于超时重传状态(避免重传多义性) LWIP 中的实现: wnd =MIN pcb->snd_wnd pcb->cwnd ); if((seg->tcphdr->seqno) - pcb->lastack + seg->len <= wnd)){// 要发送的数据位于发送窗口 和拥塞窗口之中         ……         if pcb->rttest == 0 {                开启 RTT 估计。 } } 2.2 RTT 估计的关闭: LWIP 的实现:        pcb->rttest 置为 0 即关闭 rtt 估计,共有三处会关闭 rtt 估计: tcp_receive ,完成了 rtt 估计的运算,正常关闭,等待下次重新计算 rto tcp_rexmit ,快速重传,关闭 rtt 估计。 tcp_rexmit_rto ,超时重传,关闭 rtt 估计。   2.3RTT 估计算法:         RTT 计算方法 :         Err = M-A      //A RTT 平均值, M 是实际测量值, Err 是误差         A A + gErr   // 用误差更新平均值         D D + h( | Err |-D)      //D 是均值偏差,用误差更新均值偏差         RTO = A + 4D       // 计算得到 RTO( 重传超时时间 )         g=0.125 ; h=0.25   LWIP 的实现: 1、  发送数据时: if((seg->tcphdr->seqno) - pcb->lastack + seg->len <= wnd)){               …… if (pcb->rttest == 0) {// 需要重新进行 rtt 估计 pcb->rttest = tcp_ticks // 记录当前时间戳(以 500ms 为单位) pcb->rtseq = ntohl(seg->tcphdr->seqno) // 记录当前数据分片的序列号                      }        } 2、  接收数据时: if (flags & TCP_ACK) {// 数据包含 ACK 数据确认        if (pcb->rttest && TCP_SEQ_LT(pcb->rtseq, ackno)) {// 正在进行 RTO 估算,        并且用于估算的数据的 ACK 回来了           m = (s16_t)(tcp_ticks - pcb->rttest);           // 均值偏差估算算法。 m = m - (pcb->sa >> 3);           pcb->sa += m;           if (m < 0) {                m = -m;           }           m = m - (pcb->sv >> 2);           pcb->sv += m;           pcb->rto = (pcb->sa >> 3) + pcb->sv;           pcb->rttest = 0;//rto 估算完成,准备下一次重新估算。     } } 3 、超时重传时: pcb->rto = ((pcb->sa >> 3) + pcb->sv) << tcp_backoff[pcb->nrtx];//TCP 指数退避重新计算重传时间   3、  超时重传、慢启动和拥塞避免 拥塞窗口 (congestion window cwnd) ,是指发送方在接收到对方的 ACK 确认前向允许网 络发送的数据量,数据发送后,拥塞窗口缩小;接收到对方的 ACK 后,拥塞窗口相 应增加,拥塞窗口越大,可发送的数据量越大。拥塞窗口初始值的 RFC2581 中被规定为不超过发送方 MSS 的两倍,而且不能超过两个 TCP 包,在 RFC3390 中更新了初始窗口大小的设置方法。 慢启动阈值 (slow start threshold, ssthresh) ,用来判断是否要使用慢启动或拥塞避免算法来 控制流量的一个参数,也是随通信过程不断变化的。 cwnd < ssthresh 时,拥塞窗口值已经比较小了,表示未经确认的数据量增大,需要启动慢启动算法;当 cwnd > ssthresh 时,可发送数据量大,需要启动拥塞避免算法。 拥塞窗口 cwnd 是根据发送的数据量自动减小的,但扩大就需要根据对方的接收情况进行扩大,慢启动和拥塞避免算法都是描述如何扩大该值的。 在启动慢启动算法时, TCP 发送方接收到对方的 ACK 后拥塞窗口最多每次增加一个发送方 MSS 字节的数值,当拥塞窗口超过 sshresh 后或观察到拥塞才停止算法。 启动拥塞避免算法时,拥塞窗口在一个连接往返时间 RTT 内增加一个最大 TCP 包长度的量,一般实现时用以下公式计算: cwnd += max(SMSS*SMSS/cwnd, 1)    LWIP 实现: 1、  数据到达时: if TCP_SEQ_BETWEEN(ackno, pcb->lastack+1, pcb->snd_nxt){// 收到了一个正常的 ACK if(pcb->unacked == NULL){// 未确认队列为空 pcb->rtime = -1;// 关闭重传定时器               }else { pcb->rtime = 0;// 重启重传定时器 pcb->nrtx = 0;// 重传次数清零 }   if (pcb->state >= ESTABLISHED) {// 会话建立的状态以后的状态, if (pcb->cwnd < pcb->ssthresh) {// 慢启动算法 if ((u16_t)(pcb->cwnd + pcb->mss) > pcb->cwnd) { pcb->cwnd += pcb->mss; } } else {// 拥塞避免算法                   u16_t new_cwnd = (pcb->cwnd + pcb->mss * pcb->mss / pcb->cwnd); if (new_cwnd > pcb->cwnd) { pcb->cwnd = new_cwnd; }                }         } } 2 、定时器的实现: LWIP 中实现了两个定时器处理函数: tcp_fasttmr ()和 tcp_slowtmr ()。 tcp_fasttmr 函数是每 250ms 调用一次; tcp_slowtmr 函数每 500ms 调用一次。超时重传功能是在 tcp_slowtmr 中实现的。   if pcb->persist_backoff <= 0 {// 坚持定时器还没有到时 if(pcb->rtime >= 0)// 重传定时器开启了             ++pcb->rtime;// 重传定时器 ++        } if (pcb->unacked != NULL && pcb->rtime >= pcb->rto){ // 重传定时器到时 if (pcb->state != SYN_SENT) {// 重新设定超时重传时间                 pcb->rto = ((pcb->sa >> 3) + pcb->sv) << tcp_backoff[pcb->nrtx];         } pcb->rtime = 0;// 重传计时器清零   eff_wnd = LWIP_MIN(pcb->cwnd, pcb->snd_wnd);                // 重新计算慢启动门限 pcb->ssthresh = eff_wnd >> 1; (pcb->ssthresh < (pcb->mss << 1)) {             pcb->ssthresh = (pcb->mss << 1); } pcb->cwnd = pcb->mss;         // 重传,把 unasked 队列整体移动到 unsent 队列前端; ++pcb->nrtx tcp_rexmit_rto(pcb); } }            4、  快速重传和快速恢复 TCP 接收方收到错序的 TCP 包时要发送复制的 ACK 包回应,提示发送方可能出现网络丢包;发送方收到连续 3 个重复的 ACK 包后启动快速重传算法,根据确认号快速重传那个可能丢失的包而不必等重传定时器超时后再重传,普通的重传是要等到重传定时器超时还没收到 ACK 才进行的。这个算法是 TCP 发送方应该 (SHOULD) 实现的,不是必须。 TCP 发送方进行了快速重传后进入快速恢复阶段,直到没再接收重复的 ACK 包。
快速重传和快速恢复具体过程为:
1.
当收到第 3 个重复的 ACK 包时, ssthreh 值按 ssthresh = max (FlightSize / 2, 2*SMSS)  重新设置; 2. 重传丢失的包后,将拥塞窗口 cwnd 设置为 sshresh+3*SMSS ,人工扩大了拥塞窗口; 3. 对于每个接收到的重复的 ACK 包, cwnd 相应增加 MSS ,扩大拥塞窗口; 4. 如果新的拥塞窗口 cwnd 值和接收方的通告窗口值允许的话,可以继续发新包; 5. 当收到下一个 ACK 确认了新数据时,将 cwnd 大小调整为 sshresh ,减少窗口;对接收方来说,接收到重发的 TCP 包后就要发此 ACK 确认当前接收的数据。   接收数据时: if (TCP_SEQ_LEQ(ackno, pcb->lastack)) {// 收到一个之前确认过的 ACK pcb->acked = 0;// 最近一次 ACK 确认的数据量为 0 if (tcplen == 0) {// 数据包长度为 0 if (pcb->snd_wl2 + pcb->snd_wnd == right_wnd_edge){// 通告接收窗口不变                if (pcb->rtime >= 0) {// 超时重传计时器正在运行                     if (pcb->lastack == ackno) {// 确认序列号和上次的相同                           found_dupack = 1;                           if (pcb->dupacks + 1 > pcb->dupacks)                                ++pcb->dupacks;                           if (pcb->dupacks > 3) {// 人工调整拥塞窗口                                if ((u16_t)(pcb->cwnd + pcb->mss) > pcb->cwnd) {                                      pcb->cwnd += pcb->mss;                                }                           } else if (pcb->dupacks == 3) {// 快速重传                                tcp_rexmit_fast(pcb);                                            /*                                          tcp_rexmit_fast 做如下工作:                                                   wnd = MIN pcb->snd_wnd pcb-> cwnd ); if (pcb->ssthresh < 2*pcb->mss) {                                                      pcb->ssthresh = 2*pcb->mss;                                                }                                                   pcb->cwnd = pcb->ssthresh + 3 * pcb->mss;                                                pcb->flags |= TF_INFR;// 表示正在进行快速重传                                            */ }                              }                       } } } if (!found_dupack) {//dupack 重传计数清零                pcb->dupacks = 0;           } } else if (TCP_SEQ_BETWEEN(ackno, pcb->lastack+1, pcb->snd_nxt)){/* 正常 ACK*/ if (pcb->flags & TF_INFR) {// 该会话正处于快速重传状态 pcb->flags &= ~TF_INFR;   // 恢复状态为正常状态 pcb->cwnd = pcb->ssthresh;       // 调整拥塞窗口 } ……        } 5、  Nagle 算法 Nagle 的文档定义了一种他称之为小封包问题的解决方法。当某个应用程序每次只产生 一字节的数据,就会导致网络由于这样的小封包而过载(该情况通 常被称为 发送端 SB 窗口并发症 ),从而产生该问题。一个源自键盘的单一字符- 1 字节的数据-可能导致一个 41 字节的封包被传送,该封包包含了 1 字节的 有用数据和 40 字节的头部数据。        Nagle 算法他的主要职责是数据的累积,实际上有两个门槛:一个就是缓 冲区中的字节数达到了一定量,另一个就是等待了一定的时间(一般的 Nagle 算法都是等待 200ms );这两个门槛的任何一个达到都必须发送数据了。 Nagle 算法兼顾了实时性和发送效率。        Nagle 算法相关的有两个 TCP 选线: TCP_NODELAY TCP_CORK        TCP_NODELAY TCP_CORK 基本上控制了包的“去 Nagle 化”。        TCP_NODELAY 禁用 Nagle 算法:有数据时立即发送。        TCP_CORK 实际上也禁用了 Nagle 算法,,这种数据传输方式有益于大量数据的通信性能,典型的应用就是文件服务器。 TCP_CORK 就相当于一个“塞子”,塞子塞上之后所有网络数据都被塞住,塞子拔掉之后,所有数据一起发送出来。          示例代码如下:        intfd, on = 1;               setsockopt (fd, SOL_TCP, TCP_CORK, &on, sizeof (on)); /* cork */        write (fd, …);        fprintf (fd, …);        sendfile (fd, …);        write (fd, …);        sendfile (fd, …);               on = 0;        setsockopt (fd, SOL_TCP, TCP_CORK, &on, sizeof (on)); /* 拔去塞子 */          LWIP 的实现, LWIP Nagle 算法的实现是比较“简陋”的,并且只支持 TCP_NODELAY 选项,并不支持 TCP_CORK 选项。        #define tcp_do_output_nagle(tpcb) ((((tpcb)->unacked == NULL) || /               ((tpcb)->flags & (TF_NODELAY | TF_INFR)) || /               (((tpcb)->unsent != NULL) && (((tpcb)->unsent->next != NULL) || /               ((tpcb)->unsent->len >= (tpcb)->mss))) /         ) ? 1 : 0)        tcp_do_output_nagle 0 时执行 Nagle 算法,其条件是: unacked 队列不能为空、用户没有设置 NoDelay 选项、会话不能处于快速重传状态、 unsent 队列为空或者只有一个消息、 unsent 队列的第一个对象的数据长度要小于 mss   6、  立即 / 延迟 / 捎带 ACK        6.1 立即 ACK        1 、状态为 SYN_SENT 时,发送立即 ACK        2 、接收到 FIN 数据包后,发送立即 ACK        3 、收到的整个数据包都在 pcb->rcv_nxt ,立即发送一个 dupack        4 、收到 tcp 长度为 0 的数据包,并且序列号落在接收窗口中,发送立即 ACK        LWIP 实现:               #define tcp_ack_now(pcb) /              do {/                   (pcb)->flags |= TF_ACK_NOW;/    // 设置为立即发送标记              } while (0)        6.2 延迟 ACK :稍等看是否有数据可以捎带        LWIP 实现:        1 、有数据到达时:        #define tcp_ack(pcb) /              do {/                   if((pcb)->flags & TF_ACK_DELAY) {/                  (pcb)->flags &= ~TF_ACK_DELAY;/                  (pcb)->flags |= TF_ACK_NOW;/            }/            else { /                  (pcb)->flags |= TF_ACK_DELAY;/            } /       } while (0) 2、  在定时器处理函数 tcp_fasttmr() (每 250ms 调用一次)中        if (pcb && (pcb->flags & TF_ACK_DELAY)) {// 发现 TF_ACK_DELAY 已经置位了           tcp_ack_now(pcb);// 发送延迟 ACK           tcp_output(pcb);           pcb->flags &= ~(TF_ACK_DELAY | TF_ACK_NOW); }        6.3 捎带 ACK        tcp_ack 被调用后, tcp_fasttmr 被触发前, tcp_output 函数被调用,那么:        if (pcb->state != SYN_SENT) {            TCPH_SET_FLAG(seg->tcphdr, TCP_ACK); // 发送捎带 ACK           pcb->flags &= ~(TF_ACK_DELAY | TF_ACK_NOW);//ACK 标记位清零。        }