第四讲-介质访问控制子层.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第四讲 介质访问控制子层,2,1,理解,MAC,子层的基本问题,2,理解信道分配的两种基本思想,3,掌握,ALOHA,协议、,CSMA,协议,4,理解无冲突协议、有限竞争协议,5,掌握以太网及有关的协议,6,理解无线,LAN,以及相关协议,7,了解宽带无线网络、蓝牙技术和,RFID,本讲要求,3,基本问题,广播信道中，,两主机间,的通信问题,问题分析,地址问题、流量控制、帧格式、出错处理、,信道分配问题,关键问题：,当存在多方竞争使用信道的时候，如何确定谁可以使用信道,解决问题的基本思路,（,1,）静态信道分配方案（,FDM,、,TDM,）,（,2,）动态信道分配方案（竞争机制）,4,频分多路复用,-FDM,基本思想,如果总共有,N,个用户，则整个带宽分为,N,份，每一个用户一份。,主要问题,带宽浪费，效率低下！,结论,传统的信道分配方法不适应突发性流量情况，需要寻求新的方法,动态信道分配方法,5,频分多路复用效率分析（,1,）,信道通信延时分析,信道容量：,C(bit/s),；平均延迟：,T,；,帧到达时间间隔服从指数分布，帧的平均到达率：,(fr/s),帧长度,服从指数分布，,帧的平均长度：,1/,（,bit/fr,）,符合,M,/,M,/,1,排队系统模型,M,（顾客到达时间间隔分布）,帧的,平均到达率（输入率）：,(fr/s),M,（服务时间分布）,信道服务率：信道容量,/,帧的平均长度,C(fr/s),1,（并列服务台个数）,6,频分多路复用效率分析（,2,）,单信道平均延时,（顾客在服务系统中的等待时间）,T=1/(C -),FDM,信道延时,（对于,N,个用户共享信道而言，对于每一个用户）,信道容量：,C/N,信道平均输入率：,/N,平均帧长度：,1/,T,FDM,=1/(C/N-/N),=N/(C -),=NT,TDM,的效率和,FDM,一样！,9,动态信道分配方案（,3,）,动态信道分配方案必须解决的基本问题,（,1,）谁可以发送数据？,（,2,）是否发生冲突？,（,3,）面对冲突的解决方法？,（,4,）评价标准,传输效率如何？（信道利用率、传输延迟）,基本的多路访问协议,（,1,）,ALOHA,协议,（,2,）载波侦听协议,（,3,）无冲突协议,（,4,）有限竞争协议,（,5,）无线,LAN,协议,10,ALOHA,协议,基本思想,（,1,）当用户有数据发送时，马上发送数据。,（,2,）当检测到帧损坏后，等待随机的时间后，再次发送该帧。,sender A,sender B,sender C,collision,t,可行吗？效率如何？成功传输的概率是多少？,11,ALOHA,协议分析（,1,）,帧时：,传输一帧所需要的时间，即帧长,/,信道容量,新产生帧数：设均值为,N,在一个帧时内，通信用户一共产生新的帧数，均值为,N,如果,N1,，则一定产生冲突，希望,0,N1,等待传输帧数：设均值为,G,在一个帧时内，通信用户一共产生新帧和等待重传的,帧数之和，显然,G,N,。,概率,一帧时产生,k,帧的概率为：,Prk=G,k,e,-G,/k!,K=0,时，,Prk=0=e,-G,如果假定一次传输成功的概率为,P,0,，则吞吐量,S=GP,0,12,ALOHA,协议分析（,2,）,冲突分析,传输帧,成功的条件：,t,0,t,0,+2t,时间无发送帧,成功的概率：,P,0,=Prk=0=e,-2G,注意：时间为,2,个帧时,吞吐量,S=G P,0,=G e,-2G,极值情况：,G=0.5,S,max,=1/2e=0.184,13,ALOHA,协议分析（,3,）,纯,ALOHA,效率低的原因,冲突的可能太大了！,解决基本思路,减少可能冲突的时间界限！,HOW,？,时间分槽,14,分槽,ALOHA,协议,sender A,sender B,sender C,collision,t,基本原理,将时间分成离散的间隔，每一个间隔对应一帧，数据必须从时槽的开始时刻发送。,效果,冲突危险期被减少了一半，因此效率提高了一倍。,主要问题,全局时间同步,比较困难,15,ALOHA,协议比较,16,ALOHA,协议分析,信道最佳利用率,1/e=37%,总体信道利用率不高,主要原因,无序竞争，冲突频繁,协议改进的基本思想,无序变有序，减少冲突,检测其他站点的行为,根据检测结果调整自己的行为,载波侦听！,载波侦听协议,17,载波侦听协议,CSMA,（,1,）,1-,持续,CSMA,基本原理,站点在发送数据前，先监听信道；,若信道忙，则一直等待到信道空闲,（,1-,持续，贪婪算法思想）,；,若信道空闲，则发送数据；,发送数据后，如果,发生冲突（会吗？）,，,则等待一段随机时间后，再次检测和发送数据,主要优点,减少了冲突的发生,与,ALOHA,相比，性能会提升吗？信道利用率如何？传输延时如何？,证明？测试验证？,Get your hands dirty!,18,载波侦听协议,CSMA,（,2,）,非持续,CSMA,基本原理,站点在发送数据前，先监听信道；,若信道空闲，则发送数据；,若信道忙，则等待随机一段时间后，再次检测和发送数据,发送数据后，如果发生冲突，则等待一段随机时间后，再次检测和发送数据,主要优点,进一步减少了冲突的发生,19,载波侦听协议,CSMA,（,3,）,p-,持续,CSMA,-,应用于分槽信道,基本原理,站点在发送数据前，先监听信道；,若信道空闲，则在当前时槽以,p,概率,发送数据（如何实现？）；,若信道忙，则在下一个时槽，再次检测和发送数据,发送数据后，如果发生冲突，则等待一段随机时间后，再次检测和发送数据,20,载波检测协议,CSMA,（,4,）,性能分析,21,载波侦听协议,CSMA,（,5,）,带冲突检测的,CSMA,CSMA/CD,基本原理：,一旦检测到冲突，则停止数据发送,该协议是以太网的基础,在以太网中详细介绍,CSMA,协议的启示,冲突越少，信道利用率可能会提高！,如果没有冲突的话？效果是不是会更好？,无冲突协议,22,无冲突协议,基本思想,通过协商机制，协调用户竞争信道，避免冲突发生,位图协议,二进制倒计数协议,令牌传递协议,23,位图协议（,1,）,基本原理,N,个接入站点都有惟一地址，从,0N-1,；,每一个竞争周期正好包含,N,个时槽；,如果,M,号站点要发送数据，则在,M,号时槽中传送位,1,；,按照数字顺序排队发送数据，所有数据发送完毕后，开始下一个竞争周期,资源预留协议,24,位图协议分析（,1,）,低负载情况,：数据帧很少，位图不断出现,假设竞争周期为,N,个时隙，一帧数据为,d,时隙,对于低序号的站点，平均,扫描,N/2,个时间槽完成当前时间槽扫描，然后再过,N,个时间槽后，才能够发送数据。,对于高序号的站点，平均,扫描,N/2,个时间槽完成当前时间槽扫描，然后就能够发送数据。,对于,N,个站点而言，平均,扫描,N,个时间槽后才能够发送数据。,信道利用率,=d/(d+N),平均传输延时,=d+N,个时隙,25,高负载情况,：所有站点在任何时候都有数据发送,位图协议分析（,2,）,N,位竞争周期平分到,N,个帧,每一个帧多了一个竞争时隙，即为,d+1,信道利用率,=d/(d+1),平均传输延时,=N(d+1),个时隙,主要问题,扩展性不好。即如果包含站点数目多，则竞争时隙占用了太多的信道资源。,改进思路：二进制站地址（二进制倒计数协议）,26,二进制倒计数协议（,1,）,基本原理,每一个站点有一个二进制地址,如果一个站点想要使用信道，则以二进制位串的形式广播地址（也就是一次发送地址中的一比特位）,来自不同的站的位串被布尔或（,OR,）在一起,如果一个地址中的高位,0,被改写为,1,了，则退出竞争,27,二进制倒计数协议（,2,）,效率分析,信道利用率,=d/(d+log,2,N),精心设计帧结构，可以利用竞争时隙的信息，使得信道利用率,100%,。,主要问题,站点饿死、时间同步、信道支持。,改进思路,循环地址。每次传输后，成功的站会被改写为最小的编号,28,令牌传递协议,基本思想：,站点只有获取令牌时，才能发送数据帧,令牌以一定的策略在站点间流动。（如令牌环）,令牌,站点,IEEE 802.5,令牌环,29,有限竞争协议（,1,）,竞争协议和非竞争协议性能比较分析（延时和信道利用率）,低负载情况（重点考察时延）,高负载情况（重点考察信道利用率）,竞争协议具有比较短的延时，非竞争协议具有比较长的时延。,信道空闲时间多,竞争协议仲裁时间花费增多，可能要多次重传输；非竞争协议仲裁时间花费较少，不需要重传。,竞争协议信道利用效率低，非竞争协议信道利用效率高。,结合竞争协议与非竞争协议的优势？,30,有限竞争协议（,2,）,对称协议性能分析,如果所有的站点都以相同的概率,P,获得信道，则称该,协议是对称,的。,假设,k,个站点竞争信道，有一个站点成功的获得信道的概率为,kp(1-p),k-1,，可得最优解为,p=1/k,减少竞争者的数量！,31,有限竞争协议（,3,）,基本原理,将所有站点划分成组（减少竞争者的规模）,只有,0,号组成员可以竞争,0,号时槽，竞争胜利者发送数据,然后,1,号组成员开始竞争,1,号时槽，以此类推,目的是使竞争者的数量尽量少，以靠近最优曲线的左边，期望获得最优的成功率,关键问题,：,如何将站点分配到各个时槽？,基本要求,：当负载很低的时候，每一个时槽的站点尽量多；当负载很高的时候，每一个时槽的站点尽量少,32,有限竞争协议（,3,）,自适应树搜索协议,把所有站点看做二叉树的叶子节点，构建二叉树,0,号时槽，所有站点参与竞争，如果失败，则其左孩子节点的站点参与,1,号时槽竞争，右孩子节点的站点不参与竞争，以此类推，直到有站点竞争成功。,在某节点上，如果有站点竞争成功，则下一个竞争时隙分配给它兄弟节点上的站点竞争。,失败,失败,不参与下一轮竞争,成功,下一轮,33,有限竞争协议（,4,）,自适应树搜索协议分析,目的：使竞争者的数量尽量少，以靠近最优曲线的左边，期望获得最优的成功率,在高负载的情况下，一旦发生冲突，则参与下一轮的竞争者人数减半！,在低负载的情况下，全体数据发送者参与竞争！,自适应算法：满足负载的各种情况！,自适应树搜索算法协议的改进,高负载情况下，从第,i=log,2,q,级开始开始搜索,34,以太网技术（,1,）,最初的以太网体系结构（,Xerox,）,Bob Metcalfe,3COM,35,10Base-T,10Base-F,以太网技术（,2,）,以太网电缆,36,以太网技术（,3,）,(a)10Base5,(b)10Base2,(c)10Base-T.,37,以太网技术（,4,）,host,host,host,host,Hub,10base-T,38,以太网技术（,5,）,曼彻斯特编码,0,伏表示“,0”,，,5,伏表示,1,容易引起歧义,用,+1,伏表示“,1”,，,-1,伏表示“,0”,，则需要时钟同步,需求,接收者在没有外部时钟的情况下，无歧义的确定每一位的开始、结束或者中间位置,原因,方法,每一位分为两个相等间隔，发送,1,时，第一间隔为高电压，第二间隔为低电压，发送,0,则反之,39,以太网技术（,6,）,协议,CSMA/CD,基本原理,站点在发送数据前，先监听信道,若信道忙，则等待,一段随机时间,后，再试图发送数据,若信道空闲，则发送数据；,边发数据边进行,冲突检测,，如果发现冲突，,则马上停止数据发送,，并等待,一段随机时间,后，再试图发送数据,两个关键问题,冲突检测问题,随机时间等待,40,t,=2,A,检测到,发生碰撞,STOP,以太网技术（,7,）,冲突检测,需求,：需要监听多少时间才能够确信没有冲突？,L,A,B,t,碰撞,t,=,B,检测到,信道空闲,发送数据,t,=,/2,发生碰撞,t,=2,A,检测到发生碰撞,t,=,B,发送数据,B,检测到发生碰撞,t,=,A,B,A,B,A,B,t,=0,A,检测到,信道空闲,发送数据,A,B,t,=0,t,=,B,检测到发生碰撞,停止发送,STOP,A,B,单程端到端,传播时延记为,41,以太网技术（,8,）,结论,主机必须连续发送数据,2,时间后，才能够确信不会发生冲突，也就是说，最小帧的长度是,2,时间所发送的数据,10M,以太网标准，,最大长度,2500,米（,4,个中继器）,在最坏情况下，往返时间大约,50us,（,50*10,-6,），,发送一位数据,100ns,（,100,*,10,-9,）,最小帧数据长度,50us/100ns=500,位，加上安全余量，到,512,位（,2,9,），即,64,字节。,42,以太网技术（,9,）,随机等待时间,二元指数后退算法,一个时槽,512,位时间,(2,),算法,第一次冲突，则随机等待,0,或,1,个时间槽（,2,1,）,第二次冲突，则随机等待,0,、,1,、,2,或,3,个时间槽（,2,2,）,第三次冲突，则随机等待,0-7,个时间槽（,2,3,）,第,i,次冲突，则随机等待,0-2,i,-1,个时间槽（,2,i,）,(i,最大为,10,，即随机数的最大值为,1024),43,以太网技术（,10,）,帧格式,Preamble,Type,Pad,Dest,Source,Data,CRC,8,6,6,2,4,11500,前导域：,10101010,（位填充技术）,地址：第一位,1,，组地址,24,位,24,位,08:00:20:,0e:56:7d,厂商代码,序列号,ROM,RAM,类型：数据发送对象,数据,+,填充：最少,46,字节,校验和：,CRC,校验,确认号？确认信息？序列号？,无确认重传机制,不可思议？,WHY,？,44,以太网技术（,11,）,性能分析,假设条件：,K,个站点竞争信道，一个站点在竞争时槽发送数据的概率,为,p,在某时槽，某一个站点获得信道的概率,A=kp(1-p),k-1,某一个站点通过,j,次竞争获得信道的概率,P,j,=A(1-A),j-1,某一个站点,成功发送数据的,平均竞争次数,T=,jP,j,=jA(1-A),j-1,=1/A,(,最优为,e),假设一帧数据需要,M,秒，则信道效率为,信道效率,=M/(M+2,/A),（,4.6,）,因此，需要限制电缆的长度。,最优为,1/e,45,以太网技术（,12,）,假设帧长为,F,，网络带宽为,B,，电缆长度为,L,，信道的传播速度为,c,，每发送一帧最多竞争,e,个时间槽，,一帧传输时间：,M=F/B,信道效率,=M/(M+2,/A),=,（,F/B,）,/(F/B+2(L/c)*e),1,数据往返时间,2,=2L/c,1+2BLe/cF,=,B,越大，,L,越大，则效率越差！,流量的分布：泊松分布？自相似的,46,以太网技术（,13,）,1500,字节数据,47,以太网技术分析,主要问题,随着站点增加，冲突增加，网络性能下降！,主要解决思路,增加网络带宽,快速以太网、千兆以太网,减少参与冲突竞争的站点规模,交换式以太网,48,交换式以太网,（,A,）集线器,广播式,（,B,）集线器,交换式,49,100M,以太网技术,基本原理,保留原来的帧格式、接口和过程规则，,将位时间从,100ns,降低到,10ns,。,要求,：,将最大长度由,2500,米，减少为,250,米,50,1000M,以太网技术,基本原理,保留原来的帧格式、接口和过程规则，,将位时间从,100ns,降低到,1ns,。,两种工作模式,全双工模式：所有线路都有缓存能力,交换机连接方式,半双工模式：竞争信道,HUB,连接方式，,CSMA/CD,将最大长度减少为,25,米？,载荷扩充技术：将最小帧扩张到,512,字节，最大长度是多少？,帧串技术：多帧连接一起发送。,51,10000M,（万兆）以太网技术,2002,年正式发布,主要应用：数据中心和交换局内部,以太网技术总结,30,多年发展，一直没有被超越,原因：简单！,52,无线,LAN,（,1,）,信道类型,：广播信道,两种工作模式,有基站模式（,PCF,模式）,所有通信通过基站,无基站模式（,DCF,模式）,相互间直接发送数据,直接使用,CSMA/CD,技术？,点到点协议？,53,无线,LAN,（,2,）,无基站通信模式,广播信道的特殊性,隐藏站问题,B,A,C,B,A,C,D,暴露站问题,A,向,B,发送数据,C,不能够接收到,A,的信号,C,向,B,发送数据，导致数据在,B,接收处冲突,B,向,A,发送数据,C,能够监视到信号,C,如果想向,D,发送数据，也必须等待,54,无线,LAN,（,3,）,无基站通信模式,CSMA/CA,避免冲突的多路访问,基本思想：发送方刺激一下接收方，让它输出一个短帧，然后再发送大量数据（带上传输,时间字段,）,对于,C,站点，位于,A,的范围，能接收到,RTS,信息,对于,D,站点，位于,B,的范围，能接收到,CTS,信息,CSMA/CA,解决了隐藏站问题了吗？,CSMA/CA,解决了暴露站问题了吗？,55,无线,LAN,（,4,）,基站通信基本思想,：基站轮询。,基站控制数据发送,无冲突协议,基本机制：周期性广播轮训帧,信标帧,轮询代理机制：新站点可以申请基站轮询服务,噪声问题,：数据帧分片,56,无线,LAN,（,5,）,802.11,协议栈,802.11,帧结构,57,宽带无线网络,LMDS(Local Multipoint Distribution Service),毫米波通信,802.16,标准，和,802.11,的区别？,58,逻辑链路控制,LLC,问题,：,MAC,子层没有提供出错处理机制,LLC,功能：出错处理和流控制,与,HDLC,协议很类似！,实际上几乎没有使用！,59,蓝牙技术,初衷,：将计算机和通信设备或附加部件通过短距离、低功耗、低成本的无线电波连接起来,如无线鼠标、键盘、显示器？,802.15,标准,针对每一个应用提供不同的协议栈！,60,无线射频识别,-RFID,目标,：,条形码的替代品，可远距离（,10,米）被检测,RFID,中的多路访问,RFID,读写器,RFID,标签,RFID,标签,RFID,读写器,RFID,标签,Query,时间槽,0,时间槽,1,Qrepeat,RN16,ACK,ECP,Qrepeat,时间槽,2,时间槽,n,Qrepeat,61,数据链路层协议总结（,1,）,基本问题,：两主机间数据传输问题,地址问题、流量控制、帧格式、出错处理、协议,点到点信道,出错处理,：纠错、检错,单工协议,无限制单工协议、停等协议、有噪声信道协议,滑动窗口协议,1,位、捎带技术、回退,N,帧、选择性重传,典型协议：,PPP,协议,62,数据链路层协议总结（,2,）,基本问题：广播信道中，两主机间的数据传输,方法,1,：静态分配,FDMTDM,（效率低）,方法,2,：动态分配,无序竞争,ALOHA,和分槽,ALOHA,协议,减少冲突,CSMA,（载波监听协议）,无冲突协议,位图协议,有限竞争协议,自适应树搜索协议,典型应用,以太网、无线,LAN,、宽带无线网等,MAC,子层协议,63,数据链路层协议总结（,3,）,计算机网络的基本形式,点到点方式网络,A,B,适合传输距离较远的情况，如广域网、拨号上网等,共享信道方式网络,64,Question?,