第四讲 介质访问控制子层.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 TFDM 1 C N N N C NT TDM的效率和FDM一样 7 动态信道分配方案 1 假设条件 条件1 站模型 该模型有N个独立的站 有一个程序或用户产生帧 在长度为 t的时间内 产生一帧的概率为 t 一旦一帧已被产生 则该站阻塞 直到该帧发送成功 条件2 单信道假设 8 动态信道分配方案 2 条件3 冲突假设 当两帧同时传输时 信号重叠 产生混乱 称为冲突 条件4 连续时间 分槽时间 所有的站点能够检测到冲突事件 冲突的帧必须重发 除了冲突错误外 不会有其他错误 条件5 载波侦听或不侦听 能检测到所有的冲突吗 9 动态信道分配方案 3 动态信道分配方案必须解决的基本问题 1 谁可以发送数据 2 是否发生冲突 3 面对冲突的解决方法 4 评价标准 传输效率如何 信道利用率 传输延迟 基本的多路访问协议 1 ALOHA协议 2 载波侦听协议 3 无冲突协议 4 有限竞争协议 5 无线LAN协议 10 ALOHA协议 基本思想 1 当用户有数据发送时 马上发送数据 2 当检测到帧损坏后 等待随机的时间后 再次发送该帧 可行吗 效率如何 成功传输的概率是多少 11 ALOHA协议分析 1 帧时 传输一帧所需要的时间 即帧长 信道容量 新产生帧数 设均值为N 在一个帧时内 通信用户一共产生新的帧数 均值为N 如果N 1 则一定产生冲突 希望0 N 1 等待传输帧数 设均值为G 在一个帧时内 通信用户一共产生新帧和等待重传的帧数之和 显然G N 概率 一帧时产生k帧的概率为 Pr k Gke G k K 0时 Pr k 0 e G 如果假定一次传输成功的概率为P0 则吞吐量S GP0 12 ALOHA协议分析 2 冲突分析 传输帧 成功的条件 t0 t0 2t时间无发送帧 成功的概率 P0 Pr k 0 e 2G注意 时间为2个帧时 吞吐量S GP0 Ge 2G极值情况 G 0 5Smax 1 2e 0 184 13 ALOHA协议分析 3 纯ALOHA效率低的原因冲突的可能太大了 解决基本思路减少可能冲突的时间界限 HOW 时间分槽 14 分槽ALOHA协议 基本原理 将时间分成离散的间隔 每一个间隔对应一帧 数据必须从时槽的开始时刻发送 效果 冲突危险期被减少了一半 因此效率提高了一倍 主要问题 全局时间同步 比较困难 15 ALOHA协议比较 16 ALOHA协议分析 信道最佳利用率1 e 37 总体信道利用率不高 主要原因 无序竞争 冲突频繁 协议改进的基本思想 无序变有序 减少冲突 检测其他站点的行为 根据检测结果调整自己的行为 载波侦听 载波侦听协议 17 载波侦听协议CSMA 1 1 持续CSMA 基本原理 站点在发送数据前 先监听信道 若信道忙 则一直等待到信道空闲 1 持续 贪婪算法思想 若信道空闲 则发送数据 发送数据后 如果发生冲突 会吗 则等待一段随机时间后 再次检测和发送数据 主要优点 减少了冲突的发生 与ALOHA相比 性能会提升吗 信道利用率如何 传输延时如何 证明 测试验证 Getyourhandsdirty 18 载波侦听协议CSMA 2 非持续CSMA 基本原理 站点在发送数据前 先监听信道 若信道空闲 则发送数据 若信道忙 则等待随机一段时间后 再次检测和发送数据 发送数据后 如果发生冲突 则等待一段随机时间后 再次检测和发送数据 主要优点 进一步减少了冲突的发生 19 载波侦听协议CSMA 3 p 持续CSMA 应用于分槽信道 基本原理 站点在发送数据前 先监听信道 若信道空闲 则在当前时槽以p概率发送数据 如何实现 若信道忙 则在下一个时槽 再次检测和发送数据 发送数据后 如果发生冲突 则等待一段随机时间后 再次检测和发送数据 20 载波检测协议CSMA 4 性能分析 21 载波侦听协议CSMA 5 带冲突检测的CSMA CSMA CD 基本原理 一旦检测到冲突 则停止数据发送 该协议是以太网的基础在以太网中详细介绍 CSMA协议的启示 冲突越少 信道利用率可能会提高 如果没有冲突的话 效果是不是会更好 无冲突协议 22 无冲突协议 基本思想通过协商机制 协调用户竞争信道 避免冲突发生 位图协议 二进制倒计数协议 令牌传递协议 23 位图协议 1 基本原理 N个接入站点都有惟一地址 从0 N 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 log2N 精心设计帧结构 可以利用竞争时隙的信息 使得信道利用率100 主要问题 站点饿死 时间同步 信道支持 改进思路 循环地址 每次传输后 成功的站会被改写为最小的编号 28 令牌传递协议 基本思想 站点只有获取令牌时 才能发送数据帧 令牌以一定的策略在站点间流动 如令牌环 令牌 站点 IEEE802 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 log2q级开始开始搜索 34 以太网技术 1 最初的以太网体系结构 Xerox BobMetcalfe 3COM 35 10Base T 10Base F 以太网技术 2 以太网电缆 36 以太网技术 3 a 10Base5 b 10Base2 c 10Base T 37 以太网技术 4 10base T 38 以太网技术 5 曼彻斯特编码 0伏表示 0 5伏表示1容易引起歧义 用 1伏表示 1 1伏表示 0 则需要时钟同步 需求 接收者在没有外部时钟的情况下 无歧义的确定每一位的开始 结束或者中间位置 原因 方法 每一位分为两个相等间隔 发送1时 第一间隔为高电压 第二间隔为低电压 发送0则反之 39 以太网技术 6 协议 CSMA CD 基本原理 站点在发送数据前 先监听信道 若信道忙 则等待一段随机时间后 再试图发送数据 若信道空闲 则发送数据 边发数据边进行冲突检测 如果发现冲突 则马上停止数据发送 并等待一段随机时间后 再试图发送数据 两个关键问题 冲突检测问题 随机时间等待 40 以太网技术 7 冲突检测 需求 需要监听多少时间才能够确信没有冲突 41 以太网技术 8 结论 主机必须连续发送数据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 第三次冲突 则随机等待0 7个时间槽 23 第i次冲突 则随机等待0 2i 1个时间槽 2i i最大为10 即随机数的最大值为1024 43 以太网技术 10 帧格式 前导域 10101010 位填充技术 地址 第一位1 组地址 类型 数据发送对象 数据 填充 最少46字节 校验和 CRC校验 确认号 确认信息 序列号 无确认重传机制 不可思议 WHY 44 以太网技术 11 性能分析 假设条件 K个站点竞争信道 一个站点在竞争时槽发送数据的概率为p 在某时槽 某一个站点获得信道的概率 A kp 1 p k 1 某一个站点通过j次竞争获得信道的概率 Pj A 1 A j 1 某一个站点成功发送数据的平均竞争次数 T jPj 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 无基站通信模式 广播信道的特殊性 隐藏站问题 暴露站问题 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 LocalMultipointDistributionService 毫米波通信 802