第四章介质访问控制子层

第四章介质访问控制子层网络的分类点到点连接的网络使用广播信道的网络(多用于局域网)广播信道由多个用户共享，由此产生冲突，关键的问题是解决信道的争用，即MAC(MediaAccessControl)。计算机电缆Internet远端服务器路由器数据链路层的两个子层将数据链路层拆为两个子层：逻辑链路控制LLC(LogicalLinkControl)子层介质访问控制MAC(MediumAccessControl)子层。介质访问控制MAC：当存在多方要竞争使用信道的时候，决定谁可以使用信道。逻辑链路控制LLC：主要负责向网络层提供可靠，有效的点到点数据链路，与传输媒体无关。通过逻辑连接，差错控制，流量控制等办法当不需要可靠性时，LLC可以是很薄的一层，甚至省略。底层信道对LLC子层是透明的广播式信道网络层物理层站点1网络层物理层逻辑链路控制LLCLLC媒体接入控制MACMAC数据链路层站点2LLC子层看不见下面到底是广播式信道还是点到点信道MAC的设计目标-冲突发生后再解决-提前避免冲突信道只有一个，多方争用信道的时候，谁可以使用信道？MAC的设计目标公平接入MAC的设计目标低时延MAC的设计目标寻址4.1信道分配问题中心问题：如何在多个竞争的用户间分配单个广播信道在众多通信实体之间公平、有效的分配带宽。实现通信实体间良好的连通性，获得尽可能高的吞吐量。良好的报文时延特性。分类：静态信道分配方案动态信道分配方案4.1.1静态信道分配方案静态的信道分配方案FDM频分复用TDM时分复用将信道均分为若干个子信道，每个子信道为一个用户所独占。FDM系统的性能分析：N个子信道时，每个子信道的带宽为Cbps，帧到达率为每秒帧平均帧长为1/µbit子信道平均服务率为每秒µC帧若到达率和服务速率均服从泊松分布，数据帧的平均时延TFDM若合并这N个子信道为一个信道为N个用户同时提供服务，对应的平均时延1FDMTC11()FDMTTNCNNCN静态的信道分配方案适用于适用于用户数较少且每个用户都有平滑的流量负担（电话局间通信）不适用于数据流量突发性很大的网络，很多网络（如LAN）的流量具有突发性和间歇性特征，业务量和发送速率上都具有很高的峰值/平均比率，如1000:14.1.2动态信道分配方案通常采用的信道访问方法有两类随机访问：各节点根据自已的意愿发送数据，可能会产生冲突。分布式，节点间协作化解冲突。受控访问：通过某种控制机制使得任何时刻只有一个接点接入信道，需要一个仲裁机制，可以是集中式的，也可以是分布式的。4.2多路访问协议随机接入类（亡羊补牢）无冲突类（防患于未然）4.2.1ALOHA－纯ALOHA想说就说：每当用户有数据要发送，立刻发送发送方通过广播的反馈特性侦听信道，可以知道是否发生了冲突；若发生冲突，则发送方等待一段随机的时间，再次发送该帧，直到发送成功为止M11Mi1M1iM1iM3jM3jM2kM11Mi1M1iM2kM3jN1N2N3Ni信道随机时间随机时间一个帧时ALOHA性能分析网络负载G：在一个帧时内等待发送的平均帧数（成功发送的+未成功发送的）又叫offeredload吞吐量S：在一个帧时内成功传送的平均帧数S=0信道上无成功数据帧传送S=1意味着数据帧一个接一个的传送，帧间无空隙。又叫carriedload显然，G≥S当G=S，说明数据帧在信道上无冲突假设所有帧等长，称传输一个帧所需要的时间为帧时；假设每个帧时中帧的到达服从泊松分布，平均到达率为G。吞吐量S=GP0，P0是一帧没有冲突的概率在t个帧时内产生k帧的概率服从泊松分布在两个帧时内生成零帧的概率（无冲突）为P0=e-2GS=Ge-2G()Pr[()]!kGtGteNtkkS=Ge-2G，当G=0.5时，Smax=1/2e≈0.184时隙ALOHA（SlottedALOHA）将时间分成离散间隔（slot），所有用户遵守统一的时隙边界，用户只能在时隙开始时发送数据M11N1N2N3Ni信道随机时间随机时间一个帧时M11M31M31M2kM1iM2kM2kM1iM1i时隙ALOHA的性能危险周期减少一半，系统吞吐率S=Ge-GG=1时，Smax=1/e≈0.368，是纯ALOHA的两倍每帧平均重传次数随着G的增大而呈指数增长1111(1)(1)GGkkGGkGkkkPeeEkpkeeeS=Ge-G，当G=1时，Smax=1/e≈0.369D表示以帧时为单位的归一化平均报文发送时延4.2.2载波检测多路访问协议ALOHA的信道利用率很低，根本原因在于想说就说，导致了频繁的冲突。载波检测（载波侦听）（carriersense）：可以检测到信道上当前是否有数据在传输载波侦听多路访问（CarrierSenseMultipleAccess,CSMA）--先听再说1坚持CSMA0坚持CSMAp坚持CSMA1-坚持CSMA工作原理：发送站一直侦听信道，一旦发现信道空闲马上发送数据；发生冲突后，等待一段随机的时间后再次检测和发送。优点：减少了信道空闲缺点：增大的冲突发生的概率Ni信道M1iM2jMikMikττ信道闲Mik到达Mik在结点内等待M3l……持续监测信道直至空闲发送非坚持CSMA工作原理：发送站侦听信道，发现信道空闲，则开始传送数据；如果信道不空闲，则等待一段随机的时间后再次侦听信道优点：减少了冲突概率缺点：增加了信道空闲时间，增大了数据发送延迟Ni信道M1iM2jMikMikτττ信道忙信道忙信道闲随机时间随机时间Mik到达Mik在结点内等待p-坚持CSMA（时隙信道）工作原理：如果信道忙，则发送站持续侦听信道；如果信道空闲，以概率p发送数据，以概率1-p将数据的发送延迟到下一时隙并重复这一过程。当发生冲突时，等待一段随机时间后再重新开始Ni信道M1iM2jMikMikττ信道闲，以概率p发送，1-p继续等待下一次空闲Mik到达Mik在结点内等待M3l……持续监测信道直至空闲发送非坚持CSMA可以大大减少碰撞机会，提高系统吞吐量，但是因为退避会造成时延特性变差。1坚持CSMA无退避措施，在业务量很小时，报文的发送机会多，响应速度快，当业务量增加时，碰撞的机会增多，使得吞吐量和迟延特性急剧变差。P坚持CSMA是两者的折中，选择合适的p值可以获得较为满意的系统性能。坚持对信道的检测，以利于及时知道信道的忙闲情况，避免浪费。即便发现信道空闲，也不一定非要坚持发送，若某个结点能主动退避一下的话，可以减少冲突的可能性。Q：0.01坚持的CSMA在G=9时整体性能如何？D表示以帧时为单位的归一化平均报文发送时延带冲突检测Collisiondetection的CSMA边说边听：正在发送数据的站点一旦检测到冲突，立刻停止发送。半双工系统工作流程先听再说边说边听冲突停止延时再试CSMA/CDCSMA/CD性能分析模型CSMA/CD由三种状态交替组成竞争传输空闲竞争周期竞争周期为2,是信道上间隔最远的两台机器间的传播时延每个节点发出一帧后，在2时间内无冲突，则可以肯定该帧必将成功发送。LABt碰撞t=2A检测到发生碰撞t=B发送数据B检测到发生碰撞t=t=0单程端到端传播时延记为CSMA/CD的性能(4.3.5以太网的性能)成功发送22竞争周期竞争周期…竞争周期2T0发送一帧所需平均时间TAV平均NR个竞争周期传输周期t002AVRAVTNTTT每帧的平均发送时间信道利用率CSMA/CD的性能(4.3.5以太网的性能)假设总线上有k个站要传送数据，每个站要发送帧的概率为p，则在一个竞争周期中总线上只有一个站发送帧的概率A=kp(1-p)k-1当p=1/k时，A最大，k→∞时，A→1/e则需要j个竞争周期才能成功发送一帧的概率为A(1-A)j故一个帧要成功发送所需的平均竞争周期数为：01(1)1jRjNjAAA其中a表示以帧时为单位的归一化传播时延，设F为帧长，B为网络带宽，L为电缆长度，c是信号传播的速度，则有：000100max0max02(21)1/1(21)14.44AVRTTTTNTTAAeTTea0BLaTcF2=51.2us,B=10Mbps时的网络性能111,,(1-)1(21)kBLaAkppaAcFCSMA/CD的性能分析max01114.4414.44BLTcFCSMA/CD不适用于长距离（卫星），高带宽（光纤）或短帧的网络环境，应寻求其他解决思路。信道利用率就越低。电缆越长，竞争周期越长帧越短，传送帧所需要的时间越短带宽越大，传送帧所需要的时间越短4.2.3无冲突的协议不再使用随机接入的思路，而是通过某种机制提前避免冲突。位图协议（比特映射协议）二进制倒计数协议。位图协议（BasicBitmapMethod）由竞争周期和帧传输周期组成。每个竞争周期包含N个时隙，如果站点n需要占用信道，则在第n个时隙中写入1，构成位图。当所有的N个时隙都通过后，每一个站点都知道了哪些站点希望发送数据，然后按照数字顺序开始传送数据位图协议特点：各站需严格同步各站需监听信道以了解发送时机扩展性不好假设帧长为d比特低负载情况下：信道利用率为d/(N+d)高负载情况下：信道利用率为d/(d+1)位图协议不适用于站点众多的情况站点同时按照从高比特到低比特的顺序广播其地址，同时监听信道。假定信道能够将各站的地址的对应位进行布尔或运算。冲突检测：如果某站发现其地址中原本为0的位变为1，则放弃发送。赢得信道后，站点便可发送帧，然后另一竞争周期重新开始。二进制倒计数法（binarycountdown）二进制倒计数法地址采用二进制编码，开销减少。设d为数据帧长，N为站点数，则信道利用率为d/(d+log2N)如果帧格式选择恰当，帧中第一字段为发送方地址，则效率为100%。特点各站需严格同步公平性差可能的改进？？4.2.4有限竞争协议结合随机访问法和无冲突法的优点：在轻负载时采用随机访问法来尽快接入信道。在重负载时采用无冲突法来保证信道利用率。自适应树搜索协议：把站点看作是二叉树的叶子在一次成功传送之后的第一个时隙，slot0，所有的站都允许尝试获取信道，如果发生了冲突，则在slot1中，只有树中2号节点之下的那些站才可以竞争。如果其中之一获得了信道，则这一帧之后的那个时隙被保留给节点3下面的那些站。另外，如果节点2下面的两个或者多个站希望发送数据，在slot1中会发生冲突，则slot2就由节点4下面的站来竞争。如果网络的负载很重，可以直接把slot0分配给节点2，甚至层次更深的节点。也就是说，负载越重，则越该从树的下面节点开始搜索。自适应树搜索协议原理4.2.5波分多路访问协议WDMA（WavelengthDivisionMultipleAccess，波分复用多路访问）利用不同的波长将光纤信道分给不同的用户（WDM）每一个波长又分成若干时隙（TDM）每个站在固定波长1上利用TDM向其他站发送数据每个站在固定波长2上以TDMA方式接受其他站的接入请求每个站：两个发送器，两个接收器。一个固定波长接收器，用于监听自己的控制信道，以TDMA方式接受其他站的接入请求；一个固定波长发送器，用于发送数据，以TDM方式向其他站发送数据，并声明自己的信道使用和分配情况；一个可调波长接收器，用于选择监听一个数据收发器，接收他站数据；一个可调波长发送器，用于在其它站点的控制信道上发送信息，向他站发送接入请求。A站与B站如何建立一个连接（单向A－B）：A将其数据接收器调节到B的数据信道上，等待状态时隙到来通过B的状态时隙，A知道哪些B