第四讲 介质访问控制子层

1、121 1 理解理解MACMAC子层的基本问题子层的基本问题2 2 理解信道分配的两种基本思想理解信道分配的两种基本思想3 3 掌握掌握ALOHAALOHA协议、协议、CSMACSMA协议协议4 4 理解无冲突协议、有限竞争协议理解无冲突协议、有限竞争协议5 5 掌握以太网及有关的协议掌握以太网及有关的协议6 6 理解无线理解无线LANLAN以及相关协议以及相关协议7 7 了解宽带无线网络、蓝牙技术和了解宽带无线网络、蓝牙技术和RFIDRFID本讲要求本讲要求3基本问题基本问题广播信道中，两主机间两主机间的通信问题问题分析问题分析地址问题、流量控制、帧格式、出错处理、信道分配问题信道分配问题关

2、键问题：关键问题：当存在多方竞争使用信道的时候，如何确定谁可以使用信道 解决问题的基本思路解决问题的基本思路（1）静态信道分配方案（FDM、TDM）（2）动态信道分配方案（竞争机制）4频分多路复用频分多路复用-FDM 基本思想基本思想 如果总共有N个用户，则整个带宽分为N份，每一个用户一份。 主要问题主要问题 带宽浪费，效率低下！ 结论结论 传统的信道分配方法不适应突发性流量情况，需要寻求新的方法动态信道分配方法5频分多路复用效率分析（频分多路复用效率分析（1） 信道通信延时分析信道通信延时分析 信道容量：C (bit/s)；平均延迟：T； 帧到达时间间隔服从指数分布，帧的平均到达率： (fr

3、/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/ TFDM = 1 / ( C /N - /N) = N

4、/( C - ) =NTTDM的效率和的效率和FDM一样！一样！7动态信道分配方案（动态信道分配方案（1） 假设条件假设条件 条件条件1：站模型：站模型 该模型有N个独立的站 有一个程序或用户产生帧 在长度为t的时间内，产生一帧的概率为* t 一旦一帧已被产生，则该站阻塞，直到该帧发送成功。 条件条件2：单信道假设：单信道假设8动态信道分配方案（动态信道分配方案（2） 条件条件3：冲突假设：冲突假设 当两帧同时传输时，信号重叠，产生混乱，称为冲突冲突。 条件条件4：连续时间、分槽时间：连续时间、分槽时间 所有的站点能够检测到冲突事件 冲突的帧必须重发 除了冲突错误外，不会有其他错误 条件条件5

5、：载波侦听或不侦听：载波侦听或不侦听能检测到所能检测到所有的冲突吗有的冲突吗?9动态信道分配方案（动态信道分配方案（3） 动态信道分配方案必须解决的基本问题动态信道分配方案必须解决的基本问题（1）谁可以发送数据？（2）是否发生冲突？（3）面对冲突的解决方法？（4）评价标准传输效率如何？（信道利用率、传输延迟） 基本的多路访问协议基本的多路访问协议（1）ALOHA协议（2）载波侦听协议（3）无冲突协议（4）有限竞争协议（5）无线LAN协议10ALOHA协议协议 基本思想基本思想 （1）当用户有数据发送时，马上发送数据。（2）当检测到帧损坏后，等待随机的时间后，再次发送该帧。sender Asen

6、der Bsender Ccollisiont可行吗？效率如何？成功传输的概率可行吗？效率如何？成功传输的概率是多少？是多少？11ALOHA协议分析（协议分析（1） 帧时：帧时： 传输一帧所需要的时间，即帧长/信道容量 新产生帧数：设均值为新产生帧数：设均值为N在一个帧时内，通信用户一共产生新的帧数，均值为N如果N1，则一定产生冲突，希望0N1 等待传输帧数：设均值为等待传输帧数：设均值为G在一个帧时内，通信用户一共产生新帧和等待重传的帧数之和，显然GN。 概率概率一帧时产生k帧的概率为： Prk = Gke-G / k! K=0时，时， Prk=0 = e-G 如果假定一次传输成功的概率为如

7、果假定一次传输成功的概率为P0，则吞吐量，则吞吐量S=GP012ALOHA协议分析（协议分析（2） 冲突分析冲突分析传输帧传输帧 成功的条件：成功的条件：t t0 0tt0 0+2t+2t时间无发送帧时间无发送帧 成功的概率：成功的概率：P0=Prk=0=e-2G注意：时间为注意：时间为2个帧时个帧时 吞吐量吞吐量S = G P0 = G e-2G极值情况：极值情况：G=0.5Smax=1/2e=0.18413ALOHA协议分析（协议分析（3） 纯纯ALOHA效率低的原因效率低的原因 冲突的可能太大了！ 解决基本思路解决基本思路 减少可能冲突的时间界限！HOW？时间分槽14分槽分槽ALOHA协

8、议协议sender Asender Bsender Ccollisiont 基本原理基本原理 将时间分成离散的间隔，每一个间隔对应一帧，数据必须从时槽的开始时刻发送。 效果效果冲突危险期被减少了一半，因此效率提高了一倍。 主要问题主要问题全局时间同步比较困难15ALOHA协议比较协议比较16ALOHA协议分析协议分析 信道最佳利用率信道最佳利用率 1/e=37% 总体信道利用率不高 主要原因主要原因无序竞争，冲突频繁 协议改进的基本思想协议改进的基本思想无序变有序，减少冲突 检测其他站点的行为 根据检测结果调整自己的行为载波侦听！载波侦听！载波侦听协议载波侦听协议17载波侦听协议载波侦听协议C

9、SMA（1） 1-持续持续CSMA 基本原理 站点在发送数据前，先监听信道； 若信道忙，则一直等待到信道空闲（1-1-持续，贪婪持续，贪婪算法思想）算法思想）； 若信道空闲，则发送数据； 发送数据后，如果发生冲突（会吗？）发生冲突（会吗？），则等待一段随机时间后，再次检测和发送数据 主要优点减少了冲突的发生与ALOHA相比，性能会提升吗？信道利用率如何？传输延时如何？证明？测试验证？证明？测试验证？ Get your hands dirty !18载波侦听协议载波侦听协议CSMA（2） 非持续非持续CSMA 基本原理 站点在发送数据前，先监听信道； 若信道空闲，则发送数据； 若信道忙，则等待随

10、机一段时间后，再次检测和发送数据 发送数据后，如果发生冲突，则等待一段随机时间后，再次检测和发送数据 主要优点进一步减少了冲突的发生19载波侦听协议载波侦听协议CSMA（3） p-持续持续CSMA-应用于分槽信道 基本原理 站点在发送数据前，先监听信道； 若信道空闲，则在当前时槽以p概率概率发送数据（如何实现？）； 若信道忙，则在下一个时槽，再次检测和发送数据 发送数据后，如果发生冲突，则等待一段随机时间后，再次检测和发送数据 20载波检测协议载波检测协议CSMA（4） 性能分析性能分析21载波侦听协议载波侦听协议CSMA（5） 带冲突检测的带冲突检测的CSMACSMA/CD 基本原理：一旦检

11、测到冲突，则停止数据发送该协议是以太网的基础该协议是以太网的基础在以太网中详细介绍在以太网中详细介绍 CSMA协议的启示协议的启示 冲突越少，信道利用率可能会提高！ 如果没有冲突的话？效果是不是会更好？无冲突协议无冲突协议22无冲突协议无冲突协议 基本思想基本思想 通过协商机制，协调用户竞争信道，避免冲突发生 位图协议位图协议 二进制倒计数协议二进制倒计数协议 令牌传递协议令牌传递协议23位图协议（位图协议（1） 基本原理基本原理 N个接入站点都有惟一地址，从0N-1； 每一个竞争周期正好包含N个时槽； 如果M号站点要发送数据，则在M号时槽中传送位1； 按照数字顺序排队发送数据，所有数据发送完

12、毕后，开始下一个竞争周期资源预留协议资源预留协议24位图协议分析（位图协议分析（1） 低负载情况低负载情况：数据帧很少，位图不断出现假设竞争周期为N个时隙，一帧数据为d时隙 对于低序号的站点，平均扫描N/2个时间槽完成当前时间槽扫描，然后再过N个时间槽后，才能够发送数据。 对于高序号的站点，平均扫描N/2个时间槽完成当前时间槽扫描，然后就能够发送数据。 对于N个站点而言，平均扫描N个时间槽后才能够发送数据。信道利用率信道利用率=d/(d+N)=d/(d+N)平均传输延时平均传输延时=d+N=d+N个时隙个时隙25 高负载情况高负载情况：所有站点在任何时候都有数据发送位图协议分析（位图协议分析（

13、2） N位竞争周期平分到N个帧 每一个帧多了一个竞争时隙，即为d+1信道利用率=d/(d+1)平均传输延时=N(d+1)个时隙 主要问题主要问题 扩展性不好。即如果包含站点数目多，则竞争时隙占用了太多的信道资源。改进思路：二进制站地址（二进制倒计数协议）26二进制倒计数协议（二进制倒计数协议（1） 基本原理基本原理 每一个站点有一个二进制地址 如果一个站点想要使用信道，则以二进制位串的形式广播地址（也就是一次发送地址中的一比特位） 来自不同的站的位串被布尔或（OR）在一起 如果一个地址中的高位0被改写为1了，则退出竞争27二进制倒计数协议（二进制倒计数协议（2） 效率分析效率分析 信道利用率=

14、d/(d+log2N) 精心设计帧结构，可以利用竞争时隙的信息，使得信道利用率100%。 主要问题主要问题 站点饿死、时间同步、信道支持。 改进思路循环地址。每次传输后，成功的站会被改写为最小的编号28令牌传递协议令牌传递协议 基本思想：基本思想： 站点只有获取令牌时，才能发送数据帧 令牌以一定的策略在站点间流动。（如令牌环）令牌令牌站点站点IEEE 802.5令牌环令牌环29有限竞争协议（有限竞争协议（1） 竞争协议和非竞争协议性能比较分析竞争协议和非竞争协议性能比较分析（延时和信道利用率）（延时和信道利用率） 低负载情况（重点考察时延） 高负载情况（重点考察信道利用率） 竞争协议具有比较短

15、的延时，非竞争协议具有比较长的时延。 信道空闲时间多 竞争协议仲裁时间花费增多，可能要多次重传输；非竞争协议仲裁时间花费较少，不需要重传。 竞争协议信道利用效率低，非竞争协议信道利用效率高。结合竞争协议与非竞争协议的优势？结合竞争协议与非竞争协议的优势？30有限竞争协议（有限竞争协议（2） 对称协议性能分析对称协议性能分析 如果所有的站点都以相同的概率P获得信道，则称该协议是对称协议是对称的。 假设k个站点竞争信道，有一个站点成功的获得信道的概率为kp(1-p)k-1 ，可得最优解为p=1/k减少竞争者的数量！减少竞争者的数量！31有限竞争协议（有限竞争协议（3） 基本原理基本原理 将所有站点

16、划分成组（减少竞争者的规模） 只有0号组成员可以竞争0号时槽，竞争胜利者发送数据 然后1号组成员开始竞争1号时槽，以此类推目的是使竞争者的数量尽量少，以靠近最目的是使竞争者的数量尽量少，以靠近最优曲线的左边，期望获得最优的成功率优曲线的左边，期望获得最优的成功率 关键问题关键问题：如何将站点分配到各个时槽？基本要求基本要求：当负载很低的时候，每一个时槽的站点尽量多；当负载很高的时候，每一个时槽的站点尽量少32有限竞争协议（有限竞争协议（3） 自适应树搜索协议自适应树搜索协议 把所有站点看做二叉树的叶子节点，构建二叉树 0号时槽，所有站点参与竞争，如果失败，则其左孩子节点的站点参与1号时槽竞争，

17、右孩子节点的站点不参与竞争，以此类推，直到有站点竞争成功。 在某节点上，如果有站点竞争成功，则下一个竞争时隙分配给它兄弟节点上的站点竞争。失败失败不参与下一轮竞争成功下一轮33有限竞争协议（有限竞争协议（4） 自适应树搜索协议分析自适应树搜索协议分析 目的：使竞争者的数量尽量少，以靠近最优曲线的左边，期望获得最优的成功率 在高负载的情况下，一旦发生冲突，则参与下一轮的竞争者人数减半！ 在低负载的情况下，全体数据发送者参与竞争！ 自适应算法：满足负载的各种情况！ 自适应树搜索算法协议的改进高负载情况下，从第i=log2q级开始开始搜索34以太网技术（以太网技术（1） 最初的以太网体系结构（最初的

18、以太网体系结构（Xerox）Bob Metcalfe3COM3COM3510Base-T10Base-F以太网技术（以太网技术（2） 以太网电缆以太网电缆36以太网技术（以太网技术（3）(a) 10Base5, (b) 10Base2, (c) 10Base-T.(a) 10Base5, (b) 10Base2, (c) 10Base-T.37以太网技术（以太网技术（4）hosthosthosthostHubHubS DintelIntel E xpres s1 0/1 00 S tac k able HubC hange hub s peedP owerC ollis ionM anaged

19、10B AS E- T100B AS E- TXS tatusB la c k - W i rin g s p e e dC las sIS o l id - D o w n lo a dA m b e r (M g m t )B la c k - A ct iv i tyS o l id - L in kG re e n (v t )123456789101112131415161718192021222324ServerLaser printerWorkstationWorkstationWorkstationEthernet BusLaser printerWorkstationServ

20、erLaptop 10base-T38以太网技术（以太网技术（5） 曼彻斯特编码曼彻斯特编码 0伏表示“0”，5伏表示1容易引起歧义 用+1伏表示“1”，-1伏表示“0”，则需要时钟同步00110低低-高高低低-高高高高-低低高高-低低低低-高高高高低低 需求需求接收者在没有外部时钟的情况下，无歧义的确定每一位的开始、结束或者中间位置 原因原因 方法方法每一位分为两个相等间隔，发送1时，第一间隔为高电压，第二间隔为低电压，发送0则反之39以太网技术（以太网技术（6） 协议协议CSMA/CD 基本原理 站点在发送数据前，先监听信道 若信道忙，则等待一段随机时间后，再试图发送数据 若信道空闲，则发

21、送数据； 边发数据边进行冲突检测，如果发现冲突，则马上停止数据发送，并等待一段随机时间后，再试图发送数据 两个关键问题 冲突检测问题 随机时间等待40t = 2 A 检测到发生碰撞STOP以太网技术（以太网技术（7） 冲突检测冲突检测 需求需求：需要监听多少时间才能够确信没有冲突？LABt碰撞t = B 检测到信道空闲发送数据t = / 2发生碰撞t = 2 A 检测到发生碰撞 t = B 发送数据B 检测到发生碰撞 t = ABABAB t = 0 A 检测到信道空闲发送数据ABt = 0t = B 检测到发生碰撞停止发送STOPAB单程端到端传播时延记为 41以太网技术（以太网技术（8）

22、结论结论 主机必须连续发送数据2时间后，才能够确信不会发生冲突，也就是说，最小帧的长度是2时间所发送的数据 10M以太网标准， 最大长度2500米（4个中继器） 在最坏情况下，往返时间大约50us（50*10-6）， 发送一位数据100ns（100*10-9） 最小帧数据长度50us/100ns=500位，加上安全余量，到512位（29），即64字节。42以太网技术（以太网技术（9） 随机等待时间随机等待时间二元指数后退算法二元指数后退算法帧帧帧帧帧帧帧帧 一个时槽512位时间(2) 算法 第一次冲突，则随机等待0或1个时间槽（21） 第二次冲突，则随机等待0、1、2或3个时间槽（22） 第三

23、次冲突，则随机等待0-7个时间槽（23） 第i次冲突，则随机等待0-2i-1个时间槽（2i）(i最大为10，即随机数的最大值为1024)43以太网技术（以太网技术（10） 帧格式帧格式PreambleTypePadDestSourceDataCRC8662411500 前导域：10101010（位填充技术） 地址：第一位1，组地址24 位位24 位位08:00:20:0e:56:7d厂商代码厂商代码序列号序列号ROMRAM 类型：数据发送对象 数据+填充：最少46字节 校验和：CRC校验确认号？确认信息？序列号？确认号？确认信息？序列号？无确认重传机制无确认重传机制不可思议？不可思议？WHY？

24、44以太网技术（以太网技术（11） 性能分析性能分析 假设条件：K个站点竞争信道，一个站点在竞争时槽发送数据的概率为p 在某时槽，某一个站点获得信道的概率A=kp(1-p)A=kp(1-p)k-1k-1 某一个站点通过j次竞争获得信道的概率P Pj j=A(1-A)=A(1-A)j-1j-1 某一个站点成功发送数据的平均竞争次数T=T= jPjPj j= = jA(1-A)jA(1-A)j-1j-1=1/A=1/A(最优为e) 假设一帧数据需要M秒，则信道效率为信道效率信道效率=M/(M+2=M/(M+2 /A)/A)（4.64.6）因此，需要限制电缆的长度。因此，需要限制电缆的长度。最优为1

25、/e45以太网技术（以太网技术（12） 假设帧长为F，网络带宽为B，电缆长度为L，信道的传播速度为c，每发送一帧最多竞争e个时间槽，一帧传输时间：一帧传输时间：M=F/BM=F/B信道效率信道效率=M/(M+2=M/(M+2 /A)/A) = =（F/BF/B）/(F/B+2(L/c)/(F/B+2(L/c)* *e)e) 1 1 数据往返时间数据往返时间2 2 =2L/c=2L/c1+2BLe/cF1+2BLe/cF=B B越大，越大，L L越大，越大，则效率越差！则效率越差！流量的分布：泊松分布？自相似的流量的分布：泊松分布？自相似的46以太网技术（以太网技术（13）1500字节数据47以

26、太网技术分析以太网技术分析 主要问题主要问题 随着站点增加，冲突增加，网络性能下降！ 主要解决思路主要解决思路 增加网络带宽快速以太网、千兆以太网 减少参与冲突竞争的站点规模交换式以太网48交换式以太网交换式以太网（A）集线器广播式（B）集线器交换式49100M100M以太网技术以太网技术 基本原理基本原理 保留原来的帧格式、接口和过程规则，将位时间从100ns降低到10ns。要求要求：将最大长度由将最大长度由2500米，减少为米，减少为250米米501000M1000M以太网技术以太网技术 基本原理基本原理 保留原来的帧格式、接口和过程规则，将位时间从100ns降低到1ns。 两种工作模式两

27、种工作模式 全双工模式：所有线路都有缓存能力交换机连接方式 半双工模式：竞争信道HUB连接方式，CSMA/CD 将最大长度减少为25米？ 载荷扩充技术：将最小帧扩张到512字节，最大长度是多少？ 帧串技术：多帧连接一起发送。5110000M10000M（万兆）以太网技术（万兆）以太网技术2002年正式发布主要应用：数据中心和交换局内部以太网技术总结以太网技术总结30多年发展，一直没有被超越原因：简单！52无线无线LANLAN（1 1） 信道类型信道类型：广播信道 两种工作模式两种工作模式 有基站模式（PCF模式） 所有通信通过基站 无基站模式（DCF模式） 相互间直接发送数据直接使用直接使用C

28、SMA/CD技术？技术？点到点协议？点到点协议？53无线无线LANLAN（2 2）无基站通信模式无基站通信模式 广播信道的特殊性广播信道的特殊性 隐藏站问题BACBACD 暴露站问题 A向B发送数据 C不能够接收到A的信号 C向B发送数据，导致数据在B接收处冲突 B向A发送数据 C能够监视到信号 C如果想向D发送数据，也必须等待54无线无线LANLAN（3 3）无基站通信模式无基站通信模式 CSMA/CA避免冲突的多路访问避免冲突的多路访问 基本思想：发送方刺激一下接收方，让它输出一个短帧，然后再发送大量数据（带上传输时间字段） 对于C站点，位于A的范围，能接收到RTS信息 对于D站点，位于B的范围，能接收到CTS信息 CSMA/CA解决了隐藏站问题了吗？解决了隐藏站问题了吗？ CSMA/CA解决了暴露站问题了吗？解决了暴露站问题了吗？55无线无线LANLAN（4 4） 基站通信基本思想基站通信基本思想：基站轮询。 基站控制数据发送无冲突