TCP协议，Transmission Controll Protocol。
UDP协议，User Datagram Protocol。
负责将数据报文可以从一个应用程序交付到另一台主机的应用程序上，解决的是程序进程间的通信。也可以说是这种协议的抽象，让这两个应用觉得它们是直接相连通信的。
点击查看【processon】

1、多路复用和多路分解

是IP服务扩展成进程间数据通信服务的过程。
多路复用multiplexing：不同套接字收集数据块，封装成运输层报文段并传递给网络层的工作。
多路分解demultiplexing：运输层报文段交付到正确套接字的工作

简而言之，多路复用，就是数据打包过程，多路分解是数据解封过程。

无连接的多路复用和分解

点击查看【processon】

有连接的多路复用和分解

和无连接有一个很大的区别，包含了源和目的地的IP和port，无连接只有port。
image.png

常见网络应用的运输协议

image.png

2、无连接运输：UDP

相比于IP协议，就增加了一个数据交付和差错校验。
数据交付：分组增加字段“port”两个，源和目的端口号（port）。
差错校验：分组增加字段“检验和”。

2.2 UDP报文结构

无连接的多路复用和分解
RFC 768定义。

2.3 UDP检验和：差错校验

RFC 1071定义。

源端口a（16bit） 目的端口b（16bit）
长度c（16bit） 检验和d（16bit）
数据区 
  1. //UDP 检验和原理
  3. d = ~(a + b + c);        //如果有溢出，则“溢出”回卷到最低位。
  4. int16_t flag = 0xFFFF;    //二进制：1111111111111111（16bit）
  5. if((a + b + c + d) == flag)
  6.     printf("数据无差错");
  7. else    //只有16bit有1个bit为0
  8.     printf("数据有差错");

3、可靠数据传输原理

核心思想

根据下图。
提供的服务：可靠数据传输原理的抽象就是“一个可靠的信道”，这个“信道”内部是基于不可靠的实际信道。
服务实现：这是实现框架结构。
rdt：reliable data transmission
udt：unreliable data transmission
deliver_data：分发数据到上层应用。
image.png
接下来，我们循序渐进，从简单开始，构造可靠数据传输协议。

3.1 rdt1.0：可靠信道的RDT

RDT，reliable data transmission，可靠数据传输。
最简单情况，底层信道是完全可靠的。
下图是发送方和接受方的有限状态机定义（FSM，finite state machine）。

FSM

rdt_send(data)：套接字收集数据，发送给接收方。
make_pkt(data)：data打包成信息分组，准备发送。
extract(packet, data)：接收方接收的分组，提取data，准备分发给上层应用程序。
deliver_data(data)：分发给上层应用程序。
image.png

有限状态机：饮料机

首先定义几个状态：未投入，已投5毛，已投1元，已投1.5元，已投2元。
比如有一种状态的转移情况是，先投入五毛变成已投入0.5元的状态，再投入五毛变成已投入1元的状态，再投入1元变成已投入两元的状态，点一下可乐，哐当罐子砸下来了，状态变回未投入。
FSM核心思想理解：所以有限种已确定的状态（已投入多少钱），根据不确定的输入（每次投面值不同的钱），在这几种状态中来回转换。

3.2 rdt2.0：有bit差错信道的RDT

分组bit在信道中可能损坏。
ACK：肯定确认，告诉发送方“收到分组且无误”。
NAK：否定确认，告诉发送方“收到分组但有错”。
ARQ协议**：Automatic Repeat Request，自动重传协议，发送方通过接受方的确认来判断是否需要重传。

发送方工作

1、找出差错：检验和
差错检测，例如udp的检验和字段。
纠错技术。
2、告诉有差错：ACK
ACK、NAK。这里有隐患，ACK也可能bit差错，rdt2.1版本解决。
3、重发
有差错就重发分组。

FSM

image.png

停等协议

stop-and-wait，发送方不会发送新分组，除非收到上一个分组的ACK确认。。
image.png

3.3 rdt2.1：“ACK”出错的rdt

也算是分组bit差错问题。

发送方工作

1、接收到受损“ACK”“NAK”就重发
发送方只要收到的ACK或者NAK受损，就直接重发上一个分组。
2、分组增加“序号”防止冗余
序号规则：“序号环”，0、1、2、3、4、5、6、7、0，这是一个8bit的序号。
分组增加“序号”sequence number字段，唯一区分分组，如果接受方收到的seqNo和上一次收到的相同就是重发，丢弃但还是要发送“ACK”，因为发送方他不一定知道，“做**好自己应该做的**”。

FSM

image.png
image.png

3.4 rdt3.0：有bit差错且丢包的rdt

ACK/NAK不能完美解决分组确认，计时“一刀切”，超时就是丢包。

发送方工作

1、检测丢包：“定时器”超时就算丢包
分组发送后，倒计数定时器开始计数。
可能产生重传，比如分组到达之前发送方已经“等不及”重发了。ACK + 序号可以解决。
2、丢包，重传
ACK + 序号可以解决。

FSM

image.png

比特交替协议

分组序号就是1bit，在0和1间交替。
image.png

3.5 流水线可靠数据传输协议

停等效率太低。
如等待确认之前，可以发送3个分组，利用率就可以提高3倍。
流水线：简单理解，比如一开始就可以连续发送3个分组然后等待确认，严格地说应该是可以有N个未确认分组。
image.png
image.png

流水线新问题

1、分组序号范围，1bit序号不够了。
2、分组缓存：发送方必须缓存最少哪些已发送未确认，接收方可能需要缓存（选择重传）。
3、多分组差错：如何处理丢失、损坏、延时过长会影响到分组缓存大小和序号范围。
解决3的方法：
回退N步：Go Back N，GBN。
选择重传：Selective Repeat，SR。

3.6 解决流水线丢包损坏延时：GBN协议

滑动窗口协议，Sliding-Window Protocol。

发送方工作

点击查看【processon】
N：窗口长度window size，N过大拥塞。
base：基序号，已确认的分界线，它和它右边是已发送未确认的，它是最早的已发送未被确认的分组序号。
nextseqnum：下一个序号，已经发送的分界线，它和它右边是未发送的，它是下一个待发分组序号（最小的未使用序号）。
[0, base-1]：已经发送且确认的分组。
[base, nextseqnum-1]：已发送还未被确认的分组。
[nextseqnum, base+N-1]：等待发送的分组。

接收方工作

只需维护一个expectedseqnum标记，收到的分组如果是：
expectedseqnum+1，
expectedseqnum+2，
expectedseqnum+4，
expectedseqnum+5，
expectedseqnum+6，
则交付+1，+2分组给上层。

如果收到的分组是：
expectedseqnum+2，
expectedseqnum+3，
expectedseqnum+4，
expectedseqnum+5，
expectedseqnum+6，
则全部丢弃。
但是，不管怎么样，每收到一个分组，都要响应一个ACK。

窗口滑动理解

滑动+1：收到一个ACK（base+1）。
棍子滑动+1：发送一个分组。
image.png
image.png

窗口滑动示例

image.png

FSM

微信图片_20200822065602.jpg
微信图片_20200822065606.jpg

  1. //上层想send数据
  2. if(nextseqnum - base >= N)        //是否有N个已发送未确认分组
  3.     //告诉上层满了等下再试
  4. else
  5.     产生分组，发送
  6.     rdt_send()

累计确认cumulative acknowledgement，发送方收到一个ACK，里面序号为n，则表示n以前的分组都确认收到。如果已确认分组是1，2，3，5，6，则会丢弃5、6失序分组。

3.7 解决重发剩余分组：选择重传

Selective Repeat，只重传受损或者丢失的分组。
GBN问题：发送0、1、2、3，丢了1，必须重发1、2、3。
SR只重传1。

发送方工作

基于GBN的发送方，收到一个ACK（base+x），就标记这个分组，如果base~(base+y)之间的分组都标记了，窗口就滑动y，每个分组都有一个计时器。
这个时候，[base, nextseqnum-1]之间的每个分组状态都会有不同了，如下图：
点击查看【processon】

接收方工作

base是未接收分组的最小序号，也就是接收和未接收的分界。工作原理举例：
如果收到分组2、3，则向上层交付2345，然后base=6。
如果收到分组2，则向上层交付2，然后base=3。
如果收到分组3、6，则base不变。
点击查看【processon】

3.8 技术总结

检验和：解决分组的bit差错问题。
定时器：解决分组/ACK丢失问题，认为只要是超时，就是分组丢失，，如果是ACK丢失，则会发送一个分组发送两次，导致接受方收到两个相同分组，也就是分组冗余。
序号：解决分组冗余问题。
确认/否定确认：ACK/NAK，解决确认分组接受成功问题，可能是累计确认，比如ACK 2表示2序号以前的都接受成功，可能是逐个确认，ACK 2表示2序号分组接受成功。
流水线：解决停等的效率低下问题。
窗口：GBN，解决流水线的丢失、损坏和延时导致的分组差错。
选择重传：解决需要重发丢包之后分组的问题。

4、面向连接的运输：TCP

connection-oriented，必须要先“握手”，进行一些初始化。
可靠数据传输的可靠是基于不可靠的信道，所以它完全不会寄希望于信道，也就是说，对于TCP和UDP，信道都是完成一样的传输工作，信道并不知道是否有一条TCP存在。
全双工服务full-deplex service。
点对点：单个发送方，单个接收方。
TCP把数据看成是无结构、有序的字节流，给每个字节都编了号。

MTU，Maximium Transmission Unit，最大传输单元，最大链路层帧长度，链路层能传输的最大单元。

MSS，Maximium Segment Size，最大报文段长度，是报文段数据区的最大长度，不包括首部行。
image.png

4.1 TCP报文段格式

点击查看【processon】
确认号：接收方填充，期望从发送方发送的下一字节序号，比如A收到B的0~535字节，现在期望536字节，A就会在发送的报文段确认号中填536。

序号和确认号在Telnet中的应用

假设主机A起始序号：42，B起始序号：79。
image.png

4.2 RTT的估计和超时

RTT，报文段从发送到确认的时间。超时/重传机制解决丢包问题。

RTT估计原理

  1. int EstimatedRTT = getSampleRTT();    //加权RTT
  2. int DevRTT = 0;    //记录SampleRTT偏离EstimatedRTT程度，越小偏离程度越小。
  3. int TimeoutInterval = 1.0;    //超时间隔，初始推荐1.0s
  5. //大多数TCP，隔一段时间，记录一个报文段的RTT。这个RTT叫SampleRTT，
  6. int SampleRTT = getSampleRTT();
  8. //可以发现老的EstimatedRTT的权重很小，很自然，最近的RTT才反应当前链路情况。
  9. //这种加权平均叫EWMA，Exponential Weighted Moving Average.
  10. EstimatedRTT = (1 - 0.125)*SampleRTT + 0.125*EstimatedRTT;
  12. DevRTT = (1 - 0.25)*DevRTT + 0.25*|SampleRTT - EstimatedRTT|;
  14. TimeoutInterval = EstimatedRTT + 4*DevRTT;

4.3 TCP如何数据可靠

冗余ACK技术（快速重传）：发送1、2、3、4分组，接收到1、2、4，接收方再发送一次ACK（2），发送方发现收到3次ACK（2），认为2以后的分组丢失/超时，重发2以后的分组，如果超时时间间隔过长，发送方就能提前知道丢包。可能因为在超时前能重发，所以觉得“快速”吧。
TCP是一个GBN+SR的协议。

4.4 流量控制

流量控制意思就是“控制自己发的多快”。
接收窗口recevie windows，rwnd进行流量控制。
主机A发送数据给B，如果发的过快，B的缓存满了，A再发就溢出了，解决这个问题就叫流量控制，跟拥塞控制如何区别：
好比告诉汽车在高速公路上快速行驶。
拥塞控制就是高速限速<=110km/s。
流量控制就是汽车实际速度（范围就是汽车速度表）。
所以汽车实际速度必须<=110km/s。

“接收窗口”字段排上用场，接收方愿意接收的字节数。只要B随时告诉A，A就能按需发送。

接收窗口计算

rwnd = 接收方的缓存空闲空间，具体算法如下：
image.png

  1. // rwnd：接收窗口大小，接收方缓存区空闲空间大小。
  2. // RcvBuffer：接收方缓存区大小
  3. // lastByteRead：接收方应用读取缓存区的数据的最后一个字节
  4. // lastByteRcv:接收方缓存区数据流的最后一个字节。
  6. //[0, lastByteRead]：接收方应用已读取缓存区数据
  7. //[lastByteRead+1, lastByteRcv]：缓存区中未读取的数据
  8. //lastByteRcv - lastByteRead：缓存区未读取数据大小
  10. //rwnd = RcvBuffer - (lastByteRcv - lastByteRead);
  12. //可以用上面的“窗口滑动”原理帮助理解。

4.5 TCP连接管理

建立连接：TCP三次握手

image.pngimage.png
1、接收方：“我要跟你建立连接。”
接收方发送SYN报文段，内容如下：
SYN = 1
SEQ = client_init_no。
随机生成初始序列号client_init_no，这个生成算法的研究可以避免某些安全攻击。
2、发送方：“可以，你可以建立连接吗？”
发送方收到，分配缓存和变量（这里会有SYN flood attack洪泛攻击的危险，发一堆的SYN又不走第三步，这是第一种DDos攻击，应对方法是SYN Cookie），此时是半开连接。
发送SYNACK报文段，内容如下：
SYN = 1
SEQ = server_init_no
ACK = client_init+no+1
server_init_no是接收方生成的初始序列号。
这里连接起始已经建立。
3、接收方：“好的，我可以建立连接。”
接收方分配缓存和变量。发送报文段如下：
SYN = 0
ACK = server_init_no + 1
数据区 = ……，这时已经可以发数据了。

SYN Cookie
a、上面第2步改成：发送方不做任何事情，只发送报文：
SYN = 1
SEQ = hashEx(srcIP, srcPort, dstIP, dstPort, secretNum)
ACK = client_init+no+1

hashEx：一个复杂散列函数，secretNum只有发送方知道的“秘密数”
b、发送方接受到ACK后，在分配缓存和变量，开启连接。

关闭连接：FIN

image.pngimage.png
1、接收方：“我要关闭连接”
发送FIN报文：FIN = 1
2、发送方：“好的”
发送TCP报文（ACK）
3、发送方：“我也关闭连接”
发送FIN报文：FIN = 1
4、接收方：“好的”
发送TCP报文（ACK）

连接失败：IP或端口不匹配

收到RST报文段：RST = 1。

接收方发送方状态

image.pngimage.png

5、拥塞控制原理

5.1 拥塞原因

1、分组到达速率接近链路容量，引起拥塞。就是龙头出水过快，接龙头的水管直接爆掉。
2、重传因路由器缓存溢出而丢弃（丢失）的分组。
3、大时延引起的“快速重传”导致链路转发多个分组副本。
4、分组可能在路径上被丢失，这浪费了链路资源。

5.2 拥塞控制方法

一，应用层协议做优化减轻链路压力。如出现超时/冗余ACK时，缩小窗口长度；还有前面的RTT加权计算方法。
二、更底层网络优化。如路由器反馈拥塞信息，两种方式，一路由器直接反馈发送方“拥塞分组”，二路由器在经过的分组中增加拥塞字段，接收方在响应给发送方，这至少经历了一个RTT。

5.3 拥塞控制案例：ATM ABR拥塞控制

信元cell，就是数据分组。

核心思想

链路上的数据分组中夹着这资源管理信元（RM，Resource Management cell），由于链路上的交换机产生，用来传递网络拥塞信息。
接收方收到一个RM时，RM可能会说“路上堵车”（CI bit），或者“路上有点堵”（NI bit），或者“具体有多堵”（ER），接收方心想：我收到的好几个数据包都说“路上堵车”（EFCI），不行，我得告诉发送方路上堵了（把RM发给发送方）。

具体实现

每个信元首部有1bit EFCI（Explicit Forward Congestion Indication），指示信元是否经历过拥塞。
每个RM信元首部有1bit CI（Congestion Indication）和1bit NI（No Increase）和32bit ER（Explicit Rate），CI表示严重拥塞，NI表示轻微拥塞，ER表示经过的交换机中最小速率，交换机去更新ER。

6、TCP拥塞控制

TCP会根据ACK的响应速率情况来“适当的”调整拥塞窗口长度（和传输速率），ACK到达太慢就缩小窗口长度，反之就增大窗口长度。TCP拥塞控制需要解决3个问题：
1、如何改变发送速率？
2、如何感知拥塞？
3、改变多少速率？（算法）

6.1 解决思想

1 如何改变发送速率：拥塞窗口

拥塞窗口cwnd，Congestion Window。
当理想情况下，不出现拥塞，TCP的发送速度由接收窗口rwnd决定。
引入拥塞：
lastByteSend - LastByteAcked<=min(cwnd, rwnd)
发送发已经发送未确认的分组必须小于min。
那么发送速率就由rwnd和cwnd共同影响。

2 如何感知拥塞：丢包

1、分组确认超时
2、冗余ACK：同一个分组收到4个ACK，3个冗余的。

3 改变多少速率：拥塞窗口取值

总机制：分组确认的快速影响cwnd值，即分组RTT的值。
分组RTT越小，cwnd迅速增大，暗示网络越畅通嘛。
分组RTT越大，cwnd缓慢增加。

好比，一个向大人要糖果的孩子，每次要到一个糖果，就向前走一点呼喊，大人拒绝一次，就往后退一步继续呼喊。相比TCP这个“有规矩”的好孩子，UDP就是一个“无所谓的”“不守规矩”的坏孩子，UDP每次都站在尽可能前的地方要糖果，要一次不管要没要到都直接走。

6.2 TCP拥塞控制算法

3个部分：“慢”启动，拥塞避免，快速回复。也可以叫3个状态或阶段。
“慢”启动：粗暴试探网络上限。
拥塞避免：小心试探网络上限。
快速回复：根据情况重新上面的试探。

  1. cwnd = MSS;        //初始值，此时发送速率MSS/RTT byte/s
  2. ssthresh = INT_MAX;    //拥塞窗口阈值
  4. //----慢启动阶段----
  5. //其实就是指数增长阶段，一点不慢！！！
  6. while getACK() && cwnd < ssthresh:        //收到一个ack确认
  7.     cwnd += MSS;    //看似线性其实是*2的几何增加，因为一次发送cwnd个分组也就有cwnd个ACK
  8.     send(packets*2);
  9.     if loastPacket():        //出现丢包，暗示网络严重拥塞
  10.         ssthresh = cwnd >> 1;    //拥塞阈值：一半拥塞窗口
  11.         cwnd = 1;
  12. //----慢启动阶段----
  14. //----拥塞避免阶段----
  15. if cwnd >= ssthresh:        //慢增长到达阈值，进入拥塞避免
  16.     while getACK():
  17.         cwnd = MSS*(MSS/cwnd);    //线性增长，一次发送cwnd个分组，最后增长了1个MSS。
  18.         if getDulplicatedACK():        //出现冗余ACK，暗示网络一般拥塞（相比丢包）
  19.             ssthresh = cwnd >> 1;    
  20.             cwnd = MSS;
  21.             //进入快速回复阶段
  22. //----拥塞避免阶段----
  24. //----快速回复阶段----
  25. while get_1_DulplicatedACK():
  26.     cwnd += MSS;
  27.     if get_last_DulplicatedACK():    //收到最后一个冗余ACK
  28.         //进入拥塞避免阶段
  29.     if loastPacket():    //超时丢包
  30.         ssthresh = cwnd >> 1;
  31.         cwnd = MSS;
  32.         //进入慢启动阶段
  33. //----快速回复阶段----

根据上面的算法可以看出，只要出现丢包或者冗余ACK，速度直接砍半，然后线性重新增长，这就是AIMD拥塞控制（Additive-Increase, Multiplicative-Decrease），慢启动阶段其实很短，所以大部分时候都是线性增长。

6.3 FSM

image.png