文档介绍：计算机网络原理有限竞争协议竞争协议在轻负载下可以获得良好的延迟特性,但重负载下由于冲突增加信道利用率不高;无冲突协议在重负载下可以获得很高的信道利用率(因为没有冲突),但轻负载下由于要等待发送权而延迟特性不好。有限竞争协议试图结合以上两类协议的优点和克服各自的缺点,使得在轻负载时使用竞争方式减小延迟,而在重负载时使用无冲突方法提高信道利用率。前面已经讨论了电缆网络小的两种基本的信道获取策略:竞争法,如CSMA和无冲突法。每种策略的性能都可根据下述两项重要的指标加以评定:轻载荷下的时延以及重载荷下的信道利用率。在轻裁荷下,竞争法(纯ALOHA和分隙ALOHA)由于其时延短而性能较优。但是,随着载荷的增加,信道仲裁开销越来越大,竞争法的性能也就越差。无冲突法的情况正好相反,轻载荷时,其时延较长,但随着载荷的增加,信道利用率不仅没有下降,反而有所改善。很显然,假如能把竞争法和无冲突法的优点纠合起来,产生一种新的协议,该协议在低载荷时采用竞争法使时延较短,在重载荷时采用无冲突法,使信道利用率较高,这样就太好了,事实上这样的协议的确存在,称为有限竞争协议(LimitedContentionProtocol),我们正好用它对载波侦听网络研究作个总结。到目前为止,所讨论的竞争协议都是对称的,包就是说,每个站申请使用信道的概率都是相同的,均为P0,但有趣的是,通过给不同站点分配不问的信道获得概率,有时会使整个系统的性能有所提高。在开始讨论非对称协议之前,先快速地回顾一下对称协议的性能。假设共有k个站点参与信道竞争,每个站点在每个时隙内的发送概率为p,那么在其一给定时隙内站点成功获取信道的概率就为Kp(1-p)k-1。为确定P的最优值、对P求微分,令结果为0,求得p最佳值为1/k。将p=1/k代入,可得:。从图中可以看出,当竞争站点数较少时,成功率较高。但是,一旦竞争站点数达到5,成功率就降低为接近于1/e。很明显,只要减少参均竞争的站点数,就可以增加站点获取信道的概率。有限竞争协议正是这样做的:首先将站点分组,第0组的成只允许在此0号时隙内竞争,如其中之一成功,它就获得了信道并传送它的帧,若该时隙内无人问津或产生冲突,那么第1组的成员就开始竞争1号时隙。以此类推;如果站点分组合理,就可减少每个时隙内的竞争,从而使每个时隙的工作情况接近图5-4左端的情形。图5-4对称竞争信道获取概率该协议的诀窍是如何向各站分配时隙。在讨论一般情况之前,首先考虑几个特殊的情况。一种极端的情况是每个组只行一个成员,这样可保证没有冲突,因为每个时隙中最多只有一个站点参与竞争,前面已经见过这种协议(比如二进制倒记数法)。第2种特殊的情况是每组拥有2个成员,1个时隙2站向时试图发送的概率为p2,当P较小时可忽略不计。随着组成员的增加,冲突的概率也随之增加,但是位图扫描的长度使每个站点有机会退出竞争,增加的极限情况就是一个级包括了所有的站点(比如分时隙ALOHA)。所以需要找到一种动态分组的方法,在轻载荷时每个组多分一些站点,在重负荷时,每个组少分一些站点(甚至只分1个站点)。适应树搜索协议一个特别简单的分组方法是,采用二次世界大战时期美军设计的用来检测士兵是否感染梅毒的算法该算法的过程简单叙述如下:部队从N个士兵身上抽取血液样本,首先从N个样本中各取一部分倒入同一试管中,