冲突分解算法预约多址协议NetworkDesignandAnalysis课件

NetworkDesignandAnalysisWangWenjieWangwj@冲突分解算法预约多址协议NetworkDesignandAnalysis课件多址接入协议（二）多址接入协议主要内容多址接入协议概述固定多址接入协议随机多址接入协议载波载波侦听型多址协议（CSMA）有碰撞检测功能的载波侦听型多址协议（CSMA/CD）冲突分解算法预约多址协议主要内容多址接入协议概述载波载波侦听型多址协议(1)CSMA是从ALOHA协议演变出的一种改进型协议，它采用了附加的硬件装置，每个节点都能够检测（侦听）到信道上有无分组在传输。如果一个节点有分组要传输，它首先检测信道是否空闲，如果信道有其他分组在传输，则该节点可以等到信道空闲后再传输，这样可以减少要发送的分组与正在传输的分组之间的碰撞，提高系统的利用率。CSMA协议可细分为几种不同的实现形式：非坚持型（Non-persistent）CSMA1-坚持型CSMA

p-坚持型CSMA载波载波侦听型多址协议(1)CSMA是从ALOHA协议演变出载波载波侦听型多址协议(2)非坚持型CSMA：指当分组到达时，若信道空闲，则立即发送分组；若信道处于忙状态，则分组的发送将被延迟，且节点不再跟踪信道的状态（即节点暂时不检测信道），延迟结束后节点再次检测信道状态，并重复上述过程，如此循环，直到将该分组发送成功为止1-坚持型CSMA：指当分组到达时，若信道空闲，则立即发送分组；若信道处于忙状态，则该节点一直坚持检测信道状态，直至检测到信道空闲后，立即发送该分组。

p-坚持型CSMA：指当分组到达时，若信道空闲，则立即发送分组；若信道处于忙状态，则该节点一直检测信道的状态，在检测到信道空闲后，以概率p发送该分组载波载波侦听型多址协议(2)非坚持型CSMA：指当分组到达时载波载波侦听型多址协议(3)载波载波侦听型多址协议(3)非时隙CSMA多址协议（1）非时隙CSMA协议的工作过程如下：当分组到达时，如果信道空闲，则立即发送该分组；如果信道忙，则分组被延迟一段时间后，重新检测信道。如果信道忙或发送时与其它分组碰撞，则该分组变成等待重传的分组。每个等待重传的分组将重复地尝试重传，重传间隔相互独立且服从指数分布。其具体的控制算法描述如下：若有分组等待发送，则转到第2）步，否则处于空闲状态，等待分组到达。监测信道：若信道空闲，启动发送分组，发完返回第1）步；若信道忙，放弃监测信道，选择一个随机时延的时间长度t开始延时（此时节点处于退避状态）。延时结束，转至第1）步。非时隙CSMA多址协议（1）非时隙CSMA协议的工作过程如下非时隙CSMA多址协议（2）非时隙CSMA多址协议（2）非时隙CSMA多址协议（3）非时隙CSMA多址协议（3）时隙CSMA多址协议（1）时隙CSMA协议把时间轴分成宽度为β的时隙（注意：时隙ALOHA中时隙的宽度为一个分组的长度，这里的时隙宽度为载波检测时间）。如果分组到达一个空闲的时隙，它将在下一个空闲时隙开始传输时隙CSMA多址协议（1）时隙CSMA协议把时间轴分成宽度为时隙CSMA多址协议（2）如果某节点的分组到达时，信道上有分组正在传输，则该节点变为等待重传的节点，它将在当前分组传输结束后的后续空闲时隙中以概率qr进行传输时隙CSMA多址协议（2）如果某节点的分组到达时，信道上有分时隙CSMA多址协议（3）我们可以用马尔可夫链来分析时隙CSMA协议的性能。设分组长度为1个单位长度，其总的到达过程是速率为λ的Poisson到达过程，网络中有无穷多个节点（假设B）。信道状态0、1、e的反馈时延最大为β。又设系统的状态为每一个空闲时隙结束时刻等待重传的分组数n，则相继两个状态转移的时间间隔为β或β＋1时隙CSMA多址协议（3）我们可以用马尔可夫链来分析时隙CS时隙CSMA多址协议（4）时隙CSMA多址协议（4）时隙CSMA多址协议（5）时隙CSMA多址协议（5）时隙CSMA多址协议（6）时隙CSMA多址协议（6）时隙CSMA多址协议（7）时隙CSMA多址协议（7）稳定的时隙CSMA多址协议稳定的时隙CSMA多址协议主要内容多址接入协议概述固定多址接入协议随机多址接入协议载波载波侦听型多址协议（CSMA）有碰撞检测功能的载波侦听型多址协议（CSMA/CD）冲突分解算法预约多址协议主要内容多址接入协议概述CSMA/CD(1)前面讨论的CSMA协议由于在发送之前进行载波监听，所以减少了冲突的机会。但由于传播时延的存在，冲突还是不可避免的。只要发生冲突，信道就被浪费一段时间。CSMA/CD比CSMA又增加了一个功能，这就是边发送边监听。只要监听到信道上发生了冲突，则冲突的节点就必须停止发送。这样，信道就很快空闲下来，因而提高了信道的利用率。这种边发送边监听的功能称为冲突检测。CSMA/CD(1)前面讨论的CSMA协议由于在发送之前进行CSMA/CD(2)CSMA/CD的工作过程如下：当一个节点有分组到达时，它首先侦听信道，看信道是否空闲。如果信道空闲，则立即发送分组；如果信道忙，则连续侦听信道，直至信道空闲后立即发送分组。该节点在发送分组的同时，监测信道δ秒，以便确定本节点的分组是否与其它节点发生碰撞。如果没有发生碰撞，则该节点会无冲突地占用该总线，直至传输结束。如果发生碰撞，则该节点停止发送，随机时延一段时间后重复上述过程。（在实际应用时，发送节点在检测到碰撞以后，还要产生一个阻塞信号来阻塞信道，以防止其它节点没有检测到碰撞而继续传输。）CSMA/CD(2)CSMA/CD的工作过程如下：当一个节点CSMA/CD(3)总的来说，CSMA/CD接入协议比CSMA多址接入协议的控制规则增加了如下三点：“边说边听”：任一发送节点在发送数据帧期间要保持侦听信道的碰撞情况。一旦检测到碰撞发生，应立即中止发送，而不管目前正在发送的帧是否发完。保证尽快确知碰撞发生和尽早关闭碰撞发生后的无用发送，这有利于提高信道利用率“强化干扰”：发送节点在检测到碰撞并停止发送后，立即改为发送一小段“强化干扰信号”，以增强碰撞检测效果。可以提高网络中所有节点对于碰撞检测的可信度，保证了分布式控制的一致性“碰撞检测窗口”：任一发送节点若能完整的发完一个数据帧，则停顿一段时间（两倍的最大传播时延）并监听信道情况。若在此期间未发生碰撞，则可认为该数据帧已经发送成功。此时间区间即称“碰撞检测窗口”。有利于提高一个数据帧发送成功的可信度。如果接收节点在此窗口内发送应答帧（ACK或NAK）的话，则可保证应答传输成功。CSMA/CD(3)总的来说，CSMA/CD接入协议比CSMCSMA/CD协议的性能（1）为了简化分析，首先假定一个局域网（LAN）工作在时隙状态下，以每个分组传输的结束时刻作为参考点，将空闲信道分为若干个微时隙，用分组长度进行归一化的微时隙的宽度为β。所有节点都同步在微时隙的开始点进行传输。如果在一个微时隙开始点有分组发送，则经过一个微时隙后，所有节点都检测到在该微时隙上是否发生碰撞。如果发生了碰撞，则立即停止发送。这里仍然用马尔可夫链的方法分析。分析的方法与时隙CSMA协议相同。设网络中有无穷多个节点，每一个空闲时隙结束时的等待重传的分组数为n，每个等待重传的节点在每一个空闲时隙后发送的概率为qr。CSMA/CD协议的性能（1）为了简化分析，首先假定一个局域CSMA/CD协议的性能（2）CSMA/CD协议的性能（2）CSMA/CD协议的性能（3）CSMA/CD协议的性能（3）CSMA/CD协议的性能（4）CSMA/CD协议的性能（4）CSMA/CD协议的性能（5）CSMA/CD协议的性能（5）CSMA/CACSMA/CA是有冲突避免（CollisionAvoidance）的载波侦听型多址接入协议。它是对CSMA的另一种改进方法。通常在无线系统中，一台无线设备不能在相同的频率（信道）上同时进行接收和发送，因而不能采用碰撞检测（CD）技术。因此，只能通过冲突避免的方法来减少冲突的可能性。在IEEE802.11无线局域网（WLAN）的标准中，就采用了CSMA/CA协议。它不仅支持全连通的网络拓扑，同时支持部分连通的网络拓扑。CSMA/CACSMA/CA是有冲突避免（Collision主要内容多址接入协议概述固定多址接入协议随机多址接入协议载波载波侦听型多址协议（CSMA）有碰撞检测功能的载波侦听型多址协议（CSMA/CD）冲突分解算法预约多址协议主要内容多址接入协议概述冲突分解算法（1）对于有竞争的多址接入协议如何解决冲突从而使所有碰撞用户都可以成功传输是一个非常重要的问题。从前面的讨论可以看出，通过调整对等待重传队列长度的估值，改变重传概率，可以进一步减缓碰撞。而另一种更有效的解决冲突的方式就是冲突分解（CollisionResolution）。冲突分解的基本思想是：如果系统发生碰撞，则让新到达的分组在系统外等待，在参与碰撞的分组均成功传输结束后，再让新分组传输。冲突分解算法（1）对于有竞争的多址接入协议如何解决冲突从而使冲突分解算法（2）例：设两个分组在第i个时隙发生碰撞，若每个分组独立的以1/2的概率在第i+1和i+2时隙内重传。求在这次冲突分解过程的通过率。解：在第i+1个时隙内有一个分组成功传输的概率为½。如果成功，另一个分组在第i+2个时隙内成功传输，此时需2个时隙解决碰撞。如果第i+1个时隙空闲或再次碰撞，则每个分组再独立地以概率1/2在第i+2和i+3时隙内重传。这样在第i+2个时隙内有一个分组成功传输的概率为1/4；如果成功，另一个分组在第i+3个时隙成功传输，此时共需3个时隙解决碰撞。依此类推，需要k个时隙完成冲突分解的概率为2−(k−1)。冲突分解算法（2）例：设两个分组在第i个时隙发生碰撞，若每个冲突分解算法（3）冲突分解算法（3）冲突分解算法（4）树形分裂算法（TreeSplittingAlgorithm）先到先服务（FCFSSplittingAlgorithm）分裂算法冲突分解算法（4）树形分裂算法（1）假设在第k个时隙发生碰撞，碰撞节点的集合为S。所有未介入碰撞的节点进入等待状态。S被随机地分成两个子集，用左集（L）和右集（R）表示。左集（L）先在第k+1时隙中传输。如果第k+1时隙中传输成功或空闲，则R在第k+2个时隙中传输。如果在第k+1时隙中发生碰撞，则将L再分为左集（LL）和右集（LR），LL在第k+2个时隙中传输。如果第k+2时隙中传输成功或空闲，则LR在第k+3个时隙中传输。依次类推，直至集合S中所有的分组传输成功。从碰撞的时隙（第k个时隙）开始，直至S集合中所有分组成功传输结束的时隙称为一个冲突分解期（CRP）树形分裂算法（1）假设在第k个时隙发生碰撞，碰撞节点的集合为树形分裂算法性能分析（1）树形分裂算法性能分析（1）树形分裂算法性能分析（2）树形分裂算法性能分析（2）树形分裂算法性能分析（3）树形分裂算法性能分析（3）树形分裂算法性能分析（4）树形分裂算法性能分析（4）树形分裂算法性能分析（5）树形分裂算法性能分析（5）树形分裂算法（2）例：一个有三个节点在第k个时隙发生碰撞后的分解过程如图所示，图中集合的分割是采用随机的方式，即在每次集合分割时，集合中的节点通过扔硬币的方法决定自己属于左集还是右集。树形分裂算法（2）例：一个有三个节点在第k个时隙发生碰撞后的树形分裂算法（3）该图中用了8个时隙完成了冲突分解。该算法中，在给定每个时隙结束时立即有（0,1,e）反馈信息的情况下，各个节点能构造一个相同的树，并确定自己所处的子集和确定何时发送自己的分组。具体的方法如下：树形算法中的发送顺序可对应于一个数据压入堆栈的顺序。当一个碰撞发生后，碰撞节点的集合被分为子集，形成的每一个子集作为一个元素压入堆栈。在发送时，堆栈最顶端的子集从堆栈中移出并进行发送。树形分裂算法（3）该图中用了8个时隙完成了冲突分解。树形分裂算法（4）每个节点采用一个记数器来跟踪它的分组所在的当前子集处于堆栈中的位置。如果该子集处于堆栈的顶端，则立即发送。当该节点的分组传输发生碰撞（冲突分解开始），计数器的初值置0或1（取决于该分组被放在那个子集中，显然如果该分组被放入左子集，则初值被置为0；而如果该分组被放入右子集，则初值置为1）。在冲突分解过程中，当计数器的值为0时，则发送该分组。如果计数器为非0，则在冲突分解过程中，每次时隙发生碰撞，计数器值加1，每次成功传输或时隙空闲，计数器值减1。树形分裂算法（4）每个节点采用一个记数器来跟踪它的分组所在的树形分裂算法（5）在冲突分解期（CRP）中，处理的分组是介入碰撞的分组。而在CRP中，还会不停地有新分组到达。对于CRP中新到达的分组有两种处理方法。方法一是在当前CRP结束后立即开始一个新的CRP，该新CRP所处理的分组就是当前CRP中到达的新分组。这种方法的问题是，如果当前CRP到达了很多分组，则在新的CRP中，可能要碰撞很长时间，才能通过分解得到一个很小的子集。方法二是在当前CRP结束时刻，立即将到达的分组分为j个子集（j的选择应使每个子集中的分组数稍大于1），然后对每一个子集进行冲突分解。该方法的最大通过率可以达到每个时隙0.43个分组。树形分裂算法（5）在冲突分解期（CRP）中，处理的分组是介入树形分裂算法（6）通过仔细观察树形算法，可以发现，如果在一次碰撞（如第k个时隙）以后，下一个时隙（第k+1时隙）是空闲的，则第k+2个时隙必然会再次发生碰撞。这表明将碰撞节点集合中的所有节点都分配到了右集（R），自然会再次发生碰撞。改进的方法是：当碰撞后出现空闲时隙，则不传送第二个子集（R）中的分组，而是立即将R再次分解，然后再传输分解后的第一个子集（RL），如果再次空闲，则再次进行分解，然后传送RLL集合中的分组，依次类推。通过这样的改进可以使每个时隙的最大通过率达到0.46个分组。树形分裂算法（6）通过仔细观察树形算法，可以发现，如果在一次FCFS分裂算法（1）先到先服务（FCFS）分裂算法的基本思想是根据分组到达的时间进行冲突分解，并力图保证先到达的分组最先传输成功设T(k)以前到达的分组都已发送完毕，现在需确定从T(k)开始，长度为α(k)区间内到达的分组在第k个时隙中传输。该区间被称为指配区间（AllocationInterval）。从T(k)+α(k)至当前传输时刻称为等待区间。该算法的主要功能是根据冲突分解的情况，动态地调整指配区间的长度和起始时刻。FCFS分裂算法（1）先到先服务（FCFS）分裂算法的基本思FCFS分裂算法（2）FCFS分裂算法（2）FCFS分裂算法（3）FCFS分裂算法（3）FCFS分裂算法（4）FCFS分裂算法（4）FCFS分裂算法（5）FCFS分裂算法（5）主要内容多址接入协议概述固定多址接入协议随机多址接入协议载波载波侦听型多址协议（CSMA）有碰撞检测功能的载波侦听型多址协议（CSMA/CD）冲突分解算法预约多址协议主要内容多址接入协议概述预约多址协议（1）在前面介绍的几种随机多址接入技术中，我们可以看到它们共同的关键技术是如何最大限度的减少发送冲突，从而尽量提高信道利用率和系统吞吐率。本节要讨论的预约多址协议的要点就是最大限度的减少或消除随机因素，避免发送竞争所带来的对信道资源的无秩序竞争，使系统能按各节点的业务需求合理地分配信道资源。所以，预约方式有时又被称为按需分配方式。预约多址协议（1）在前面介绍的几种随机多址接入技术中，我们可预约多址协议（2）预约方式要求在网络节点之间“隐式”的或“显式”地交换预约控制信息。依据这些信息，各网络节点可以执行同一个控制算法，以达到分布式控制操作的协调。预约信息的传输需要占用信道资源。因此，预约信息的多少，反映了多址协议开销的多少。依据这种开销形式的不同，我们将预约方式分为隐式预约方式和显式预约方式。在随机多址协议中，当数据分组发生碰撞时，整个分组都被破坏。如果分组较长，则信道的利用率较低。当数据分组较长时，我们可以在数据分组传输之前，以一定的准则，发送一个很短的预约分组，为数据分组预约一定的系统资源。如果预约分组成功传输，则该数据分组在预约到的系统资源（频率、时隙等）中无冲突的传输。由于预约分组所浪费的信道容量很少，因而提高了系统效率。预约多址协议（2）预约方式要求在网络节点之间“隐式”的或“显预约多址协议（3）预约多址协议（3）时隙预约多址协议（1）时隙预约多址协议（1）时隙预约多址协议（2）时隙预约多址协议（2）时隙预约多址协议（3）假定分组的到达是Poisson到达，分组的平均长度为1（）。假设每个预约的分组可以在当前帧中预约多个分组的传输。由于传播时延的影响，使得在卫星系统中当前帧中预约的分组只能在下一帧中进行传输，则在卫星系统中第i个分组的平均等待时延为：时隙预约多址协议（3）假定分组的到达是Poisson到达，分时隙预约多址协议（4）时隙预约多址协议（4）时隙预约多址协议（5）上面的分析中，采用了可变帧长的方案。该方案会带来两个方面的问题：一是如果某些节点在接收预约分配信息时，发生错误，则这些节点将无法跟踪下一个预约期，即出现不同用户之间的不同步，系统将无法工作；二是系统中会出现不公平的现象，非常繁忙的节点可能在每一帧中预约了很多时隙，从而使得帧长很长，这样会使许多节点无法接入系统。为了解决上述问题，可采用固定帧长的方案，每一个节点仍在预约时隙中进行预约，每个节点有一个预约的时隙。如果在当前帧中分组传输不完，可推迟到下一帧中进行传输。这样从概念上讲，在系统中就形成了一个已