《计算机通信网》第4章MAC子层.pptVIP

第4章 介质访问子层 （MAC子层）,4.1 背景 4.2 共享介质的信道分配 4.3 典型的多路访问协议 4.4 网桥,4.1 概述,考虑本地有多台计算机联成一个网 基本要求 每台计算机只有一个通信接口 任意计算机之间都可以相互发送数据 计算机在网络中的地位平等 采用何种方法可以把这些计算机都连起来？,A,C,B,D,E,F,任意一台计算机(例如A)，可以其它把数据送给其它的任意的计算机(例如C),基本的联网方式,用一个信道把所有计算机连接起来 信道的通信容量为C (Capability) 所有的计算机都利用该信道发送和接收数据 联网问题转化为 如何为每台计算机分配使用的信道资源？ 静态分配 频分复用，FDM 时分复用，TDM 动态分配,A,B,C,D,E,F,术语：多路复用与多路访问,多路复用：Multiplex 多个通信复用到一个信道上 TDM、FDM通过划分子信道，实现多个一对一的通信 多路访问：Multi-Access 在一个信道上，实现与多个站点的通信 TDM的联网通信方式，称为TDMA FDM的联网通信方式，称为FDMA 其它的还有 CSMA，载波侦听多路访问 CDMA，码分多路访问 WDMA，波分多路访问,4.1 背景,计算机网络分为两类 点到点信道的网络 共享信道的网络（广播信道的网络或广播式网络） 广播信道也称为： 多路访问信道或随机访问信道 广播信道网络的特点 所有站点共享同一信道 一个站发送的数据将传遍整个网络 同时发送会产生冲突 需要某种信道访问机制介质访问子层研究的问题,频率f,4.1 背景,典型的广播信道网络 卫星网络 无线广域网（GSM、GPRS、WCDMA等） 无线局域网WLAN（802.11） 局域网 共享式以太网 令牌环网 光纤网络 广播信道网络面临和需要解决的问题 如何识别不同的站点 站点何时如何使用信道信道分配问题 所有这些问题由MAC子层协议解决 介质访问子层（medium access control）,4.2 共享介质的信道分配,静态分配（无竞争） 频分多路复用FDM（频分，各站使用独立频段） 需要考虑频段间隔，以免相互干扰 时分多路复用TDM（时分，各站使用独立时间段） 需要考虑时间段（时隙）独立，以免干扰 静态分配方式简单可靠，但延时较大，信道利用率低，不适应突发的数据传送和用户数量变化的情况,4.2 共享介质的信道分配,动态分配 动态分配需要考虑的要素 如何发送 任意，想发就发 发送前是否侦听载波：盲目 或 等待信道空闲 得到许可再发送 如何接收 地址识别 是否检测冲突 冲突怎样解决 不使冲突出现 减少冲突 减少冲突影响,STOP,NO,YES,Collision,4.2 共享介质的信道分配,动态分配 不固定为每个站点分配信道 需要时才分配 空闲时可由其它站点使用 动态分配的方式很多 集中仲裁的动态分配（需要管理站） 向管理站预约：需要时申请，许可后发送数据（举手的方式） 申请时可能冲突，许可后发送无冲突 由管理站轮询 (点名的方式) 单播轮询方式：依次询问每个站，有数据发的站点发送，无冲突 组播或广播轮询：可能有冲突 分布仲裁的动态分配（无需管理站） 允许竞争存在，尽量避免或减少冲突 减少冲突的措施：发前侦听信道，检测冲突，冲突后随机后退等 令牌控制信道的使用 只有得到令牌的站，才能发送数据（无冲突方式）,另一种动态分配方式的分类,竞争信道 节点无序抢占信道 允许冲突存在 有序访问 控制节点访问信道次序 无冲突 有限竞争 结合竞争方式和无冲突方式 轻负载时，使用竞争方式 重负载时，使用无冲突方式,本章重点随机竞争算法,算法优点 信道利用率高 其它站点不发送时，可占用更多的信道资源 联网方式简单 不需要进行信道划分 站点数可变 通信方式简单 发，或者不发(不存在子信道带来的问题) 适合于计算机间的组网通信 通信的对象可变 通信的数据量可变，通信能力强 站点可自由上下网 最大问题 如何最大限度避免出现发送冲突,4.3 典型的多路访问协议,有竞争的多路访问协议 纯ALOHA协议 各站想发就发，碰撞随时可能发生 时槽ALOHA协议 规定统一发送时刻，碰撞时帧完全重叠 CSMA协议 发前侦听信道，忙则随机后退 有三种策略：0坚持、1坚持和P坚持 CSMA/CD 发前侦听信道，发送时同时检测信道 检测到冲突立即停发，释放信道 CSMA/CA：WLAN的MAC协议,发前不听不看， 冲突严重,虽发前侦听信道，但冲突一旦发生不能立即停下，资源浪费,冲突立即释放信道，提高信道利用率,信道竞争模型,竞争模型 N个独立工作的站点，随机地发送数据帧 进入信道的帧的速率是一个随机过程(设均值为G) 某个帧成功传输的条件(无论谁接收、不考虑误码): 没有与其它帧在时间上有重叠,进入信道 (帧速率G),成功传输出信道 （吞吐率S）,冲突的帧 （消失在信道上),S：归一化吞吐率 S=吞吐量/信道容量 G：归一化帧速率 G=帧速率/信道容量 显然：SG,信道竞争模型,帧速率的概率分布 在任意的一个时间段T(帧长度)内，生成k个帧的概率服从泊松分布 其中G为平均帧速率,典型值： T内生成0帧的概率为 pT(0)=e-G T内生成1帧的概率为 pT(1)=Ge-G 2T内生成0帧的概率为 p2T(0)=e-2G,信道竞争模型,背景知识：泊松(Poisson)分布 无穷多个独立工作站点随机生成(发送)帧的概率分布 设有一小的时间间隔dt，若 在dt内生成一帧的概率为dt(dt1),且独立于其它时间间隔 当dt足够小时，生成多于1帧的概率可忽略不计 在各不重叠的时间间隔，生成的帧数是独立的随机变量 概率结构与时间位置无关 则可推出在t时间内生成n个帧的概率为 均值为 方差为,为帧的平均生成速率 (研究表明：当站点数超过20个时,其生成帧的概率分布已非常接近泊松分布）,信道竞争模型,竞争模型的性能特性： 吞吐率S与帧速率G的关系：S=GP0（P0成功传输概率） 帧的数量少冲突概率小传输成功率高吞吐率高 帧的数量多冲突概率大传输成功率低吞吐率低,帧速率小,帧速率适中,帧速率过大,G(帧速率),S(吞吐率),G小,G适中,G过大,G小：吞吐率随帧速率的增加而增加(成功传输的帧增多),G过大：吞吐率随帧速率的增加反而下降(更多的冲突),理想情况,1,1,4.2.1 ALOHA,Pure ALOHA 工作原理 节点只要有数据就可以直接占用信道，启动发送 不考虑与别的站点是否冲突的无序竞争，“想发就发” 可以预测 帧速率较大时，冲突会急剧上升 只能工作在帧速率较小的场合 何种帧速率适合Pure ALOHA Pure ALOHA所能达到的吞吐率,70年代，夏威夷大学为了用无线电将分散在各个岛屿的计算机连接起来，Norman Abramson等人设计了一种巧妙地解决信道分配问题的新算法，称为ALOHA（or pure ALOHA)。 该协议开创了通信介质共享领域的新时代,Pure ALOHA 的性能,为简单起见，假定所有站点发送的帧是等长的，占用信道的时间为T 设某个站点在t时刻发送一个帧，该帧成功发送的条件是： 在t-Tt+T的2T间隔内没有其它站点发送(如图所示) 即成功发送概率P0(根据帧速率的泊松分布)为 P0=P2T内无帧产生=e-2G 由S=GP0，可得Pure ALOHA的吞吐率 S=Ge-2G,站1,站2,t,t+T,t -T,站N,Pure ALOHA 性能曲线,性能描述 当帧速率G小于信道容量的 50%时，发送帧产生的冲突较少，吞吐率随帧速率而增加 当帧速率G大于信道容量的 50%后，发送帧产生的冲突急剧上升，吞吐率下降 Pure ALOHA的最佳性能出现在G=0.5，S=1/2e=0.184（吞吐率为信道容量的18.4%) 信道利用率(吞吐率)低的原因是站点的无序竞争,S=Ge-2G,理想吞吐率,Slot ALOHA,针对Pure ALOHA无序竞争的冲突，加以改进 改进方法 把信道划分为T为单位的时隙，站点只能在时隙的开始处发送帧 没有冲突、或完全冲突，减少冲突帧的持续时间 改进的代价是所有站点实现时隙的同步(增加了实现难度) 谁负责时隙管理，管理者出故障怎么办等 改进后，性能提高多少？,Slot ALOHA,设：某个站点在t时刻发送一个帧，该帧成功发送的条件是： 在t-Tt的间隔内没有新帧产生(新帧将在t时刻发送) 其概率为P0=PT内无帧产生=e-G Slot ALOHA的吞吐率为 S=GP0=Ge-G 与Pure ALOHA相比 减少了冲突的可能性 可容纳更高的帧速率 从而提高了信道的吞吐率 Pure ALOHA的2倍 最大吞吐率 出现在G=100%处 S=1/e=36.8,CSMA,如果发送和接收都在同一个信道上，发送之前可发现信道是否被其它站点占用，从而可以降低冲突“先听后发” 工作原理：载波侦听多路访问 发送前侦听信道 信道空闲，就启动发送 信道被占用，就等到信道空闲再发送 如果有两个以上站点都在等，一旦信道空闲就会同时发送而冲突。因此，需要错开各站点启动发送的时间。 三种错开发送时间的策略 1坚持CSMA：立即发送 0坚持CSMA：等待一段随机长度的时间(随机后退) p坚持CSMA：可能立即发送(概率p)，可能等待(概率1-p) 错开时间后，后发的站点因又发现信道被占用而继续侦听 信道上的传播延时会对站点的载波侦听带来不利影响,CSMA载波侦听动画（一）,t,信道空闲,A侦听信道，立即发送数据,信号到达B处,B侦听信道，抑制发送,A,B,CSMA载波侦听动画连续（一）,t,信道空闲,A侦听信道，立即发送数据,信号到达B处,B侦听信道，抑制发送,A,B,CSMA载波侦听动画（二）,t,信道空闲,A侦听信道，立即发送数据,信号到达B处，产生冲突,B侦听信道，立即发送,A,B,信号传播延时,CSMA降低了冲突概率 因为信号传播延时是很短的以2/3光速传播,1坚持CSMA,信道闲后，启动发送的概率p=1 准备发送：侦听信道 若信道闲,启动发送 否则,持续侦听信道直到信道闲，启动发送 前一发送完成，后面很容易产生冲突 下一帧不冲突的概率：在一个T内最多产生一帧的概率 p=p(0)+p(1)=e-G+Ge-G=(1+G)e-G,Ready,信道忙,否,侦听,Ready,是,站A,站B,站C,站D,侦听,侦听,0坚持CSMA,信道闲后，启动发送的概率(p=0) 再等待一段时间后决定是否发 准备发送：侦听信道 若信道闲，启动发送 否则，等到信道闲，再等待一随机时间后在尝试发送 降低多个站同时侦听信道时可能出现的冲突,Ready,信道忙,否,侦听,Ready,是,后退,站A,站B,站C,站D,随机延时后侦听,侦听,随机延时后侦听,p坚持CSMA,信道闲后，启动发送的概率为p，继续等待的概率为1-p 准备发送：侦听信道 若信道闲，启动发送 否则，等到信道闲，以概率p启动发送，以概率1-p继续等待 降低多个站同时侦听信道时可能出现的冲突 最佳方案： 调整概率p，使得发送的站点数=1,Ready,信道忙,否,侦听,Ready,是,后退,Rp,R=rand(),是,站A,站B,站C,站D,A计算概率为可以发送,D计算概率为不能发送,几种竞争协议的效率,吞吐率 轻负载下，1-坚持的性能好，0-坚持差，p-坚持中等 重负载下，1-坚持的性能差，0-坚持好，p-坚持中等,CSMA/CD（结合P216、P233）,载波侦听多路访问/冲突检测 引入 已经发生冲突的帧，继续发送的部分是浪费 冲突检测 发送的过程中继续检测信道，以及时发现冲突 发生冲突后，立即停止发送,站A,站B,站C,冲突,浪费,冲突检测方法,电平判断 冲突信号相互叠加，总电平将超过额定值 逻辑判断 发送的数据与同时收回来的数据不一致 集线器上有两个及以上的端口“活动”,+,=,超高,冲突检测时间,最多花多长时间发现冲突 接近于0，但不等于0 为传播时延距离/0.7光速 发送超过2时间后不需要再检测冲突了,冲突检测后的处理,检测到冲突后立即停止传输 停止传输后，随机延迟一段时间再尝试发送 若各站的延迟时间相同，则一定会再次冲突 延迟时间以时间片为单位 一个时间片最大冲突检测时间 随机延时算法截断二进制指数回退算法,while attempts attemptlimit and collision k = min(attempts,10); r = radom(0, 2k); attempts = attempts + 1; end of while,r为计算出的延时时间片,竞争访问信道,竞争访问信道面临的问题及解决方案 有冲突出现 尽量减少冲突降低冲突概率 监听载波 随机后退 尽量减小冲突带来影响 分时槽 监听载波 冲突检测 减少用户发送延迟 发送延迟：从准备发送到正确发送数据的时间间隔 降低冲突概率 减小冲突持续时间,4.3 典型的多路访问协议,无冲突的协议：控制节点访问信道次序 位图协议预定协议 在信道访问前先申请（预定）信道，然后按序访问 发送站在自己的争用时隙中置位 在争用时隙结束后，各发送站按顺序发送,4.3 典型的多路访问协议,无冲突的协议： 二进制倒计数法 各发送站发送自己的地址，同时监听自己发出的地址是否改变 地址发完后，没有发现地址改变的发送站继续发送数据,无冲突协议,二进制倒计数法 例,站A、站B、站C、站D，地址分别为0010、0100、1001、1010,0 0 1 0,0 1 0 0,1 0 0 1,1 0 1 0,假设四个站点同时希望发送，它们将自己的地址送出， 并同时监听网络上的数据。,A,B,C,D,发送顺序,先,后,0,0,1,1,1,1,1,1,D站可以发送数据,发送站中地址最高的可以发送数据 高地址站具有高优先级 地址动态变化，以使保证公平性,4.4以太网,采用了CSMA/CD技术的局域网 范围小、数传速率高，共享介质 一根电缆连接所有的站点 背景 IEEE802委员会 IEEE802.3,MAC媒体访问控制层,PHY物理层,LLC逻辑链路控制层,高层,数据链路层,以太网MAC层,媒体访问技术CSMA/CD 传输前侦听载波 信道空闲立即发送 信道忙则一直侦听，直到信道空闲，然后立即发送 发送过程中同时检测冲突 发现冲突立即停止传输，并在随机延时后尝试发送 停止传输后，用二进制指数回退算法计算延时 一些重要的规定 最小帧长64字节，最大帧长1518字节 最多连续冲突次数：16次 帧间间隔12字节,以太网MAC层,帧格式 前导码：10101010串，用于同步 目的地址：6字节 三种形式 单播、单目、普通地址 指定站点接收 多播、组播、组地址 一组站点同时接收 广播地址 所有站点全部接收,前导码,目的地址,源地址,长度/类型,数据,帧校验,8字节,6字节,6字节,2字节,461500字节,4字节,以太网帧格式,目的地址 第一字节，最“高”位 为0表示单播地址普通地址 为1表示多播地址组地址 全部为1表示广播地址 例： 0x 01 00 5E 73 0C 01 组播地址 0x 00 90 0A 27 0B 0C 单播地址 0x FF FF FF FF FF FF 广播地址,以太网帧格式,长度/类型字段 小于1536表示帧长度帧中数据字段的长度 数据内容是变长的，最大为1500 大于1536表示帧类型数据字段封装的协议类型 0x800：表示数据内容是IP分组 0x806：ARP分组,前导码,目的地址,源地址,长度/类型,数据,帧校验,8字节,6字节,6字节,2字节,461500字节,4字节,目的地址,源地址,0x800,IP分组,以太网帧格式,帧校验字段 32位CRC校验 MAC层发现帧错误后，仅向上层报告而不进行差错控制,前导码,目的地址,源地址,长度/类型,数据,帧校验,8字节,6字节,6字节,2字节,461500字节,4字节,4.4.4共享式与交换式以太网,共享式以太网 一根电缆(或HUB)连接所有的站点 站点采用CSMA/CD竞争信道,HUB模拟共享信道,HUB,交换式以太网,交换式以太网 端口与站点采用全双工通信 共享缓冲区、交换矩阵、CrossBar等 在端口间转发数据帧 所有端口并行工作 没有信道竞争，关闭了CSMA/CD,帧缓冲区,转发,根据目的MAC向相应端口转发帧,以太网交换机,快速以太网(Fast Ethernet),数传速率为100Mbps的以太网 802.3u 与10Mbps的以太网兼容10/100M自适应 电缆：5类双绞线 接口：RJ45 编码：8B/6T MAC层：CSMA/CD 全双工（交换式）下不用,千兆以太网,数传速率为1000Mbps的以太网 802.3z，802.3ab等 “电”缆： 802.3z光纤，802.3ab双绞线 编码：8B/10B MAC层：CSMA/CD 全双工（交换式）下不用 帧扩充（载荷扩充）技术，将小于64字节的帧扩充到512字节发送 帧突发（帧串）技术，一次可连续发送多个小于512字节的帧，直到1500字节,4.5无线局域网,协议标准 IEEE802.11系列协议 11b 11g 11a 11n 11i 无线的“以太网” 希望像以太网那样普及、方便、易用 技术和CSMA/CD类似 CSMA/CA,高层,LLC,802.3 MAC,802.3 PHY,802.11 MAC,802.11 PHY,无线局域网协议,无线局域网的广播特性 信道共用 无基站，对等式 无线环境的特殊性： 冲突域不固定,A,B,C,A C之间并 不冲突，但 在B看来，大 家都是冲突的,无线局域网,隐藏站点 A向B发送数据时 C监测不到载波 C也向发送数据，造成冲突 A对C隐藏 暴露站点 B向A发送数据 C向D发送数据 本来互不干扰 但在B发送时， C检测信道，以为会 发生冲突，而停止 B暴露在C、D之间,A,B,C,A,B,C,D,难,无线局域网协议,MACA 冲突避免 解决隐藏站点冲突 A欲向B发送数据，先发送RTS帧提醒B B应答CTS，阻止在B覆盖范围内的其他所有站点发送数据（不包括A） C收到CTS后，不向B发送数据而避免了冲突 （在B周围的所有站点中只有A能发送数据）,A,B,C,RTS,CTS,RTSRequest To Send CTSClear To Send,无线局域网协议,MACA 解决暴露站点问题 C收不到A发出的CTS发送抑制帧 C可以在B向A发送数据的同时向D发送数据 新的问题 RTS帧的冲突,A,B,C,D,CTS,数字蜂窝,GSM 数字数据与数字信号 数字数据：集成、压缩、纠错、加密 数字信号：抗干扰、高数据传输速率、可再生 GSM的信道分配 FDMTDM（图2-43） 动态分配 GSM的公共信道 呼叫信道下行信道 随机访问信道上行信道 存在多路访问冲突问题，用slotted ALOHA解决 访问授权信道下行信道,用于连接的建立,扩,4.4 网桥,网桥又称MAC桥，是一种L2中继设备 主要强调互连 网桥通过多个端口互连不同的LAN 多种LAN技术的发展催生了网桥 各个LAN的MAC技术、速率均可不同 初期典型网桥：用于多网互连、特别是主干网接入 以太网桥：互连粗缆、细缆 TR网桥：互连16Mbps、4Mbps FDDI网桥：互连FDDI、以太网 传统网桥基于软件、性能不高、市场并不大 交换机就是硬件化的多端口网桥，目前以太网的主要设备,网桥的特点,隔离冲突域 网桥各端口具有独立的MAC实体 各端口为独立的冲突域 隔离流量 只有必要的帧才被网桥中继 宿地址与源地址同端口的帧，不转发 网桥各端口的流量相对隔离 可靠性，限制故障范围 安全性需要，将局域网隔离 特点的应用 网桥可以用于互连（对于不同类型的LAN） 网桥更可用于分段！（对于相同的LAN）,网桥隔离冲突域,网桥隔离冲突域，但不隔离广播域,A 站,B 站,C 站,D 站,所有站点位于同一冲突域,网桥隔离冲突域 将网络分隔成两个冲突域 每一个端口及其相连的站点位于同一冲突域,网桥连接局域网,网桥互连多个不同的LAN 各个局域网MAC技术和速率均可不同存储转发 网桥可能需要做协议转换（现在较少使用）