学步园

这次我们来分析tcp的拥塞控制,我们要知道协议栈都是很保守的,也就是说只要有一个段被判断丢失,它就会认为发生了拥塞.而现在还有另一种,也就是路由器来通知我们发生了拥塞,这里ip头还会有一个ECN的位(准确的说是两位),来表示已经发送拥塞,不过这里要注意首先收到ECN的是接受方,可是真正需要被通知的却是发送方,因此当接受方收到ECN之后,用下一个ack来通知发送方有拥塞发生了,然后发送方才会做出响应. 

可以看到这里会有个问题的,那就是我们如何来之到对端是否支持ECN,在内核中一般都是在握手的时候就会确定对端是否支持ECN.这里可以看到我们ip头里面必须用到2位,因为这里我们会有3个状态: 

第一个发送端不支持ECN,第二个状态发送端支持ECN,第三个状态,发生了拥塞. 

可以看到我们在握手的时候双方通过交换ECN的信息,从而能得到这条连接是否支持ECN. 

下面这段在tcp_transmit_skb中的代码片断就是如何通知对端本地支持ecn的代码。可以看到代码很简单，就是判断是否是一个syn包，如果是的话就进入ecn的握手处理。 

Java代码  

1. if (likely((tcb->flags & TCPCB_FLAG_SYN) == 0))  
2.         TCP_ECN_send(sk, skb, tcp_header_size);  

而在TCP_ECN_send中最终会通过下面这两个宏来设置是否支持ecn。可以看到都是通过设置tos。 

Java代码  

1. //支持  
2. #define INET_ECN_xmit(sk) do { inet_sk(sk)->tos |= INET_ECN_ECT_0; } while (0)  
3.   
4. //不支持  
5. #define INET_ECN_dontxmit(sk) \  
6.     do { inet_sk(sk)->tos &= ~INET_ECN_MASK; } while (0)  

内核中是使用ip头的TOS域的剩余2两位来表示ECN的.下面就是ECN的三种状态: 

Java代码  

1. enum {  
2.   
3. //发送端不支持ecn  
4.     INET_ECN_NOT_ECT = 0,  
5. //下面这个貌似没有用到，不知道有什么意义。  
6.     INET_ECN_ECT_1 = 1,  
7. //发送端支持ecn  
8.     INET_ECN_ECT_0 = 2,  
9. //发生了拥塞  
10.     INET_ECN_CE = 3,  
11.   
12. //掩码  
13.     INET_ECN_MASK = 3,  
14. };  

而这里通过ecn来设置拥塞是通过IP_ECN_set_ce方法来做的，这个设置是在ip层(是在qos的enqueue也就是出队列方法)来做的，我们先来看这个方法。这个方法就是通过ip头的tos域来判断是否为INET_ECN_CE，如果是这个则说明发生了拥塞(路由器通知我们)，此时我们需要设置这个ip头的tos域，然后发送给对端，从而通知对端。 

Java代码  

1. static inline int IP_ECN_set_ce(struct iphdr *iph)  
2. {  
3.     u32 check = (__force u32)iph->check;  
4.     u32 ecn = (iph->tos + 1) & INET_ECN_MASK;  
5.   
6.     /* 
7.      * After the last operation we have (in binary): 
8.      * INET_ECN_NOT_ECT => 01 
9.      * INET_ECN_ECT_1   => 10 
10.      * INET_ECN_ECT_0   => 11 
11.      * INET_ECN_CE      => 00 
12.      */  
13. //可以看到如果没有发生拥塞或者说不支持ecn的话直接返回。  
14.     if (!(ecn & 2))  
15.         return !ecn;  
16.   
17.     /* 
18.      * The following gives us: 
19.      * INET_ECN_ECT_1 => check += htons(0xFFFD) 
20.      * INET_ECN_ECT_0 => check += htons(0xFFFE) 
21.      */  
22. ///然后开始计算对应的域。  
23.     check += (__force u16)htons(0xFFFB) + (__force u16)htons(ecn);  
24.   
25.     iph->check = (__force __sum16)(check + (check>=0xFFFF));  
26.   
27. //设置tos为 INET_ECN_CE从而通知对端。  
28.     iph->tos |= INET_ECN_CE;  
29.     return 1;  
30. }  

然后我们来看接受端如何来处理ECN通知的拥塞，这里检测拥塞(ECN通知的)是通过TCP_ECN_check_ce这个方法来做的。 

Java代码  

1. static inline void TCP_ECN_check_ce(struct tcp_sock *tp, struct sk_buff *skb)  
2. {  
3.     if (tp->ecn_flags & TCP_ECN_OK) {  
4. //如果发生了拥塞，则设置flags。  
5.         if (INET_ECN_is_ce(TCP_SKB_CB(skb)->flags))  
6.             tp->ecn_flags |= TCP_ECN_DEMAND_CWR;  
7.         /* Funny extension: if ECT is not set on a segment, 
8.          * it is surely retransmit. It is not in ECN RFC, 
9.          * but Linux follows this rule. */  
10.         else if (INET_ECN_is_not_ect((TCP_SKB_CB(skb)->flags)))  
11.             tcp_enter_quickack_mode((struct sock *)tp);  
12.     }  
13. }  

接下来来看拥塞状态机，也就是发送的状态机，在linux内核中，发送端的状态分为下面5种，而这个状态是保存在inet_connection_sock的icsk_ca_state域中的。 

Java代码  

1. enum tcp_ca_state  
2. {  
3.     TCP_CA_Open = 0,  
4. #define TCPF_CA_Open    (1<<TCP_CA_Open)  
5.     TCP_CA_Disorder = 1,  
6. #define TCPF_CA_Disorder (1<<TCP_CA_Disorder)  
7.     TCP_CA_CWR = 2,  
8. #define TCPF_CA_CWR (1<<TCP_CA_CWR)  
9.     TCP_CA_Recovery = 3,  
10. #define TCPF_CA_Recovery (1<<TCP_CA_Recovery)  
11.     TCP_CA_Loss = 4  
12. #define TCPF_CA_Loss    (1<<TCP_CA_Loss)  
13. };  

然后就简要的描述下这4个状态。 

1 TCP_CA_Open 

这个状态是也就是初始状态，我们可以看到在tcp_create_openreq_child(这个函数的意思可以看我前面的blog)中，当我们new一个新的socket之后就会设置这个socket的状态为TCP_CA_Open。这个也可以说是fast path。 

2 TCP_CA_Disorder 

当发送者检测到重复的ack或者sack就进入这个状态。在这个状态，拥塞窗口不会被调整，但是这个状态下的话，每一次新的输入数据包都会触发一个新的端的传输。 

3 TCP_CA_CWR 

这个状态叫做 (Congestion Window Reduced),顾名思义，也就是当拥塞窗口减小的时候会进入这个状态。比如当发送者收到一个ECN，此时就需要减小窗口。这个状态能够被Recovery or Loss 所打断。当接收到一个拥塞提醒的时候，发送者是每接收到一个ack，就减小拥塞窗口一个段，直到窗口大小减半。因此可以这么说当发送者正在减小窗口并且没有任何重传段的时候，就会处于CWR状态。 

4 TCP_CA_Recovery 

当足够数量的(一般是3个)的连续的重复ack到达发送端，则发送端立即重传第一个没有被ack的数据段，然后进入这个状态。处于这个状态的时候，发送者也是和CWR状态类似，每次接收到ack后减小窗口。在这个状态，拥塞窗口不会增长，发送者要么重传标记lost的段，要么传输新的段。当发送者进入这个状态时的没有被ack的段全部ack之后就离开这个状态。 

5 TCP_CA_Loss 

当RTO超时后，发送者就进入这个状态。此时所有的没有被ack的段都标记为loss，然后降低窗口大小为1,然后进入慢开始阶段。loss状态不能被其他状态所中断。而这个状态的退出只有当进入loss时，所有的被标记为loss的段都得到ack后，才会再次返回open状态。 


然后我们再来看一下，linux中拥塞控制的用到的一些变量，这些变量前面的blog或多或少都有提过了，这次再统一描述一下。 

在linux的协议栈实现中，用于拥塞控制的变量的关系满足下面的表达式： 

Java代码  

1. left_out = sacked_out + lost_out  
2. packets_out = SND.NXT - SND.UNA  
3. in_flight = packets_out - left_out + retrans_out  

sacked_out指的是被sack的段的个数。 
lost_out指的是在网络中丢失的段的数目。这里要注意loss_out所包括的段依赖于所选择的recovery 方法的不同而不同(也就是依赖于不同的算法)。而且我们知道tcp并不能准确的得到数据包是否被丢弃，因此这个值只能是个猜测值。 

因此我们可以看到left_out表示的就是已经离开网络可是还没有被ack的数据包。 

packets_out指的是发送了还没有被确认的数据包。 

retrans_out指的是重传的段的数目。 

在linux协议栈的实现中，有两种算法来计算lost packets 

1 FACK 

这个算法是最简单的一个启发式算法，在这种算法中 

lost_out = fackets_out - sacked_out并且left_out = fackets_out. 

可以看到这里丢失的包不包括sacked的数据包。而fackets_out也就是sack和丢失的数据包的总和。 

2 NewReno 

这里还有一个classic Reno算法，是比较老的一个算法，这个算法中发送端收到一个新的ACK后旧退出TCP_CA_Recovery状态，而在NewReno中，只有当所有的数据包都被确认后才退出 
TCP_CA_Recovery状态。 

这里还有两个很重要的方法，分别是tcp_time_to_recover和tcp_xmit_retransmit_queue，这两个函数内核注释的也很详细： 

这两个方法后面会详细分析。 

然后我们主要来看tcp_fastretrans_alert这个函数，所有的拥塞处理可以说都是在这个函数中进行的。这个函数被调用的条件是： 

通过前面的blog我们知道，我们是在tcp_ack()中调用的，进入这个函数就意味着我们碰到了拥塞状态或者在拥塞状态处理tcp。在这个函数中，实现了下面的这些算法： 

1 失败重传。 
2 从不同的拥塞状态恢复。 
3 检测到一个失败的拥塞状态从而使数据包的传输的延迟。 
4 从所有的拥塞状态恢复到Open状态。 



我们来一段段的看代码： 

下面这一段主要是进行一些初始化，以及校验工作。 

这里的这些flag标记就不详细介绍了，我前面的blog都有介绍，并且内核源码注释的也比较详细。 

Java代码  

1. struct inet_connection_sock *icsk = inet_csk(sk);  
2.     struct tcp_sock *tp = tcp_sk(sk);  
3. ///FLAG_SND_UNA_ADVANCED表示Snd_una被改变，也就是当前的ack不是一个重复ack。而FLAG_NOT_DUP表示也表示不是重复ack。  
4.     int is_dupack = !(flag & (FLAG_SND_UNA_ADVANCED | FLAG_NOT_DUP));  
5. //判断是否有丢失的段。  
6.     int do_lost = is_dupack || ((flag & FLAG_DATA_SACKED) &&  
7.                     (tcp_fackets_out(tp) > tp->reordering));  
8.     int fast_rexmit = 0, mib_idx;  
9.   
10. //如果发送未确认的数据包为0，则我们必须要重置sacked_out.  
11.     if (WARN_ON(!tp->packets_out && tp->sacked_out))  
12.         tp->sacked_out = 0;  
13. //如果sacked_out为0，则fackets_out也必须设置为0.这是因为fack的计数依赖于最少一个sack的段。  
14.     if (WARN_ON(!tp->sacked_out && tp->fackets_out))  
15.         tp->fackets_out = 0;  
16.   
17.     <