这是我在Coursera上的学习笔记。课程名称为《Computer Networks》，出自University of Washington。
由于计算机网络才诞生不久，目前正在以高速在发展，所以有些旧的教材可能都已经跟不上时代了。这门课程在2013年左右录制，知识相对还是比较新的。覆盖了计算机网络中的各个协议层，从物理层到应用层都讲得非常仔细。学完这门课程之后对计算机网络会有比较深刻的了解。
概述
课程位置
关于传输层和网络层的上半部分
话题
阻塞就类似于显示生活中的堵车
阻塞CONGESTION的本质
路由器或者交换机都有输入输出的缓冲
在一个路由器或者交换机中，如果有很多端口持续地向同一个端口发送数据，缓冲区就会被填满，从而导致大量丢包。这就是阻塞。
阻塞造成的影响
见图
当阻塞发生的时候，发送速度会明显减小。网络延迟会明显增大
带宽分配
就是给发送者分配合理的带宽。这是是一项很重要的任务。
好的分配应该是高效的，公平的。高效意味着没有阻塞发生。公平意味者每个发送者都能享受到带宽。
关键问题：高效的方案需要网络层和传输层共同参与。因为网络层能够察觉到拥塞，而只有传输层才能控制流量
为什么带宽分配很难呢
发送方的负载一直在变化
接收方的承受能力在不同的网络也是不同的
网络是分布式的，没有人知道整个网络的状态
解决方案
发送方根据自己察觉到的情况自动作出相应调整
设计调整策略，从而使得网络的使用率最高效最公平
调整是一直在进行的动作，因为负载每时每刻都在变化
话题
阻塞的本质
公平分配带宽
AIMD控制法则
TCP阻塞控制历史
ACK时钟
TCP慢启动
TCP快速重传
ECN阻塞规避
带宽公平分配
话题
什么是公平的带宽分配
回忆
好的带宽分配意味着公平和高效
实际应用中，高效比公平更重要
高效和公平的比较
高效和公平不能兼得
举例。假设现在有这样的网络流量：A->B B->C A->B->C
先考虑公平。A->B 1/2，B->C 1/2，A-C 1/2，这种情况下网络使用率只能达到 1.5
再考虑高效。A->B 1，B->C 1，A->C 0。这种情况下网络使用率达到2
什么才算公平
公平的目的是避免某些节点没有分配到资源，导致“饥饿”
所以每个数据流分配相同的带宽是最公平的
每个数据流分配相同的带宽
网速的瓶颈在于最慢的链路
瓶颈的存在意味着有些链路速度快，有些链路速度慢。这种情况下平均分配带宽是不可能的。
max-min公平分配
增加一个流量的同时一定会减少另一个流量
网络流量就像水流
步骤
每个数据流的速度都以0起步
逐渐增加数据流的速度直到某个数据流的速度达到了瓶颈
保持达到瓶颈的速度
返回第二步，继续操作剩下的数据流
AIMD算法Additive Increase Multiplicative Decrease
话题
AIMD是一种带宽分配模型
回忆
我们想要给发送者分配带宽，需要既高效又公平
我们应该怎样分配带宽呢？有多种方法
带宽分配模型
带宽分配模型分为多种
开循环：在带宽被使用前就已经事先分配好了。
闭循环：在带宽使用的时候逐渐调整
主机支持或网络支持
基于window或基于速度
TCP是闭循环，主机支持，基于window
本章主要将闭循环、主机支持、基于window的带宽分配模型
网络层会返回信息告诉发送者是否有网络阻塞
传输层负责调整发送者的发送速度
AIMD 线性提速、指数降速
当网络畅通时，传输速度缓慢上升（线性提速）；当网络遇到阻塞时，传输速度急速下降（指数降速）
AIMD执行的最终结果就是越来越趋向于即公平又高效的平衡点
AIMD属性
收敛于即高效又公平的平衡点
需要从网络获取反馈
反馈信号
信号有多种，包括：丢包、数据包延迟、路由器指示（阻塞信号）
TCP阻塞控制历史
话题
TCP阻塞控制的历史
1980阻塞塌方
早期TCP使用固定大小的滑动窗口（比如一次发送8个数据包）
但是当ARPANET成长的时候会发生很多奇怪的事情
由于网络组件中的消息队列太长，重发的数据包充斥着整个网络，造成有效传输速度减少了很多
Van Jacobson
发明了阻塞控制的方法
还有traceroute tcpdump pathchar, IP header compression, multicast tools
TCP tahoe/reno
在不改变路由器的情况下，避免网络阻塞
主要的办法是滑动超时时间，引入阻塞窗口的概念，类似滑动窗口
TCP tahoe/reno使用网络反馈的丢包信号来调整阻塞窗口
我们将研究TCP的以下行为：ACK始终、自适应超时、慢开始、快速重传、快速恢复
TCP发展历史
1974 TCP论文
1975 三次握手协议
1981 TCP 和 IP
1983 TCP/IP
1986 第一次发现网络阻塞
1988 TCP Tahoe
1990 TCP Reno
1993 TCP Vegas
1994 ECN
1995 TCP New Reno
1996 TCP SACK
2004 FAST TCP
2004 TCP BIC
2006 TCP CUBIC
2007 Compound TCP
2008 TCP LEDBAT
最近几年出现了很多阻塞控制的方法，但是课程内容只讲解传统的阻塞控制方法
ACK时钟
话题
滑动窗口使用了内置的时钟
滑动窗口的 ACK 时钟
根据滑动窗口协议，只有当发送方接收到ACK后，才会发送新的数据包
请思考一种情况，发送方在刚开始时数据包发送很快，比如5包/秒。但是由于中途遇到低速网络，对方接收数据的时候变成了1包/秒。那么ACK信号的速度也是1个/秒。这样，发送方接收ACK的速度也是1秒1个。根据滑动窗口协议，接收到ACK后才能发送新的数据。所以发送方的发送速度从原来的5包/秒变成了1包/秒。这就是ACK时钟。
它能让发送者保持最高效的发送速率，同时缩短了沿途路由器的消息队列，从而减少了丢包率和网络延迟。
TCP和ACK时钟
TCP通过滑动窗口使用了ACK时钟
滑动窗口控制了网络中流通的数据包数量（也称为阻塞窗口）
TCP一次发送很少的数据包，来保持网络流量的平滑
TCP慢启动
话题
TCP如何实现AIMD
回忆
我们想要通过AIMD实现TCP的带宽分配
发送方使用阻塞窗口来设置传输速度
发送方根据丢包情况调整传输速度
需要TCP适应大幅度的速度变化
TCP启动问题
我们想要快速接近最合适的速率。但是在刚开始的时候很难刚好适应
启动速度太快会导致丢包，启动速度太慢会花费很长的时间才能达到刚好适应
慢启动方案
启动速度呈指数上升
随着速度的提升，最终会由于网络阻塞发生丢包。之后，将指数提速切换成线性提速。这就是慢启动
慢启动时，也就是指数提速时，每收到1个ACK，就增加1个滑动窗口。这样传输速度就能呈现指数上升了
线性提速时，每滑动窗口个ACK之后增加1个滑动窗口
TCP tahoe
第一阶段是慢启动阶段，滑动窗口cwnd=1。每个ACK之后cwnd增加1
第二阶段是线性增长阶段，每接到一个ACK，滑动窗口cwnd增加1/cwnd。大概每个RTT之后增加一个cwnd
之后是切换threshold，初始threshold为无穷大。当cwnd > ssthresh时，切换到线性增长模式。当发生丢包之后设置ssthresh为cwnd/2。超时之后使用慢启动
timeout misfortunes
为什么要在超时之后才使用慢启动呢
超时给ACK时钟足够的时间来发挥作用
我们需要在丢包超时前就检测到丢包，这样才能更好地执行AIMD
TCP快速重发、快速恢复
话题
TCP如何实现AIMD
回忆
我们想要TCP通过AIMD法则来实现合理的网速分配
发送方通过阻塞窗口（滑动窗口）来设置速度
发送放使用慢启动来实现ACK时钟
在超时之后发送方将滑动窗口设为1，然后重新开始慢启动
通过ACK推断丢包情况
TCP使用累加型的ACK
重复的数据给我们提示哪些数据没被对方收到。出现重复ACK是因为ACK时钟
快速重发
将三个重复的ACK视为丢包，此时立即重发。三个重复的ACK来自ACK时钟
快速重发可以快速修复丢失的数据包，特别是还没超时的时候就能检测到丢包并迅速修复
但是在等ACK变化的时候有一段时间是没有传输数据的
所以我们仍然需要指数减速的方法
根据ACK推断哪些包是没有丢的
每个新的重复的ACK意味着有数据已经被对方收到了
快速恢复
在快速重传之后，有一段时间是浪费掉的。所以，在快速重传之后，需要进行“指数减速”。并且在之后的一小段时间内需要将重复的ACK视为正常的ACK。并且在这段时间内，ACK需要仍然没有递增，此时还是要继续发送后续的数据包。这就是快速恢复。
在ACK需要增加之后就退出快速恢复。
快速重发可以修复一小段丢包，使得ACK时钟持续运行
我们需要重新认识AIMD，在丢包之后不会发生超时或者TCP慢启动。而是减少滑动窗口后继续发送数据
TCP Reno实现了慢启动、快速重发、快速恢复，指数减速是指将滑动窗口减速到原来的一半
TCP Reno, NewReno, SACK
Reno一次只能恢复一个丢包，多次丢包最终会超时然后重发
NewReno加强了ACK推断的过程，一次能修复多个丢包并且不会发生超时重发
SACK是一个更好的方法，接收方可以发送一个范围的ACK，这样发送方就不需要猜测哪些数据包丢失了
阻塞信号
话题
路由器如何帮助主机避免阻塞
阻塞控制与避免阻塞
传统的TCP到最后会让网络进入阻塞状态然后恢复
所以我们需要好的方法来避免阻塞，而不是进行阻塞控制，碰到阻塞后重发
反馈信号
延迟和路由器信号可以让我们避免阻塞
丢包、数据包延迟、路由器信号丢可以帮助我们避免阻塞
ECN 显式阻塞信号
当路由器检测到网络阻塞时，它会在受影响的数据包的IP头中增加标记。在数据包到达接收方之后，接收方会将数据包丢掉。这样接收方就能知道网络已经发生阻塞了。然后接受方向发送方发送阻塞信号。
优点
路由器向主机发送清楚的信息
阻塞能提早检测到，避免了丢包的发生
不需要发送额外的数据包
缺点
路由器和主机需要升级才能支持ECN
我个人的观点
为什么发生阻塞的时候信号要先传递给接收方呢？然后再由接收放传递给发送方。这样不是浪费了很多时间吗？我觉得可以在发生阻塞的时候将信号直接从路由器发送到发送方，可以通过ICMP协议发送阻塞信号。这样发送方就能更早地检测到网络阻塞了。
ACK序号=数据包序号+payload长度。所以对方发送seq=10,length=5的数据包时，接收方应该回应ack seq=15，而不是14
?
读书笔记：计算机网络第7章：阻塞控制,布布扣,bubuko.com
原文：http://blog.csdn.net/caipeichao2/article/details/26283067
