MAC层

第四章介质访问子层•信道分配问题•多路访问协议•IEEE802标准和局域网•局域网互连和网桥•高速局域网OSI参考模型和802工程模型的关系•从OSI参考模型的角度来看，IEEE802标准主要涉及物理层和数据链路层及网络层的一部分，其中数据链路层被分为介质访问控制（MAC）子层和逻辑链路控制（LLC，LogicalLinkControl）子层。–物理层和介质访问控制子层：局域网可采用多种传输介质和拓扑结构，相应需要多种不同的介质访问控制方式。–逻辑链路控制子层：完成通常意义下的数据链路层的功能，使网络的上层可完全独立于各种不同的物理底层。–网际（network）层：由于局域网基本使用广播信道，各节点之间无需路由选择。但当涉及多个局域网互连时，就必须设置一网际层来实现路由选择的问题，相当于网络层的一个子层。NetworkLayerDataLinkLayerPhysicalLayerNetworkLLCMACPhysicalOSI参考模型802工程模型IEEE802标准系列图示802.3MAC802.3物理层802.4MAC802.4物理层802.5MAC802.5物理层802.6MAC802.6物理层802.2LLC802.1A概述及体系结构802.1B寻址、管理802.1B网际互联物理层链路层网际层广播式网络•局域网大多采用广播传输技术（共享信道）。•广播信道（broadcastchannel）或多路访问信道（multiaccesschannel）或随机访问信道（randomaccesschannel）中，所有站点共享一个传输信道，任何时候只允许一个站点使用信道（向信道上发送数据）。若有两个或多个站点同时发送数据，则信号在信道上就会发生碰撞或冲突（collision），导致数据发送的失败。介质访问控制（MAC）•解决冲突的办法就是采用一套信道分配的策略来控制各个站点如何使用信道，即介质（信道）访问（使用）控制MAC（MediumAccessControl）。•由于网络中使用的传输介质及拓扑结构的不同，使得介质访问控制的策略也不相同，因此在局域网的数据链路层底部特别设置一个介质访问控制子层来专门负责信道分配的问题。§4.1信道分配问题•信道分配策略可分为两大类：–静态分配：如传统的FDM和TDM，将频带或时间片固定地分配给各个站点。适用于站点数量少且固定的场所，控制简单，效率高。–动态分配：异步时分多路复用。分为两种：•随机访问（争用，contention）：只要有数据，就可直接发送，发生冲突后再采取措施解决冲突。适用于负载轻的网络，负载重时效率低。•控制访问：发送站点必须先获得发送的权利，再发送数据，不会发生冲突。在负载重的网络中可获得很高的信道利用率。主要有轮转（round-robin）和预约（reservation）两种方式。静态分配•静态分配无法适应用户数的动态变化。•突发性通信造成信道的闲置，使利用率降低。•平均时延：设信道容量为C比特/秒，数据到达率为λ帧/秒，平均每帧长度服从指数概率密度函数分布1/μ比特/帧，则平均时延为：1T=————μC-λ若将单个信道分为N个独立分布的FDM子信道，则平均时延为：1NTFDM=———————=————=NTμ(C/N)-(λ/N)μC–λ是单个信道时延的N倍。TDM也有类似问题。动态分配模型一些假设：•站模型：由N个独立的站组成，每站在Δt时间内生成新帧的概率为λΔt，λ为一常量。•单通道假设：所有通信都通过单个信道进行。•冲突假设：如果两帧同时发送，产生冲突，所有的站都能检测到冲突。除冲突外没有其他错误。•连续时间：帧能在任何时候开始发送。•时隙：时间被分为离散的区间（时隙），帧总是在时隙开始的瞬间发送。•载波侦听：所有的站都能检测到信道是否正在使用。•非载波侦听：各站在使用信道前不检测信道是否空闲。§4.2多路访问协议•争用协议一：ALOHA协议–20世纪70年代，美国夏威夷大学的ALOHA网通过无线广播信道将分散在各个岛屿上的远程终端连接到本部的主机上，是最早采用争用协议的网络。–有两个版本：纯ALOHA协议（PureALOHA）：时间是连续的，不需要时间同步。时隙ALOHA协议（SlottedALOHA）：时间是离散的，需要时间同步。纯ALOHA协议•每个站点只要有数据就可发送；通过监听信道来发现是否发生冲突；若冲突，则等待一段随机时间，再重新发送。•研究发现，各个帧的长度相同，就可获得最大的吞吐量（单位时间内能够成功发送的数据帧的平均数量）。纯ALOHA信道的分析•一个争用系统一方面不断生成新的数据帧发送，另一方面由于冲突造成老的数据帧的重发。•若在一个帧时Tframe（frametime，一个数据帧占有的时间长度）内平均有N个新帧生成，显然，必须满足0N1。再加上一些重发的老帧，该时间内实际发送的帧的平均数为G。–当负载很小时，几乎不发生冲突，可认为N≈G。–当负载增大而产生冲突时，GN。–在各种负荷下，设传送成功的概率为P0，则存在S=GP0的关系，这里S即为吞吐量，G为网络负载。•在任一帧时内生成k帧的概率服从泊松分布（Poissondistributed）：Gke-GPr[K]=—————K!纯ALOHA系统中的易损时间区•在下图中可以看出，在时间区t0~t0+2t内，除阴影帧外只要有其它数据帧开始发送，都会产生冲突，这个时间区（即2t，两个帧时）称为易损时间区（vulnerableperiod）。纯ALOHA信道的效率•生成0帧的概率=G0e-G/0!=e-G•由于两个帧时内，则在易损时间区内不生成任何其它帧的概率为：P0=e-2G•代入S=GP0可得：S=Ge-2G•当G=0.5时，可获得最大的吞吐量Smax=1/2e≈18.4%时隙ALOHA协议•1972年提出了可将纯ALOHA的利用率提高一倍的方法，即时隙ALOHA系统。•将信道时间分为离散的时间片，每个时间片可以用来发送一个帧。一个站点有数据发送时，必须等到下个时间片的开始才能发送。•这种时间的同步是通过设置一个可定时发送时钟信号的特殊站点来实现的。•时隙ALOHA的易损时间区是纯ALOHA的一半（即t，一个帧时），因此可得：S=Ge-G•当G=1时，可获得最大的吞吐量Smax=1/e≈36.8%争用协议二：CSMA协议•载波侦听多路访问（CarrierSenseMultipleAccess）协议中，各站点不是随意发送数据帧，而是先要监听一下信道，根据信道的状态来调整自己的动作，只有发现信道空闲后才可发送数据。即“讲前先听”•可大大减少冲突，获得远大于1/e的利用率，广泛应用于LAN中。•常见的四种CSMA协议：–1-坚持式CSMA（1-persistentCSMA）–非坚持式CSMA（non-persistent）–p-坚持式CSMA（p-persistentCSMA）–带有冲突检测的CSMA（CSMAwithCollisionDetection）1-坚持式CSMA•当一个站点要发送数据时，首先监听信道，若信道忙，就坚持监听，一旦发现信道空闲，就立即发送数据（发送数据的概率为1）。若发生冲突，就等待一随机时间，再重新开始监听信道。•两种发生冲突的可能：–信号传输的延迟造成的冲突。–多个站点在监听到信道空闲时，同时发送。•此协议的性能高于ALOHA协议。非坚持式CSMA•当一个站点要发送数据时，首先监听信道，若信道忙，就随机等待一段时间后再开始监听信道（非坚持）；一旦发现信道空闲，就立即发送数据。•此协议的信道利用率高于1-坚持式CSMA协议。•网络的延迟增大。p-坚持式CSMA•用于时隙信道。当一个站点要发送数据时，首先监听信道，若信道忙则等到下个时间片再开始监听信道；若信道空闲便以概率p发送数据，而以概率q=1-p推迟到下个时间片再重复上述过程，直到数据被发送。•概率p的目的就是试图降低1-坚持式协议中多个站点同时发送而造成冲突的概率。•采用坚持监听是试图克服非坚持式协议中造成的时间延迟。•p的选择直接关系到协议的性能。各种随机访问协议的信道利用率与负载的关系图CSMA/CD•CS协议的“讲前先听”对ALOHA系统进行了有效的改进，但在发送过程中若发生冲突，仍要将剩余的无效数据发送完，既浪费了时间又浪费了带宽。•CD协议的“边讲边听”可对CSMA作进一步改进。发送过程中，仍然监听信道，通过检测回复信号的能量或脉冲宽度并将之与发送的信号作比较，就可判断是否发生冲突。一旦发生冲突，立即取消发送，等待一随机时间后再重新尝试发送。•CSMA/CD有三种状态：竞争、传输和空闲周期。碰撞检测•“碰撞检测”就是计算机边发送数据边检测信道上的信号电压大小。•当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（互相叠加）。•当一个站检测到的信号电压摆动值超过一定的门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞。•所谓“碰撞”就是发生了冲突。因此“碰撞检测”也称为“冲突检测”。1kmABt碰撞t=t0+εB检测到信道空闲发送数据t=t0+ε/2发生碰撞t=t0+2A检测到发生碰撞t=t0+εB发送数据B检测到发生碰撞t=t0+ε/2ABABABt=t0A检测到信道空闲发送数据ABt=t0t=t0+B检测到发生碰撞停止发送STOPt=t0+2εA检测到发生碰撞STOPAB单程端到端传播时延记为CSMA/CD协议中的竞争时间片•竞争时间片（contentionslot）的长度为信道最大传输延迟（propagationdelay）的2倍（即2τ，图中为2Tprop）。表示一个站点发送数据后，最多需经2τ的时间才能确认是否“抓住”（seized）了电缆。•例如，对于1公里长的同轴电缆，τ约为5µs，则其竞争时间片为2τ，即10µs。竞争时间片的理解•竞争时间片也叫冲突检测时间。•使用特殊的编码用于冲突检测。•帧的最小长度？•较大的τ（长的信道）和短帧对冲突的影响。4.2.3无冲突（collision-free）协议•顾名思义无冲突协议就是不会产生冲突的协议。•两种无冲突协议：–位图（bit-map）协议也叫比特映像协议–二进制倒计数（binarycountdown）协议也叫二进制地址相加协议位图协议•假设有N个站点（编号为0~N-1），下图中N=8。•将信道时间划分成一系列交替的预约周期（位图）和数据传输周期：–一个预约周期由N个1比特的竞争时隙组成，每个时隙对应一个站点。任何一个站点有数据发送时，必须在它的竞争时隙期间发送“1”进行预约。–预约周期结束后，预约过的站点按编号顺序进行发送，永不冲突。最后一站点发完数据后，开始新一轮的预约周期。位图协议的性能•低负荷时，数据发送少，基本重复预约周期。–对于低编号的站点，平均需等待N/2时隙（本次预约周期）外加N时隙（下一轮预约周期），共1.5N时隙后才可发送。–对于高编号的站点，平均只需等待N/2时隙（本次预约周期）就可发送。–因此，所有站点平均等待时间为N个时隙。则低负荷下的效率为d/(N+d)，其中d为一个数据帧的比特量。•高负荷时，基本上N比特竞争时隙按比例平均分配给N帧数据，即每帧需要一比特的额外开销，则效率为d/(d+1)。位图协议的改进•小时隙轮换优先权协议：对位图协议稍加改进，一个站点在预约后可立即发送，发送后紧接着又进入预约周期，由后继站点进行预约发送。•改善了位图协议在低负荷下的效率，每个站点的平均等待时间都为N/2个时隙。01234567012345671113171115二进制倒计数协议•每个站点的地址用等长的二进制数表示。每个要发送数据的站点先广播发送它们的二进制地址（按高位到低位的顺序）。这些地址在信道上被按位相加（逻辑或）。各站点在发送地址时监听信道，当发现自己地址中的某个“0”在信道上变为“1”时，即退出竞争。最后参与竞争的地址最高的站点获得发送权。发送结束后，重新进入下一轮竞争。二进制倒计数协议的效率及改进•对共有N个站点的系统中，地址长度为ceil(lo