TCP拥塞控制算法内核实现剖析（二）

so_brave

TCP拥塞控制算法内核实现剖析（二）

内核版本：2.6.37

主要源文件：linux-2.6.37/ net/ ipv4/ tcp_bic.c



======================================================================================================

1. /* BIC TCP Parameters */
   
2. 
   
3. struct bictcp {
   
4. 
   
5.         u32 cnt ; /* increase cwnd by 1 after ACKs */
   
6. 
   
7.         u32 last_max_cwnd ; /* last maximum snd_cwnd */
   
8. 
   
9.         u32 loss_cwnd ; /* congestion window at last loss */
   
10. 
    
11.         u32 last_cwnd ; /* the last snd_cwnd */
    
12. 
    
13.         u32 last_time ; /* time when updated last_cwnd */
    
14. 
    
15.         u32 epoch_start ; /* beginning of an epoch */
    
16. 
    
17. #define ACK_RATIO_SHIFT 4
    
18. 
    
19.         u32 delayed_ack ; /* estimate the ratio of Packets/ACKs << 4 */
    
20. 
    
21. } ;
    
22. 
    
23. 
    
24. 
    
25. /* Scale factor beta calculation
    
26. 
    
27. * max_cwnd = snd_cwnd * beta
    
28. 
    
29. */
    
30. 
    
31. #define BICTCP_BETA_SCALE 1024
    
32. 
    
33. 
    
34. 
    
35. /* In binary search ,
    
36. 
    
37. * go to point (max+min) / N
    
38. 
    
39. */
    
40. 
    
41. #define BICTCP_B 4   /*并不是真正的二分*/

复制代码

全局变量

1. static int fast_convergence = 1 ; /* BIC能快速的达到一个平衡值，开关*/
   
2. 
   
3. static int max_increment = 16 ; /* 每次增加的MSS 不能超过这个值，防止增长太过剧烈*/
   
4. 
   
5. static int low_window = 14 ; /* lower bound on congestion window , for TCP friendliness */
   
6. 
   
7. static int beta = 819 ; /* = 819 / 1024(BICTCP_BETA_SCALE) ，beta for multiplicative increase 。？*/
   
8. 
   
9. static int initial_ssthresh ; /* 初始的阈值 */
   
10. 
    
11. static int smooth_part = 20 ; /* log(B/(B*Smin))/log(B/(B-1))+B, # of RTT from Wmax-B to Wmax 。？*/
    
12. 
    
13. /* initial_ssthresh的初始值被设置成2^31-1=2147483647 */

复制代码

==========================================================================================================

1. struct inet_connection_sock {
   
2. 
   
3.         ...
   
4. 
   
5.         u32 icsk_ca_priv[16] ;
   
6. 
   
7. #define ICSK_CA_PRIV_SIZE (16*sizeof(u32))
   
8. 
   
9. }
   
10. 
    
11. 
    
12. 
    
13. static inline void *inet_csk_ca( const struct sock *sk )
    
14. 
    
15. {
    
16. 
    
17.         return (void *)inet_csk(sk)->icsk_ca_priv ;
    
18. 
    
19. }

复制代码

============================================================================================================

不明白？!

1. 
   
2. /* Slow start with delack produces 3 packets of burst , so that it is safe "de facto". This will be
   
3. 
   
4. * default - same as the default reordering threshold - but if reordering increases , we must
   
5. 
   
6. * be able to allow cwnd to burst at least this much in order to not pull it back when holes
   
7. 
   
8. * are filled.
   
9. 
   
10. */
    
11. 
    
12. static __inline__ __u32 tcp_max_burst ( const struct tcp_sock *sk )
    
13. 
    
14. {
    
15. 
    
16.         return tp->reordering ;
    
17. 
    
18. }
    
19. 
    
20. /* u8 reordering ; Packets reordering metric */
    
21. 
    
22. 
    
23. 
    
24. /* RFC2681 Check whether we are limited by application or congestion window
    
25. 
    
26. * This is the inverse of cwnd check in tcp_tso_should_defer
    
27. 
    
28. */
    
29. 
    
30. /* 返回0，不需要增加cwnd ; 返回1，cwnd被限制，需要增加 */
    
31. 
    
32. int tcp_is_cwnd_limited ( const struct sock *sk , u32 in_flight )
    
33. 
    
34. {
    
35. 
    
36.         const struct tcp_sock *tp = tcp_sk(sk) ;
    
37. 
    
38.         u32 left ;
    
39. 
    
40.         if( in_flight >= tp->snd_cwnd ) /* 不是规定in_flight < snd_cwnd ? */
    
41. 
    
42.                 return 1 ;
    
43. 
    
44.         left = tp->snd_cwnd - in_flight ;
    
45. 
    
46.         if( sk_can_gso(sk) &&
    
47. 
    
48.                 left * sysctl_tcp_tso_win_divisor < tp->snd_cwnd &&
    
49. 
    
50.                 left * tp->mss_cache < sk->sk_gso_max_size )
    
51. 
    
52.                 return 1 ;
    
53. 
    
54.         return left <= tcp_max_busrt( tp ) ;
    
55. 
    
56. }

复制代码

=============================================================================================================

1. static void bictcp_cong_avoid ( struct sock *sk , u32 ack , u32 in_flight )
   
2. 
   
3. {
   
4. 
   
5.         struct tcp_sock *tp = tcp_sk(sk) ;
   
6. 
   
7.         struct bictcp *ca = inet_csk_ca(sk) ;
   
8. 
   
9.         /* 如果发送拥塞窗口不被限制，不能再增加，则返回 */
   
10. 
    
11.         if( !tcp_is_cwnd_limited(sk , in_flight))
    
12. 
    
13.                 return ;
    
14. 
    
15.         if( tp->snd_cwnd < tp->snd_ssthresh )
    
16. 
    
17.                 tcp_slow_start( tp ) ;
    
18. 
    
19.         else {
    
20. 
    
21.                 bictcp_update(ca , tp->snd_cwnd ) ;
    
22. 
    
23.                 tcp_cong_avoid_ai( tp , ca->cnt ) ;
    
24. 
    
25.         }
    
26. 
    
27. }

复制代码

从以上函数可以看出，BIC的慢启动和reno相同。在拥塞避免阶段，当snd_cwnd <= low_window ，两者也采用相同方法。

只有当snd_cwnd > low时，BIC才开始显示出它的特性。



在include/ net / tcp.h中，

1. /* TCP timestamps are only 32-bits */
   
2. 
   
3. #define tcp_time_stamps ((__u32)(jiffies))
   
4. 
   
5. 
   
6. 
   
7. /*
   
8. 
   
9. * Compute congestion window to use.
   
10. 
    
11. */
    
12. 
    
13. static inline void bictcp_update( struct bictcp *ca , u32 cwnd )
    
14. 
    
15. {
    
16. 
    
17.         if ( ca->last_cwnd == cwnd &&
    
18. 
    
19.                 (s32) ( tcp_time_stamp - ca->last_time) <= HZ / 32 )  /* 31.25ms以内不更新ca！！！*/
    
20. 
    
21.         return ;
    
22. 
    
23.         ca->last_cwnd = cwnd ;
    
24. 
    
25.         ca->last_time = tcp_time_stamp ;
    
26. 
    
27.         if ( ca->epoch_start == 0 ) /* recording the beginning of an epoch */
    
28. 
    
29.                 ca->epoch_start = tcp_time_stamp ;
    
30. 
    
31.         /* start off normal */
    
32. 
    
33.         if( cwnd <= low_window ) {  /*为了保持友好性*/
    
34. 
    
35.                 ca->cnt = cwnd ;  /*这样16个以内的ack，可使snd_cwnd++ */
    
36. 
    
37.                 return ;
    
38. 
    
39.         }
    
40. 
    
41.         /* binary increase */
    
42. 
    
43.         if ( cwnd < ca->last_max_cwnd ) {  /*上次掉包前一个snd_cwnd */
    
44. 
    
45.                 __u32 dist = (ca->last_max_cwnd - cwnd) / BICTCP_B ; /* 四分之一 */
    
46. 
    
47.                 if ( dist > max_increment ) /* linear increase */
    
48. 
    
49.                         /*dist > 16，处于线性增长阶段，每收到16个ACK，会使snd_cwnd++ */
    
50. 
    
51.                         ca->cnt = cwnd / max_increment ;
    
52. 
    
53.                 else if ( dist <= 1U ) /* binary search increase */
    
54. 
    
55.                         /* dist <=1 ， ca->cnt=5*cwnd，会造成snd_cwnd增长极其缓慢，即处于稳定阶段 */
    
56. 
    
57.                         ca->cnt = (cwnd * smooth_part ) / BICTCP_B ;
    
58. 
    
59.                 else /* binary search increase */
    
60. 
    
61.                         /* 1 < dist <= 16 ，每收到dist个ACK，会使snd_cwnd++，故增长很快 */
    
62. 
    
63.                         ca->cnt = cwnd / dist ;
    
64. 
    
65.         } else { /* 进入max_probing阶段 */
    
66. 
    
67.                 if ( cwnd < ca->last_max_cwnd + BICTCP_B ) /* cwnd < ca->last_max_cwnd + 4 */
    
68. 
    
69.                         ca->cnt = (cwnd * smooth_part ) / BICTCP_B ; /* ca->cnt = 5*cwnd ; slow start */
    
70. 
    
71.                 else if ( cwnd < ca->last_max_cwnd + max_increment * ( BICTCP_B - 1))
    
72. 
    
73.                         /* 增长率从5/(3*cwnd)~47/(3*cwnd)，snd_cwnd的增长加快*/
    
74. 
    
75.                         ca->cnt = (cwnd * (BICTCP_B - 1)) / (cwnd - ca->last_max_cwnd) ;
    
76. 
    
77.                 else
    
78. 
    
79.                         ca->cnt = cwnd / max_increment ; /* 增长率为16/cwnd ，更快 */
    
80. 
    
81.         }
    
82. 
    
83.         /* if in slow start or link utilization is very low */
    
84. 
    
85.         if ( ca->loss_cwnd == 0 ) {  /* 没有发生过丢包，所以snd_cwnd增长应该快点*/
    
86. 
    
87.                 if ( ca->cnt > 20 ) /* increase cwnd 5% per RTT */
    
88. 
    
89.                       ca->cnt = 20 ;
    
90. 
    
91.         }
    
92. 
    
93.         /* 相当于乘与delayed_ack的百分比，delayed得越严重，则snd_cwnd应该增加越快*/
    
94. 
    
95.         /* 这样有无delayed对snd_cwnd的影响不大*/
    
96. 
    
97.         ca->cnt = (ca->cnt << ACK_RATIO_SHIFT) / ca->delayed_ack ;
    
98. 
    
99.         /* ca->cnt cannot be zero */
    
100. 
     
101.         if ( ca->cnt == 0)
     
102. 
     
103.                 ca->cnt = 1 ;
     
104. 
     
105. }

复制代码

从以上函数可以看出，和reno相比，BIC在拥塞避免阶段snd_cwnd增长极快。

当ca->last_max_cwnd - snd_cwnd >= 4 时，snd_cwnd最慢的增长率为 1/16 。

而当ca->last_max_cwnd - snd_cwnd <4 时，增长率非常低，可以使当前的snd_cwnd维持很长一段时间，

即以最合适的snd_cwnd发送数据。

这两点使BIC在高带宽、长时延的环境下能达到较高的吞吐量。



1. 搜索阶段

1. (1) cwnd < last_max_cwnd - 64， 则cnt = cwnd / 16
   
2. 
   
3. (2) last_max_cwnd - 64 <= cwnd < last_max_cwnd -4 ，则cnt = cwnd / dist
   
4. 
   
5. (3) last_max_cwnd - 4 <= cwnd < last_max_cwnd ，则cnt = 5*cwnd

复制代码

总体来说，snd_cwnd增长先快后慢，趋于稳定。

2. max probing阶段

1. 
   
2. (1) last_max_cwnd <= cwnd < last_max_cwnd + 4，则cnt = 5*cwnd
   
3. 
   
4. (2) last_max_cwnd + 4 <= cwnd < last_max_cwnd + 48 ，则cnt = 3*cwnd / (cwnd - last_max_cwnd)
   
5. 
   
6. (3) cwnd >= last_max_cwnd + 48 ，则cnt = cwnd / 16

复制代码

总体来说，snd_cwnd的增长先慢后快，越来越快。

健康木乃伊

很好阿  希望于楼主多多交流哦