第三章数据链路层zb2009

第三章 数据链路层数据链路层需要考虑的问题数据链路层的位置：物理层之上，网络层之下利用物理层提供的服务（对网络层屏蔽物理层的差异和实现细节）向网络层提供可靠有效的通信目标：在数据链路层上，两台相邻的机器之间实现可靠、有效的通信定位：解决点到点链路上传输信息存在的问题。链路：相邻结点构成的一条线路。对比：端到端3.1数据链路层的设计要点向网络层提供一个定义良好的服务接口处理传输错误：差错控制调节数据流，确保慢速的接收方不会被快速的发送方淹没，并保证高效传输：流控这些机制并非只在链路层出现。3.1.1为网络层提供的服务目标：将数据从源机器的网络层传输到目标机器的网络层。服务3.1.1为网络层提供的服务无确认的无连接服务不建立点到点间的逻辑连接不保证帧能够被接收方正确接收适用于服务质量较好的信道和实时性业务e.g.大多数的LAN有确认的无连接服务不建立点到点之间的逻辑连接接收方对收到的每一帧进行确认，提供可靠性。适用于不可靠的信道e.g.无线系统缺点：可能收到多个重复帧（如ACK报文丢失）注：在数据链路层上提供确认只是一种优化而不是要求。有确认的有连接服务三个阶段：连接建立；数据帧传送；连接释放需要建立源机器和目标机器之间的逻辑连接保证该连接上的每一帧都被正确接收，并且只接收一次保证接收帧的顺序和发送帧的顺序一致相当于为网络层提供一个可靠的比特流面向连接的服务执行的三个阶段建立连接（初始化变量、计数器以及缓冲区）变量和计数器记录哪些帧收到或未收到；缓冲区用于暂存要发送和刚收到的帧。传送数据（帧）拆除连接（资源回收）例3.1.2成帧（framing）成帧：将物理层的位流分解成离散的帧数据链路层成帧的原因传输距离越长，越有可能发生错误,就需要重发整个数据块，用较小的数据块，每个数据块出错的可能就会减少，需要重发的数据随之亦少判断错误：源端机器计算每一帧的校验和，目的端机器收到帧后重新计算校验和在一个多点线路上,一般较理想的做法是不让一个工作站长期占有线路,否则会引起其它工作站的长时间延迟接收器的缓存大小也有限制成帧方法字符计数法含字节填充的分界符法含位填充的分界标志法物理层编码违例法字符计数法含字节填充的分界符法帧利用特殊的标志字节（FLAG）作为帧的开始和结束两个连续的FLAG代表当前帧结束和下一帧开始。如果数据中出现FLAG，则进行字节填充（ESC）如果ESC出现在数据中，同样进行字节填充含位填充的分解标志法数据帧可以包含任意长度的位（bit），每个字符也可以有任意的长度的位每一帧开始和结束都有一个特殊的位模式01111110（即flag）当数据中出现连续5个位“1”，发送方自动在其后插入一个位“0”接收方看到5个连续的“1”，自动删去其后的“0”物理层编码违例法只适用于物理介质上的编码方法含有冗余信息的网络例：若数据采用曼彻斯特编码，则可利用1-1或0-0用于帧分界。注：实际中，许多数据链路层协议联合采用字符计数法和其他方法，以保证更大的可靠性3.1.3差错控制（errorcontrol）问题：如何保证所有的帧最终被提交给目标机器的网络层，并保持正确的顺序解决方法接收方对所接收到的帧进行确认发送方使用定时器发送方对帧分配序号3.1.4流控制（flowcontrol）问题如何确保慢速的接收方不被快速的发送方淹没解决基于反馈的流控制（feedback-basedflowcontrol）基于速率的流控制（rate-basedflowcontrol）3.2错误检测和纠正传输错误一直存在。模拟线路，无线链路传输错误的分类：突发性错误、孤立错误。孤立错误影响面广；突发性错误难以纠正。错误处理的策略：纠错码（error-correctioncode）：在发送的数据块中包含足够冗余信息，以便接收方可以推断（识别）出原本发送的数据信息。FEC（forwarderrorcorrection）前向纠错技术。广泛用于无线链路检错码（error-detectioncode）：所包含的冗余信息只能让接收方判断出发生了错误，但不能推断出哪里发生了错误。通常接收方通过请求重传来获得正确数据块。以上两种不同的技术有不同的适用环境可靠信道，可使用检错码：光纤链路错误频发信道，更适于使用纠错码：无线链路3.2.2检错码：用于误码率很低的链路CRC（CyclicRedundancyCheck，循环冗余校验码），也叫多项式编码（Polynomialcode）基本思想：将位串看作是系数为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，则表明传输过程中有错误。计算校验和的方法：设生成多项式G(x)为r阶。在m位帧的尾部加上r个0位。对应多项式为xrM(x)利用模2除法，用G(x)去除xrM(x)。利用模2减法，从xrM(x)的位串中减去余数（小于等于r位）。结果就是将被传输的带校验位的帧。其对应多项式为T(x)。CRC方法性能：可以检测任何一位错误。一些特殊的多项式已经成为国际标准。CRC-32用于IEEE802。实践中计算CRC的方法：硬件构造移位寄存器电路。多项式编码校验和的计算过程3.3基本数据链路协议基本假设假设物理层、数据链路层和网络层都是独立的进程，通过来回传递报文进行通信(各层协议的独立性)假设机器A希望使用一个可靠的、面向连接的服务，向机器B发送一个长的数据流假设A的数据链路层在向网络层请求数据总能够成功假设机器不会崩溃，协议仅仅处理通信错误，不处理因为机器崩溃和重启而引起的问题目的主机的数据链路层仅仅将数据递交给网络层就可以了，不进行其他处理数据链路层不考虑校验和的计算假设数据链路层总是（通过查询）等待事件发生关键数据类型数据类型boolean 表示“真”或“假”seq_nr 帧序号，总是在0到MAX_SEQ之间packet 数组，表示一个网络层的分组frame_kind 帧类型（数据，ACK，NAK）frame 数据链路层的帧结构

typedefstruct { frame_kindkind; /*帧类型*/ seq_nrseq; /*帧序号*/ seq_nrack; /*确认序号*/ packetinfo; /*帧的载荷，即网络层分组*/}frame;/*数据链路层的帧。“帧头＋净荷”结构*/关键函数wait_for_event 等待事件发生frame_arrival 帧到达事件cksum_err 收到一个校验和出错的帧timeout 定时器超时network_layer_ready 网络层就绪ack_timeout ACK定时器超时to_network_layer 将数据递交给网络层;2、3层接口from_network_layer 申请网络层数据;2、3层接口to_physical_layer 将数据发送到物理线路上；1、2层接口from_physical_layer 从物理线路上获取一个帧；1、2层接口start_timer 启动（或重启）定时器end_timer 关闭定时器start_ack_timer 启动产生ACK的定时器end_ack_timer 结束产生ACK的定时器enable_network_layer 允许网络层有分组发送时中断链路层disable_network_layer 禁止网络层有分组发送时中断链路层3.1.1无限制单工协议假设数据只是单向传送发送方和接收方的网络层一直处于就绪状态忽略处理时间缓存空间无限大通信信道永远不会损坏或丢失帧一个无限制的单工协议3.3.2单工的停-等协议去掉协议1中接收方网络层永远就绪的假设通信信道无错数据流量单向如何避免快的发送方淹没慢的接收方接收方向发送方反馈信息发送方减速：每发一帧，就暂停发送，等待对方确认。Stop-and-wait.一个单工的停-等协议停-等协议的信道利用率Tf：数据发送时延（传输时延）Td：在线路上的传播时延信道利用率Cr示例：卫星链路例。单程传播时间为270ms。数字传输服务用32Mbps,典型的4000位/帧。传输时间tf=4000/32M=125us,得：

a=270ms/125us=2160。对于简单停止-等待应答通讯协议,效率只有0.00023!局域网例。距离范围d＝1Km,数据速率为10Mbps。信号在铜线中的传输速率为V=2108m/s和500位/帧,tf=500/10M=50us,有：a=5us/50us=0.1,利用率0.833.通过Modem在语音级线路上传输数据例。数据速率9600bps,同样V=2108m/s和500位/帧。传输距离任意,如d＝100Km,则：

a=(9600bps100Km)/(2108500bits)=9.610-3。效率等于0.981结论在部分场合(小a)，如低速、长帧、短距，简单的停止-等待过程可提供较高的线路利用率。对除此之外的另一些场合，则希望有更巧妙的处理过程以提高传输效率。3.3.3有噪声信道的单工协议前提：一个可能会出现错误的通信信道定时器：发送方经过一段时间后仍然收不到帧的确认后，将再次重发该帧帧序号：供接收方区分重复帧；停等方式下，用1比特表示即可。ARQ（AutomaticRepeatreQuest，自动重复请求协议，或自动请求重发）s.seq:表示当前发送帧的序号一个支持重传的肯定确认（ACK）协议-Senders.ack:表示已收到帧的序号一个支持重传的肯定确认（ACK）协议-Receiver3.4滑动窗口协议：双工数据传送滑动窗口（slidingwindow）机制发送的每一个帧都被编号（保证帧顺序接收）如果帧中的序号位为n，则帧编号的范围是从0到2n-1，2n-1后从0重新开始在发送方和接收方分别设立两个窗口：发送窗口（sendingwindow）和接收窗口（receivingwindow），每个窗口内含有一个或一组序号的帧。发送窗口的大小WT代表在还没有收到对方确认（ACK）信息的情况下发送端最多可以发送多少个数据帧。接收窗口的大小WR表示接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。接收方应具有一定的缓冲能力发送窗口的规则归纳如下：（1）发送窗口内的帧是允许发送的帧，而不考虑有没有收到确认。发送窗口右侧所有的帧都是不允许发送的帧。（2）每发送完一个帧，允许发送的帧数就减1。但发送窗口的位置不变。（3）如果所允许发送的WT个帧都发送完了，但还没有收到任何确认，那么就停止发送新的数据帧。这时，发送端就进入等待状态。（4）每收到一个对窗口内最小序号帧的确认，发送窗口就向前(即向右方)滑动一个帧的位置。接收窗口的规则归纳如下：（1）在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。否则，就丢弃它。（2）每按序收到一个序号正确的帧，接收窗口就向前(即向右方)滑动一个帧的位置。发送窗口和接收窗口可以有不同的上下界、甚至可以有不同的大小。 捎带确认（piggybacking）技术在双向通信中经常使用捎带确认技术将确认帧延迟一小段时间，以便可以和本方下一个要发送的数据帧一起合并发送的技术。捎带确认更好的利用了信道带宽。3.4.11位滑动窗口协议：双向即停等式：发送和接收窗口均等于1。3.3.2使用回退n帧（gobackn）技术的协议窗口大小：发送窗口为w（w最大为2n-1），接收窗口为1。接收方除了按序接收的那一帧外，不接收任何帧（丢弃）。发送方超时后，按顺序重传所有未确认帧。发送窗口大小为7Go-back-n方式下，发送窗口的大小限制如果序号位为n，则发送窗口w最大为2n-1ABF0.1RR1F1.1F1.2F2.2F3.2F7.2F0.2RR1::ABF0.xRR1F1.xF2.xF3.xF7.xF0.xRR1::Timeout=?窗口大小=8＝23窗口大小=8＝23注：这里，（F0.1)代表正发送第0帧，并期待对方的第1帧（已收到第0帧）。RR1表示收到第0帧，期待第1帧。ABF0.1RR1F1.1F1.2F2.2F3.2F7.2RR0::ABF0.xRR1F1.xF2.xF3.xF7.xRR1::Timeout窗口大小=7＝23-13.4.3使用选择性重传(SelectiveRepeat)的协议接收端接收所有序号落在接收窗口内的帧，对于丢失或错误的帧，利用NAK指示发送端出错，发送端仅仅发送丢失或错误的帧接收端需要设置缓冲区，来缓冲非顺序到达的帧，以便顺序提交给网络层窗口大小：发送窗口和接收窗口都大于1。发送窗口大小为6选择性重传方式下，最大接收窗口的大小限制如果序号位为n，最大接收窗口大小≤2n/2=2n-1通常，发送窗口和接收窗口取一样大。(a.b)发送窗口大小为7(c.d)发送窗口大小为43.6数据链路层协议示例3.6.1高级数据链路控制HDLC两种链路配置：非平衡配置和平衡配置非平衡配置 平衡配置非平衡配置：支持点对点和点对多点平衡配置：支持点对点面向位（bit），使用位填充帧格式：地址域：用于多个终端的线路上区分不同终端控制域：序列号、确认等数据域：任何信息，可以任意长校验和域：循环冗余码，生成多项式16bit，CRC-CCITT帧分界：01111110（0x7E）三种类型的帧：通过控制域区分信息帧管理帧（监控帧）：差错控制和流控无序号帧：主要用于控制目的；在提供不可靠的无连接服务时，也可承载数据。3种帧的控制域：（a）信息帧（b）管理帧（c）无序号帧Modifier控制域：管理帧：4种ReceiveReady（RR）帧类型0（Type0）：正确接收，确认下一个希望收到的帧Reject（REJ）帧类型1：发生差错，发送方将重传该帧和其后所有未确认帧ReceiveNotReady（RNR）帧类型2：暂停接收，并确认下一个希望收到的帧。用于流控SelectiveReject（SREJ）帧类型3：选择性拒绝，要求只重传指定帧。只用于选择性重传无编号帧：指明帧类型，5比特（最多32种）。常用作链路建立/拆除：SABM（SetAsynchronousBalancedMode）：初始化线路DISC（Disconnect）：拆除连接UA（UnnumberedAcknowledgement）：对控制帧的确认UI（UnnumberedInformation）：无编号信息帧FRMR（FRaMeReject）：所收到的帧语义不正确(如非法帧，长度不对等)。举例：复合站的链路建立与释放数据传输阶段：传送信息帧，并结合RR、RNR、REJ等管理帧实现信息传送、流控和差错控制。P/F（Poll/Final,查询/结束）比特。用法：用法1（非平衡方式下）：主站利用P=1请求从站发送数据，从站在传输结束后设置F=1；用法2（平衡方式下）：P=1时强迫对方立即返回管理帧，而不是等待一个捎带确认。3.6.2Internet中的数据链路层点到点通信的应用场合本地路由器和远端路由器的点到点连接主机到路由器的拨号连接。点到点链路PPP——点到点协议（PointtoPointProt