第二讲-数据链路层课件

MAC协议协议 无线网络需要克服的问题无线网络需要克服的问题 无线局域网无线局域网MAC协议协议 无线传感网络无线传感网络MAC协议协议内容提要内容提要n1.数据链路层概述n2.MAC协议qCSMAqIEEE 802.11 MAC协议qS-MAC协议数据链路层介绍数据链路层介绍n数据链路层在五层结构中的位置qMAC在协议结构中的重要性（52页第二段）n数据链路层的基本概念q下一张PPTn数据链路层的简单模型q如下图所示数据链路层基本概念数据链路层基本概念r数据链路数据链路(data link)除了物理线路外，还必须有通信除了物理线路外，还必须有通信协议来控制这些数据的传输。把实现这些协议的硬件协议来控制这些数据的传输。把实现这些协议的硬件和软件加到链路上，就构成了数据链路。和软件加到链路上，就构成了数据链路。r数据链路层的主要功能数据链路层的主要功能m(1)链路管理链路管理m(2)帧定界帧定界 m(3)流量控制流量控制m(4)差错控制差错控制 m(5)将数据和控制信息区分开将数据和控制信息区分开 m(6)透明传输透明传输 m(7)寻址寻址r链路管理：当网络中的两个结点要进行通信时，数据链路管理：当网络中的两个结点要进行通信时，数据的发方必须确知收方是否已经处在准备接收的状态。的发方必须确知收方是否已经处在准备接收的状态。数据链路的建立、维持和释放就叫做链路管理数据链路的建立、维持和释放就叫做链路管理。m信道分割方法，如后信道分割方法，如后数据链路层基本概念数据链路层基本概念n信道的分割方法q信道分割,按时间,频率或编码n时分、码分、频分q随机分割(动态)nALOHA,S-ALOHA,CSMAq轮转分割n从主结点发出轮询,令牌传递（token passing）数据链路层介绍数据链路层介绍n数据链路层在五层结构中的位置n数据链路层的基本概念q下一张PPTn数据链路层的简单模型q如下图所示局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动数据链路层的简单模型数据链路层的简单模型数据链路层的简单模型数据链路层的简单模型(续）续）局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动下面介绍数据链路层的差错控制传输差传输差错产生错产生过程过程差错检测n在传输过程中可能会产生比特差错：1 可能会变成 0 而 0 也可能变成 1。n在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER(Bit Error Rate)。n误码率与信噪比有很大的关系（正比关系）。n为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。循环冗余检验的原理 n在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。n在发送端，先把数据划分为组。假定每组 k 个比特。n假设待传送的一组数据 M=101001（现在 k=6）。我们在 M 的后面再添加供差错检测用的 n 位冗余码一起发送。冗余码的计算 n用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。n得到的(k+n)位的数除以事先选定好的长度为(n+1)位的除数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 少1 位，即 R 是 n 位。冗余码的计算举例 n现在 k=6,M=101001。n设 n=3,除数 P=1101，n被除数是 2nM=101001000。n模 2 运算的结果是：商 Q=110101，余数 R=001。n把余数 R 作为冗余码添加在数据 M 的后面发送出去。发送的数据是：2nM+R 即：101001001，共(k+n)位。110101 Q(商)P(除数)1101 101001000 2nM(被除数)1101 1110 1101 0111 0000 1110 1101 0110 0000 1100 1101 001 R(余数)，作为 FCS 循环冗余检验 1101010110 Q 商 除数 G 110101 101000110100000 2nM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数循环冗余检验的原理说明循环冗余检验的原理说明假设待传送的数据假设待传送的数据 M M=1010001101=1010001101（共（共k k bit bit）。我们在）。我们在M M的的后面再添加供差错检测用的后面再添加供差错检测用的 n n bit bit 冗余码冗余码一起发送。一起发送。循环冗余检验举例循环冗余检验举例帧检验序列 FCS n在数据后面添加上的冗余码称为帧检验序列 FCS(Frame Check Sequence)。n循环冗余检验 CRC 和帧检验序列 FCS并不等同。nCRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。nFCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的唯一方法。接收端对收到的每一帧进行 CRC 检验 n(1)若得出的余数 R=0，则判定这个帧没有差错，就接受(accept)。（严格说，这么做是不正确的，有可能出现R为0，而帧有差错，那为什么可以这么做呢，其理由是：R为0，而帧有差错的概率很小）n(2)若余数 R 0，则判定这个帧有差错，就丢弃。（严格说，这么做是正确的，即R 0 这个帧一定出了差错）n但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。（因此，这是一种后向纠错方法）n只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。nCRC校验码的检错能力：校验码的检错能力：q可检出所有奇数个错；可检出所有奇数个错；q可检出所有双位错；可检出所有双位错；q可检出所有可检出所有G(x)长度的突发错。长度的突发错。n常用的生成多项式常用的生成多项式G(x)：qCRC16=x16+x15+x2+1qCRC32=x32+x26+x23+x22+x16+x11+x10+x8+x7+x5+x4 +x2+x+1应当注意 n仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(accept)。n“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错”。n也就是说：“凡是接收端数据链路层接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。n要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。内容提要内容提要n1.概述q前面介绍了差错检验的问题，下面介绍链路管理n2.MAC协议qCSMAqIEEE 802.11 MAC协议qS-MAC协议CSMA 载波监听多点接入载波监听多点接入n“多点接入”表示许多计算机以多点接入的方式连接在一根总线上。n“载波监听”是指每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不要发送数据，以免发生碰撞。nCSMA分为坚持型与非坚持型nCSMA/CD 表示 Carrier Sense Multiple Access with Collision Detection。检测到碰撞后检测到碰撞后n在发生碰撞时，总线上传输的信号产生了严重的失真，无法从中恢复出有用的信息来。n每一个正在发送数据的站，一旦发现总线上出现了碰撞，就要立即停止发送，免得继续浪费网络资源，然后等待一段随机时间后再次发送。电磁波在总线上的有限传播速率的影响电磁波在总线上的有限传播速率的影响 n当某个站监听到总线是空闲时，也可能总线并非真正是空闲的。nA 向 B 发出的信息，要经过一定的时间后才能传送到 B。nB 若在 A 发送的信息到达 B 之前发送自己的帧(因为这时 B 的载波监听检测不到 A 所发送的信息)，则必然要在某个时间和 A 发送的帧发生碰撞。n碰撞的结果是两个帧都变得无用。1 kmABt碰撞t=2 A 检测到发生碰撞 t=B 发送数据B 检测到发生碰撞 t=t=0单程端到端传播时延记为 传播时延对载波监听的影响 1 kmABt碰撞t=B 检测到信道空闲发送数据t=/2发生碰撞t=2 A 检测到发生碰撞 t=B 发送数据B 检测到发生碰撞 t=ABABAB t=0 A 检测到信道空闲发送数据ABt=0t=B 检测到发生碰撞停止发送STOPt=2 A 检测到发生碰撞STOPAB单程端到端传播时延记为 争用期n最先发送数据帧的站，在发送数据帧后至多经过时间 2（两倍的端到端往返时延）就可知道发送的数据帧是否遭受了碰撞。（如上一页所示）n以太网的端到端往返时延 2 称为争用期，或碰撞窗口。n经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。争用期的长度 n以太网取 51.2 s 为争用期的长度。n对于 10 Mb/s 以太网，在争用期内可发送512 bit，即 64 字节。n以太网在发送数据时，若前 64 字节没有发生冲突，则后续的数据就不会发生冲突。最短有效帧长 n如果发生冲突，就一定是在发送的前 64 字节之内。n由于一检测到冲突就立即中止发送，这时已经发送出去的数据一定小于 64 字节。n以太网规定了最短有效帧长为 64 字节，凡长度小于 64 字节的帧都是由于冲突而异常中止的无效帧。强化碰撞 n当发送数据的站一旦发现发生了碰撞时：n立即停止发送数据；n再继续发送若干比特的人为干扰信号(jamming signal)，以便让所有用户都知道现在已经发生了碰撞。数据帧干扰信号 TJ人为干扰信号 ABTBt B 发送数据A 检测到冲突开始冲突信道占用时间A 发送数据B 也能够检测到冲突，并立即停止发送数据帧，接着就发送干扰信号。这里为了简单起见，只画出 A 发送干扰信号的情况。内容提要内容提要n1.概述n2.MAC协议qCSMAqIEEE 802.11 MAC协议 qS-MAC协议CSMA/CD协议不适用于无线网络协议不适用于无线网络r主要原因如下：主要原因如下：无线局域网中的隐蔽站问题无线局域网中的隐蔽站问题r隐蔽站隐蔽站:A,C两个站点不能互相两个站点不能互相“听见听见”m障碍物障碍物,信号衰减信号衰减m在在B站点发生冲突站点发生冲突 r802.11MAC的设计目标的设计目标:避免可能在避免可能在B站发生的冲突站发生的冲突rCSMA/CA:带有冲突避免（Collision Avoidance）策略的CSMA，见第53页倒数第3、4段的描述。暴露站问题暴露站问题IEEE 802.11 MAC协议协议rIEEE 802.11 MAC协议分为分布式协调功能协议分为分布式协调功能(Distributed Coordination Function,DCF)和点协调和点协调功能功能(Point Coordination Function，PCF)两种访问控两种访问控制方式，其中制方式，其中DCF方式是方式是IEEE 802.11协议的基本访协议的基本访问控制方式。（问控制方式。（54页第页第1、2段）段）帧间间隔帧间间隔rIEEE 802.11 MAC协议规定了三种基本帧间间隔协议规定了三种基本帧间间隔(InterFrame Space，IFS)，用来提供访问无线信道，用来提供访问无线信道的优先级：的优先级：mSIFS(short IFS)：最短帧间间隔。：最短帧间间隔。mPIFS(PCF IFS)：PCF方式下节点使用的帧间间隔。方式下节点使用的帧间间隔。mDIFS(DCF IFS)：DCF方式下节点使用的帧间问隔。方式下节点使用的帧间问隔。根据根据CSMA/CACSMA/CA协议，当节点要传输一个分组时，它首先侦听信道状协议，当节点要传输一个分组时，它首先侦听信道状态。如果信道空闲，而且经过一个帧间间隔时间态。如果信道空闲，而且经过一个帧间间隔时间DIFSDIFS后，信道仍然空后，信道仍然空闲，则站点立即开始发送信息。如果信道忙，则站点始终侦听信道，闲，则站点立即开始发送信息。如果信道忙，则站点始终侦听信道，直到信道的空闲时间超过直到信道的空闲时间超过DIFSDIFS。当信道最终空闲下来的时候，节点进。当信道最终空闲下来的时候，节点进一步使用二进制退避算法，进入退避状态来避免发生碰撞。一步使用二进制退避算法，进入退避状态来避免发生碰撞。随机退避时间按下面公式进行计算：随机退避时间按下面公式进行计算：退避时间退避时间=Random()aSlottime 其中，其中，Random()是在竞争窗口是在竞争窗口0，CW内均匀分布的伪内均匀分布的伪随机整数；随机整数；CW是整数随机数，它的数值位于标准规定是整数随机数，它的数值位于标准规定的的aCWmin和和aCWmax之间；之间；aSlottime是一个时槽时是一个时槽时间，包括发射启动时间、介质传播时延、检测信道的间，包括发射启动时间、介质传播时延、检测信道的响应时间等。响应时间等。网络节点在进入退避状态网络节点在进入退避状态时，启动一个退避计时器，时，启动一个退避计时器，当计时达到退避时间后结束当计时达到退避时间后结束退避状态。在退避状态下，退避状态。在退避状态下，只有当检测到信道空闲时才只有当检测到信道空闲时才进行计时。如果信道忙，退进行计时。如果信道忙，退避计时器中止计时，直到检避计时器中止计时，直到检测到信道空闲时间大于测到信道空闲时间大于DIFSDIFS后才继续计时。当多个节点后才继续计时。当多个节点推迟且进入随机退避时，利推迟且进入随机退避时，利用随机函数选择最小退避时用随机函数选择最小退避时间的节点作为竞争优胜者。间的节点作为竞争优胜者。802.11 MAC层层:CSMA/CA简述简述802.11 CSMA:发送方发送方-如果检测到信道闲置了如果检测到信道闲置了DISF 秒秒.然后然后传输整个帧传输整个帧(无冲突检测无冲突检测)-如果检测到信道忙如果检测到信道忙 然后然后 进行二进制避退进行二进制避退802.11 CSMA 接收方接收方:如果接收如果接收 OK 等待等待 SIFS后返回ACKIEEE 802.11 MAC 协议协议802.11 CSMA 协议协议:其他方其他方rNAV:网络分配向量网络分配向量（Network Allocation Vector）r802.11 帧具有传输时间字段帧具有传输时间字段r其他站点其他站点(听见有传输时听见有传输时)必必须推迟若干须推迟若干 NAV时间单位再时间单位再对信道进行访问对信道进行访问冲突避免冲突避免:RTS-CTS 交换交换rCSMA/CA:进行显式的信进行显式的信道预留道预留m发送方发送方:发送简短的发送简短的 RTS:request to sendm接收方接收方:使用简短的使用简短的 CTS:clear to send回回应应rCTS 为发送方预留了信道为发送方预留了信道,并通知了其他并通知了其他(可能是隐蔽可能是隐蔽的的)站点站点r避免了隐蔽站点问题避免了隐蔽站点问题 A,B,CA,B,D冲突避免冲突避免:RTS-CTS 交换交换r由于由于RTS/CTS比较短比较短:m发送时间短，发生冲突的发送时间短，发生冲突的可能小可能小m最终的结果同冲突检测基最终的结果同冲突检测基本一致本一致 802.11 MAC 802.11 MAC协议通过协议通过立即主动确认机制立即主动确认机制和和预留机制预留机制提高性能。在主动确认提高性能。在主动确认机制中，当目标节点收到一个发送给它的有效数据帧机制中，当目标节点收到一个发送给它的有效数据帧(DATA)(DATA)时，必须向源节时，必须向源节点发送一个应答帧点发送一个应答帧(ACK)(ACK)，确认数据已被正确接收到。为了保证目标节点在发，确认数据已被正确接收到。为了保证目标节点在发送送ACKACK过程中不与其它节点发生冲突，目标节点使用过程中不与其它节点发生冲突，目标节点使用SIFSSIFS帧间隔。主动确认机帧间隔。主动确认机制只能用于有明确目标地址的帧，不能用于组播和广播报文传输。制只能用于有明确目标地址的帧，不能用于组播和广播报文传输。802.11 MAC 小结小结rCSMA/CAm什么是什么是CSMA/CAr3种种IFSrRTC/CTS rNAV无线传感器网络无线传感器网络MAC协议概述协议概述r无线传感器网络无线传感器网络MAC协议需要考虑协议需要考虑3个问题（个问题（52页）页）m节省能量节省能量m可扩展性可扩展性m网络效率网络效率r传统传统MAC协议不适于无线传感器网络（协议不适于无线传感器网络（52页最后一段）页最后一段）m例如，例如，IEEE 802.11 MAC协议协议r无线传感器网络无线传感器网络MAC协议通常采用协议通常采用“侦听侦听/睡眠睡眠”的策略的策略（53页）页）MAC协议分类协议分类r分类方式（分类方式（53页）页）m分配信道的方式分配信道的方式时分复用无竞争型时分复用无竞争型随机竞争型随机竞争型（53页倒数第页倒数第5段）例如，段）例如，SMAC 混合型：二者结合混合型：二者结合m使用的信道数目使用的信道数目单信道单信道多信道多信道m控制方式控制方式集中式控制集中式控制发布式控制发布式控制52Sensor MAC协议协议rSensor MAC协议概述协议概述m是一种基于竞争的是一种基于竞争的MAC层协议层协议mS-MAC协议的适用条件是传感器网络的数据传输量不大，网络内部能够协议的适用条件是传感器网络的数据传输量不大，网络内部能够进行数据的处理和融合以减少数据通信量，网络能容忍一定程度的通信进行数据的处理和融合以减少数据通信量，网络能容忍一定程度的通信延迟延迟m在在802.1l MAC协议的基础上，针对传感器网络的节省能量需求而提出的协议的基础上，针对传感器网络的节省能量需求而提出的m采用采用RTS/CTS/DATA/ACK作为基本传输机制作为基本传输机制SMAC协议-基本思想r周期性睡眠和监听机制：睡眠与监听的周期交替r流量自适应侦听机制：不进入睡眠而是保持侦听状态r 串扰避免机制：邻居通信的时候，进入睡眠状态r消息传递机制：支持长消息传输SMAC协议-基本思想r周期性睡眠和监听（57页）m为什么周期性睡眠和监听m什么是周期性睡眠和监听S-MAC协议将时间分为帧，帧内分监听工作阶段和睡眠阶段，侦听，睡眠，侦听，睡眠，当节点处于睡眠阶段时，关闭无线电波，以节省能量。当节点处于监听工作阶段，可以发送数据mSYNC消息与调度表 pa3若没有收到其它站点的调度若收到其它站点的调度（又若收到多个调度）m动态设置调度表 pa4m虚拟簇 见下 具有相同调度的节点形成一个所谓具有相同调度的节点形成一个所谓的虚拟簇的虚拟簇，边界节点记录两个或多个调，边界节点记录两个或多个调度。如果传感器网络的部署范围较广，度。如果传感器网络的部署范围较广，可能形成众多不同的虚拟簇，使得可能形成众多不同的虚拟簇，使得S-S-MACMAC协议具有良好的可扩展性。协议具有良好的可扩展性。为了适应新加入节点，每个节点要为了适应新加入节点，每个节点要定期广播自己的调度信息，使新节点可定期广播自己的调度信息，使新节点可以与已经存在的相邻节点保持同步。如以与已经存在的相邻节点保持同步。如果节点同时收到两种不同的调度，如图果节点同时收到两种不同的调度，如图所示的处于两个不同调度区域重合部分所示的处于两个不同调度区域重合部分的节点，那么这个节点可以选择先收到的节点，那么这个节点可以选择先收到的调度，并记录另一个调度信息。的调度，并记录另一个调度信息。邻居节点通过协商的一致性睡眠调邻居节点通过协商的一致性睡眠调度机制形成虚拟簇，减少节点的空闲侦度机制形成虚拟簇，减少节点的空闲侦听时间。听时间。周期性侦听睡眠机制回顾：1.什么是周期性侦听睡眠2.什么是虚拟簇？带来何种益处？（左下）3.如何形成虚拟簇？通过传输SYNC消息以及动态调整调度表。SMAC协议-基本思想r流量自适应侦听机制m为什么（57页最后一段）m在一次通信过程中，通信节点的邻居在此次通信结束后唤醒并保持监听一段时间。如果节点在这段时间接收到RTS帧，则可以立即接收数据，而不需要等到下一个监听周期，从而减少了两个节点间的数据传输延迟。SMAC协议-基本思想r串扰避免机制（58页第2-4段）m串扰的危害：增加能量消耗，因此要避免m串扰避免机制载波监听，信道忙时睡眠，避免接收串扰数据包SMAC协议-基本思想r消息传递机制m58页第5段m将长的信息包分成若干个短的DATA段m所有DATA使用一个RTSCTS控制分组占用信道m每个DATA都有ACK保障传输成功SMAC协议-基本思想r周期性睡眠和监听机制：睡眠与监听的周期交替r流量自适应侦听机制：不进入睡眠而是保持侦听状态r 串扰避免机制：邻居通信的时候，进入睡眠状态r消息传递机制：支持长消息传输小结小结r差错检验差错检验mCRCr2个问题个问题r802.11 MAC mCSMA/CA什么是什么是CSMA/CAmRTC/CTSmNAVrS-MACm4种机制种机制r思考题思考题 6-11