计算机网络——运输层①
传输层协议简述
本章中主要研究两种传输层协议:TCP协议和UDP协议。 传输层在协议栈中位于网络层之上,网络层提供了主机到主机的逻辑通信,而运输层提供了进程与进程之间的通信。
传输层明显地受制于网络层的功能,但是仍可以实现网络层不能保证的服务。 比如,如果网络层不能保证延迟和带宽,那么传输层协议也无能为力; 相对地,即使网络层是不可靠的,传输层也能实现可靠的通信。
最常见的网络层协议,即IP,仅提供尽力而为的交付服务(Best-effort delivery service),既不保证数据报的交付、不保证交付的顺序,也不保证完整性,因此其也被称为不可靠服务。 但是,IP模型为每一台端系统都分配唯一的IP地址,用来识别主机。 相对的,UDP也是不可靠的,而TCP则提供可靠数据传输。
多路复用与多路分解
正如我们之前介绍的,网络层提供了主机到主机的逻辑通信,而运输层提供了进程与进程之间的通信。 这意味着不同进程之间的通信需要共享相同的网络。 为了把不同进程之间的通信合并到的网络层基础中,所有运输层协议都必须实现多路复用(Multiplexing)和多路分解(Demultiplexing,也称分用)。
更准确地说,多路复用就是为每个数据块封装用于识别的首部信息而生成报文段。 相对地,多路分解就是通过报文段的首部信息把数据交付到正确的套接字中,从而交付到不同的进程中。
为了实现这一目标,每一个套接字连接都有唯一的标识符,即端口号,而每个报文段都含有关于端口号的信息,从而实现报文段和套接字的对应,
对无连接的运输层协议(如UDP协议),只需要知道目的地的IP地址和端口号就可以确定这个套接字。 具体而言,目的地的IP地址允许进行多路复用,所有到达同一IP地址的数据报使用同样的网络层基础; 相对地,到达目的地后,不同目的地端口号的数据报会到达不同的套接字。 尽管源端口号和源IP地址对运输层是不必要的,知道这些信息是有用的,因为收到信息后通常需要进行回复。
对有连接的运输层协议(如TCP协议),我们需要知道目的地和源的IP地址和端口号。
这是因为TCP服务器只使用一个端口号作为“欢迎套接字”(即调用accept
时使用的套接字),在接受连接时还会根据源端口和源IP地址创建新的套接字(即accept
返回的套接字)。
为了区别不同的客户创建连接时形成的套接字,使用源端口和源IP地址是不可或缺的。
用户数据报协议
我们首先观察UDP协议,这几乎可以算最简单的传输层协议,其只进行最低限度的服务,只提供多路复用/分用和最简单的校验功能。 在使用UDP进行通讯时,两端之间不会进行握手,因此UDP是无连接的。
尽管不提供任何保证,UDP仍有一些优点,因此常常被选用:
- 允许应用层对数据发送的精细控制;
- 不需要建立连接,也不需要维护连接状态;
- 首部开销小。
同时UDP也具有一些缺点,特别是大量的UDP流量拥塞会导致TCP降低发送速度,因为TCP具有拥塞控制协议。
当然,通过应用层的修改可以使使用UDP的应用享受可靠传输,但这会导致应用开发的难度增大。
为UDP计算校验和
根据RFC 1071,UDP使用反码(又名一补码)加法计算校验和。
首先,把所有8比特字节两两组合,变成16比特的字,如果只有奇数字节则在末尾填充零。
然后,把它们当作反码进行加法运算。
反码的加法运算有一个特点,即进位的为要绕回到最低位。
因此两个16比特反码1011101110110101
和1000111100001100
的和为0100101011000010
。
这个校验机制只能验证信息的完整性,而不能进行纠错。
当发生损坏时,只能要么丢弃整个分组,要么发出警告。
可靠数据传输
我们接下来研究TCP的一个部分,即可靠的数据传输,是如何做到的。 我们只研究单向的数据传输,双向的传输本质上和两个单向传输没有任何区别,因为TCP/IP在概念上是全双工的。 我们使用分组而非数据报,因为这些技术不止在传输层有用,而是可通用于整个计算机网络。
停止并等待协议
比特差错信道
对完全可靠的信道,我们只需要简单的发送或接收分组即可,此时不会发生差错,因此数据传输也是可靠的。
我们现在考虑不可靠的信道,更特殊的,我们考虑只会发生比特差错的信道,此时暂时不考虑丢包的问题。
我们只需要引入一对简单的肯定确认(positive ACKnowledgment,借助无线电通信的术语,也可称为“已抄收”)和否定确认(Negative AcKnowledgment)消息即可。 这个协议有以下三个要点:
- 差错检测:接收方必须有检测比特差错的能力,这可以通过类似上文UDP校验的算法实现。
- 接收方反馈:接收方必须向发送方反馈自己是否接收到正确的分组。这可以通过ACK和NAK分组实现,仅需一个比特。
- 重发:发送方接收到NAK消息后必须重发上一个报文。
值得注意的是,这个协议正常工作的前提是停等的(Stop and wait),这就是说发送发一次只发送一个分组,然后停止并等待接收方的ACK或NAK消息。 当发送方等待应答消息时,其不能从应用层接收更多的数据。
这种基于重传机制的可靠数据传输协议称为自动重传请求(Automatic Repeat reQuest,ARQ)协议。
然而,这个协议依然具有致命的缺陷,即,如果回复的ACK或NAK消息受损,那么怎么办? 我们假设应答消息依然具有校验和,因此发送方可以发现应答消息损坏,此时有三种可能的方法:
- 递归询问:发送方也向接收方发送NAK消息,要求对方重发。这次重发的NAK也可能损坏,因此这并非非常好的解决方案。
- 增强校验和:强化校验和的算法使其具有纠错功能。如果不考虑丢包那么就能解决问题。
- 冗余分组:如果发现应答消息受损,之间重发上一个分组,无论应答是ACK还是NAK。
冗余分组似乎是最合适的方法,但是其仍然存在一些困难: 首先,冗余分组显然会浪费带宽; 其次,最主要的问题在于,由于消息损坏,接收方无法事先(A priori,先验的)知道某个分组是重发的还是新的。
为了解决这个问题,我们可以为分组附加一个序号(SEQuence number),而接收方只需要检查序号就能知道一个分组是新的还是重发的。
由于停等协议的特点,其一次至多只发送一个分组,因此我们只需要一比特的序号。 接收方只需要检查这次的序号是否和上次相同就能确定是否重发,而发送方重发时序号不变,发送新分组时把序号取反即可。 如果接收方本来期待序号为零的分组,而收到了序号为一的分组,那么可以确定这个分组是重发的,进而丢弃这个分组。 需要注意,无论分组序号如何,如果发现损坏则一律发送NAK要求重发。
我们还可以注意到一个细节,如果我们为应答分组也编上序号,那么NAK是不必要的。 实际上,发送端只关心上一个分组是否正常送达,并不关心其是否是冗余的。 因此,发送端只需要检查应答的分组和刚刚发送的分组序号是否一致即可确定是否要重发上一个分组。 如果发送端发收到了一个编号为零的未损坏ACK应答,那么有两种可能:
- 发送端刚刚发送了一个编号为零的分组,分组正常送达(无论是否是冗余的),下一个发送编号为一的分组。
- 发送端刚刚发送了一个编号为一的分组,接收端收到了损坏的分组,重发这个分组。
如果发送端收到一个损坏ACK应答,那么重发上一个分组,此时这个分组是冗余的,而接收方直接丢弃它并发送对应的ACK响应。
总结一下,我们假设有无限的分组等待发送,对发送端其只有三个动作:
- 初始时,发送序号为零的分组;
- 如果接受的ACK损坏或和才发送的分组序号不符,则重发上一个分组;
- 如果接受的ACK序号和内容正常,那么序号取反(加一),然后发送下一个分组(或等待应用层产生下一个分组)。
对接收端只有两个动作,假设初始时期望收到序号为零的分组:
- 如果收到的分组序号和期望的不一致或分组损坏,那么丢弃这个分组,发送期望序号取反(加一)的ACK分组;
- 如果收到的分组序号和内容正常,那么接受这个分组,发送带有期望序号的ACK分组。
丢包信道
现在我们考虑一个可能丢包的信道,此时我们必须加入某些机制来发现丢失的分组。 在这里,我们使用定时器来发现丢包。
具体而言,发送端在发送一个分组之后就启动定时器,然后如果接收到序号正确的ACK分组就停止并重置定时器,然后序号加一并继续发送下一个分组。 如果定时器超时了(通常通过中断或异常来实现),说明刚刚发出的分组或响应的ACK分组丢失了,就重发上一个分组。
如果ACK丢失或定时器时间过短,这种机制就会发送冗余的分组。 然而在上一种情况下构造的接收端程序可以处理这种分组,因此不需要改变接收端的程序。
此外,我们把所有重发的代码让定时器接管,如果收到错误的ACK则什么都不做,等待定时器超时。
总结一下,发送端这次有四个动作:
- 初始时,发送序号为零的分组并启动定时器;
- 如果定时器超时,那么重发上一个分组并重置定时器;
- 如果接受的ACK损坏或序号不符,那么什么都不做;
- 如果收到正常的ACK,那么停止定时器,序号取反(加一),并发送下一个分组(或等待应用层产生下一个分组)且启动新的定时器。
而接收端的动作和上文所述一致。
实际上,由于定时器的作用,接收端甚至可以不需要在收到错误的包时进行ACK
应答。
这种停等协议对丢包信道工作正常,但是对带宽的使用效率低且在分组失序的情况下会出现问题。
考虑下面这种情况:
- 发送端发送一个序号为零的分组,然后因为超时又重发了一遍;
- 接收端接收到第一个分组,并发送了
ACK 0
; - 发送端接受了接收端的
ACK 0
,然后发送了下一个序号为一的分组; - 接收端接收了第三个序号为一的分组,然后发送
ACK 1
; - 由于失序,发送端发送的第二个序号为零的分组现在才到达,接收端只能认为其是正确的下一个分组,从而产生问题。
通过增加序号空间,而不是仅仅使用一比特的序号,可以缓解失序的问题。 接下来介绍的流水线算法可以解决这些问题。
流水线
现在我们介绍两个常见的流水线化的协议用来解决这两个问题。 所谓流水线化,就是不用发送一个分组然后停止并等待应答消息。 相对地,流水线化的协议一次发送多个分组而不等待确认,然后在收到应答消息之后再做出回应。
为了实现流水线传输,有几个要点需要考虑:
- 必须增加序号范围,至少一次传输中每个分组的序号应该是唯一的;
- 必须加入缓冲,发送方至少需要缓存已发送而未确认的分组,而接收方可能需要缓存已接受的分组;
- 必须提出新的传输协议,以处理各种情况。
本章研究两个重要的流水线协议。
回退N步
回退N步(Go Back N,GBN)协议在发送方维护一个长度固定的窗口,并在确认收到后向前滑动,因此也被称为滑动窗口(Sliding window)协议。
具体而言,发送端选择一个常量$N$作为窗口长度,然后维护两个变量base
和nextseqnum
,分别代表当前窗口的起始序号(称为“基序号”)和下一个待发送的分组的序号。
假设分组线性排列成一个数组,那么下标为在闭区间[base, nextseqnum-1]
之间的所有分组都已经发送而没有确认;
相对地,闭区间[nextseqnum, base+N-1]
之内的分组表示将要发送的分组(如果应用层可以提供足够的的分组的话)。
更前面的分组都是已经确定收到的,而更后面的分组序号尚不可用。
实践中序号通常被保存在一个$k$比特的无符号整数中,因此可用的序号范围是$[0, 2^k-1]$。 序号的运算遵循模$2^k$同余加法群的基本规则。 在使用GBN协议时,我们要求窗口大小必须不能大于可用的最大序号,否则会导致混淆。 在SR协议中这个要求更为严格。
在GBN协议中,ACK序号具有累计确认的语义。
这就是说,如果发送端收到序号为$n$的ACK
分组,那么说明接收端收到了序号从开始到$n$的所有分组。
使用GBN协议的发送端有五种动作:
- 初始动作:设置
base = nextseqnum = 1
; - 发包调用:应用层调用发送报文的接口,此时根据发送窗口状态有两种动作:
- 发送窗口已满(即
nextseqnum = base + N
),此时拒绝发送报文,返回一个错误或缓存分组以等待; - 发送窗口未满,把分组放入窗口中,立刻发送分组,并使
nextseqnum
自增一,发出分组后启动定时器。
- 发送窗口已满(即
- 超时:定时器超时后,重新发送窗口中所有有效的分组(即闭区间
[base, nextseqnum-1]
中的分组),然后重启定时器; - 确认:收到序号为
n
的完整ACK
分组,根据累计确认语义,直接令base = n+1
,此时根据nextseqnum
决定是否重启定时器:- 若
base = nextseqnum
,说明所有分组都已经收到了,停止定时器; - 若
base < nextseqnum
,说明尚有未确认的分组,重启定时器。 - 此外,如果我们选择缓存发送窗口外的分组,那么移动滑窗时需要发送进入滑窗的缓存分组。
- 若
- 损坏:收到损坏的
ACK
分组,什么也不做。
接收端只有三种动作:
- 初始动作:设置
expectedseqnum = 1
、sndpkt = ACK_0
,分别表示期望的分组序号和上一次发送的ACK包(用于指示重传); - 正确接收:如果收到分组未损坏,且其序号等于期望的分组序号
expectedseqnum
,那么接受这个分组,更新sndpkt = ACK_expectedseqnum
并发送; - 损坏:如果收到损坏的分组,或收到的分组序号和
expectedseqnum
不同,那么重发上一个ACK
分组,即sndpkt
。
GBN协议的特点之一在于其接收端并不维护滑动窗口的任何信息,而只维护期望收到的序号; 相对地,发送方如果进行重发,则其必须重发整个窗口的内容,因此得名回退N步。
在出现失序的分组时,这会导致一些流量的浪费。
比如当接收端期望序号为n
的分组,而实际到达的是n+1
号分组,这个分组即使正确也必须被抛弃,然后发送方必须重发整个窗口中的内容。
这个问题在选择重传中得到了一些改善。
选择重传
如果窗口宽度和时延都很大,那么GBN协议由于其必须重传所有窗口中内容的性质而性能大幅下降。 选择重传(Selective Repeat)协议通过只重传需要的分组而规避这一点。
于GBN协议不同,SR协议在发送端和接收端分别维护两个不同的滑动窗口来让接收方缓存所有失序的分组。
这一策略受以下观察的启发:
如果窗口长度为$N$,那么每个序号为$n$接收的分组对应的发送方窗口的基序号(即base
)必须位于$[n-N,n]$之间。
因此如果正确的接收了$n$及其之前的所有分组,那么还可能出现的分组的序号必须在区间$[n-N,n+N)$之中。
所以,只需要缓存从$n$开始一个窗口大小的分组即可,相当于把expectseqnum
换成了区间$[n,n+N)$。
然而,为了实现以分组为单位的重发,我们必须为每个分组分配自己的定时器,这又会带来额外的开销。
我们设发送方的基序号为send_base
,接收端滑窗的基序号为rcv_base
。
发送方仍有五个动作:
- 初始动作:和GBN相同,但把
base
替换为send_base
; - 发包调用:和GBN相同,发出的分组标记为“未确认”;
- 超时:如果一个分组的定时器超时,那么重发这个分组并重启其定时器;
- 确认:如果收到编号为
n
的ACK
分组,那么将n
号分组标记为“已确认”并向前移动滑窗直到send_base
号分组未确认或尚未产生,如果移动滑窗导致新的分组进入滑窗,则发送之; - 损坏:收到损坏的
ACK
分组,什么也不做。
接收方仍有三个动作:
- 初始动作:设置
rcv_base = 1
; - 正确接收:根据收到的分组的序号决定:
- 如果分组序号落在$[rcv\_base-N, rcv\_base-1]$之中,说明这个分组是已接受的分组,但发送方的滑窗尚未移动,发送对应序号的
ACK
分组; - 如果分组序号落在$[rcv\_base,rcv\_base+N-1]$之中,那么发送对应序号的
ACK
分组。特别地,当序号和rcv_base
相等时,向前移动滑窗直到序号为rcv_base
的分组尚未被接受,然后把滑窗rcv_base
扫过的所有已接受的分组交付至应用层。
- 如果分组序号落在$[rcv\_base-N, rcv\_base-1]$之中,说明这个分组是已接受的分组,但发送方的滑窗尚未移动,发送对应序号的
- 损坏:如果收到损坏的分组,或分组的序号不在上述两种情况之一,那么什么也不做。
值得注意的是,SR协议中的ACK
分组没有累计确认的语义,其只表示对一个分组的确认。
另外,由于我们实际上维护了两个长度分别为$N$的滑窗,现在序号的最大值必须大于窗口长度的两倍。
这可以通过考虑所有ACK
分组都丢失的极端情况确认。
乱序的通信
我们在上文的所有讨论都是建立在发送方和接收方的分组不会被重新排序的基础上的。 否则,尽管使用了更大的序号空间,以上两种流水线协议仍不能应对乱序的数据包,即使大大降低了乱序分组干扰正常协议的可能。
实际中,为了确保乱序的通信能够进行,TCP协议使用32位的序号。 除此之外,仅当协议认为含有某个序号的分组已经从网络中消失了,才会重新使用这个序号。 通常假定一个分组在网络中的存活时间为三分钟(RFC 1323),因此三分钟之内不会使用相同的序号标识不同的分组。
总结
为了实现可靠数据传输,我们学习了以下机制:
- 校验和:用于验证数据的完整性;
- 定时器:用于发现丢包现象;
- 序号:用于标识并发现所有分组;
- 肯定与否定确认:用于通知发送方;
- 滑动窗口与流水线:提高性能;
迄今为止,我们介绍的所有可靠传输协议都是ARQ协议。 TCP实际使用的传输方式是GBN和SR协议的结合。