Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1760012
  • 博文数量: 1493
  • 博客积分: 38
  • 博客等级: 民兵
  • 技术积分: 5834
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-19 17:28
文章分类

全部博文(1493)

文章存档

2016年(11)

2015年(38)

2014年(137)

2013年(253)

2012年(1054)

2011年(1)

分类:

2012-06-04 08:48:13

原文地址:TCP拥塞窗口校验算法 作者:lovelylich

CWV解决的问题:当主机没有数据包发送,或发送数据包量小于拥塞窗口的情况下,由于数据包个数过少,不能确保当前拥塞窗口正确反映了网络容量。

CWV算法的核心思想就是在每个RTT内递减拥塞窗口, 使得当前拥塞窗口能保守地正确反映网络拥塞情况。此外,CWV算法还使得拥塞窗口只在network-limited状态增长。

该算法中的基本概念:
1. network-limited指应用程序有足够的数据包可发送,但拥塞窗口不允许, 这种情况下拥塞窗口总能正确反映网络拥塞状态。
2. application-limited指应用程序没有足够的数据包可发送, 拥塞窗口还有很多空间可用于数据发送。这种情况下的拥塞窗口不能正确反映网络容量,因为没有足够的数据包测试网络容量。


算法第一步:
当TCP每次发送数据包时检查距上次发包时间是否超过RTO。 如果超过, 则设置ssthreshold为max(3/4*cwnd, ssthreshold)。然后超时多少倍RTO, cwnd就减半多少次, 即乘法递减策略。
snd_cwnd_stamp设置为当前时间:记录最近一次空闲后递减拥塞窗口或者处于network-limited状态的时间。
snd_cwnd_used 置0:该值记录自上次network-limited以来,处于application-limited期间的最大拥塞窗口。
注: 此处3/4倍cwnd, 是对慢启动阈值的经验估计值

tcp_transmit_skb()在调用IP层发包函数前一步调用 tcp_event_data_sent() , 以此来设置CWV相关变量:

点击(此处)折叠或打开

  1. /* Congestion state accounting after a packet has been sent. */
  2. static void tcp_event_data_sent(struct tcp_sock *tp,
  3.                 struct sk_buff *skb, struct sock *sk)
  4. {
  5.     ....
  6.     ....
  7.     if (sysctl_tcp_slow_start_after_idle &&
  8.       //如果发送方自上次发包以来已经超过至少一个RTO, 则执行算法第一步
  9.      (!tp->packets_out && (s32)(now - tp->lsndtime) > icsk->icsk_rto))
  10.         tcp_cwnd_restart(sk, __sk_dst_get(sk));

  11.     tp->lsndtime = now;
  12.     ......
  13.     ......
  14. }

点击(此处)折叠或打开

  1. /* RFC2861. Reset CWND after idle period longer RTO to "restart window".
  2.  * This is the first part of cwnd validation mechanism. */
  3. static void tcp_cwnd_restart(struct sock *sk, struct dst_entry *dst)
  4. {
  5.     struct tcp_sock *tp = tcp_sk(sk);
  6.     s32 delta = tcp_time_stamp - tp->lsndtime;
  7.     u32 restart_cwnd = tcp_init_cwnd(tp, dst);
  8.     u32 cwnd = tp->snd_cwnd;

  9.     tcp_ca_event(sk, CA_EVENT_CWND_RESTART);
  10.      //设置慢启动阈值为3/4当前拥塞窗口和慢启动阈值中的最大者
  11.     tp->snd_ssthresh = tcp_current_ssthresh(sk)
  12.     restart_cwnd = min(restart_cwnd, cwnd);
  13.     //超时多少RTO, cwnd就减半多少倍
  14.     while ((delta -= inet_csk(sk)->icsk_rto) > 0 && cwnd > restart_cwnd)
  15.         cwnd >>= 1;
  16.     tp->snd_cwnd = max(cwnd, restart_cwnd);
  17.     tp->snd_cwnd_stamp = tcp_time_stamp; //重置变量,以便下次计算。
  18.     tp->snd_cwnd_used = 0;
  19. }
算法第二步:
在发送数据包成功后, 检查当前已发送数据包个数是否大于cwnd。
如果大于则说明当前处于network-limited状态,无需确认拥塞窗口正确性。
记录当前时间,并且重置snd_cwnd_used为0, 等待以后计算拥塞窗口正确性。

如果已发送数据包个数小于cwnd, 则说明TCP处于application-limited状态。
如果当前未确认包个数大于拥塞窗口, 则保存该拥塞窗口最大值。
如果自上次记录时间起,已经超过RTO。 则说明发送发处于该拥塞窗口半满状态发包已经持续大于1倍RTO且小于2倍RTO的时间了。(因为每次发包都会走到该流程,所以最多是1倍RTO时间的半满状态,考虑RTO超时。)

tcp_write_xmit()函数在调用 tcp_transmit_skb ()函数把所有需要发送的数据包发送完成后, 会调用tcp_cwnd_validate ()来根据此次发送的数据包量, 确定TCP处于network-limited状态还是application-limited状态, 并采取相应策略。

 点击(此处)折叠或打开

  1. /* Congestion window validation. (RFC2861) */
  2. static void tcp_cwnd_validate(struct sock *sk)
  3. {
  4.     struct tcp_sock *tp = tcp_sk(sk);

  5.     if (tp->packets_out >= tp->snd_cwnd) {
  6.         /* Network is feed fully. */
  7. //如果处于network-limited状态, 则重置变量等待以后计算。
  8.         tp->snd_cwnd_used = 0;
  9.         tp->snd_cwnd_stamp = tcp_time_stamp;
  10.     } else {
  11.         /* Network starves. */
  12. //保存在网络饥饿期间的最大拥塞窗口, 用于测量这期间的网络容量
  13.         if (tp->packets_out > tp->snd_cwnd_used)
  14.             tp->snd_cwnd_used = tp->packets_out;

  15.         if (sysctl_tcp_slow_start_after_idle &&
  16. //如果距离上次记录cwnd_used时间超过rto,则减小拥塞窗口
  17.          (s32)(tcp_time_stamp - tp->snd_cwnd_stamp) >= inet_csk(sk)->icsk_rto)
  18.             tcp_cwnd_application_limited(sk);
  19.     }
  20. }

根据以上算法,tcp_cwnd_application_limited()函数在TCP处于cwnd半满状态发包,且持续一个RTO的情况下被调用。 此时,依旧按照3/4倍cwnd和sstreshold中的最大值设置ssthreshold,而拥塞窗口设置为当前拥塞窗口和半满状态持续一个RTO以来的发送到网络中的最大数据包个数的平均值。随后, 重置snd_cwnd_used为0,snd_cwnd_stamp为当前值。因此,直到下次RTO才会再次递减拥塞窗口, 即在application-limited的状态下, 每过RTO时间递减拥塞窗口。

点击(此处)折叠或打开

  1. void tcp_cwnd_application_limited(struct sock *sk)
  2. {
  3.     struct tcp_sock *tp = tcp_sk(sk);

  4.     if (inet_csk(sk)->icsk_ca_state == TCP_CA_Open &&
  5.      sk->sk_socket && !test_bit(SOCK_NOSPACE, &sk->sk_socket->flags)) {
  6.         /* Limited by application or receiver window. */
  7.         u32 init_win = tcp_init_cwnd(tp, __sk_dst_get(sk));
  8.         u32 win_used = max(tp->snd_cwnd_used, init_win);
  9.         if (win_used < tp->snd_cwnd) {
  10.     //由于在application-limited阶段, 我们不会增长cwnd,只会递减。所以只有当snd_cwnd_used < cwnd的时候,才取两者均值。
  11.             tp->snd_ssthresh = tcp_current_ssthresh(sk);
  12.             tp->snd_cwnd = (tp->snd_cwnd + win_used) >> 1;
  13.         }
  14.         tp->snd_cwnd_used = 0;
  15.     }
  16.     tp->snd_cwnd_stamp = tcp_time_stamp;
  17. }
慢启动阈值的算法是取当前拥塞窗口和慢启动阈值的3/4 中的最大值。见下面代码:

点击(此处)折叠或打开

  1. static inline __u32 tcp_current_ssthresh(const struct sock *sk)
  2. {
  3.     const struct tcp_sock *tp = tcp_sk(sk);
  4.     if ((1 << inet_csk(sk)->icsk_ca_state) & (TCPF_CA_CWR | TCPF_CA_Recovery))
  5.         return tp->snd_ssthresh;
  6.     else
  7.         return max(tp->snd_ssthresh,
  8.              ((tp->snd_cwnd >> 1) +
  9.              (tp->snd_cwnd >> 2)));
  10. }
以上是CWV算法对拥塞窗口的减少,CWV算法也会使得拥塞窗口只能在network-limited状态增长。
拥塞控制算法只有在通过CWV算法检测的情况下,才会决定采用慢启动还是拥塞避免来增长拥塞窗口。

点击(此处)折叠或打开

  1. void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)
  2. {
  3.     struct tcp_sock *tp = tcp_sk(sk);

  4.     if (!tcp_is_cwnd_limited(sk, in_flight))
  5.         return;

  6.     /* In "safe" area, increase. */
  7.     if (tp->snd_cwnd <= tp->snd_ssthresh)
  8.         tcp_slow_start(tp);
  9.    
  10.     ......
  11. }

 点击(此处)折叠或打开

  1. /* RFC2861 Check whether we are limited by application or congestion window
  2.  * This is the inverse of cwnd check in tcp_tso_should_defer
  3.  */
  4. int tcp_is_cwnd_limited(const struct sock *sk, u32 in_flight)
  5. {
  6.     const struct tcp_sock *tp = tcp_sk(sk);
  7.     u32 left;

  8.     if (in_flight >= tp->snd_cwnd)
  9.         return 1;

  10.     left = tp->snd_cwnd - in_flight;
  11.     if (sk_can_gso(sk) &&
  12.      left * sysctl_tcp_tso_win_divisor < tp->snd_cwnd &&
  13.      left * tp->mss_cache < sk->sk_gso_max_size)
  14.         return 1;
  15.     //当已发送数据包个数远小于cwnd时,即便这次发送max_burst个数据包,也不能填满cwnd,说明当前处于application-limited状态,所以返回false,禁止cwnd增长
  16.     return left <= tcp_max_burst(tp);  
  17. }

阅读(814) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~