通信网络基础2-1

第二章端到端的传输协议通信与信息工程学院2024/10/31第2章端到端的传输协议本章将讨论在物理层的比特管道上如何形成一条可靠的业务通道为上层提供可靠的服务。要解决的问题：如何标识高层送下来的数据块（分组）的起止位置；如何发现传输中的比特错误；发现错误后，如何消除这些错误。2024/10/31第2章端到端的传输协议

2.1组帧技术2.2链路层的差错控制技术

2.3标准数据链路控制协议及其初始化

2.4网络层和运输层的点对点传输协议2024/10/312.1组帧技术当数据链路层将网络层的分组连续送到物理层进行传输时，有一个问题要解决，如何决定什么时刻是一帧开始？什么时刻是一帧结束？哪一段是差错校验的比特？这就是组帧技术需解决的问题。

1010101111001101101110100011100101010011011100010011101101101开始点？结束点？校验比特？2024/10/312.1组帧技术面向字符的组帧技术面向比特的组帧技术采用长度计数的组帧技术2024/10/312.1.1面向字符的组帧技术(1)面向字符的组帧技术是指物理层传输的基本单元是一个字符（通常用一个字节表示一个字符），并在此基础上形成具有一定格式的字符串例如：RS-232C异步串行接口协议。该协议在传送每个字符前后分别加上起始位D起、停止位D止，以便区分不同的字符。2024/10/312.1.1面向字符的组帧技术(2)Internet网中常用的面向字符的组帧技术的协有SLIP(SerialLineInternetProtocol)和PPP（PointtoPointProtocol）。2024/10/31SLIP协议（1）SLIP帧运载的是高层IP数据报。它采用两个特殊字符；END（十六进制C0H，H表示十六进制）和ESC（十六进制DBH）。END用于表示一帧的开始和结束。C0C0IP数据报2024/10/31SLIP协议（2）为了防止IP数据报中出现相同的END字符而使收端错误地终止一帧的接收，SLIP中使用了转义字符ESC。当IP数据报中出现END字符时，就转换成ESC和ESC-END（其中ESC-END=DCH）两个字符。当IP数据报中出现ESC时，就转换成为ESC和ESC-ESC（其中ESC-ESC=DDH）两个字符。C0DBC0DBDCDDC0DB11111111IP数据报2024/10/31SLIP协议（3）收端只要收到END字符即表示一帧的开始或结束。每当遇到ESC字符就进行字符转换，恢复IP报文中的原有的END和ESC字符。这样就可以完全以一个IP数据报的形式向IP层提交数据。2024/10/31PPP协议（1）PPP中，采用7EH作一帧的开始和结束标志（F）；其中地址域（A）和控制域（C）取固定值（A=FFH，C=03H）。IP数据报F7EAFFC03FCSF7E协议2024/10/31PPP协议（2）协议域（两个字节）取0021H表示该帧运载的信息是IP数据报，取C021H表示该帧的信息是链路控制数据，取8021H表示该帧的信息是网络控制数据；帧校验域（FCS）也为两个字节，它用于对信息域的校验2024/10/31PPP协议（3）若信息域中出现7EH，则转换为（7DH，5EH）两个字符。当信息域出现7DH时，则转换为（7DH，5DH）两个字符。当信息流中出现ASCII码的控制字符（即小于20H），即在该字符前加入一个7DH字符。2024/10/312.1.1面向字符的组帧技术(3)上述帧格式均支持数据的透明传输，这些帧结构在处理时非常简单，但缺点是效率较低，插入了许多转义字符。另外，数据长度必须以字节为单位。2024/10/312.1.2面向比特的组帧技术(1)在面向比特的组帧技术中，通常采用一个特殊的比特串，称为Flag,如0160（1j表示连续j个“1”）来表示一帧的正常结束和开始。与面向字符的组帧技术面临相同的问题，即当信息比特流中出现与Flag相同的比特串（如连续出现6个“1”）如何处理？2024/10/312.1.2面向比特的组帧技术(2)这里采用的办法是比特插入技术，发端信息流中，每出现连续的5个“1”就插入一个“0”。这样被插“0”后的信息比特流中就不会有多于5个“1”的比特串。接收端在收到5个“1”以后，如果收到的是“0”就将该“0”删去；如果是“1”就表示一帧结束。2024/10/312.1.2面向比特的组帧技术(3)采用比特插入技术，除了消除信息帧中出现Flag的作用以外，它还带来其他作用，如要丢弃或中止一帧，则可连续发送7个或7个以上的“1”。当链路连续出现15个“1”则认为链路空闲。因此016是一个结束标志，如果016后面是0表示正常结束，如果016后面是1表示非常中止。2024/10/31帧的开销(1)设输入的信息比特流是独立同分布的二进制变量，其“0”和“1”等概出现。假定采用01j作为结束标志，现在来求j为多少时效率最高或插入比特开销最小。2024/10/31帧的开销(2)首先考察在第i位要插入“0”的情况及相应概率。如果原始数据从i-(j-1)位到i位（i≥j）的比特为01j-1，则在第i位后面将要插入一个“0”，其概率为2-j。(它等效为出现01j-1序列的概率)XXXXXXXXXXXXXXXXXX011111

12 ii-(j-1)02024/10/31帧的开销(3)如果原始数据从i-2(j-1)到i位（i≥2j-1）的比特为012(j-1)，则也将在第i位后面插入一个“0”，其概率为2-2j+1。XXXXXXXXXXXXX01111111111

12 ii-2(j-1)002024/10/31帧的开销(4)可以继续考察在第i位前连续出现n(j-1)个“1”的情况及相应的概率。在后面的讨论中，将忽略第二次插“0”及更长连续“1”的插“0”情况。这里需要注意的是：如果输入比特流的前j-1个比特均为“1”，则将要在第j位插入一个“0”，其概率为2-(j-1)。2024/10/31帧的开销(5)设原始数据的长度为k,k≥j-1时的平均插入“0”的数目为1⋅2−(j−1)+[k−(j−1)]⋅2−j

=(k−j+3)2−j加上一个结束标志，总的开销为OV=(k−j+3)2−j

+j+1对上式取均值，有E{OV}=(E{k}−j+3)2−j

+j+12024/10/31帧的开销(7)通常E{k}>>j，所以上式可以用一个上界来表示(j>3)，即E{OV}≤E{k}2−j

+j+1上式右边对应的最小j值为j=Int[log2{E{k}}]式中，Int[x]表示取x的整数部分。2024/10/31帧的开销(7)2024/10/31帧的开销(8)化简得:E{OV}≤log2{E{k}}+2例如：E{k}=1000bit时，最佳的j=9，平均一帧的开销小于12bit。而在标准的DLC协议，取j=6，平均一帧的开销约为23bit。因此，从理论上讲，应当改变现有标准DLC的帧标志位的长度。2024/10/312.1.3采用长度计数的组帧技术组帧技术的关键是正确地表示一帧何时结束除前面采用Flag和特殊字符外，还可以采用帧长度来指示一帧何时结束。2024/10/312.2链路层的差错控制技术2.2.1差错检测2.2.2ARQ协议2.2.3最佳帧长2024/10/312.2.1差错检测链路层差错检测的目的是：如何有效地发现一帧数据比特经过物理信道传输后是否正确。常用的检错方法奇偶校验循环冗余校验CRC（CyclicRedundancyCheck）检错的基本思路是发端按照给定的规则，在K个信息比特后面增加L个按照某种规则计算的校验比特；在接收端对收到的信息比特重新计算L个校验比特。比较接收到的校验比较和本地重新计算的校验比特，如果相同则认为传输无误，否则认为传输有错。2024/10/311.奇偶校验码例：信息序列长K=3，校验序列长L=4。输入信息比特为｛S1，S2，S3｝，校验比特为｛C1，C2，C3，C4｝，校验的规则为C1=S1⊕S3，C2=S1⊕S2⊕S3，C3=S1⊕S2，C4=S2⊕S32024/10/311.奇偶校验码例如：设发送的信息比特为{100}，经过奇偶校验码生成的校验序列为{1110}，则发送的信息序列为{1001110}。若经过物理信道传输后，接收的序列为{1011110}，则本地根据收到的信息比特{101}计算出的校验序列应为{0011}。显然该序列与接收到的校验序列{1110}不同，表明接收的信息序列有错。2024/10/311.奇偶校验码如果L取1，即C=S1⊕S2⊕S3⊕…⊕SK为最简单的单比特的奇偶校验码，它使得生成的码字（信息比特+校验比特）所含“1”的个数为偶数。该码可以发现所有奇数个比特错误，但是不能发现任何偶数个错误。2024/10/31CRC校验CRC（循环冗余校验）是根据输入比特序列(SK-1,SK-2,…,S1,S0)通过下列CRC算法产生L位的校验比特序列(CL-1,CL-2,…,C1,C0)2024/10/31CRC校验将输入比特序列表示为下列多项式的系数：S(D)=SK-1DK-1+SK-2DK-2+…+S1D+S0式中：D可以看成为一个时延因子，Di对应比特Si所处的位置。例如：10101100，S(D)=D7+D5+D3+D22024/10/31CRC校验(3)设CRC校验比特的生成多项式为则校验比特对应下列多项式的系数式中，Remainder[•]表示取余数。式中的除法与普通的多项式长除相同，其差别是系数是二进制，其运算以模2为基础。2024/10/31CRC校验（4）例如(D5+D3)/(D3+D2+1)的商为D2+D余数为D2+D最终形成的发送序列为2024/10/31CRC校验（5）常用的几个L阶CRC生成多项式为：CRC-16（L=16）：CRC-CCITT（L=16）：CRC-32（L=32）：2024/10/31CRC校验（6）例2.1：设输入比特序列为（10110111），采用CRC-16生成多项式，求其校验比特序列。解：输入比特序列可表示为2024/10/31CRC校验(7)由此式可得校验比特序列为：（0000001110110010）。最终形成的经过校验后的发送序列为101101110000001110110010。2024/10/31CRC校验(8)在接收端，将接收到的序列与生成多项式g(D)相除，并求其余数。如果则认为接收无误。2024/10/31CRC校验(9)注意：

有两种情况：一是接收的序列正确无误；二是有错，但此时的错误使得接收序列等同于某一个可能的发送序列。后一种情况称为漏检。2024/10/312.2.2ARQ协议(1)前面解决了如何发现传输帧的错误问题，下面要解决当接收端发现传输帧有错如何处理的方法。最简单的处理方法是（收端）自动请求发端重发（ARQ，AutomaticRetransmissionRequest）。收端收到一帧后，经过CRC检验，如果发现该帧传输有误，则通过反馈信道（该信道可以与前向传输相同，也可以不同）以某种反馈规则通知发端重复上述过程，直到收端收到正确的帧为止。对反馈规则和重传规则的设计，要保证整个自动重传协议的正确性和有效性。2024/10/312.2.2ARQ协议(2)为了研究ARQ协议，我们对物理比特管道（物理链路）作如下假定：（1）在物理信道上传输的帧到达接收端前被时延了一个任意可变的时间；（2）帧在传输过程中可能会丢失，也可能出错；（3）帧到达的顺序与发送的顺序相同。2024/10/312.2.2ARQ协议(3)有四种不同形式的ARQ重传协议停等式ARQ返回n-ARQ选择重发式ARQ并行等待式ARQ2024/10/311.停等式ARQ（1）停等式ARQ（Stop-and-WaitARQ）的基本思想是在开始下一帧传送以前，必须确保当前帧已被正确接收。2024/10/311.停等式ARQ（1）假定A发，B收。具体的传送过程如下：A发送一帧后，B如果接收正确，则B向A返回一个肯定的应答ACK；B如果接收错误，则B向A返回一个否定应答NAK。A必须在收到B的正确ACK后，方可发送下一帧。如果A发送一帧后（并给定时器设置一个初值），在一个规定的时间内（定时器溢出），没有收到对方的ACK，则重发该帧；如果收到了NAK，也要重发该帧。2024/10/311.停等式ARQ（2）由于A到B之间的双向链路都可能出错，上述协议能否正常工作？或者说如何保证该协议能够正确工作呢？基本的方法是在传输的帧中增加发送序号（SN）和接收序号（RN）。接收序号RN通常用接收端希望接收的下一个发送帧的序号SN(也可以是下一帧的第一个字节的编号)2024/10/31无发送序号情况2024/10/31无接收序号情况2024/10/31假定A向B发送分组（A→B），节点A的发送算法如下：（1）置SN=0。（2）如果从高层接收到一个分组，则将SN指配给该分组；如果没有高层分组，则等待。（3）将发送序号为SN的分组装入物理帧中发送给接收节点B。（4）如果从B接收的RN>SN，则将SN加1，返回（2）。如果在规定的有限长时间内，没有从B接收到RN>SN的帧（应答），则返回（3）进行重传。等待式ARQ协议的严格描述2024/10/31等待式ARQ协议的严格描述节点B的接收算法如下：（1）置RN=0。（2）无论何时从A正确接收一个SN=RN的帧，将该帧中的分组送给高层，并将RN加1。（3）在接收到该分组后的一个规定的有限长时间内，将RN放入一帧的RN域中发给A。返回（2）。2024/10/31等待式ARQ协议性能评估算法（协议）的正确性算法（协议）的有效性2024/10/31等待式算法（协议）的正确性所谓算法的正确性是指算法始终能够正常工作，正确接收输入的数据和状态，产生正确的动作和正确的输出结果。对于不同的算法，其正确性有不同的描述。对于停等式ARQ协议而言，所谓“该算法是正确的”是指：A能够始终不断地从高层接收数据分组，B能够始终按照发端的顺序向B的高层呈送接收到的分组，既不重复，也不丢失。2024/10/31等待式算法的正确性证明算法的正确性证明可分为两部分：一是稳妥性（Safety），即算法决不会产生不正确的结果（在这里是指提交给上层分组的顺序不对）；二是活动性（Liveness），即算法会永远不停地产生结果（不会产生死循环，一旦进入死循环，将不会进行进一步的处理），在这里指在A节点能够不停地接收高层的分组，在B节点能够不停地将这些分组呈送给高层2024/10/31等待式ARQ协议稳妥性证明在停等式ARQ中，稳妥性是很明显的。在算法开始时，SN=0，RN=0，节点B等待RN=0的帧，因而仅会有SN=0帧中的分组送上高层。由于RN是将要接收的下一个帧的序号，接收到一个新的帧后RN加1，这样重发帧的序号小于RN，因而其中的分组不可能送给高层。所以，节点B能按顺序将分组呈现给高层。2024/10/31等待式ARQ算法活动性证明（1）为了考察该算法的活动性，假定A在t1时刻开始发送给定的分组i，B在t2时刻正确接收到该分组，A在t3时刻正确接收到B的应答。显然，如果t2＝∞，则表示B收不到A的分组；如果t3＝∞，则表示A收不到B的应答。因而，要证明该算法的活动性就要证明2024/10/31等待式ARQ算法活动性证明（2）为了证明该协议的正确性，我们假定：①所有错误的分组都能被CRC检出；②一个分组能够被正确接收的概率为q，q>0。2024/10/31等待式ARQ算法活动性证明（3）令t时刻的RN和SN为RN(t)和SN(t)，显然它们是时间t的非降函数。由于SN(t)是t时刻以前，从B接收到的最大请求序号，所以SN(t)≤RN(t)。由于分组i在t1时刻开始第一次传输（A在t1以前从未传送过分组i），则根据稳妥性（算法不会产生不正确的结果）有RN(t1)≤i，又因为SN(t1)＝i，所以有2024/10/31等待式ARQ算法活动性证明(4)又根据假定：在t=t2时，根据RN(t)的非降特性，有t1<t2。在t=t3时，利用RN(t)和SN(t)的非降特性和SN(t)≤RN(t)，则有t2<t32024/10/31等待式ARQ算法活动性证明(5)根据算法，A将会重复发送分组i，其重发的间隔是有限的。又由于分组被成功接收的概率q>0，因而分组i会在有限次传输后被正确接收。也就是说，从t1至t2的间隔是有限的。由于A不停地以有限长的间隔发送分组i，这将导致节点B以有限的间隔发送应答（包括RN的分组）。由于B成功传输的概率q>0，所以应答在有限的时间内到达A，即t3是有限的。证毕。2024/10/31等待式ARQ算法在前面的讨论中，假定SN和RN是随时间任意增加的。这样就需要很大的比特域来表示发送序号。但实际上是不需要的，可以采用一个整数的模值（modN）来表示，如SNmod8,SNmod128等。很容易看出对于停等式ARQ，取模2就足够了。2024/10/31等待式ARQ算法有效性(1)算法的有效性可以从三个主要方面来表述：一是吞吐量（或通过量），二是链路的利用率，三是分组延迟。吞吐量是指在给定的物理信道和输入分组流的条件下，接收端能够呈送给高层的分组速率（分组/秒或比特/秒）。链路的利用率是指物理层（比特管道）的传输容量中用于有效分组传输所占的比例。在信道中，如果被等待、重传和其它不必要的传输所占的比例越少，则信道利用率越高。分组延迟是指链路层从发端收到高层的分组开始到收端将该分组呈送给高层为止所需的时间。2024/10/31等待式ARQ算法有效性(2)设数据帧是固定帧长，其传输时间为TD秒，肯定和否定应答帧长为TACK秒，物理信道的传播时延为Tp秒，则在忽略算法的处理时延的情况下，一帧的传输周期为假定任意一个数据帧平均需要发送NT次（一次初发，NT－1次重发）才能成功2024/10/31等待式ARQ算法有效性(2)则该帧平均一共需要NT个传输周期，物理链路的最大平均利用率为：（即物理链路以最大可能的负荷在传输时的平均利用率）令，忽略应答帧的传输时间（认为TACK＝0），则有2024/10/31等待式ARQ算法有效性(3)又假定数据帧的误帧率为p=1-q，应答帧因长度很短从而其出错的可能性可以忽略，即认为应答帧总是可以正确传输，则一个数据帧发送i次成功的概率为从而有链路的最大平均利用率2024/10/31等待式ARQ算法有效性(4)等待式ARQ的最大平均吞吐量为（分组/秒）等待式ARQ的平均分组延迟为：D＝组帧时延＋

≈组帧时延＋2024/10/31等待式ARQ算法有效性(5)组帧时延是指从高层分组的第一比特到达链路层开始，到链路层将该分组的所有比特收齐，经过增加控制头（如帧起止标志发送序号，接收序号等）和校验比特（CRC）形成可传输的数据帧为止。它取决于网络层与链路层之间的接口速率和方式，以及链路层的处理速度和方式。例如：若网络层与链路层运行在相同的微处理器或计算机系统上，采用数据块传递的方式来传递分组，则组帧时延可以相当小，且可以忽略。如果网络层与链路层采用传输速率为R（比特/秒）的接口交换数据，则组帧的时延为K/R（这里K为分组的长度（比特数））。2024/10/31等待式ARQ算法有效性(6)2024/10/312.返回n-ARQ(1)返回n-ARQ(也称为连续ARQ)的基本思路是：发端在没有收到对方应答的情况下，可以连续发送n帧。收端仅接收正确且顺序连续的帧，其应答中的RN表示RN以前的所有帧都已正确接收。（这里收端不需要每收到一个正确的帧就发出一个应答，可对接收到的正确顺序的最大帧序号进行应答。）2024/10/312.返回n-ARQ(2)发送窗口宽度2024/10/312.返回n-ARQ(3)从图中可以看出，如果收端能及时返回应答，则发端可连续不断地全速连续发送帧。（如果我们减缓应答返回的速率，则可以控制发端发送帧的速率，从而达到速率控制的目的。）下面考察双向都有数据传输并且帧长度不等长时，发送端窗口滑动的情况。2024/10/31传输错误对发送窗口的影响(n=4)尽管2，3，4号帧传输正确，但它们的序号与接收端期望的序号不符而不能被正确接收，因而仍需要重传。2024/10/31反向帧长对发端窗口的影响0123413405134窗口[3,6][1,4][0,3][4,7]SN节点A节点BRN01234提交的分组2024/10/31反向帧出错对发端的影响反向帧出错可能对发端无影响，也可能对发端有影响。2024/10/312.返回n-ARQ算法描述返回n-ARQ算法的具体描述（假定A为发端、B为收端）设发端使用SNmin表示A目前没有收到应答的帧中序号最小的帧（即发端窗口的低端），SNmax表示它将要指配给从高层新到达分组的帧序号。A节点将试图传送SNmin到SNmax－1之间的帧。2024/10/31返回n-ARQ算法的具体描述(2)发端（A节点）的算法：（1）置SNmin＝0，SNmax＝0（2）算法以任意顺序重复执行第（3）、（4）、（5）步。在每一步的条件满足时刻到该步被执行的时刻之间的时延是任意的，但是该时延是一个有限的值。（3）如果SNmax<SNmin+n，且上层有一个新分组到达，将SNmax指定给承载该分组的帧，并将SNmax加1。(继续发送)（4）如果接收的RN>SNmin，则置SNmin=RN。（窗口右移）（5）如果SNmin<SNmax，且当前没有帧在传输，从[SNmin，SNmax）中选择一个或一组帧进行传输。当SNmin不再改变时，SNmin帧的重传间隔应当小于一个规定的有限值。2024/10/31返回n-ARQ算法的具体描述(3)收端（B节点）的算法：（1）置RN=0，重复执行（2）和（3）。（2）当接收到的SN=RN，将分组呈送给高层以，并将RN加1。（3）在接收到A的任何一个正确帧后，在一个有限的时间内，将收端的RN发给A。2024/10/312.返回n-ARQ上述算法实际上是一个框架，它是指一类算法，其定时、操作顺序可以根据需要来安排。例如，可以在发送完SNmin→SNmax-1的帧后，立即返回再次发送SNmin→SNmax-1的帧，而不是等到应答定时器超时后再重发。2024/10/312.返回n-ARQ返回n-ARQ的序号也可以用模为m(m>n)的整数来表示。例如，取模8则可用3比特来表示序号，此时最大的窗口取值只能为7。如果n=m，则系统无法正常工作。其原因如下：假设，发端发送8帧后，收到了对方的所有确认，则将发送新的8帧，其序号为0~7。如果发端发送8帧后，收端发送的应答未能到达发端，发端将重发这8帧，其序号仍为0~7。由于这两种情况对收端而言是无法区分的，因而在接收到第二次序号为0~7的帧时，收端无法区分是新的帧还是重发的帧。2024/10/312.返回n-ARQ影响返回n－ARQ协议效率的原因反向帧长过长要求增加n反向应答出错要求增加n正向传输出错(n增加将导致重传的内容加大)加快出错的反馈速度。即收端一旦接收到一个错误帧，立即返回一个短的应答帧（监控帧），使发端尽快返回重发。2024/10/31返回n-ARQ的效率(1)假定数据帧长是一个固定值，且假定应答帧传输时间很小可以忽略。返回n-ARQ的效率与链路的传输时延(TP)，帧长(TD)，窗口n等参数紧密相关。令d=TD+2TP2024/10/31返回n-ARQ的效率(2)当nTD>d时，应答帧可以及时返回，在传输帧无差错的情况下，链路的最大平均利用率为1。发端可连续不断地向链路上发送帧。当nTD<d时，链路的最大平均利用率为nTD/d。即在d=TD+2TP时间内，发端至多可以发送n个分组2024/10/31返回n-ARQ的效率(3)设传输过程中的误帧率为p，每出现一个错帧，发端就会重复n帧。若一帧经过i次传输成功，则表明经过了（i-1）次返回后该帧才传输成功，而每次返回需要传输n帧，因而总的所需传输的帧数为1+(i-1)n，其出错的概率为pi-1(1-p)。由此可得：成功传输一帧平均所需传输的帧数为：

(2-19)2024/10/31返回n-ARQ的效率(4)利用该式可得返回n-ARQ方式中链路最大平均利用率为：

(2-20)式中的α=TP/TD为一帧的传输时延/帧长2024/10/31返回n-ARQ的效率(5)代入式（2-19）得从图中可以看出，链路利用率与相对传输时延、窗口n的大小紧密相关。当相对传输时延相对较大（如在卫星链路中）时，为了达到较高的链路利用率，应选择较大的n。从图中可以看出，当n=|(1+2α)|，（|x\表示取大于等于x的最小整数）时，链路利用率最高。也就是最佳的窗口宽度（nTD）近似等于一帧的传输时间+2倍的传播时延。2024/10/31选择重发式ARQ(1)选择重发式ARQ（SelectiveRepeatARQ）是对返回n-ARQ的改进。在返回n-ARQ中，如果前向传输的某一个帧出错，则在收到对方的否定应答后，该帧及其后续的帧都要重传，而不管这些后续是否传输正确。选择重发式ARQ的思路与返回n-ARQ相同，其窗口仍为n，但仅仅重发有错的帧。2024/10/31选择重发式ARQ(2)为了实现选择有错帧进行重发的目的，这就要求接收节点具有对分组排序的能力（因为这时接收到的分组是乱序的），并且在应答时除了应答RN以外，还要包括大于RN的哪些帧已被正确接收的信息。接收节点可以用RN+k个比特（每个比特的位置的取值对应于RN后面第n个帧的接收状态是ACK或NAK）来进行应答。2024/10/31选择重发式ARQ(3)选择重发式ARQ的链路利用率同样可用和返回n－ARQ同样的方式来表示，但这里重传的帧仅为出错的帧，即从而可得选择重发式ARQ的链路利用率为：2024/10/31选择重发式ARQ(4)当RN和SN采用模m来表示时，要求m≥2n；否则，如果取m>n，会引起接收数据的序号混淆。2024/10/314.ARPANETARQ(1)ARPANETARQ采用了8个并行等待式ARQ，每一个等待式ARQ对应一个虚似信道。输入分组可以任意分配到空闲的虚拟信道A-H上。如果所有虚信道忙，分组将在DLC层外等待。2024/10/314.ARPANETARQ(2)处于忙状态的虚拟信道上的分组被复接到物理比特管道上传输。可以采用轮询的方法来循环查询各个虚拟信道，当轮询到某一忙信道时，如果应答还没有收到，则将该虚拟信道的分组再次发送到物理信道上。因此，该复接方式就不需要设置定时器来计算等待应答的时间。2024/10/314.ARPANETARQ(3)2024/10/314.ARPANETARQ(4)使用该协议的一个问题：DLC层不负责排序，因而高层应当具有分组排序功能2024/10/312.2.3最佳帧长2024/10/312.2.3最佳帧长(1)从两个方面来考察最佳帧长：一个方面是在一条链路上使传输效率最高的最佳帧长。另一个方面是在多条链路构成的传输路径上，使得传输效率最高的最佳帧长。2024/10/312.2.3最佳帧长(2)在实际传输过程中，每一帧数据通常包括数据负荷和控制信息。如果帧长较短，控制比特所占用的比例较大，因而链路利用率下降。如果帧长较长，在数据帧传输过程中，因信道误码的存在而导致帧传输错误的概率较大，重传的次数将增大，这也会导致链路利用率的下降。因此存在一个最佳帧长，使链路利用率最高。2024/10/312.2.3最佳帧长(3)数据负荷的长度为ld比特控制信息的长度为lh比特总的数据长度为lf比特(lf=ld+lh)链路的误比特率为pb(信道错误为随机错误)数据帧的差错率或误帧率p为当Pb很小时，上式可近似为2024/10/312.2.3最佳帧长(4)以等待式ARQ为例，可得链路的有效利用率为式中Tb为比特宽度，将代入并经整理得：2024/10/312.2.3最佳帧长(5)将上式对ld求导，并令其为零，可得最佳数据帧长度为例如，当2024/10/312.2.3最佳帧长(6)下面，我们将讨论在分组经过多次中转才能到达目的节点时，能使得网络开销最小和时延最小情况下的最佳帧长。一条消息分成不同长度的分组经过中转到达目的节点的过程如右图。2024/10/312.2.3最佳帧长(7)从降低时延的角度，分组的长度应尽可能小。分组长度较小会带来什么问题？设消息的长度为M，分组的长度为K，通常每一帧都包含固定的开销V（含头和尾），这样每一条消息要分成Int[M/K]+分组，Int[x]+表示大于或等于x的最小整数。在消息的传输过程中，前Int[M/K]个分组均有K个比特，而最后一个分组的比特数在1到K之间。一条消息要传输的总比特数为M+Int[M/K]+×V。2024/10/312.2.3最佳帧长(8)2024/10/312.2.3最佳帧长(9)帧长K减小，会导致帧数增加，这会引起传输开销增加和网络处理负荷增加，因此应当增加帧长。在M→∞时，开销所占的比例为V/(V+K)。因此，增加帧长会降低开销。综合考虑时延和开销两个方面，就存在一个最佳帧长。2024/10/312.2.3最佳帧长(10)设每条链路的容量为C（b/s），将一条消息经过中继传到目的节点的总时间为T，在忽略各节点的处理和缓存时延的情况下有：T=消息在最后一条链路上的传输时间+(j-1)条链路引起的时延对M求均值得2024/10/312.2.3最佳帧长(11)2024/10/312.2.3最佳帧长(12)用代入上式，并使得上式最小的最佳帧长为:2024/10/312.2.3最佳帧长(13)在上面的讨论中，我们未讨论打包的时延，即只关心消息进入系统后到达目的节点的时延。而对于某些流型业务（如语音），将要关心给定的某一个比特进入网络到该比特离开网络的时延，这时就必须考虑打包的时延。2024/10/312.2.3最佳帧长(14)设输入的比特速率为R，分组长度为K，收发之间各链路的容量分别为C1，C2，…（均大于R），分组的开销为V个比特，则一个比特的时延为T=打包时延+各链路的传输时延2024/10/312.2.3最佳帧长(15)从上式可以看出，当链路速率提高后，T主要由K/R决定。例如：对于64kb/s的数字语音，通常要求打包时延小于10ms，因此K通常取500比特或更小。2024/10/312.2.3最佳帧长(16)上面都是从单个用户的角度来讨论网络处于轻负荷状态下，最佳帧长如何选取的问题。但是对于网络而言，各个用户的最佳长度各不相同。这就会出现当不同长度的分组在一条链路上传输时，长度很长的分组传输时延很大，从而阻碍了短分组的快速传递。这就像一条单行线上，一辆慢速行驶的货车，阻塞了后面小车的快速行驶。这种现象称为“slowtrunkeffect”（慢速货车效应）。因此，最佳的帧长度应当由网络来设定，而不是由各终端自行设计。2024/10/312.3标准数据链路控制协议及其初始化2.3.1标准的数据链路控制协议2.3.2数据链路层协议的初始化2024/10/312.3.1标准的数据链路控制协议目前常用的标准数据链路控制（DLC）协议有：IBM提出的SDLCISO建议的HDLCANSI规定的ADCCPCCITT建议的LAPB其中，HDLC与ADCCP功能相同，SDLC是HDLC的一个功能子集。LAPB也是HDLC的一个子集。HDLC（ADCCP）是为多种物理链路设计的。这些链路包括多址链路、点对点链路、全双工和半双工链路。2024/10/31链路的工作方式通信双方链路的工作方式通常分为三类：全双工、半双工和单工方式。单工方式指通信双方仅有单向数据流动，一方为发端，另一方为收端，链路上仅为一条单向物理信道；全双工是指通信双方可以同时向对方发送和接收对方的数据流，链路上同时有两条不同流向的物理信道；半双工通信指通信双方可以向对方发送或从对方接收数据流，但不可以同时收发，任一方在发送时不能接收，在接收时不能发送。2024/10/312.3.1标准的数据链路控制协议HDLC包括三种工作模式：正常响应模式（NRM）用于主从式链路。即链路的一端是主站（节点），另一端是从站。主站负责控制和协调双方的通信过程。典型的应用场合是一个计算机与多个外设之间的链路。采用轮询（Polling）机制，实现主站与从站之间的通信。异步响应模式（ARM）也是采用主从模式，但对从站没有严格的限制，该方式未被广泛使用，后面将不再讨论它。异步平衡模式（ABM）用于全双工点对点的链路，链路两端的节点具有相同的责任进行链路控制。这是应用最广泛的协议之一。LAPB使用ABM，SDLC使用NRM和ARM模式。2024/10/31标准DLC的帧结构(1)上面几种协议都使用该帧结构。Flag：011111102024/10/31标准DLC的帧结构(2)地址域在常用情况下为一个字节（8比特），它用于多用户共享一条链路时区分不同的节点。在不同的工作方式下，地址域的功能可以不同。例如：在NRM方式中，地址域总是从站的地址。当用于点对点通信时，地址域没有作用。2024/10/31标准DLC的帧结构(3)控制域用来区分不同的帧类型。它有三种格式：信息帧（Ⅰ）、监控制（S）和无编号帧（U）2024/10/31标准DLC的帧结构(4)信息帧(I)采用模8的返回n-ARQ方式进行传输，它对应的控制包括SN和RN。监控帧(S)用于在无数据传输时返回ARQ的信息（如：RN）或加速返回ACK和NAK信息。无编号帧(U)用于链路的建立和终止以及附加信息的传输。2024/10/31标准DLC的帧结构(5)控制信息种类的区分是靠控制域的第1和2比特来区分的。第1比特为0表示为信息帧，第1和2比特为“10”表示监控帧，第1和2比特为“11”表示为无编号帧。控制域中的第5个比特为查询/结束（P/F）比特，在查询时称为P比特，在响应时称为F比特2024/10/31标准DLC的帧结构(6)在不同的工作模式中，P/F比特的用法不同。例如：在NRM模式中，主站查询从站时，置P=1。从站响应如果有多个帧，则应将最后一个响应帧F置1，其余各响应帧置F=0。在ABM方式中，任一站均可主动发送S和I帧，此时将P置1，对方收到P=1的帧后，将F置1进行应答。2024/10/31标准DLC的帧结构(7)监控帧（S）有四种类型：RR－接收准备好RNR－接收未准备好REJ－拒绝SREJ－选择拒绝它们通过控制域中的第3和4个比特来区分。“00”对应RR，“10”对应RNR，“01”对应REJ，“11”对应SREJ。2024/10/31标准DLC的帧结构(8)RR是正常的响应帧，它用于反向没有数据帧时，携带RN对发端进行应答。RNR是用于收端暂不能接收更多帧（缓冲区满）时给对方的提示，RNR中也包括RN。REJ用于刚接收的帧出错或者帧的序号与期望的序号不符时，给发端的应答。发端将重发序号为RN及其后面的分组，同时表明RN以前的分组已正确接收。REJ可以改善返回n-ARQ的效率。SREJ是一种简单的选择重发方式，它要求发端重发序号为RN的分组。2024/10/31标准DLC的帧结构(9)无编号帧（U）用于链路的建立、拆除和特殊控制。无编号帧是采用第3，4，6，7，8个比特来区分不同类型的。目前，只定义了15种无编号帧。无编号帧可用于设置工作模式，如置正常响应模式SNRM（SetNRM），置异步平衡模