计算机网络 一. 什么是TCP
TCP 协议是一种面向连接的&＃xff0c;为不同主机进程间提供可靠数据传输的协议。TCP 协议假定其所使用的网络栈下层协议&＃xff08;如IP 协议&＃xff09;是非可靠的&＃xff0c;其自身提供机制保证数据的可靠性传输。在目前的网络栈协议族中&＃xff0c;在需要提供可靠性数据传输的应用中&＃xff0c;TCP 协议是首选的&＃xff0c;有时也是唯一的选择。TCP 协议是在最早由Cerf 和Kahn[1]所提出的有关网络数据包传输协议的概念之上建立的。TCP 协议被设计成符合分层协议结构&＃xff0c;工作在ISO/OSI 七层网络模型中的传输层中&＃xff0c;使用网络层协议&＃xff08;如最常见的IP 协议&＃xff09;提供的服务。网络层协议尽最大努力传输上层提供的数据但并不保证数据传输的可靠性。可靠性保证必须由上层协议&＃xff08;如TCP 协议&＃xff09;提供。网络层协议主要完成的工作有&＃xff1a;
1> 实现不同网络&＃xff08;主机&＃xff09;间的数据包路由传递。
2> 在发送端&＃xff08;或中转站&＃xff09;提供数据包分片功能以使数据包大小满足 PMTU&＃xff08;Path-MTU&＃xff09;。
3> 在接收端提供数据包分片重组功能。
4> 负责数据包优先级&＃xff0c;安全性等问题。
传输层协议&＃xff08;主要针对 TCP 协议而言&＃xff09;主要完成的工作有&＃xff08;并非所有的传输层协议都需要提供这些功能如UDP 协议就不提供可靠性数据传输&＃xff09;&＃xff1a;
1> 提供多路复用。
2> 实现数据基本传输功能。
3> 建立通信通道。&＃xff08;三次握手&＃xff09;
4> 提供流量控制。(滑动窗口)
5> 提供数据可靠性传输保证。
数据可靠性传输保证是其中最为重要的方面&＃xff0c;也是TCP 协议区别于其它协议的最重要特性。所谓提供数据可靠性传输不仅仅指将数据成功的由本地主机传送到远端主机&＃xff0c;数据可靠性传输包括如下内容&＃xff1a;
1> 能够处理数据传输过程中被破坏问题。
2> 能够处理重复数据接收问题。
3> 能够发现数据丢失以及对此进行有效解决。
4> 能够处理接收端数据乱序到达问题。
二. 如何保证TCP传输的可靠性&＃xff08;数据超时重传&＃43;数据应答机制&＃xff09;
TCP 协议必须提供对所有这些问题的解决方案方可保证其所声称的数据可靠性传输。TCP协议规范和当前绝大多数TCP 协议实现代码均采用数据重传和数据确认应答机制来完成TCP 协议的可靠性数据传输。数据超时重传和数据应答机制的基本前提是对每个传输的字节进行编号&＃xff0c;即我们通常所说的序列号。数据超时重传是发送端在某个数据包发送出去&＃xff0c;在一段固定时间后如果没有收到对该数据包的确认应答&＃xff0c;则&＃xff08;假定该数据包在传输过程中丢失&＃xff09;重新发送该数据包。而数据确认应答是指接收端在成功接收到一个有效数据包后&＃xff0c;发送一个确认应答数据包给发送端主机&＃xff0c;该确认应答数据包中所包含的应答序列号即指已接收到的数据中最后一个字节的序列号加1&＃xff0c;加1 的目的在于指出此时接收端期望接收的下一个数据包中第一个字节的序列号。数据超时重传和数据确认应答以及对每个传输的字节分配序列号是TCP 协议提供可靠性数据传输的核心本质。
1&＃xff09;数据确认应答数据包中应答序列号的含义
应答序列号并非其表面上所显示的意义&＃xff0c;其实际上是指接收端希望接收的下一个字节的序列号。所以接收端在成功接收到部分数据后&＃xff0c;其发送的应答数据包中应答序列号被设置为这些数据中最后一个字节的序列号加一。所以从其含义上来说&＃xff0c;应答序列号称为请求序列号有时更为合适。应答序列号在TCP 首部中应答序列号字段中被设置。而TCP 首部中序列号字段表示包含该TCP 首部的数据包中所包含数据的第一个字节的序列号&＃xff08;令为N&＃xff09;。如果接收端成功接收该数据包&＃xff0c;之前又无丢失数据包&＃xff0c;则接收端发送的应答数据包中的应答序列号应该为&＃xff1a;N&＃43;LEN。其中LEN 为接收的数据包的数据长度。该应答序列号也是发送端将要发送的下一个数据包中第一个字节的序列号&＃xff08;由此亦可看出上文中将应答序列号称为请求序列号的原因所在&＃xff09;。
2&＃xff09;数据确认应答中的累积效应
TCP 协议中接收端对所接收数据的应答是累积的。累积的含义有二&＃xff1a;
1>应答序列号是逐渐递增的&＃xff0c;这与发送端数据编号是递增的相吻合。
2>不可进行跨越式数据应答。
所谓不可进行跨越式数据应答&＃xff0c;可以以数据包乱序到达为例进行说明。如果由于发送端所选择传输路径的不同&＃xff0c;较后发送的序列号较大的数据包先到达接收端&＃xff0c;而先发送的序列号较小的数据包由于线路问题&＃xff08;或路由器故障&＃xff09;被暂时延迟在网络中&＃xff0c;此时接收端不可对这些序列号较大的数据进行应答。如果接收端需要发送一个应答数据包&＃xff0c;则应答序列号仍然应该设置成对序列号较小的数据包的请求&＃xff08;注意应答序列号指的是接收端希望接收的下一个字节的序列号&＃xff0c;故在数据传输过程中将应答数据包称为数据请求数据包更为合适&＃xff09;。举例来说&＃xff0c;如果接收端目前的应答序列号为201&＃xff0c;表示接收端正在等待发送端发送从201 开始编号的数据&＃xff0c;之后发送端连续发送了两个数据包&＃xff0c;第一个数据包中数据序列号范围为201-300&＃xff0c;第二个数据包中数据序列号范围为301-400。如果由于选择了不同的传输路径造成第二个数据包最先到达接收端&＃xff0c;而第一个数据包在网络中延迟了一段时间&＃xff0c;则接收端不可对第二个数据包进行应答&＃xff0c;即不可发送应答序列号为401 的确认应答数据包&＃xff0c;而是不断发送应答序列号为201的应答数据包直到该序列号的数据到达。我们通常所说的快速重传机制即发送端在连续接收到3 个相同序列号的应答数据包后需要立刻重传应答序列号所表示的数据。因为此时表示极有可能出现了数据包丢失的情况&＃xff0c;如上例中第一个数据包如果丢失在网络中并且发送端重传的相同数据包由于选择相同的线路也未能到达接收端&＃xff0c;则接收端将不断发送应答序列号为201 的应答数据包而不会将应答序列号设置为401。注意此时接收端已接收到序列号从301-400 的数据。
3&＃xff09;重传应答机制与序列号结合&＃xff1a;
1> 能够处理数据在传输过程中被破坏的问题。
首先通过对所接收数据包的校验&＃xff0c;确认该数据包中数据是否存在错误。如果有&＃xff0c;则简单丢弃或者发送一个应答数据包重新对这些数据进行请求。发送端在等待一段时间后&＃xff0c;则会重新发送这些数据。本质上&＃xff0c;数据传输错误的解决是通过数据重传机制完成的。
2> 能够处理接收重复数据问题。
首先利用序列号可以发现数据重复问题。因为每个传输的数据均被赋予一个唯一的序列号&＃xff0c;如果到达的两份数据具有重叠的序列号&＃xff08;如由发送端数据包重传造成&＃xff09;&＃xff0c;则表示出现数据重复问题&＃xff0c;此时只须丢弃其中一份保留另一份即可。多个数据包中数据重叠的情况解决方式类似。本质上&＃xff0c;数据重复问题的解决是通过检查序列号完成的。
3> 能够发现数据丢失以及进行有效解决。
首先必须说明&＃xff0c;此处数据包丢失的概念是指在一段合理时间内&＃xff0c;应该到达的数据包没有到达&＃xff0c;而非我们平常所理解的永远不到达。所以数据包丢失与数据包乱序到达有时在判断上和软件处理上很难区分。数据丢失的判断是猜测性的&＃xff0c;我们无法确定一个数据包一定丢失在传输过程中&＃xff0c;大多是被延迟在网络中&＃xff0c;即实质的问题只是数据包乱序到达。将二者区分开来的一个主要依据是在合理的时间内&＃xff0c;由这个可能丢失的数据包所造成的序列号“空洞“是否能够被填补上。可能的数据丢失一个显然的结果是在接收端接收的数据出现序列号不连续现象。如接收端只接收到序列号从1 到100 的数据包&＃xff0c;之后又接收到序列号从200 到300 的数据包&＃xff0c;而且在一段合理的
时间内&＃xff08;由此基本排除乱序问题&＃xff09;&＃xff0c;序列号从101 到199 的数据一直未到达&＃xff0c;则表示包含序列号从101 到199 的数据包在传输过程中很可能丢失&＃xff08;或者有极不正常的延迟&＃xff09;。对数据包是否丢失判断的另外一个干扰因素是发送端的重传机制&＃xff0c;如果一个序列号较前的数据包在网络中丢失&＃xff0c;造成序列号较后的数据包提前到达接收端&＃xff0c;也会暂时造成序列号不连续&＃xff0c;但由于发送端在没有接收到确认应答时&＃xff0c;会重新发送序列号较前的那个数据包&＃xff0c;如果此后接收端接收到一个重传的数据包&＃xff0c;则仅仅只会在接收端造成数据包乱序到达的表象。无论实质如何&＃xff0c;如果软件实现判断出数据包丢失&＃xff0c;则接收端将通过不断发送对这些丢失的数据的请求数据包&＃xff08;也即应答数据包&＃xff0c;见前文中对数据应答数据包和数据应答累积效应的说明&＃xff09;来迫使发送端重新发送这些数据。通常发送端自身会自发的重传这些未得到对方确认的数据&＃xff0c;但由于重传机制采用指数退避算法&＃xff0c;每次重传的间隔时间均会加倍&＃xff0c;所以通过发送方主动重传机制恢复的时间较长&＃xff0c;而接收端通过不断发送对这些丢失数据的请求&＃xff0c;发送端在接收到三个这样的请求数据包后&＃xff08;三个请求数据包中具有同一个请求序列号--也即前文中所说的应答序列号&＃xff09;&＃xff0c;会立刻触发对这些数据的重新发送&＃xff0c;这称为快速恢复或者快速重传机制。本质上&＃xff0c;对于数据丢失问题的解决是通过数据重传机制完成的。在此过程中序列号和数据确认应答起着关键的作用。
4> 能够处理接收端数据乱序到达问题。
如果通信双方存在多条传输路径&＃xff0c; 则有可能出现数据乱序问题&＃xff0c;即序列号较大的数据先于序列号较小的数据到达&＃xff0c;而发送端确实是按序列号由小到大的顺序发送的。数据乱序的本质是数据都成功到达了&＃xff0c;但到达的顺序不尽如人意。对这个问题的解决相对比较简单&＃xff0c;只需对这些数据进行重新排序即可。本质上&＃xff0c;对数据乱序问题的解决是通过排序数据序列号完成的。
2&＃xff0e;TCP 协议可靠性数据传输软件实现基本原理
由上文可见&＃xff0c;序列号&＃xff0c;数据超时重传和数据确认应答机制保证了 TCP 协议可靠性传输的要求。由于需要对所发送的数据进行编号&＃xff0c;又需要对接收的数据进行应答&＃xff0c;所以使用TCP 协议的通信双方必须通过某种机制了解对方的初始序列号。只有在确切知道对方的初始序列号的情况下&＃xff0c;才能从一开始对所接收数据的合法性进行判断。另外还需要在本地维护一个对方应答的序列号&＃xff0c;以随时跟随对方的数据请求。在最后通信通道关闭时&＃xff0c;可以确知本地发送的数是否已被对方完全接收&＃xff1b;此外这个对方应答序列号在控制本地数据通量方面也发挥着重要的作用&＃xff1a;用本地发送序列号减去对方应答序列号则可以立刻得知目前发送出去的数据有多少没有得到对方的应答。
综上所述&＃xff0c;可靠性传输要求通信双方维护如下序列号&＃xff1a;
SND.NXT本地将要发送的下一个序列号。该变量对应TCP 首部中序列号字段。表示该数据包中所包含数据的第一个字节的序列号。每次发送一个数据包&＃xff0c;该变量都需要进行更新&＃xff1a;SND.NXT &＃61; SND.NXT &＃43; 本次发送的数据包中包含的数据长度SND.ACKED
对方对本地所发送数据到目前为止进行了应答的序列号&＃xff0c;换句话说&＃xff0c;SND.ACKED&＃43;1 表示本地已发送出去但尚未得到对方应答的数据集中对应的第一个&＃xff08;最小的&＃xff09;序列号。RCV.NXT本地希望接收的下一个序列号。该序列号被称为应答序列号&＃xff0c;也可称为请求序列号&＃xff0c;在本地发送的应答报文中&＃xff0c;TCP 首部中应答序列号字段即设置为该变量的值&＃xff0c;表示本地希望从对方接收的下一个字节的序列号。
图 1&＃xff08;上图&＃xff09;显示了TCP 首部格式。序列号字段对应前文中SND.NXT 变量&＃xff0c;应答序列号字段对应前文中RCV.NXT 变量。ACK 标志位设置为1 表示这是一个应答数据包。实际上对于 TCP 协议而言&＃xff0c;在成功建立连接后&＃xff0c;此后发送的所有数据包的ACK 标志位均被设置为1&＃xff0c;即在传送正常数据的同时传送应答&＃xff0c;如此处理可以减少网络中传输的数据包数量。
三.TCP如何建立连接
图 1TCP 首部格式中SYN 标志位仅使用在建立TCP 连接的过程中&＃xff0c;TCP 建立连接的过程被称为“三路握手“连接&＃xff0c;即一般通信双方共需要传输三个数据包方能成功建立一个TCP 连接。我们通常将建立连接作为使用TCP 协议理所当然的前导过程&＃xff0c;但很少去质疑这样一个建立连接过程的必要性。实际上&＃xff0c;在上文中已经做出部分解释&＃xff0c;使用TCP 协议必须首先建立一个连接是保证TCP 协议可靠性数据传输的基本前提&＃xff08;当然由于TCP 协议是一个有状态协议&＃xff0c;必须通过某种机制进行通信双方状态上的同步&＃xff0c;而建立连接就是这样一种机制&＃xff09;。至于为何需要三个数据包&＃xff0c;原因是建立连接过程中信息的交换必须至少使用三个数据包&＃xff0c;从下文的分析来看&＃xff0c;建立连接最多需要使用四个数据包。需要再次提到的是&＃xff1a;SYN 标志位只是用在建立连接的三个&＃xff08;或者四个&＃xff09;数据包中&＃xff0c;一旦连接建立完成后&＃xff0c;之后发送的所有数据包不可设置SYN 标志位。单从保证数据可靠性传输角度而言&＃xff0c;TCP 协议需要在正式数据传输之前首先进行某些信息的交换&＃xff0c;这个信息即是双方的初始序列号&＃xff08;另外的一些信息包括最大报文长度通报等&＃xff09;。
诚如前文所述&＃xff0c;序列号的使用对于 TCP 协议而言至关重要&＃xff0c;在正式数据传输之前&＃xff0c;双方必须得到对方的初始字节数据的编号&＃xff0c;这样才有可能对其所接收数据的合法性进行判断&＃xff0c;才有其它的对数据重复&＃xff0c;数据重叠等一系列问题的进一步判别和解决。故交换各自的初始序列号必须在正式数据传输之前完成&＃xff0c;我们美其名曰这个过程为连接建立过程。至于双方TCP 协议各自状态的更新主要是软件设计上可靠性保证的一个辅助&＃xff0c;并非这个所谓的建立过程所主要关注的问题。
初始序列号的交换从最直接的角度来说需要四个数据包&＃xff1a;
1> 主机 A 向主机B 发送其初始序列号。
2> 主机 B 向主机A 确认其发送的初始序列号。
3> 主机 B 向主机A 发送其初始序列号。
4> 主机 A 向主机B 确认其发送的初始序列号。
我们将<2><3>两步合为一步&＃xff0c;即B 向A 确认其&＃xff08;A 之前发送的&＃xff09;初始序列号的同时发送其&＃xff08;即B 自己的&＃xff09;初始序列号。所谓确认数据包即将数据包的ACK 标志位设置为1 即可。注意这三个&＃xff08;或四个&＃xff09;数据包中SYN 标志位设置为1&＃xff0c;而且SYN 标志位也仅在这三个&＃xff08;或四个&＃xff09;数据包中被设置为1。
此处有一个问题&＃xff1a;即A&＃xff0c;B 主机在通报各自初始序列号的同时能否传输一些正常数据&＃xff0c;原理上可以&＃xff08;TCP 协议规范上并没有说不可以&＃xff09;&＃xff0c;但是大多数实现在通报初始序列号时都不附带正常数据&＃xff0c;而是将其作为一个单独的过程&＃xff0c;由此正式确立建立连接一说。
四.TCP如何拆除连接
当前连接的双方都可以发起拆除连接操作&＃xff0c;但简单的拆除连接可能会造成数据丢失。为此&＃xff0c;TCP采用四次握手的方式拆除连接。
四次握手与三次握手类似&＃xff1a;
①1发拆除请求
②2收到请求&＃xff0c;并发确认&＃xff0c;1收到该确认后&＃xff0c;不再发送数据&＃xff0c;但任然会接收数据&＃xff08;半连接&＃xff09;
③2发拆除请求
④1收到请求&＃xff0c;并确认&＃xff0c;到此拆除完成
五. 为什么拆除连接要比建立连接多一次握手
六.TCP滑动窗口机制
(1).窗口机制
滑动窗口协议的基本原理就是在任意时刻&＃xff0c;发送方都维持了一个连续的允许发送的帧的序号&＃xff0c;称为发送窗口&＃xff1b;同时&＃xff0c;接收方也维持了一个连续的允许接收的帧的序号&＃xff0c;称为接收窗口。发送窗口和接收窗口的序号的上下界不一定要一样&＃xff0c;甚至大小也可以不同。不同的滑动窗口协议窗口大小一般不同。发送方窗口内的序列号代表了那些已经被发送&＃xff0c;但是还没有被确认的帧&＃xff0c;或者是那些可以被发送的帧。下面举一个例子&＃xff08;假设发送窗口尺寸为2&＃xff0c;接收窗口尺寸为1&＃xff09;&＃xff1a;
分析&＃xff1a;①初始态&＃xff0c;发送方没有帧发出&＃xff0c;发送窗口前后沿相重合。接收方0号窗口打开&＃xff0c;等待接收0号帧&＃xff1b;②发送方打开0号窗口&＃xff0c;表示已发出0帧但尚确认返回信息。此时接收窗口状态不变&＃xff1b;③发送方打开0、1号窗口&＃xff0c;表示0、1号帧均在等待确认之列。至此&＃xff0c;发送方打开的窗口数已达规定限度&＃xff0c;在未收到新的确认返回帧之前&＃xff0c;发送方将暂停发送新的数据帧。接收窗口此时状态仍未变&＃xff1b;④接收方已收到0号帧&＃xff0c;0号窗口关闭&＃xff0c;1号窗口打开&＃xff0c;表示准备接收1号帧。此时发送窗口状态不变&＃xff1b;⑤发送方收到接收方发来的0号帧确认返回信息&＃xff0c;关闭0号窗口&＃xff0c;表示从重发表中删除0号帧。此时接收窗口状态仍不变&＃xff1b;⑥发送方继续发送2号帧&＃xff0c;2号窗口打开&＃xff0c;表示2号帧也纳入待确认之列。至此&＃xff0c;发送方打开的窗口又已达规定限度&＃xff0c;在未收到新的确认返回帧之前&＃xff0c;发送方将暂停发送新的数据帧&＃xff0c;此时接收窗口状态仍不变&＃xff1b;⑦接收方已收到1号帧&＃xff0c;1号窗口关闭&＃xff0c;2号窗口打开&＃xff0c;表示准备接收2号帧。此时发送窗口状态不变&＃xff1b;⑧发送方收到接收方发来的1号帧收毕的确认信息&＃xff0c;关闭1号窗口&＃xff0c;表示从重发表中删除1号帧。此时接收窗口状态仍不变。
若从滑动窗口的观点来统一看待1比特滑动窗口、后退n及选择重传三种协议&＃xff0c;它们的差别仅在于各自窗口尺寸的大小不同而已。1比特滑动窗口协议&＃xff1a;发送窗口&＃61;1&＃xff0c;接收窗口&＃61;1&＃xff1b;后退n协议&＃xff1a;发窗口>1&＃xff0c;接收窗口>1&＃xff1b;选择重传协议&＃xff1a;发送窗口>1,接收窗口>1。
(2).1比特滑动窗口协议
当发送窗口和接收窗口的大小固定为1时&＃xff0c;滑动窗口协议退化为停等协议&＃xff08;stop&＃xff0d;and&＃xff0d;wait&＃xff09;。该协议规定发送方每发送一帧后就要停下来&＃xff0c;等待接收方已正确接收的确认&＃xff08;acknowledgement&＃xff09;返回后才能继续发送下一帧。由于接收方需要判断接收到的帧是新发的帧还是重新发送的帧&＃xff0c;因此发送方要为每一个帧加一个序号。由于停等协议规定只有一帧完全发送成功后才能发送新的帧&＃xff0c;因而只用一比特来编号就够了。其发送方和接收方运行的流程图如图所示。
(3).后退n协议
由于停等协议要为每一个帧进行确认后才继续发送下一帧&＃xff0c;大大降低了信道利用率&＃xff0c;因此又提出了后退n协议。后退n协议中&＃xff0c;发送方在发完一个数据帧后&＃xff0c;不停下来等待应答帧&＃xff0c;而是连续发送若干个数据帧&＃xff0c;即使在连续发送过程中收到了接收方发来的应答帧&＃xff0c;也可以继续发送。且发送方在每发送完一个数据帧时都要设置超时定时器。只要在所设置的超时时间内仍收到确认帧&＃xff0c;就要重发相应的数据帧。如&＃xff1a;当发送方发送了N个帧后&＃xff0c;若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息&＃xff0c;则该帧被判为出错或丢失&＃xff0c;此时发送方就不得不重新发送出错帧及其后的N帧。
从这里不难看出&＃xff0c;后退n协议一方面因连续发送数据帧而提高了效率&＃xff0c;但另一方面&＃xff0c;在重传时又必须把原来已正确传送过的数据帧进行重传&＃xff08;仅因这些数据帧之前有一个数据帧出了错&＃xff09;&＃xff0c;这种做法又使传送效率降低。由此可见&＃xff0c;若传输信道的传输质量很差因而误码率较大时&＃xff0c;连续测协议不一定优于停止等待协议。此协议中的发送窗口的大小为k&＃xff0c;接收窗口仍是1。
(4).选择重传协议
在后退n协议中&＃xff0c;接收方若发现错误帧就不再接收后续的帧&＃xff0c;即使是正确到达的帧&＃xff0c;这显然是一种浪费。另一种效率更高的策略是当接收方发现某帧出错后&＃xff0c;其后继续送来的正确的帧虽然不能立即递交给接收方的高层&＃xff0c;但接收方仍可收下来&＃xff0c;存放在一个缓冲区中&＃xff0c;同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后&＃xff0c;就可以原已存于缓冲区中的其余帧一并按正确的顺序递交高层。这种方法称为选择重发(SELECTICE REPEAT)&＃xff0c;其工作过程如图所示。显然&＃xff0c;选择重发减少了浪费&＃xff0c;但要求接收方有足够大的缓冲区空间。
滑动窗口协议
仍然考虑链路的延迟与带宽的乘积为8 K B&＃xff0c;帧尺寸为1 K B的情形。让发送方在收到第一帧的A C K的同时准备发送第九帧。允许我们这样做的算法称为滑动窗口&＃xff08; sliding window&＃xff09;&＃xff0c;时间线如图2 - 2 1所示。
1. 滑动窗口算法
滑动窗口算法工作过程如下。首先&＃xff0c;发送方为每1帧赋一个序号&＃xff08;sequence number&＃xff09;&＃xff0c;记作S e q N u m。现在&＃xff0c;让我们忽略S e q N u m是由有限大小的头部字段实现的事实&＃xff0c;而假设它能无限增大。发送方维护3个变量&＃xff1a;发送窗口大小&＃xff08;send window size&＃xff09;&＃xff0c;记作S W S&＃xff0c;给出发送方能够发
送但未确认的帧数的上界&＃xff1b; L A R表示最近收到的确认帧&＃xff08; last acknowledgement re c e i v e d&＃xff09;的序号&＃xff1b;L F S表示最近发送的帧&＃xff08;last frame sent&＃xff09;的序号&＃xff0c;发送方还维持如下的不变式&＃xff1a;
LAR-LFR≤RWS
当一个确认到达时&＃xff0c;发送方向右移动L A R&＃xff0c;从而允许发送方发送另一帧。同时&＃xff0c;发送方为所发的每个帧设置一个定时器&＃xff0c;如果定时器在A C K到达之前超时&＃xff0c;则重发此帧。注意&＃xff1a;发送方必须存储最多S W S个帧&＃xff0c;因为在它们得到确认之前必须准备重发。
接收方维护下面3个变量&＃xff1a;接收窗口大小&＃xff08;receive window size&＃xff09;&＃xff0c;记为RW S&＃xff0c;给出接收方所能接收的无序帧数目的上界&＃xff1b; L A F表示可接收帧&＃xff08;l a rgestacceptable frame&＃xff09;的序号&＃xff1b;L F R表示最近收到的帧&＃xff08;last frame re ce i v e d&＃xff09;的序号。接收方也维持如下不变式&＃xff1a;
LFS-LAR≤SWS
当一个具有顺序号S e q N u m的帧到达时&＃xff0c;接收方采取如下行动&＃xff1a;如果S e q N u m≤L F R或S e q N u m > L A F&＃xff0c;那么帧不在接收窗口内&＃xff0c;于是被丢弃&＃xff1b;如果L F R&＃xff1c;Se q N u m≤L A F&＃xff0c;那么帧在接收窗口内&＃xff0c;于是被接收。现在接收方需要决定是否发送一个A C K。设S e q N u m To A C K表示未被确认帧的最大序号&＃xff0c;则序号小于或等于S e q N u m To Ac k的帧都已收到。即使已经收到更高序号的分组&＃xff0c;接收方仍确认S e q N u m To A c k的接收。这种确认被称为是累积的&＃xff08;c u m u l a t i v e&＃xff09;。然后它设置L F R &＃61; S e q Nu m To A c k&＃xff0c;并调整L A F &＃61; L F R &＃43; RW S。例如&＃xff0c;假设L F R&＃61; 5&＃xff08;即&＃xff0c;上次接收方发送的A C K是为了确认顺序号5的&＃xff09;&＃xff0c;并且RWS &＃61; 4。这意味着L A F &＃61; 9。如果帧7和8到达&＃xff0c;则存储它们&＃xff0c;因为它们在接收窗口内。然而并不需要发送A C K&＃xff0c;因为帧6还没有到达。帧7和8被称为是错序到达的。&＃xff08;从技术上讲&＃xff0c;接收方可以在帧7和8到达时重发帧5的A C K。&＃xff09;如果帧6当时到达了&＃xff08;或许它在第一次丢失后又重发从而晚到&＃xff0c;或许它只是被延迟了&＃xff09;&＃xff0c;接收方确认帧8&＃xff0c;L F R置为8&＃xff0c;L A F置为1 2。如果实际上帧6丢失了&＃xff0c;则出现发送方超时&＃xff0c;重发帧6。我们看到&＃xff0c;当发生超时时&＃xff0c;传输数据量减少&＃xff0c;这是因为发送方在帧6确认之前不能向前移动窗口。这意味着分组丢失时&＃xff0c;此方案将不再保证管道满载。注意&＃xff1a;分组丢失时间越长&＃xff0c;这个问题越严重。
注意&＃xff0c;在这个例子中&＃xff0c;接收方可以在帧7刚一到达时就为帧6发送一个认帧N A K&＃xff08;negative acknowledgment&＃xff09;。然而&＃xff0c;由于发送方的超时机制足以发现这种情况&＃xff0c;发送N A K反而为发送方增加了复杂性&＃xff0c;因此不必这样做。正如我们已提到的&＃xff0c;当帧7和8到达时为帧5发送一个额外的A C K是合理的&＃xff1b;在某些情况下&＃xff0c;发送方可以使用重复的A C K作为一个帧丢失的线索。这两种方法都允许早期的分组丢失检测&＃xff0c;有助于改进性能。
关于这个方案的另一个变种是使用选择确认&＃xff08;selective acknowledgements&＃xff09;。即&＃xff0c;接收方能够准确地确认那些已收到的帧&＃xff0c;而不只是确认按顺序收到最高序号的帧。因此&＃xff0c;在上例中&＃xff0c;接收方能够确认帧7、8的接收。如果给发送方更多的信息&＃xff0c;就能使其较容易地保持管道满载&＃xff0c;但增加了实现的复杂性。
发送窗口大小是根据一段给定时间内链路上有多少待确认的帧来选择的&＃xff1b;对于一个给定的延迟与带宽的乘积&＃xff0c;S W S是容易计算的。另一方面&＃xff0c;接收方可以将RW S设置为任何想要的值。通常的两种设置是&＃xff1a;RW S&＃61; 1&＃xff0c;表示接收方不存储任何错序到达的帧&＃xff1b; RW S&＃61;S W S&＃xff0c;表示接收方能够缓存发送方传输的任何帧。由于错序到达的帧的数目不可能超过S W S个&＃xff0c;所以设置RWS >S W S没有意义。
2. 有限顺序号和滑动窗口
现在我们再来讨论算法中做过的一个简化&＃xff0c;即假设序号是可以无限增大的。当然&＃xff0c;实际上是在一个有限的头部字段中说明一个帧的序号。例如&＃xff0c;一个3比特字段意味着有8个可用序号0 ~ 7。因此序号必须可重用&＃xff0c;或者说序号能回绕。这就带来了一个问题&＃xff1a;要能够区别同一序号的不同次发送实例&＃xff0c;这意味着可用序号的数目必须大于所允许的待确认帧的数目。例如&＃xff0c;停止等待算法允许一次有1个待确认帧&＃xff0c;并有2个不同的序号。
假设序号空间中的序号数比待确认的帧数大1&＃xff0c;即S W S ≤ M A a xS e q N u m -1 &＃xff0c;其中M a x Seq N u m 是可用序号数。这就够了吗&＃xff1f;答案取决于RW S 。如果RW S &＃61; 1&＃xff0c;那么MaxSeqNum≥SWS&＃43;1是足够了。如果RW S等于S W S&＃xff0c;那么有一个只比发送窗口尺寸大1的M a x S e q N u m是不够的。为看清这一点&＃xff0c;考虑有8个序号0 ~ 7的情况&＃xff0c;并且S W S &＃61; RW S &＃61; 7。假设发送方传输帧0 ~ 6&＃xff0c;并且接收方成功接收&＃xff0c;但A C K丢失。接收方现在希望接收帧7&＃xff0c;0 ~ 5&＃xff0c;但发送方超时&＃xff0c;然后发送帧0 ~ 6。不幸的是&＃xff0c;接收方期待的是第二次的帧0 ~ 5&＃xff0c;得到的却是第一次的帧0 ~ 5。这正是我们想避免的情况。
结果是&＃xff0c;当RW S &＃61; S W S时&＃xff0c;发送窗口的大小不能大于可用序号数的一半&＃xff0c;或更准确地说&＃xff0c;SWS<(Maxseqnum&＃43;1)/2直观地&＃xff0c;这说明滑动窗口协议是在序号空间的两半之间变换&＃xff0c;就像停止等待协议的序号是在0和1之间变换一样。唯一的区别是&＃xff0c;它在序号空间的两半之间连续滑动而不是离散的变换。
注意&＃xff0c;这条规则是特别针对RW S &＃61; S W S的。我们把确定适用于RW S和S W S的任意值的更一般的规则留做一个练习。还要注意&＃xff0c;窗口的大小和序号空间之间的关系依赖于一个很明显以至于容易被忽略的假设&＃xff0c;即帧在传输中不重新排序。这在直连的点到点链路上不能发生&＃xff0c;因为在传输过程中一个帧不可能赶上另一个帧。然而&＃xff0c;我们将在第5章看到用在一个不同环境中的滑动窗口算法&＃xff0c;并且需要设计另一条规则。
3. 滑动窗口的实现
下面的例程说明我们如何实现滑动窗口算法的发送和接收的两个方面。该例程取自一个正在使用的协议&＃xff0c;称为滑动窗口协议S W P&＃xff08;Sliding Window Pro t o c o l&＃xff09;。为了不涉及协议图中的邻近协议&＃xff0c;我们用H L P&＃xff08;高层协议&＃xff09;表示S W P上层的协议&＃xff0c;用L I N K&＃xff08;链路层协议&＃xff09;表示S W P下层的协议。我们先定义一对数据结构。首先&＃xff0c;帧头部非常简单&＃xff1a;它包含一个序号&＃xff08; S e q N u m&＃xff09;和一个确认号&＃xff08; A c k N u m&＃xff09;。它还包含一个标志&＃xff08; F l a g s&＃xff09;字段&＃xff0c;表明帧是一个A C K帧还是携带数据的帧。
其次&＃xff0c;滑动窗口算法的状态有如下结构。对于协议发送方&＃xff0c;该状态包括如上所述的变量L A R和L F S&＃xff0c;以及一个存放已发出但尚未确认的帧的队列&＃xff08; s e n d Q&＃xff09;。发送方状态还包含一个计数信号量&＃xff08; counting semaphore&＃xff09;&＃xff0c;称为s e n d Wi n d o w N o t F u l l。下面我们将会看到如何使用它&＃xff0c;但一般来说&＃xff0c;信号量是一个支持s e m Wa i t和s e m S i g n a l操作的同步原语。每次调用S e m S i g n al&＃xff0c;信号量加1&＃xff0c;每次调用S e m Wa i t&＃xff0c;信号量减1。如果信号量减小&＃xff0c;导致它的值小于0&＃xff0c;那么调用进程阻塞&＃xff08;挂起&＃xff09;。一旦执行了足够的s e m S i g n a l操作而使信号量的值增大到大于0&＃xff0c;在调用s e m Wa i t的过程中阻塞的进程就允许被恢复。
对于协议的接收方&＃xff0c;如前所述&＃xff0c;该状态包含变量L F R &＃xff0c;加上一个存放已收到的错序帧的队列&＃xff08;r e c v Q&＃xff09;。最后&＃xff0c;虽然未显示&＃xff0c;发送方和接收方的滑动窗口的大小分别由常量S W S和RW S表示。
S W P的发送方是由s e n d S W P过程实现的。这个例程很简单。首先&＃xff0c; s e m Wa i t使这个进程在一个信号量上阻塞&＃xff0c;直到它可以发另一帧。一旦允许继续&＃xff0c; s e n d S W P设置帧头部中的顺序号&＃xff0c;将此帧的拷贝存储在发送队列&＃xff08; s e n d Q&＃xff09;中&＃xff0c;调度一个超时事件以便处理帧未被确认的情况&＃xff0c;并将帧发给低层协议。
值得注意的一个细节是刚好在调用m s g A d d H dr之前调用s t o r e _ s w p _ h d r。该例程将存有S W P头部的C语言结构&＃xff08; s t a t e -> h d r&＃xff09;转化为能够安全放在消息前面的字节串&＃xff08; h b u f&＃xff09;。该例程&＃xff08;未给出&＃xff09;必须将头部中的每一个整数字段转化为网络字节顺序&＃xff0c;并且去掉编译程序加入C语言结构中的任意填充。7 . 1节将详细讨论字节顺序的问题&＃xff0c;但现在&＃xff0c;假设该例程将多字整数中最高有效位放在最高地址字节就足够了。
这个例程的另一个复杂性是使用s e m Wa i t 和s e n dW i n d ow N o t F u l l 信号量。S e n dWi n d o w N o t F u l l被初始化为发送方滑动窗口的大小S W S&＃xff08;未给出这一初始化&＃xff09;。发送方每传输一帧&＃xff0c; s e m Wa i t操作将这个数减1&＃xff0c;如果减小到0&＃xff0c;则阻塞发送方进程。每收到一个A C K&＃xff0c;在d e l i v e r SW P中调用s e m S i g n a l操作&＃xff08;见下面&＃xff09;将此数加1&＃xff0c;从而激活正在等待的发送方进程。
在继续介绍S W P的接收方之前&＃xff0c;需要调整一个看上去不一致的地方。一方面&＃xff0c;我们说过&＃xff0c;高层协议通过调用s e n d操作来请求低层协议的服务&＃xff0c;所以我们就希望通过S W P发送消息的协议能够调用s e n d&＃xff08;S W P, p a c k e t&＃xff09;。另一方面&＃xff0c;用来实现S W P的发送操作的过程叫做s e n d S W P&＃xff0c;并且它的第一个参数是一个状态变量&＃xff08; S w p S t a t e&＃xff09;。结果怎样呢&＃xff1f;答案是&＃xff0c;操作系统提供了粘结代码将对s e n d的一般调用转化为对s e n d S W P的特定协议调用的粘结代码。这个粘结代码将s e n d的第一个参数&＃xff08;协议变量S W P&＃xff09;映射为一个指向s e n d S W P的函数指针和一个指向S W P工作时所需的协议状态的指针。我们之所以通过一般函数调用使高层协议间接调用特定协议函数&＃xff0c;是因为我们想限制高层协议中对低层协议编码的信息量。这使得将来能够比较容易地改变协议图的配置。现在来看d e l i v e r操作的S W P的特定协议实现&＃xff0c;它在过程d e l i v e r SW P中实现。这个例程实际上处理两种不同类型的输入消息&＃xff1a;本结点已发出帧的A C K和到达这个结点的数据帧。在某种意义上&＃xff0c;这个例程的ACK部分是与send SWP中所给算法的发送方相对应的。通过检验头部的F l a g s字段可以确定输入的消息是ACK还是一个数据帧。注意&＃xff0c;这种特殊的实现不支持数据帧中捎带A C K。当输入帧是一个ACK时&＃xff0c;delive rSWP仅仅在发送队列&＃xff08;send Q&＃xff09;中找到与此ACK相应的位置&＃xff08;slot&＃xff09;&＃xff0c;取消超时事件&＃xff0c;并且释放保存在那一位置的帧。由于A C K可能是累积的&＃xff0c;所以这项工作实际上是在一个循环中进行的。对于这种情况值得注意的另一个问题是子例程swp In Wind o w的调用。这个子例程在下面给出&＃xff0c;它确保被确认帧的序号是在发送方当前希望收到的A C K的范围之内。
当输入帧包含数据时&＃xff0c; d e l i v e r S W P首先调用m s g S t r i pH d r和l o a d _ s w p _ h d r以便从帧中提取头部。例程l o a d _ s w p_ h d r对应着前面讨论的s t o r e _ s w p _ h d r&＃xff0c;它将一个字节串转化为容纳S W P头部的C语言数据结构。然后d e l i v e r SW P调用s w p I n Wi n d o w以确保帧序号在期望的序号范围内。如果是这样&＃xff0c;例程在已收到的连续的帧的集合上循环&＃xff0c;并通过调用d e l i v e r HL P例程将它们传给上层协议。它也要向发送方发送累积的A C K&＃xff0c;但却是通过在接收队列上循环来实现的&＃xff08;它没有使用本节前面给出的s e q N u m To Ac k变量&＃xff09;。
最后&＃xff0c;s w p I n Window是一个简单的子例程&＃xff0c;它检查一个给定的序号是否落在某个最大和最小顺序号之间。
4. 帧顺序和流量控制
滑动窗口协议可能是计算机网络中最著名的算法。然而&＃xff0c;关于该算法易产生混淆的是&＃xff0c;它可以有三个不同的功能&＃xff0c;第一个功能是本节的重点&＃xff0c;即在不可靠链路上可靠地传输帧。&＃xff08;一般来说&＃xff0c;该算法被用于在一个不可靠的网络上可靠地传输消息。&＃xff09;这是该算法的核心功能。
滑动窗口算法的第二个功能是用于保持帧的传输顺序。这在接收方比较容易实现&＃xff0c;因为每个帧有一个序号&＃xff0c;接收方要保证已经向上层协议传递了所有序号比当前帧小的帧&＃xff0c;才向上传送该当前帧。即&＃xff0c;接收方缓存了&＃xff08;即没有传送&＃xff09;错序的帧。本节描述的滑动窗口算法确实保持了帧的顺序&＃xff0c;尽管我们可以想象一个变异&＃xff0c;即接收方没有等待更早传送的帧都到达就将帧传给下一个协议。我们可以提出的一个问题是&＃xff1a;我们是否确实需要滑动窗口协议来保持帧的顺序&＃xff0c;或者&＃xff0c;这样的功能在链路层是否是不必要的。不幸的是&＃xff0c;我们还没有看到足够多的网络体系结构来回答这个问题我们首先需要理解的是&＃xff0c;点到点链路序列如何由交换机连接而形成一条端到端的路径。
滑动窗口算法的第三个功能是&＃xff0c;它有时支持流量控制&＃xff08;f l o w c o n t ro l&＃xff09;&＃xff0c;它是一种接收方能够控制发送方使其降低速度的反馈机制。这种机制用于抑制发送方发送速度过快&＃xff0c;即抑制传输比接收方所能处理的更多的数据。这通常通过扩展滑动窗口协议完成&＃xff0c;使接收方不仅确认收到的帧&＃xff0c;而且通知发送方它还可接收多少帧。可接收的帧数对应着接收方空闲的缓冲区数。在按序传递的情况下&＃xff0c;在将流量控制并入滑动窗口协议之前&＃xff0c;我们应该确信流量控制在链路层是必要的。
尚未讨论的一个重要概念是系统设计原理&＃xff0c;我们称其为相关性分离&＃xff08;separation of concerns&＃xff09;。即&＃xff0c;你必须小心区别有时交织在一种机制中的不同功能&＃xff0c;并且你必须确定每一个功能是必要的&＃xff0c;而且是被最有效的方式支持的。在这种特定的情况下&＃xff0c;可靠传输、按序传输和流量控制有时组合在一个滑动窗口协议里&＃xff0c;我们应该问问自己&＃xff0c;在链路层这样做是否正确。带着这样的疑问&＃xff0c;我们将在第3章&＃xff08;说明X. 2 5网如何用它实现跳到跳的流量控制&＃xff09;和第5章&＃xff08;描述T C P如何用它实现可靠的字节流信道&＃xff09;重新考虑滑动窗口算法。
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有