00-ALOHA-CSMA-CD-冲突窗口最小帧长.ppt

1 4 3随机接入技术 ALOHA AdditiveLinkOn lineHAwaiiSystem 目标 当网络的通信量较小时 让用户自由地发送数据所产生冲突的概率并不大 只要协议考虑到如何处理好冲突的问题 像这样的多点接入方式称为随机接入 纯ALOHAALOHA网络是美国Hawaii大学于1968年9月研制 于1970年建立的分组传送的由无线电信道组成的计算机通信网络 2 纯ALOHA 纯ALOHA工作原理每个站只要有数据发送 就可自由的发送一个数据帧 但必须收到接收节点的确认信号ACK之后 才能发送下一个数据帧 AlOHA系统的一般模型 3 纯ALOHA 图4 3 2纯ALOHA的工作原理 4 纯ALOHA 冲突的解决方案冲突 两个以上的站同时发送报文分组 由于在时间上重叠从而造成冲突 导致发送失败 解决方案 补救方法 发送节点在一个timeoutinterval内未收到确认信号ACK 自动重发 5 时隙ALOHA S ALOHA 1 目的 为了提高随机接入系统的吞吐量 可以将所有各站在时间上都同步起来 并将时间划分为一段段等长的时隙T0 同时规定 不论帧在何时产生 它只能在每个时隙开始时才能发送出去 这样的ALOHA系统称为时隙ALOHA S ALOHA 工作原理 6 时隙ALOHA S ALOHA 2 主要性能参数 吞吐率 吞吐量 S T0内成功发送的帧数0 S 1 网络负载G T0内总共发送的平均帧数T0的含义 独占信道时成功发送一帧所用的时间帧成功发送的条件 该帧与其前后2帧的间隔均大于T0 S ALOHA与ALOHA比较 重负载条件下以争用为基础的不稳定性 延迟随提供的负载按指数形式增加 7 4 4随机接入技术 CSMA 发前先听 目的 载波监听多点接入CSMA是从ALOHA演变出的一种改进协议 又称为载波监听多点访问 由于采用了附加的硬件装置 每个站都能在发送数据前监听信道上其他站是否在发送数据 如在发送 则此站就暂不发送数据 从而减少了发送冲突的可能 这样就提高了整个系统的吞吐量 根据监测时刻不同 及监测后采用策略的差异 可分为四种 非坚持CSMA non persistentCSMA 1 坚持CSMAP 坚持CSMACSMA CD 边听边发 非坚持CSMA 非坚持CSMA的工作原理 a 监听到数据 闲 则发送 b 监听到数据 忙 按一定退避算法延迟一段时间 这就是 非坚持 的含义 返回 a 优点 采用随机重传时间减少碰撞概率 缺点 延迟时间内可能会出现通道闲的情况 利用率不高 9 坚持CSMA 坚持CSMA的工作原理坚持CSMA的特点是在监听到信道忙 仍坚持听下去 一直坚持听到信道空闲为止 有两种不同的策略 1 坚持CSMA 1 的含义是当信道一但 闲 数据以概率为1的原则发送 a 信道一但 闲 数据以概率为1的原则发送 b 信道 忙 连续监听 直至监听到通道 闲 返回 a 优点 提高信道利用率 缺点 若有两个或更多的站同时在监听信道 则一但信道空闲就必然使这些同时发送的packet互相冲突 10 P 坚持CSMA P 坚持CSMA的工作原理 a 若信道 闲 以0 p 1的概率发送 以概率 1 p 延迟一个随机时间段再发送 b 信道 忙 则继续侦听到信道闲 返回a 优点 p坚持CSMA可根据信道上通信量的多少设定不同的p值 因而可以使信道的利用率进一步提高 Valueofp AvoidinstabilityunderheavyloadnstationswaitingtosendEndoftransmission expectednumberofstationsattemptingtotransmitisnumberofstationsreadytimesprobabilityoftransmittingnpIfnp 1onaveragetherewillbeacollisionRepeatedattemptstotransmitalmostguaranteeingmorecollisionsRetriescompetewithnewtransmissionsEventually allstationstryingtosendContinuouscollisions zerothroughputSonp 1forexpectedpeaksofnIfheavyloadexpected psmallHowever aspmadesmaller stationswaitlongerAtlowloads thisgivesverylongdelays 12 非坚持 p坚持和1坚持这三种的优缺点 和CSMA一样 CSMA CD也可划分为时隙和非时隙的 而这两种中的每一种又可再分为非坚持 p坚持和1坚持这三种 三种坚持各有优缺点 非坚持不能充分利用信道刚刚转入空闲期的这段时间 1坚持又容易在上述这段时间产生冲突 p坚持可以在一定长度上克服这些缺点 但却很难选择一个能用于各种通信量强度的p值 CSMA CD与CSMA以及ALOGH的吞吐量比较 当a 0 01时几种CSMA CD CSMA以及ALOGH的S G曲线 其中 是端到端的时延 S是吞吐量 G是网络负载 14 CSMA CD 边发边听 CSMA CD的工作原理CSMA由于在发送数据之前进行载波监听 所以减少了冲突的机会 但由于传播时延的存在 即使发前先听 冲突还是不可避免的 只要发生冲突 信道就被浪费一段时间T0 t 冲突时间 后退时间 但CSMA CD比CSMA又增加了一个功能 这就是边发边监听 只要监听到发生冲突 则冲突的双方就停止 立即放弃此数据帧的发送 这样 信道就很快空闲下来 因而提高了信道的利用率 CSMA CD先听后说 边发边听 冲突时退避 WithCSMA collisionoccupiesmediumfordurationoftransmissionStationslistenwhilsttransmittingIfmediumidle transmit otherwise step2Ifbusy listenforidle thentransmitIfcollisiondetected jamthenceasetransmissionAfterjam waitrandomtimethenstartfromstep1 CSMA CDOperation WhichPersistenceAlgorithm IEEE802 3uses1 persistentBothnonpersistentandp persistenthaveperformanceproblems1 persistent p 1 seemsmoreunstablethanp persistentGreedofthestationsButwastedtimeduetocollisionsisshort ifframeslongrelativetopropagationdelayWithrandombackoff unlikelytocollideonnexttriesToensurebackoffmaintainsstability IEEE802 3andEthernetusebinaryexpo nentialbackoff BinaryExponentialBackoff AttempttotransmitrepeatedlyifrepeatedcollisionsFirst10attempts meanvalueofrandomdelaydoubledValuethenremainssamefor6furtherattemptsAfter16unsuccessfulattempts stationgivesupandreportserrorAscongestionincreases stationsbackoffbylargeramountstoreducetheprobabilityofcollision 1 persistentalgorithmwithbinaryexponentialbackoffefficientoverwiderangeofloadsLowloads 1 persistenceguaranteesstationcanseizechannelonceidleHighloads atleastasstableasothertechniquesStationswithfewcollisionstransmitfirst CollisionDetection Onbasebandbus collisionproducesmuchhighersignalvoltagethansignalCollisiondetectedifcablesignalgreaterthansinglestationsignalSignalattenuatedoverdistanceLimitdistanceto500m 10Base5 or200m 10Base2 Fortwistedpair star topology activityonmorethanoneportiscollision hub Specialcollisionpresencesignal 20 CSMA CD产生冲突对信道占用时间的影响 从图中可以看出 发送冲突使A浪费时间TB TJ TB是A站从发送数据开始到发现有了冲突的时间间隔 TJ是各自都发送一个强化冲突的干扰信号 其持续时间 同时 整个信道被占用的时间还要增加一个单程端到端的传播时延t 因此总线的争用期应为TB TJ t TB的最小值为t 最大值为2t 所以争用期的最小值是2t TJ 而争用期的最大值是3t TJ 21 CSMA CD协议的时间槽 时间槽 能够检测到冲突的时间区间 也称为争用时隙或碰撞窗口 若两站点之间传播时延为a 则时间槽 2a 站点2发送帧 当 0时 将不会再发生冲突 这时 时间槽 2a 22 时间槽的意义 一个站点开始发送后 若在时间槽内没有检测到冲突 则本次发送不会再发生冲突 时间槽与网络跨距 传输速率 最小帧长有密切的关系 以太网中 时间槽 51 2 s传输速率 10Mb s时 一个时间槽内可发送512bits 即64字节 所以也称一个时间槽长度为64字节 由此可知 1 冲突只可能在一帧的前64字节内发生 2 帧长度小于64字节时 将无法检测出冲突 以太网规定 最小帧长度为64字节3 长度小于64字节的帧 碎片帧 都是无效帧 23 与时间槽相关的网络参数 采用CSMA CD的局域网中 由于时间槽的限制 传输速率R