湖州网站建设推广,金融中介做网站需要,网站个人备案 企业备案,化妆品网站静态模板哈工大计算机网络课程数据链路层协议详解之#xff1a;多路访问控制#xff08;MAC#xff09;协议
在上一小节介绍完数据链路层功能和所提供的服务后#xff0c;接下来我们介绍一个在数据链路层非常重要的一个协议#xff1a;多路访问控制MAC协议。
多路访问控制主要是…哈工大计算机网络课程数据链路层协议详解之多路访问控制MAC协议
在上一小节介绍完数据链路层功能和所提供的服务后接下来我们介绍一个在数据链路层非常重要的一个协议多路访问控制MAC协议。
多路访问控制主要是为了解决一类链路的使用问题。作为网路中的链路大致可以分为以下两类 点对点链路 顾名思义链路只连接两个相邻端点没有第三个结点与该链路相连。在这种情况下点对点通信就变得比较简单比如拨号接入的PPP或者以太网交换机与主机间的点对点链路。 广播链路共享介质 早期的总线以太网HFC的上行链路802.11无线局域网 显然在一个网络中如果使用广播链路共享介质来进行通信时就必须有一个机制来协调通信各方的通信数据同时需要保证在传输时数据互不干扰。这个协议就是多路访问控制MAC协议。
多路访问控制协议所要解决的就是采用单一共享广播信道进行通信的场景。在这种场景中如果有两个或两个以上的结点同时利用共享信息传输数据时势必就会相互干扰。
这种干扰在MAC协议里被称为冲突collision。 这种冲突会导致接收端的结点同时接收到两个或者多个信号导致接收失败
In a word在使用广播共享链路传输数据时必须要使用特殊的协议来协调多方通信。而本节介绍的多路访问控制协议multiple access control protocol就是为了解决上述问题而提出的。
作为MAC协议在被设计时有一些基本的考虑
期望采用分布式算法决定结点如何共享信道即决策结点何时可以传输数据。尽可能不需要一个集中的结点来协调通信各方的通信过程。在协调各方通信时协议必须基于信道本身通信信道共享协调信息。即无需带外信道用于协调。
理想MAC协议
给定速率为R bps的广播信道。
假设我们设计的是一个非常理想的MAC协议的话这个协议可能期望具有以下功能
当某一时刻信道只有一个结点在传输数据时它可以以速率R发送使用广播信道的全部带宽。当有M个结点期望发送数据时每个节点平均发送数据的平均速率为R/M。协议可以实现完全分散控制各方通信。 无需特定节点协调。无需时钟、时隙同步。 简单。协议越简单越好
当然这是理想状况下MAC协议的设计概括实际场景下是无法满足上述条件的。但是在这种理想条件下有助于我们理解MAC协议期望解决的主要问题或者实现的主要功能是哪些对我们后续理解MAC协议具有一定指导意义。
MAC协议分类
从计算机网络的角度出发典型的可以用于广播链路共享的协议分类根据实现的技术手段包括以下三大类 信道划分channel partitioningMAC协议。 使用多路复用技术。把信道资源划分成不同的资源片分配给不同的结点使用每个节点在通信过程中只占用其自己分配到的信道资源。这样由于资源已经被事前划分了就不会出现冲突问题。根据多路复用技术进一步划分如TDMA、FDMA、CDMA、WDMA等技术来支持多个用户共享信道资源。这一类方案采用的是针对信道资源进行划分从而使得通信各方只占用其分配到的资源片来实现信道共享。 随机访问random accessMAC协议 这一类协议在局域网中非常多见。信道不划分允许冲突。任意结点需要通信时都会使用该信道的全部带宽资源。因为是随机访问即任意时间都可以有用户传输数据的需求所以是允许冲突的。由于冲突会导致接收失败 所以该类协议需要提供冲突“恢复”机制。即当发生冲突接收失败时需要有机制能重新发送冲突数据最终保证接收端接收数据的完整性。 轮转taking turnsMAC协议 综合前面两类协议的优点通过采用某种机制使得结点能够轮流使用信道保证在使用信道时不发生冲突。每个节点在传输数据时能够使用信道的全部带宽。
信道划分MAC协议
信道划分协议采用的解决方案是将信道资源按照某种技术手段进行划分并分配给通信各方。各方在通信时只使用分配的资源片从而解决相互冲突的问题。
TDMA
下面以TDMA作为例子进行简单介绍。
TDMAtime division multiple access
TDMA时分多路复用技术实际上是将时间划分成一个个时隙将每个时隙分配给不同的结点从而使不同的结点只有在它所分配到的时隙时才能发送数据而不能占用其他结点的时隙。
分配给所有结点的时隙循环一个周期就构成一个复用帧。如下图所示一个复用帧内包含了所有结点在自己时隙里发送的数据。 在使用TDMA的信道划分协议中分配给某个节点的时隙如果它在这个时隙内不发送数据的话这个资源也要为它保留如上图空闲位置所示。
FDMA
同样的FDMAfrequency division multiple access 码分多路复用技术是针对频率来划分信道资源。
将信道频谱划分成若干频带frequency bands每个频带分配给不同用户去使用每个用户将自己需要传输的数据信号调制到对应的频带上去从而只在自己的频带上进行传输。
频分多路复用如下所示可以看到有的频带分配给用户后可能在某一段时间内该用户不发送数据此时这段频带资源仍然需要保留。 作为信道划分的MAC协议来说如果当网络负载特别重的时候假设所有结点都发数据此时将信道资源分配给各用户后所有被划分的资源都被利用此时的信道利用率是最高的。
但是从上面TDMA和FDMA的介绍也可以看到如果网络负载比较低时信道资源划分给各用户后某一时间可能只有一个用户发送数据此时信道资源利用率会非常低因为它只能使用分配给自己的资源片其余资源都必须空闲保留。
当然这种协议的好处也在于信道划分后各用户的数据传输不冲突。
随机访问MAC协议
作为随机访问MAC协议它的最大特点就是
当结点有数据帧需要发送时利用信道全部带宽来发送。动态性强没有事先的结点间协调。任何一个时刻下任何一个结点都可以发送数据帧。
在随机访问MAC协议下多个结点同时传输数据时就可能会出现“冲突”问题。因此随机访问MAC协议需要定义 如何检测冲突。即需要有冲突检测机制。 比如有的随机访问MAC协议是把数据帧发送出去后等待对方的确认。如果在规定时间内收到了对方的确认则认为没有冲突否则认为有冲突。 当发生冲突后如何从冲突中恢复e.g. 通过延迟重传 由于发生冲突意味着数据发送/接收的失败因此当发生冲突时一定要有一个机制来消解冲突带来的数据发送失败的影响。
典型的随机访问MAC协议包括
时隙sloted ALOHAALOHACSMA、CSMA/CD、CSMA/CA
时隙sloted ALOHA
首先来看一下时隙sloted ALOHA协议。
时隙sloted ALOHA协议有这样几个假设 网络中所有结点发送的数据帧大小是相同的。 时间被划分为等长的时隙。每个时隙可以传输一个数据帧 每个时隙通常是这样划分的一个时隙刚好能允许任何一个结点在这个时隙的开始发送数据帧当时隙结束时数据帧刚好被发送出去。 结点只能在时隙开始时刻发送数据帧。并在时隙结束时发完完成。 结点间时钟同步。 既然每个节点都只能在时隙开始时刻发送数据显然节点之间一定是时钟同步的。 如果2个或2个以上节点在同一时隙发送数据帧结点即检测到冲突。
作为时隙ALOHA协议它的运行理论来说相对比较简单每个节点的运行会遵行以下准则
当结点有新的数据帧待发送时会在下一个时隙开始时发送。如果发送数据帧时无冲突该结点可以在下一个时隙继续发送新的数据帧如果发送数据帧时有冲突该结点在下一个时隙以概率p重传该帧直至发送成功。
下面我们通过一个示例来看一下时隙ALOHA协议运行过程 假设网络中三个结点都共享同一个广播链路来传输数据。作为时隙ALOHA协议像我们上面介绍的任何一个结点只能在时隙的开始时刻发送数据帧。
在上述示例图中用C来标识一个冲突E来标识空闲S来标识发送成功。
在第一个时隙下三个结点同时发送数据帧一定是会导致冲突的。所以在之后的时隙下每个节点都有一定的概率去重发该失败帧。在第三个时隙下结点1和结点2同时重传数据帧又导致失败需要继续重发。最终结点2在第四个时隙时只有它发送数据帧无冲突产生所以发送成功。以此类推最终结点1在第8个时隙时重传数据帧成功而结点3在第9个时隙时重传数据帧成功。
通过上面的示例过程总结一下时隙ALOHA协议的优缺点
优点
单个结点活动时可以连续以信道全部带宽速率传输数据。高度分散化各结点只需同步时钟时隙。协议相对简单。
缺点
容易造成冲突进而导致失败数据帧的重传造成时隙浪费。空闲时隙。实际上结点也许能以远小于分组传输时间检测到冲突。但时隙ALOHA机制并没有这样的机制。时钟同步。必须要求网络所有结点间时钟需要同步不然无法确定一个时隙的开始和结束。
进一步的我们分析一下时隙ALOHA协议在处理数据帧发送时的效率情况。首先给出效率指标的计算方式
效率长期运行时成功发送帧的时隙所占比例。
比如对于时隙ALOHA协议来说它的效率实际上就是计算在长期的一段时间内成功发送数据帧的时隙占这段时间所有时隙的比例。
有了上面的定义我们来分析具体的场景
假设N个结点有很多帧等待传输每个节点在每个时隙均已概率p发送数据。
此时对于一个给定节点来说在一个时隙将帧发送成功的概率 p(1-p)N-1。上述公式的含义就是在某一时刻只有一个结点以概率p发送数据帧而其他结点都不发数据帧1-p概率进而得到的联合概率。
扩展到任意个结点即N个结点发送成功的概率为
P Np(1-p) N-1 对上式求当N趋于无穷时的极限可得
最大效率 1/3 0.37 即时隙ALOHA协议当结点无穷大时的最大效率0.37即最好情况下信道被成功利用的时间仅占37%。
显然时隙ALOHA协议的效率不是很让人满意当很多人都在使用时最好情况下信道利用率仅有37%剩下63%的情况会出现冲突造成浪费。
ALOHA
接下来再看一下ALOHA协议也称纯ALOHA协议。 它跟时隙ALOHA协议最大的区别在于它不进行时隙的划分。
特点 更加简单无需同步 当有新的帧生成时立即发送 冲突可能性增大 在t0时刻发送帧会与在[t0-1, t01]期间其他结点发送的帧冲突。 如上图所示作为纯ALOHA协议来说它的易损时间区是两个时隙因为它可能跟前后两个时隙的发送都会产生冲突。对比来看时隙ALOHA协议的易损时间区是一个时隙因为它规定只能在时隙的开始时发送数据所以冲突只会发送在一个时隙内。
因此直观来看纯ALOHA协议的效率一定比时隙ALOHA的效率还要低。
计算过程如下所示 P给定结点成功发送帧 P该结点发送 P无其他结点在[t0-1, t0]期间发送帧 P无其他结点在[t0, t01]期间发送帧 p*1-p)N-1 * (1-p)N-1 p*(1-p)2(N-1) … 选取最优的p并令n - ∞ 1/2e 0.18 结论纯ALOHA协议的效率比时隙ALOHA协议更差。
需要说明一点的是虽然纯ALOHA协议的效率比较差但在历史上它存在的重要意义在于它几乎是最早提出的MAC协议。
CSMA协议
通过上面对ALOHA协议的介绍可以发现上述两种ALOHA协议的效率都比较采用的都是比较简单的方法只要希望发送数据时就会进行发送操作而不管当前信道下是否已经有数据帧在传输。这种方式不仅会导致其他结点消息的发送失败实际上它自己的数据发送也不会成功因此是一种比较“自私”的协议。
怎么样来改进上述协议的本节介绍的CSMA协议就是在这方面做了很大改进。
CSMAcarrier sense multiple access载波监听多路访问协议。
CSMA协议最大的改进地方在于每一个结点发送数据帧之前一定会先监听信道实际上是通过监听信道中的载波信号来判断信道中是否有其他结点发送数据。 也就是说如果发现信道中有数据正在发送的话就不会发送数据。
如果发现信道中没有载波也就是信道是空闲的此时才会把完整的数据帧发送出去。
如果发现信道忙也就是有载波则会推迟发送数据帧避免出现冲突。
根据信道忙时推迟发送的策略不同又可以将CSMA协议分为不同类型
1-坚持CSMA 当发现信道忙不能立即发送数据帧时会以概率p1一直监听这个信道。一旦信道空闲时就立马发送数据帧。 非坚持CSMA 当发现信道忙之后不坚持持续监听信道而是随机等待一段时间后再去探测信道是否空闲。 P-坚持CSMA 当发现信道忙之后以概率P坚持监听信道以概率1-p随机等待一段时候后再监听信道。
仍然需要注意的是在CSMA协议中冲突仍然是无法避免的。比如对于1-坚持CSMA来说如果有两个结点同时监听信道一旦信道空闲之后同时往信道中发送数据帧此时就会导致冲突。
另外信号传播延迟的存在也会导致冲突。 比如如下示意图 假设A、B、C、D是网络中物理空间有一定距离的几个结点这几个结点都通过一段共享链路来进行通信。
假设t0时刻B节点要发送数据此时它会监听信道发现信道空闲就会开始发送整个数据帧。
由于数据在信道中的传输是需要时间的同时结点D因为跟结点B在物理链路上有一段距离导致其在t1时刻需要发送数据帧时还无法检测到刚刚结点B发送的数据信号。此时在t1时刻它监听信道发现信道也空闲就会发送数据帧从而导致两个数据信号在信道中叠加。 从上图进一步的观察到在整个数据帧传输完成之前在某一时刻tn时这种叠加信号实际上已经会被结点B或结点D感知到了其实后续帧的发送就已经没有意义了。但作为普通的CSMA协议来说只要某个结点确定要发送数据帧则一定会将完整的帧全部发完。
因此对于一般的CSMA协议来说这种继续发送冲突帧的情况会造成信道资源的浪费。
上述问题的解决思想实际上也非常简单即如果结点在发送数据的同时能够检测到信道是否产生冲突如果发送了冲突能够及时终止后面数据帧的发送就能够解决上述信道资源浪费的问题。
按照这样的思想设计的协议就是CSMA/CD协议。
CSMA/CD协议
CSMA/CDCSMA with Collision Detection即带有冲突检测的CSMA协议。
这里需要注意一点的是这里添加的CD冲突检测功能并不是说只有CSMA/CD协议才有冲突检测功能。实际上只要是随机访问MAC协议都会有一种冲突检测机制只不过这种冲突检测机制可能会不同。比如有的CSMA协议只能靠对方的确认才能知道是否发送了冲突。
这里CSMA/CD协议中的CD强调的是该协议能够边发送数据时边检测冲突或者说可以在非常短的时间内检测到冲突。
特点 短时间内可以检测到冲突 冲突后传输中止减少信道资源浪费。 比如一个结点需要发送一个很长的完整数据帧如果刚发送若干个比特就检测出冲突从而终止后续比特发送相当于节省了一个完整数据帧的信号延迟传输造成的信道资源浪费对整个信道资源利用率的提升非常有帮助。
比如在下图中当结点检测到冲突后即终止后续数据帧的发送。 冲突检测 有限局域网易于实现测量信号强度比较发射信号与接收信号。 比如以太网在广播链路介质共享的实现方案中使用的MAC协议就是CSMA/CD协议。 无线局域网很难实现接收信号强度淹没在本地发射信号强度下。 因为无线信号在空中的传播过程中衰减比较快距离越远衰减后的信号频率越小。因此作为无线信号的发射需要借助天线使用较大功率发送出去。这样在本地既要发送自己的信号同时还要依赖信号强度判断有没有其他结点发送数据就比较困难。因为其他结点的信道经过无线传播到达本地时可能已经衰减的比较小了即已经被本地信号的频率淹没了。
作为CSMA/CD协议它的边发送数据帧边检测冲突这样一个特性对整个协议来说是非常重要的。因为作为这个特性决定了使用CSMA/CD协议网络的很多特征。把这样的特性概括为一句比较简单的话就是“边发边听不发不听“。
下面我们以一个示例来展示上述过程 假设作为广播链路的网络使用的CSMA/CD协议该网络中两个距离最远的结点对是AB相距的距离为dmax。同时广播链路带宽为R bps网络数据帧传输的最小长度为Lminbits信号传播速度为Vm/s。
有了上述的网络参数之后考虑以下极端场景
在某一时刻结点A需要发送数据这个时候检测到信道是空闲的就开始发送数据。当结点A发送的第一个bit即将到达结点B但还没有到达结点B这样一个极限状态。
此时假设结点B也正好要发送数据由于还没有信号到达结点B所以结点B检测信道会发现信道是空闲的从而立即开始发送数据。而当结点B刚发送完数据之后就跟到达的结点A发送的信号叠加在一起冲突就发生了。
当然由于信号量叠加之后结点B可以立即监听到冲突的发生从而停止发送后续比特数据。但是结点A要需要等待结点B发送的信号传输到结点A时才能检测到信号量的叠加从而感知到冲突。
显然在这样一个极端场景下结点A从发送数据开始到检测到冲突发生需要2个传输延迟的时间。
也就是说按照CSMA/CD协议如果要让结点A能够满足边发边听的特性就意味着结点A发送的数据帧的传输延迟一定要满足这个条件
L/R 2d max / V 该条件表示的含义是结点发送数据帧的传输延迟一定要大于等于整个链路最大传播延迟的两倍。不然的话在检测到冲突之前可能结点的数据帧已经发完了。而结束发送之后就不会再检测冲突了但实际是发送了冲突的。发生了冲突却没检测出来会导致协议的可靠性大打折扣。所以需要满足上述条件。
有了上述条件之后把Lmin带入上述条件得到
L min/R 2d max / V 作为结点A到B在上述示例里仅考虑了信号传播速度事实上在实际网络中可能中间存在一些例如中继器等物理层设备也会造成一定的延迟。此时可以将上述改造成
L min/R RTT max RTTmax表示距离最远的两个结点数据信号传输的往返时间。
上述结论对CSMA/CD协议的网络来说是非常重要的假设网络中的带宽和信号传播速度是确定的显然Lmin和dmax成正比关系。因此要想网路能够按照CSMA/CD协议检测到更远距离的冲突可靠性更高的话这个最小数据帧长度就要增加反之就要缩小。
同时按照上述的结论如果一个网络的最小数据帧长度确定了这个时候网络的带宽比如从十兆到百兆百兆到千兆那么一个CSMA/CD冲突可检测范围也会变小R增大d变小。
最后再来介绍一下CSMA/CD协议的效率
Tprop LAN中2个结点间的最大传播延迟
ttrans 最长帧传输延迟 效率 1 1 5 t p r o p / t t r a n s 效率\frac{1}{15t_{prop}/t_{trans}} 效率15tprop/ttrans1
这个效率可以简单理解为当tprop趋近于0或者ttrans趋近于∞时效率趋近于1。
从效率可以看出CSMA/CD协议要远优于ALOHA协议并且简单分散。
轮转访问MAC协议
回顾一下之前小节中介绍的信道划分MAC协议的特点
网络负载重时共享信道效率高且公平网络负载轻时共享信道效率低。
随机访问MAC协议特点
网络负载轻时共享信道效率高单个结点可以利用信道的全部带宽。网络负载重时产生冲突开销。
因此轮转访问MAC协议综合了上述两类MAC协议各自的优点。首先希望保证在共享介质的传输中不会产生冲突问题其次每个结点在传输数据时能够利用信道的全部带宽。
典型的轮转访问MAC协议包括
轮询polling
在网络中存在一个主结点由主结点负责轮流“邀请”从属结点发送数据。换句话说每个从结点只有在被“邀请”时才能发送数据其他时候不能发送数据。在这种场景下每个结点发送数据的时候都可以利用链路的全部带宽。
典型应用 “哑dumb”从属设备 比如现在的传感器网络假如传感器是一个非智能的传感器那么主结点比如基站就可以利用这种轮询的方式去到不同的传感器上发送指令告知其可以发送数据。 比如在上面的网络中信道是共享的共享使用的方式是有一个主结点向从结点发送轮询的指令被轮询的主机只有在收到指令之后才可以发送数据以此类推。
轮询方式存在的问题 轮询开销。 任何一个结点都需要收到轮询的指令后才可以发送数据。而这个轮询指令的发送实际上也是要占用信道带宽的。 等待延迟 需要等待轮询指令的到来。 单点故障 整个网络是靠主结点轮询来工作的一旦主结点宕机这个网络就瘫痪了。
令牌传递token passing
另一个比较典型的轮转访问MAC协议叫做令牌传递token passing
该协议的工作原理是
网络中存在有且只有一个令牌token。令牌代表了共享介质的使用权。控制令牌依次从一个结点传递到另一个结点。令牌特殊帧。当一个结点获取到令牌之后才可以发送数据。因为网络中只有一个令牌所以一个时刻下只会有一个结点发送数据所以不会发送冲突。
由于令牌传播的特性使得很多令牌网络会构成一个环形的特性使得令牌沿着环形网络的某个方向进行传递。 令牌传递的问题 令牌开销。 令牌在网络中的传递也有带宽开销的问题。 等待延迟。 结点需要等待令牌的到来才能发送数据。 单点故障。 如果由于网络故障导致拥有令牌的结点没有成功把令牌归还到网络中去那么网络中可能就没有令牌了任何结点都没有信道的使用权来发送数据了。 当然在实际网络中这种问题也会被考虑的一般会有一个主结点来检测令牌是否丢失如果丢失了则会产生一个新的令牌放在网络上。
MAC协议总结
最后我们对上述介绍的MAC协议做个总结。 信道划分MAC协议将信道的物理特性比如时间、频带、码片进行划分。于是就有了TDMA、FDMA、CDMA。 该协议的特点是当信道负载比较高时利用率比较高。但负载比较低时利用率时比较低的。 随机访问MAC协议 它的特点是当网络中有数据帧要发送时即发送同时提供检测冲突机制。根据检测冲突机制的不同方式可以划分成ALOHA、时隙ALOHA、CSMA、CSMA/CD CSMA/CD应用于以太网 CSMA/CA应用于802.11无线局域网 轮转访问MAC协议 主结点轮询、令牌传递 应用场景蓝牙、FDDI、令牌环网
