数据链路层设计要点课件

The Data Link LayerChapter 3内容a)数据链路层设计要点b)错误检测和纠正c)基本数据链路协议d)滑动窗口协议e)协议验证f)数据链路层协议示例数据链路层设计要点为网络层提供的服务分帧错误控制流控数据链路层功能向网络层提供一个定义良好的接口处理传输错误调节数据流确保慢速的接收方不会被快速的发送方淹没分组和帧之间的关系.为网络层提供的服务(a)虚拟通信过程.(b)实际通信过程.1.无确认的无连接服务2.有确认的无连接服务3.有确认的面向连接服务4.P156示例：为网络层提供的服务数据链路层协议的位置3层看来，2层提供了某种连接服务成帧a)目标：把位流分解到离散的帧中字符计数法含字节填充的分界符法含位填充的分界符法物理层编码违例法字符计数法成帧字符流.(a)无错.(b)一位差错.101111，计数值被破坏含字节填充的分界符法成帧(a)使用标志字节作为帧的开始和结束(b)字节填充前后的4个字节序列例子缺点是依赖于缺点是依赖于8位字符模式位字符模式含位填充的分界符法分帧位填充 标志位模式为01111110，每5个1填充1个0(a)原始数据.(b)线路上的数据.(c)删除填充之后存储在接收方存储器中的数据.物理层编码违例法成帧如果物理介质上的编码方法中包含冗余信息，可以使用例：+1表示高电平、1表示低电平+11表示比特“1”；11表示比特“0”，而+1+1和11不表示数据，有可能用于帧分界注：多种方法的联合使用可能会提高帧边界检测的速度内容a)数据链路层设计要点b)错误检测和纠正c)基本数据链路协议d)滑动窗口协议e)协议验证f)数据链路层协议示例错误检测和纠正纠错码检测码突发错误：集中在某些比特位产生错误。例如 1000100位数据块，每一位错误概率0.001；如果错误是孤立的，那么每个1000位数据块都可能有某1位发生错误；如果错误每次发生都是连续的100位，那么这些错误可能只发生在12块数据块中，大部分数据块没有错误。编码基础知识编码基础知识汉明距离：两个码字中不相同的位的格式，设码字x,y，其汉明距离为w(xy)，其中w(z)表示z比特串中1的个数若x和y的汉明距离为d，则x至少需要d个错误位才会变成y。所有可用码字之间最小的汉明距离称为最小汉明距离一些结论：为了检测d位错误，需要d+1的最小汉明距离为了纠正d位错误，需要2d+1的最小汉明距离编码基础知识编码基础知识奇偶校验码：数据后面增加1位奇偶位，奇偶位的取值保证码字中1的数目是偶数（偶校验）或者奇数（奇校验）例如1011010，偶校验时发送10110100，奇校验时发送10110101奇偶校验编码方法汉明距离为2？可以检测单个错误一种距离为5的编码方案A=0000000000 B=0000011111 C=1111100000 D=1111111111可以纠正2个错误，例如0000000111会被纠正为B码字纠错码之汉明码考虑n位码字n=m+r其中m位为报文，r位为校验位。r下界：m+r+12r当m=7时,8 2rr可以计算r最小值4汉明码手工计算 (1)(2)3 (4)5 6 7 (8)9 10 11 偶校验偶校验H:1 0 0 1 0 0 03=1+2;5=1+4;6=2+4;7=1+2+4;9=1+8;10=2+8;11=1+2+8;3|5|7|9|11 3|6|7|10|11 5|6|7 9|10|11 0 0 1 0m:1 1 0 1 1 0 1 1 1 0 0汉明码也能够纠正突发错误，只需要把传输的码字按照矩阵排列即可。通常用于出错概率比较高的链路检错码（7，4）汉明码可以纠正单）汉明码可以纠正单个错误，可以检测个错误，可以检测2位错误位错误（最小汉明距离为（最小汉明距离为3）奇偶校验编码方法汉明距离奇偶校验编码方法汉明距离为为2，可以检测单个错误，可以检测单个错误为了增加突发性错误的检测为了增加突发性错误的检测概率，可以使用分组的奇偶校概率，可以使用分组的奇偶校验码验码可以纠正单个错误可以纠正单个错误是否能检测是否能检测3位错误呢？位错误呢？码流码流A BM-1 M坏块被接受坏块被接受每一列都有每一列都有正确的奇偶位正确的奇偶位2na1a2an-1anH1b1b2bn-1bnH2m-11m-12m-1nm-1nHn-1m1m2mn-1mnHnV1V2Vm-1VmHn+1检错码循环冗余校验码一帧有m位，对应M(x)发送方和接收方有共同的生成多项式G(x)，阶为r发送方M(x)xr G(x)=S(x)+R(x)，发送方发送T(x)=M(x)xr R(x)接收方计算T(x)/G(x)，如果整除则认为没有错误；如果不整除，则认为发生了错误，错误可以用E(x)表示所有长度小于等于r位的错误，可以检测（G(x)为r+1位）当G(x)含有x+1因子时，可以检测只影响奇数个位的突发错误当长度大于r时，如果所有位模式等概，则错判概率约为(1/2)r标准化的G(x)多项式P167检测码多项式编码校验和的计算过程.基本数据链路层协议无限制的单工协议单工的停等协议有噪声信道的单工协议通用头文件15种数据类型：帧类型可以是数据、ACK帧、NAK帧帧的序列号用于接收方检测重复的帧ACK序列号指出了接收方刚接收到的帧的序列号分组信息在数据帧时有效，包含网络层分组通用头文件2接口函数初始状态wait_for_event层间接口from/to_network_layerfrom/to_physical_layer定时器发送方数据定时器start/stop_timer接收方ACK定时器start/stop_ack_timer层交互enable/disable_n._l.内联宏inc无限制的单工协议信道单向信道不会损坏或者丢失帧网络层始终就绪接收方缓存空间无限处理时间可以忽略无限制的单工协议发送数据高层-低层接收数据低层-高层单向单工的停等协议信道半双工信道不会损坏或者丢失帧网络层始终就绪接收方只能处理一帧，没有缓存和排队机制处理时间不可忽略，发送方需要考虑接收方的处理时间单工的停等协议需要等待接收方响应给发送方响应有噪声信道的单工协议信道半双工网络层始终就绪信道会损坏和丢失帧接收方只能处理一帧，没有缓存和排队机制损坏和丢失帧：定时器避免冗余：序列号序列号的位数？接收方只需要判断一帧是新帧还是已经接收的帧有重传的ACK协议发送方发送方s.info=buffer;s.seq=n;to_phical_layer(&s)start_timer发送发送0帧帧Wait for ACK0n=1s.info=buffer;s.seq=n;to_phical_layer(&s)start_timer发送发送1帧帧正确接收了一帧正确接收了一帧&该帧是该帧是ACK0 stop_timerInc(n)n=0Wait for ACK1正确接收了一帧正确接收了一帧&该帧是该帧是ACK1 stop_timerInc(n)有重传的ACK协议接收方接收方等待等待帧帧n=0等待等待帧帧n=1接收到一帧&不是帧0发送ACK1接收到一帧&帧序号为0to_network_layer;Inc(n);发送ACK0接收到一帧&不是帧1发送ACK0接收到一帧&帧序号为1to_network_layer;Inc(n);发送ACK1滑动窗口协议1位滑窗协议Go Back N选择重传滑窗协议概述全双工数据传输两条数据单工信道一条信道，数据帧和ACK帧混合，用帧头部信息区分不同帧捎带确认：确认信息附在往外发送的数据帧上需要增加定时器来决定是否使用捎带确认滑动窗口协议发送窗口发送方已经发送但没有确认的帧，和允许发送的帧。窗口大小可能动态变化接收窗口接收方可以接受的帧示例：窗口大小为1序列号为3比特长.(a)初始时.(b)第一帧发送以后(c)第一帧接收以后(d)第一个确认帧收到以后.1位滑窗协议1Continued 通常只有某一个数通常只有某一个数据链路层程序需要据链路层程序需要首先发送一帧，然首先发送一帧，然后才进入循环后才进入循环1位滑窗协议2更新buffer内容，不执行时buffer依旧是刚发送的帧两个if条件，4种程序流程1位滑窗协议3(a)通常的情形.(b)双方并发地发送初始分组（进入循环之前，都发送了一帧）向量含义是(seq,ack,分组号)；星号表示网络层接受了一个分组停等协议的性能考虑传播延迟，即考虑分组在路上的时间使用停等协议（窗口大小为1）例:1 Gbps链路,15 ms 端到端传播延迟,1KB 分组:Ttransmit=8210/pkt109 b/sec 8 usU sender:利用率 发送方忙于发送数据的时间与发送时间之比L(packet length in bits)R(transmission rate,bps)=约每30ms可以发送1KB 分组-每秒约33kB、即约0.26Mbps，而链路带宽是 1 Gbps后果：网络协议限制了物理资源的使用!管道化基本思想是允许发送方在阻塞(wait_for_event)之前发送w帧，w1w的取值与带宽时延积有关。带宽R为Xbps，时延为Ys，那么带宽时延积为XYb，即时延期间发送方可以发送的数据量，或者发送方填满链路所需要的数据量把链路看作管道，则带宽时延积说明了管道的容量管道化：在链路上发送多帧，使得链路上的数据量逼近管道容量管道化问题：在一个很长的帧流中，某一帧被损坏或者丢失，接收方该如何损坏帧之后到达的正确帧呢？Go Back N&选择重传管道化与错误回复(a)接收窗口大小为1.(b)接收窗口尺寸较大.回退回退n帧帧接收方丢弃错误帧之后的所有帧发送方在没有被确认的帧超时后，退回该帧，重新发送选择重传选择重传接收方缓存错误帧之后的正确帧；发送方在没有被确认的帧超时后重新发送该帧使用NAK提高性能检测到错误时，接收方主动向发送方发送NAK，激发重传操作使用 Go Back N的滑窗协议双向数据流信道会损坏帧，丢失帧网络层希望发送分组时，需要引发network_layer_ready事件；链路层使用enable_network_layer和disable_network_layer来阻止链路层引发ready事件使用 Go Back N的滑窗协议Continued 用于检查用于检查b是否在是否在窗口窗口 a,c)内部内部捎带确认发送数据捎带确认发送数据作为作为GBN接收方，接收方，当期望接收的帧是当期望接收的帧是frame_expected时，时，意味着刚接收到意味着刚接收到frame_expected-1这一帧这一帧没有接收到任何帧时，没有接收到任何帧时，使用使用MAX_SEQSliding Window Protocol Using Go Back NContinued ack_expected指向发送方发送出去但没有被确指向发送方发送出去但没有被确认的第一个帧认的第一个帧next_frame_to_send指向发送方发送下一帧指向发送方发送下一帧时使用的帧号时使用的帧号所以所以ack_expected,next_frame_to_send）表示发送方的发送窗口表示发送方的发送窗口nbuffered在发送一帧以后增加在发送一帧以后增加1，在正确接收，在正确接收到一帧的到一帧的ack后减少后减少1，所以指明了已经发送但，所以指明了已经发送但是没有被确认的帧的数量，说明了窗口大小是没有被确认的帧的数量，说明了窗口大小frame_expected接收方期望接收的帧，在接收方期望接收的帧，在GBN中，接收方按序接收，所以中，接收方按序接收，所以frame_expected帧左侧的帧恰好是接收到需要帧左侧的帧恰好是接收到需要ACK的帧的帧Sliding Window Protocol Using Go Back NContinued 发发送送接接收收Sliding Window Protocol Using Go Back N超超时时发发送送发送方接收到发送方接收到ack，滚动窗口，滚动窗口关于nbuffered大小Assume MAX_SEQ=7nbuffered=807070707Assume MAX_SEQ=7nbuffered=7067564xyAck0Ack1ACK7ACK7Ack0ACK5ACK6ACK6关于定时器用软件来模拟多个定时器三个超时事件分别在三个超时事件分别在10:00:00.510:00:00.5+00:00:00.810:00:00.5+00:00:00.8+00:00:00.6缓存接收到的失序帧线路质量比较差，就不应该把正确的帧抛弃，而应该利用起来选择重传:序列号与窗口大小a)例:b)序列号:0,1,2,3c)窗口大小=3d)接收方区分不了到底是窗口大小只有3个还是序列号小于等于3!e)接收方会不正确的把冗余数据作为新的数据发送给上层f)Q:序列号大小与窗口大小的关系是什么?(MAX_SEQ+1)/2选择重传带来的。接收方缓存区大小：显然应该与窗口大小一致定时器数量：发送方缓存区的数量间隔：紧一点，发送方较快超时帧号：确定帧号较复杂，协议中假设为oldest_frame辅助定时器接收方没有即时的反向流量时，辅助定时器超时激发ACK发送方数据重传之前，接收方应该优先超时，然后主动发送ACK帧接收方在接收正确到达的帧时，启动辅助定时器否定确认接收方接收到受损帧接收方接收到的帧不是期望的帧，并且该期望的帧的NAK没有发送过A Sliding Window Protocol Using Selective RepeatContinued 可以发送可以发送数据帧和数据帧和nak帧帧与协议与协议5含义相同含义相同Continued A Sliding Window Protocol Using Selective Repeat(2)窗口上限窗口上限三个缓存对应输三个缓存对应输入输出窗口和到入输出窗口和到每个缓存是否有每个缓存是否有数据的指示数据的指示A Sliding Window Protocol Using Selective Repeat(3)Continued 发送方发送方接收方接收方指示将要发送的帧的序列号指示将要发送的帧的序列号怀疑有错，发送怀疑有错，发送nak，不然准备，不然准备接收下来，先启动辅助定时器接收下来，先启动辅助定时器当期望的帧到了当期望的帧到了以后，期望目标以后，期望目标转移，需要重设转移，需要重设no_nak等与期望等与期望帧相关的变量帧相关的变量是否在接收窗是否在接收窗口内？是则缓口内？是则缓存下来，并尝存下来，并尝试递交网络层试递交网络层A Sliding Window Protocol Using Selective Repeat(4)注意到发送方发送时注意到发送方发送时ack是是frame_expected-1，此时，此时还原为还原为frame_expected发送方发送方滚动窗口滚动窗口协议验证有限状态机模型Petri 网模型有限状态机发送方或者接收方在任意时刻总是处于某种状态有限状态机是协议分析所常用的工具描述等待方协议时，其主要状态为等待0或者1帧描述整个发送方、接收方、信道所构成的系统的协议时，系统的主要状态为各个组成部分主要状态的合理组合状态转换指从一种状态到达另外一种状态，通常时事件触发初始状态即系统开始运行时，或者某个起始时刻系统所具有的状态从初始状态开始，经过状态转换，分析所有可能达到的状态和不可能达到的状态称为可达性分析。可达性分析是分析协议正确性的基本技术Finite State Machined Models1.(a)协议3的状态图.(b)转换（变迁、跃迁）.2.SRC:Source Receive ChannelPetri 网Petri网具有四个基本元素：库所Place、变迁transition、弧arc、标记token所有可能的状态由Place表示，在图中用圆圈表示系统当前所处的状态由token表示，图中为粗黑点转换用水平或者垂直的线表示，基本上可以理解为瞬时态arc是从库所到转换的输入弧，或者转换到库所的输出弧下图为典型的包含两个库所和两个转换的Petri网.Petri Net Models(2)协议3的Petri网描述SRC的状态分别描述初始态：初始态：S等待等待ACK0，0帧在帧在C上，上，R等待接收等待接收0可能激活的转换：可能激活的转换：2，5，10Case1:超时则超时则2激活，激活，发送方重发发送方重发0帧，依旧帧，依旧在等待在等待ACK0状态，信状态，信道接收到道接收到0帧，依旧在帧，依旧在0帧在帧在C上的状态上的状态Case2:接收方顺利接收接收方顺利接收0帧则帧则10激活，接收方激活，接收方发送发送ACK，进入等待，进入等待1帧状态，信道进入帧状态，信道进入ACK在在C状态，发送方状态状态，发送方状态不变，但此时不变，但此时1可能激可能激活活Example Data Link ProtocolsHDLC High-Level Data Link ControlThe Data Link Layer in the InternetHigh-Level Data Link ControlFrame format for bit-oriented protocols.成帧成帧成帧成帧检错、纠错检错、纠错序列号、确认等序列号、确认等High-Level Data Link Control(2)不同类型帧的控制域(a)信息帧（数据帧）.(b)管理帧：确认帧、NAK帧（GBN）、选择重传.等(c)控制或者提供不可靠连接.The Data Link Layer in the Internet通过调制解调器拨号上网的点到点链路.PPP Point to Point ProtocolThe PPP full frame format for unnumbered mode operation.成帧成帧 Flag（面向字符）（面向字符）错误检测（校验和域）错误检测（校验和域）序列号、确认（控制域，默认不提供可靠传输）序列号、确认（控制域，默认不提供可靠传输）额外的：额外的：NCP:可以协商承载的协议（可以协商承载的协议（IP,IPX等网络层协议或者其它协议）等网络层协议或者其它协议）LCP:用于启动线路、测试线路，协商参数、关闭连接用于启动线路、测试线路，协商参数、关闭连接PPP LCP链路启动到关闭的简化状态图P203PPP Point to Point Protocol(3)不同类型的LCP帧用于PPP所设计的目标，例如协商、测试、管理连接等。其中协商机制是PPP的特色之一思考a)链路层如何成帧b)CRC校验如何工作c)可靠数据传输都需要在终端设置哪些变量，各有什么作用？