考研笔记-计算机之计算机网络:运输层关键算法“表”述(一)

表-各层协议的关键算法

协议层

协议算法

算法实现

运输层

TCP可靠传输算法

见“表-可靠传输协议”

考研笔记-计算机之计算机网络：各协议层实现的功能“表”述

TCP超时重传时间选择的自适应算法

自适应算法：

1) 新的RTT_S=（1 – α）×（旧的RTT_S）+α×（新的RTT样本）；（0<α<1，建议值α=0.125）

2) 新的RTT_D=（1 – β）×（旧的RTT_D）+β×|新的RTT样本– 旧的RTT_S|；（0<β<1，建议值β=0.25）

3) RTO = RTT_S+4×RTT_D；

（其中，RTT_S为平滑的往返时间；RTT_D为RTT的偏差的加权平均值，RTT_D的初始值为得到的RTT样本值的一半；RTO为超时重传时间）

改进（消除重传报文对定时判断的影响）算法：

1) 当发生报文重传时，每重传一次，执行一次：新的RTO=2×旧的RTO；

2) 当不再发生报文重传时，执行上面的自适应算法。

TCP拥塞控制算法

当cwnd<ssthresh时执行慢开始算法，当cwnd>ssthresh时执行拥塞避免算法，当cwnd=ssthresh时执行慢开始或拥塞避免算法：

1) 慢开始阶段（拥塞窗口指数增大）：

当cwnd<ssthresh时，每收到一个对新的报文段的确认（重传的不算在内）后，把拥塞窗口增加一个MSS对应的字节数（拥塞窗口大小的单位是字节），即每经过一个往返时间RTT（一个传输轮次所对应的时间），拥塞窗口的大小加倍；

2) 拥塞避免阶段（拥塞窗口加法增大）：

当cwnd>ssthresh时，每经过一个往返时间RTT，拥塞窗口的大小增加一个MSS对应的字节数；（具体实现可以采用如下办法，即RTT时间内每收到一个确认ACK，便将拥塞窗口cwnd增加MSS*(MSS/cwnd)，其中“MSS/cwnd”中的cwnd在该RTT时间内始终为该RTT开始时刻的大小。这样每经过一个往返时间RTT（即一个传输轮次），拥塞窗口的大小将增加1个MSS的大小）

3) 发生超时时刻（慢开始门限值乘法减小，即减为拥塞窗口的一半；拥塞窗口置为1个MSS大小）：

慢开始或拥塞避免阶段，当发生超时时，ssthresh变为当前cwnd值的一半（但不能小于2个MSS的大小），cwnd设置为1个MSS对应的字节数，随后执行慢开始算法；

4) 收到连续3个重复确认时刻（慢开始门限值乘法减小，即减为拥塞窗口的一半；拥塞窗口置为慢开始门限值）：

慢开始或拥塞避免阶段，当收到连续3个重复确认时，ssthresh变为当前cwnd值的一半（但不能小于2个MSS的大小），cwnd设置为ssthresh的新值，随后执行拥塞避免算法；（此处理方法即为快恢复）

5) 快重传算法（快重传是实现快恢复的前提）：

接收方，每收到一个失序的分组，就立即发出重复确认（对按序到达的最后一个分组的确认），而不是等待自己发送数据时才进行捎带确认；

发送方，只要收到三个重复确认，就立即重传未被确认的分组，而不是等到重传计时器到期。

说明：

1) 一个传输轮次所经历的时间其实就是往返时间RTT（该RTT是动态变化的，不同轮次的RTT不同），使用“传输轮次”更加强调：把拥塞窗口所允许发送的报文段都连续发送出去，并收到了对已发送的最后一个字节的确认。

2) 当发生“收到连续3个重复确认”时，将拥塞窗口置为慢开始门限值（转入拥塞避免），而不是拥塞窗口置为1个MSS大小（转入慢开始），是因为既然能够收到连续3个重复确认，说明接收方已连续收到三个报文段，故此时的网络很可能还未发生阻塞。

TCP流量控制算法

TCP的流量控制是通过发送方根据接收方接收窗口的大小调节自身的发送窗口的大小，以保证发送方发送窗口的大小不大于接收方接收窗口的大小实现的。

但当出现发送方收到接收方的窗口值（接收窗口）为0的报文后停止发送，而后接收方发送的窗口值（接收窗口）不为0的报文又丢失的情况时，将出现双方相互等待的死锁局面，解决该死锁问题的方法是：【TCP的可靠传输不是可以保证接收方在收不到对其窗口值不为0的报文段的确认时可以重传吗？LQ?】

1) TCP为每一个连接设置一个持续计时器，只要TCP连接的一方收到对方的零窗口通知，就启动持续计时器；

2) 若持续计时器设置的时间到期，就发送一个零窗口探测报文段（仅携带1字节的数据），而对方在确认这个探测报文段时给出了现在的窗口值；

3) 如果窗口仍然是零，那么收到这个报文段的一方就重新设置持续计时器；如果窗口不是零，那么死锁的僵局就可打破；

（TCP规定，即使设置为零窗口，也必须接收以下三种报文段：零窗口探测报文段、确认报文段和携带紧急数据的报文段）

TCP高效传输算法

发送方（发送方和接收方是相对且动态变化的）：

Nagle算法：

1) 若发送应用进程把要发送的数据逐个字节地送到TCP的发送缓存，则发送方就把第一个数据字节先发送出去，把后面到达的数据字节都缓存起来；

2) 当发送方收到对第一个数据字节的确认后，再把发送缓存中的所有数据组装成一个报文段发送出去，同时继续对随后到达的数据进行缓存；

3) 只有在收到对前一报文段的确认后才继续发送下一个报文段；或者，

4) 当缓存的数据已达到发送窗口大小的一半或已达到报文段的最大长度时，就立即发送一个报文段。

接收方（发送方和接收方是相对且动态变化的）：

不立即发送确认报文和向发送方通知自己当前的接收窗口大小，而是当接收缓存的空闲空间已达到接收窗口大小的一半或已达到报文段的最大长度时，接收方才发送确认报文并向发送方通知自己当前的接收窗口大小