计算机网络课件第三章数据链路层-zb

1、数据链路层需要考虑数据链路层的位置：物理层之上，网络层之下利用物理层提供的服务（对网络层物理层的差异细节）向网络层提供可靠有效的通信目标：在数据链路层上，两台相邻的机器之间实现可靠、有效的通信定位：解决 点到点链传输信息存在。链路：相邻结点的一条线路。对比：端到端3.1 数据链路层的设计要点向网络层提供一个定义良好的服务接口处理传输错误：差错控制调节数据流，确保慢速的接收会被快速的发送方淹没，高效传输：流控这些机制并非只在链路层出现。3.1.1 为网络层提供的服务目标：将数据从源机器的网络层传输到目标机器的网络层。服务3.1.1为网络层提供的服务无确认的无连接服务不建立点到点间的逻辑连接不保证

2、帧能够被接收方正确接收适用于服务质量较好的信道和实时性业务e.g. 大多数的LAN有确认的无连接服务不建立点到点之间的逻辑连接接收收到的每一帧进行确认，提供可靠性。适用于不可靠的信道e.g. 无线系统缺点：可能收到多个重复帧（如ACK报文丢失）注：在数据链路层上提供确认只是一种优化而不是要求。有确认的有连接服务三个阶段：连接建立；数据帧传送；连接需要建立源机器和目标机器之间的逻辑连接保证该连接上的每一帧都被正确接收，并且只接收一次保证接收帧的顺序和发送帧的顺序一致相当于为网络层提供一个可靠的比特流面向连接的服务执行的三个阶段建立连接（初始化变量、计数器以及缓冲区）变量和计数器哪些帧收到或未收到

3、；缓冲区用于暂存要发送和刚收到的帧。传送数据（帧）拆除连接（资源回收）例3.1.2 成帧（framing）成帧：将物理层的位流分解成离散的帧数据链路层成帧的原因传输距离越长，越有可能发生错误,就需要重发整个数据块，用较小的数据块，每个数据块出错的可能就会减少，需要重发的数据随之亦少判断错误：源端机器计算每一帧的校验和，目的端机器收到帧后重新计算校验和在一个多点线,一般较理想的做法是不让一个工作站长期占有线路,否则会引起其它工作站的长时间延迟的缓存大小也有限制成帧方法字符含字节填充的分界符法含位填充的分界标志法物理层编码违例法字符含字节填充的分界符法帧利用特殊的标志字节（FLAG）作为帧的开始和

4、结束两个连续的FLAG代表当前帧结束和下一帧开始。如果数据中出现FLAG，则进行字节填充（ESC）如果ESC出现在数据中，同样进行字节填充含位填充的分解标志法数据帧可以包含任意长度的位（bit），每个字符也可以有任意的长度的位每一帧开始和结束都有一个特殊的位模式01111110（即flag）当数据中出现连续5个位“1”，发送方自动在其后一个位“0”接收方看到5个连续的“1”，自动删去其后的“0”物理层编码违例法只适用于物理介质上的编码方法含有冗余信息的网络例：若数据采用曼彻斯特编码，则可利用1-1或0-0用于帧分界。注：实际中，许多数据链路层协议联合采用字符方法，以保证更大的可靠性和其他3.1

5、.3 差错控制（error control）问题：如何保证所有的帧最终被提交给目标机器的网络层，并保持正确的顺序解决方法接收所接收到的帧进行确认发送方使用定时器发送帧分配序号3.1.4 流控制（flow control）问题如何确保慢速的接收解决被快速的发送方淹没基于反馈的流控制（feedback-based flow control）基于速率的流控制（rate-based flow control）3.2 错误检测和纠正传输错误一直存在。模拟线路，无线链路传输错误的分类：突发性错误、孤立错误。孤立错误影响面广；突发性错误难以纠正。错误处理的策略：纠错码（error-correction co

6、de）：在发送的数据块中包含足够冗余信息，以便接收方可以推断（识别）出原本发送的数据信息。FEC（forward error correction）前向纠错技术。广泛用于无线链路检错码（error-detection code）：所包含的冗余信息只能让接收方判断出发生了错误，但不能推断出哪里发生了错误。通常接收方通过请求重传来获得正确数据块。以上两种不同的技术有不同的适用环境可靠信道，可使用检错码：光纤链路错误频发信道，更适于使用纠错码：无线链路3.2.2 检错码：用于误码率很低的链路CRC（Cyclic Redundancy Check，循环冗余校验码），也叫多项式编码（Polynomial

7、 code）基本：将位串看作是系数为0或1的多项式。1个k位的帧看作k-1次多项式的系数列表，该多项式共有k项，从xk-1到x0。(k-1)阶多项式。110001- x5 + x4 +1多项式算法运算：模2运算（无进位借位）。等同于异或。如何使用CRC法发送方和接收方必须先约定一个生成多项式（generatorpolynomial ）G(x)。其最和最低位必须为1。设一帧为m位，对应于多项式M(x)。在其后追加一个校验和（checksum），使得追加校验和之后的帧所对应的多项式能够被G(x) 除尽。当接收方收到带校验和的帧后，用G(x) 去除它。如果余数不为0，则表明传输过程中有错误。计算校验

8、和的方法：设生成多项式G(x)为r阶。在m位帧的尾部加上r个0位。对应多项式为xrM(x)利用模2除法，用G(x)去除xrM(x)。利用模2减法，从xrM(x)的位串中减去余数（小于等于r位）。结果就是将被传输的带校验位的帧。其对应多项式为T(x)。西安电子科技大学专区CRC方法性能：可以检测任何一位错误。一些特殊的多项式已经成为国际标准。CRC-32用于IEEE 802。实践中计算CRC的方法：硬件构造移位寄存器电路。多项式编码校验和的计算过程3.3 基本数据链路协议基本假设假设物理层、数据链路层和网络层都是独立的进程，通过来回传递报文进行通信(各层协议的独立性)假设机器A希望使用一个可靠的

9、、面向连接的服务，向机器B发送一个长的数据流假设A的数据链路层在向网络层请求数据总能够成功假设机器不会，协议仅仅处理通信错误，不处理因为机器和重启而引起目的主机的数据链路层仅仅将数据递交给网络层就可以了，不进行其他处理数据链路层不考虑校验和的计算假设数据链路层总是（通过查询）等待事件发生关键数据类型数据类型seq_nrpacketframe_kindframetypedef structframe_kind seq_nr seq_nrpacket表示“真”或“假”帧序号，总是在0到MAX_SEQ之间数组，表示一个网络层的分组帧类型（数据，ACK，NAK）数据链路层的帧结构kind; seq;

10、ack;info;/*帧类型*/*帧序号*/*确认序号*/*帧的载荷，即网络层分组*/ frame; /* 数据链路层的帧。“ 帧头净荷”结构 */关键函数wait_for_eventframe_arrivalcksum_errtimeoutnetwork_layer_readyack_timeout to_network_layer from_network_layer to_physical_layer from_physical_layer start_timer end_timer start_ack_timer end_ack_timerenable_network_layerdis

11、able_network_layer等待事件发生帧到达事件收到一个校验和出错的帧定时器超时网络层就绪ACK定时器超时将数据递交给网络层; 2、3层接口申请网络层数据; 2、3层接口；1、2层接口将数据发送到物理线获取一个帧；1、2层接口从物理线启动（或重启）定时器关闭定时器启动产生ACK的定时器结束产生ACK的定时器允许网络层有分组发送时中断链路层网络层有分组发送时中断链路层3.1.1假设数据只是单向传送发送方和接收方的网络层一直处于就绪状态忽略处理时间缓存空间无限大单工协议通信信道不会损坏或丢失帧一个的单工协议3.3.2 单工的停-等协议去掉协议1中接收方网络层通信信道无错数据流量单向如何避

12、免快的发送方淹没慢的接收方接收方向发送方反馈信息就绪的假设发送方：每发一帧，就暂停发送，等待对方确认。Stop-and-wait.一个单工的停-等协议停-等协议的信道利用率Tf：数据发送时延（传输时延）Td：信道利用率Cr的时延DTdTfT +2TfdTdTf数据帧的发送时间1C rT 2T1 2a发送一帧所需要的总时间fdR La Td 时延 L / C CTf传输时延 P / RP其中L为信道的长度，C为信号在信道中P为帧长，R为信道发送数据的速率R L 也被称为带宽时延积C的速率ataACK示例：时间为270ms。数字传输服务用32Mbps, 典型链路例。单程的4000位/帧。传输时间t

13、f=4000/32M=125us, 得：a=270ms/125us =2160。对于简单停止-等待应答通讯协议,效率只有0.00023!局域网例。距离范围d1Km,数据速率为10 Mbps。信号在铜线中的传输速率为V=2108m/s和500位/帧, tf=500/10M=50us, 有： a=5us/50us=0.1, 利用率0.833.通过Modem在语音级线传输数据例。数据速率9600bps, 同样V=2108m/s和500位/帧。传输距离任意, 如d100Km,则：a=(9600bps100Km)/(2108500bits)=9.610-3。效率等于0.981结论在部分场合(小a)，如低

14、速、长帧、短距，简单的停止-等待过程可提供较高的线路利用率。对除此之外的另一些场合，则希望有更巧妙的处理过程以提高传输效率。3.3.3 有噪声信道的单工协议前提：一个可能会出现错误的通信信道定时器：发送方经过一段时间后仍然收不到帧的确认后，将再次重发该帧帧序号：供接收方区分重复帧；停等方式下，用1比特表示即可。ARQ（Automatic Repeat reQuest，自动重复请求协议，或自动请求重发）s.seq: 表示当前发送帧的序号一个支持重传的肯定确认（ACK）协议-Senders.ack: 表示已收到帧的序号一个支持重传的肯定确认（ACK）协议-Receiver3.4 滑动窗口协议：双工

15、数据传送滑动窗口（sliding window）机制发送的每一个帧都被（保证帧顺序接收）如果帧中的序号位为n，则帧1后从0重新开始的范围是从0到2n-1， 2n-在发送方和接收方分别设立两个窗口：发送窗口（sending window）和接收窗口（receiving window），每个窗口内含有一个或一组序号的帧。发送窗口的大小WT代表在还没有收到对方确认（ACK）信息的情况下发送端最多可以发送多少个数据帧。接收窗口的大小WR表示接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。接收方应具有一定的缓冲能力发送窗口的规则归纳如下：（1）发送窗口内的帧是允许发送的帧，而不考虑

16、有没有收到确认。发送窗口右侧所有的帧都是不允许发送的帧。（2）每发送完一个帧，允许发送的帧数就减1。但发送窗口的位置不变。（3）如果所允许发送的WT个帧都发送完了，但还没有收到任何确认，那么就停止发送新的数据帧。这时，发送端就进入等待状态。（4）每收到一个对窗口内最小序号帧的确认，发送窗口就向前(即向右方)滑动一个帧的位置。西安电子科技大学专区com 联系接收窗口的规则归纳如下：（1）在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。否则，就丢弃它。（2）每按序收到一个序号正确的帧，接收窗口就向前(即向右方)滑动一个帧的位置。发送窗口和接收窗口可以有不同的上下界、甚至可以

17、有不同的大小。西子科技 学专区联系捎带确认（piggybacking）技术在双向通信中经常使用捎带确认技术将确认帧延迟一小段时间，以便可以和本方下一个要发送的数据帧一起合并发送的技术。捎带确认更好的利用了信道带宽。3.4.11位滑动窗口协议：双向即停等式：发送和接收窗口均等于1。3.3.2 使用回退n帧（go back n）技术的协议窗口大小：发送窗口为w（w最大为2n-1） ，接收窗口为1。接收方除了按序接收的那一帧外，不接收任何帧（丢弃）。发送方超时后，按顺序重传所有未确认帧。发送窗口大小为7Go-back-n方式下，发送窗口的大小限制如果序号位为n，则发送窗口w最大为2n-1ABAB=

18、?:注：这里，（F0.1)代表正发送第0帧，并期待对方的第1帧（已收到第0帧）。RR1表示收到第0帧，Timeout期待第1帧。窗口大小=823窗口大小=823RR 1RR 1F 0.2F 0.xF 7.2F 7.xF 3.2F 3.xF 2.2F 2.xF 1.2F 1.xF 1.1RR 1RR 1F 0.xF 0.1ABAB:Timeout窗口大小=723-1RR 0RR 1F 7.2F 7.xF 3.2F 3.xF 2.2F 2.xF 1.2F 1.xF 1.1RR 1RR 1F 0.xF 0.13.4.3 使用选择性重传(Selective Repeat)的协议接收端接收所有序号落在接

19、收窗口内的帧，对于丢失或错误的帧，利用NAK指示发送端出错，发送端仅仅发送丢失或错误的帧接收端需要设置缓冲区，来缓冲非顺序到达的帧，以便顺序提交给网络层窗口大小：发送窗口和接收窗口都大于1。发送窗口大小为6选择性重传方式下，最大接收窗口的大小限制如果序号位为n，最大接收窗口大小2n/2=2n-1通常，发送窗口和接收窗口取一样大。(a.b)发送窗口大小为7(c.d)发送窗口大小为43.6 数据链路层协议示例3.6.1 高级数据链路控制HDLCAD（Advanced Dommunication ControlProcedure，高级数据通信控制规程），ANSISDLC（Synchronous Da

20、ta Link Control，同步数据链路控制）HDLC（High-level Data Link Control，高级数据链路控制），ISOLAP（Link Acs Procedure，链路规程），CCITT两种链路配置：非平衡配置和平衡配置主站A次站B命令（B）复合站A复合站B响应（B）命令（B）响应（B）命令（B或C）命令（A）响应（A）主站A次站B次站C非平衡配置非平衡配置：支持点对点和点对多点平衡配置平衡配置：支持点对点响应（B）响应（C）面向位（bit），使用位填充帧格式：地址域：用于多个终端的线控制域：序列号、确认等区分不同终端数据域：任何信息，可以任意长校验和域：循环冗余码，

21、生成多项式16bit，CRC-CCITT帧分界：01111110（0 x7E）三种类型的帧：通过控制域区分信息帧管理帧（帧）：差错控制和流控无序号帧：主要用于控制目的；在提供不可靠的无连接服务时，也可承载数据。控制域：3种帧的控制域：（a）信息帧 （b）管理帧 （c）无序号帧Modifier管理帧：4种ReceiveReady（RR）帧类型0（Type 0）：正确接收，确认下一个希望收到的帧Reject（REJ）帧类型1：发生差错，发送重传该帧和其后所有未确认帧ReceiveNotReady（RNR）帧类型2：暂停接收，并确认下一个希望收到的帧。用于流控SelectiveReject（SREJ

22、）帧类型3：选择性，要求只重传指定帧。只用于选择性重传无帧：指明帧类型，5比特（最多32种）。常用作链路建立/拆除：SABM（Set Asynchronous Balanced Mode ）：初始化线路DISC（Disconnect）：拆除连接UA（Unnumbered Acknowledgement）：对控制帧的确认UI（Unnumbered Information）：无信息帧FRMR（FRaMe Reject）：所收到的帧语义不正确(如帧，长度不对等)。举例：复合站的链路建立与站A站B数据传输阶段：传送信息帧，并结合RR、RNR、REJ等管理帧实现信息传送、流控和差错控制。 P/F（Poll/Final,查询/结束）比特。用法：用法1（非平衡方式下）：主 站利用P=1请求从站发送数据，从站在传输结束后设置F=1；用法2（平衡方式下）：P=1时强迫对方立即返回管理帧，而不是等待一个捎带确认。B，SABM，P链路建立阶段B，UA，F数据传输阶段A，DISC，P链路阶段A，UA，F3.6.2ernet中的数据链路层点到点通信的应用场合本地路由器和远端路由器的点到点连接主机到路由器的拨号连接。点到点链路PPP点到点协议