加载中…
个人资料
老衲五木
老衲五木
  • 博客等级:
  • 博客积分:0
  • 博客访问:352,549
  • 关注人气:330
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

慢启动算法与拥塞避免算法《LwIP协议栈源码详解——TCP/IP协议的实现》

(2012-08-28 20:48:42)
标签:

lwip

tcp

发送方

接收方

算法

分类: 嵌入式网络那些事

这节讨论慢启动算法与拥塞避免算法。版权声明:下面这几段的内容大部分来自于《TCP/IP详解,卷1:协议》,若有雷同,纯非巧合!

假如按照前面所有的讨论,发送方一开始便可以向网络发送多个报文段,直至达到接收方通告的窗口大小为止。当发送方和接收方处于同一个局域网时,这种方式是可以的。但是如果在发送方和接收方之间存在多个路由器和速率较慢的链路时,就有可能出现一些问题。中间路由器缓存分组,可能消耗巨大的时间和存储器空间开销,这样TCP连接的吞吐量会严重降低。

要解决这种问题,TCP需要使用慢启动(slow start)算法。该算法通过观察新分组进入网络的速率应该与另一端返回确认的速率相同而进行工作。慢启动为发送方的TCP增加了另一个窗口:拥塞窗口(congestion window),记为cwnd。当与另一个网络的主机建立TCP连接时,拥塞窗口被初始化为 1个报文段(即另一端通告的报文段大小)。每收到一个ACK,拥塞窗口就增加一个报文段。发送方取拥塞窗口与通告窗口中的最小值作为发送上限。

拥塞窗口是发送方使用的流量控制,而通告窗口则是接收方使用的流量控制。发送方开始时发送一个报文段,然后等待ACK。当收到该ACK时,拥塞窗口从1增加为2,即可以发送两个报文段。当收到这两个报文段的 ACK时,拥塞窗口就增加为4。这是一种指数增加的关系。

说到慢启动算法,就不得不说拥塞避免算法,在实际中这两个算法通常是在一起实现。通常慢启动算法是发送方控制数据流的方法,但有时发送方的数据流会达到中间路由器的极限,此时分组将被丢弃。拥塞避免算法是一种处理丢失分组的方法。该算法假定由分组受到损坏引起的丢失是非常少的(远小于1%),因此在发送方看来,分组丢失就意味着在源主机和目的主机之间的某处网络上发生了拥塞。发送方可以通过两种方式来判断分组丢失:发生数据包发送超时和接收到重复的确认。

当拥塞发生时,我们希望降低分组进入网络的传输速率,发送方通过慢启动与拥塞避免算法主动调节分组进入网络的速率,同时发送方也通过接收方通告的窗口大小来被动调节分组发送速率。

拥塞避免算法和慢启动算法需要对每个连接维持两个变量:一个拥塞窗口cwnd和一个慢启动门限ssthresh。这样算法一般按照如下过程进行:

1) 对一个给定的连接,初始化cwnd为1个报文段,ssthresh为65535个字节。

2) TCP输出例程的输出不能超过cwnd和接收方通告窗口的大小。拥塞避免是发送方使用的流量控制,而通告窗口则是接收方进行的流量控制。前者是发送方感受到的网络拥塞的估计,而后者则与接收方在该连接上的可用缓存大小有关。

3) 当拥塞发生时(超时或收到重复确认),ssthresh被设置为当前窗口大小的一半(cwnd

和接收方通告窗口大小的最小值,但最少为 2个报文段)。此外,如果是超时引起了拥塞,则cwnd被设置为1个报文段(这就是慢启动) 。

4) 当新的数据被对方确认时,就增加cwnd,但增加的方法依赖于我们是否正在进行慢启

动或拥塞避免。如果cwnd小于或等于ssthresh,则正在进行慢启动,否则正在进行拥塞避免。慢启动一直持续到我们回到当拥塞发生时所处位置的一半时候才停止(因为我们记录了在步骤2中给我们制造麻烦的窗口大小的一半),然后转为执行拥塞避免。

慢启动算法初始设置cwnd为1个报文段,此后每收到一个确认就加 1,这会使窗口按指数方式增长:发送1个报文段,然后是2个,接着是4个……。拥塞避免算法要求每次收到一个确认时将cwnd增加1 /cwnd。与慢启动的指数增加比起来,这是一种加性增长(additive increase)。我们希望在一个往返时间内最多为 cwnd增加1个报文段(不管在这个RTT中收到了多少个ACK),然而慢启动将根据这个往返时间中所收到的确认的个数增加cwnd。

说了半天用一句话来概括慢启动算法和拥塞避免算法:每个TCP控制块有两个字段cwnd和ssthresh,当数据发送时,发送方只能取cwnd和接收方通告窗口大小中的较小者作为发送上限。当有确认返回时,若此时cwnd值小于等于ssthresh,则做慢启动算法,即每收到一个确认,cwnd都加1;若此时cwnd值大于ssthresh,则做拥塞避免算法,即每收到一个确认,cwnd都加1/cwnd,这保证了在一个RTT估计内,cwnd增加值不超过1。当cwnd增加到某个值时拥塞发生,则按照3)所示来更新cwnd和ssthresh的值。晕,MS不是一句话,是一段话!

这里我们按照上面算法所述的步骤来看看LWIP具体是怎样来描述整个过程的。

1)      给定一个连接,初始化其cwnd与ssthresh。cwnd都被初始化为1,而ssthresh字段在客户端与服务器端略有不同,在客户端执行主动连接,调用函数tcp_connect,在其中完成相关字段值的设置:

pcb->cwnd = 1;

pcb->ssthresh = pcb->mss * 10;

pcb->state = SYN_SENT;

在发送出SYN包并收到服务器的返回SYN+ACK后,客户机在函数tcp_process中对相关字段进行进一步的设置:

pcb->ssthresh = pcb->mss * 10;

pcb->cwnd = ((pcb->cwnd == 1) ? (pcb->mss * 2) : pcb->mss);

而在服务器端,进行被动连接,在函数tcp_listen_input中设置相关字段的值:

npcb->snd_wnd = tcphdr->wnd;

npcb->ssthresh = npcb->snd_wnd;

可以看到在服务器端,ssthresh被设置为了对方通告的接收窗口大小。

2)      TCP输出例程的输出不能超过cwnd和接收方通告窗口的大小。在tcp_output函数中是用下面的代码来发送数据段的:

wnd = LWIP_MIN(pcb->snd_wnd, pcb->cwnd);  // 取有效发送窗口大小值

seg = pcb->unsent;    //取得第一个发送数据段

……

while (seg != NULL &&ntohl(seg->tcphdr->seqno) - pcb->lastack + seg->len <= wnd)

{                              // 数据段在有效发送窗口内

pcb->unsent = seg->next;

tcp_output_segment(seg, pcb);   // 则发送数据段

……

seg = pcb->unsent;       // 取得下一个发送数据段

}

3)发生拥塞时,需要更新cwnd和ssthresh的值。若拥塞是由超时引起的,则相应的更新代码在tcp_slowtmr中被实现,如下,这段熟悉的代码我们在超时重传中也见到过:

if(pcb->rtime >= 0)

++pcb->rtime;

if (pcb->unacked != NULL && pcb->rtime >= pcb->rto) {   // 超时发生

……    // 与超时重传相关的部分

eff_wnd = LWIP_MIN(pcb->cwnd, pcb->snd_wnd); // 取得超时的有效发送大小

pcb->ssthresh = eff_wnd >> 1;   // ssthresh设置为有效大小的一半

if (pcb->ssthresh < pcb->mss)  { // 修正ssthresh至少为2个报文段

pcb->ssthresh = pcb->mss * 2;

}

pcb->cwnd = pcb->mss;    // 设置cwnd大小为1个报文段大小

}

若拥塞是由重复确认引起的,则相应的更新代码在tcp_receive函数中实现,这段代码涉及到快速恢复与重传部分的知识,我们重点放在后面讲解。

if (pcb->lastack == ackno) {

……

……

if (pcb->cwnd > pcb->snd_wnd)     // ssthresh设置为有效发送窗口的一半

pcb->ssthresh = pcb->snd_wnd / 2;

else

pcb->ssthresh = pcb->cwnd / 2;

if (pcb->ssthresh < 2*pcb->mss) {   // 修正ssthresh至少为2个报文段

pcb->ssthresh = 2*pcb->mss;

}

pcb->cwnd = pcb->ssthresh + 3 * pcb->mss; // 这里不解?

……

}

4) 当新的数据被对方确认时,更新cwnd和ssthresh的值。

if (TCP_SEQ_BETWEEN(ackno, pcb->lastack+1, pcb->snd_max)){

……

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;

}

}

}

……

}

这段代码基本就是上面所说的第四步的直接翻译了。需要注意的是new_cwnd为什么要用上面的等式计算出来呢?那是因为cwnd的大小是按照mss的大小为单位增加减少的,其他不解释。

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有