计算机网络原理--有限竞争协议

计算机网络原理有限竞争协议竞争协议在轻负载下可以获得良好的延迟特性，但重负载下由于冲突增加信道利用率不高；无冲突协议在重负载下可以获得很高的信道利用率（因为没有冲突），但轻负载下由于要等待发送权而延迟特性不好。有限竞争协议试图结合以上两类协议的优点和克服各自的缺点，使得在轻负载时使用竞争方式减小延迟，而在重负载时使用无冲突方法提高信道利用率。前面已经讨论了电缆网络小的两种基本的信道获取策略：竞争法，如CSMA和无冲突法。每种策略的性能都可根据下述两项重要的指标加以评定：轻载荷下的时延以及重载荷下的信道利用率。在轻裁荷下，竞争法（纯ALOHA和分隙ALOHA）由于其时延短而性能较优。但是，随着载荷的增加，信道仲裁开销越来越大，竞争法的性能也就越差。无冲突法的情况正好相反，轻载荷时，其时延较长，但随着载荷的增加，信道利用率不仅没有下降，反而有所改善。很显然，假如能把竞争法和无冲突法的优点纠合起来，产生一种新的协议，该协议在低载荷时采用竞争法使时延较短，在重载荷时采用无冲突法，使信道利用率较高，这样就太好了，事实上这样的协议的确存在，称为有限竞争协议（LimitedContentionProtocol），我们正好用它对载波侦听网络研究作个总结。到目前为止，所讨论的竞争协议都是对称的，包就是说，每个站申请使用信道的概率都是相同的，均为P0，但有趣的是，通过给不同站点分配不问的信道获得概率，有时会使整个系统的性能有所提高。在开始讨论非对称协议之前，先快速地回顾一下对称协议的性能。假设共有k个站点参与信道竞争，每个站点在每个时隙内的发送概率为p，那么在其一给定时隙内站点成功获取信道的概率就为Kp(1-p)k-1。为确定P的最优值、对P求微分，令结果为0，求得p最佳值为1/k。将p＝1/k代入，可得：1]1[]/1Pr[kkkkp的成功率图4.8绘出了概率曲线。从图中可以看出，当竞争站点数较少时，成功率较高。但是，一旦竞争站点数达到5，成功率就降低为接近于1/e。很明显，只要减少参均竞争的站点数，就可以增加站点获取信道的概率。有限竞争协议正是这样做的：首先将站点分组，第0组的成只允许在此0号时隙内竞争，如其中之一成功，它就获得了信道并传送它的帧，若该时隙内无人问津或产生冲突，那么第1组的成员就开始竞争1号时隙。以此类推；如果站点分组合理，就可减少每个时隙内的竞争，从而使每个时隙的工作情况接近图5-4左端的情形。05101520250.00.20.40.60.81.0已就绪的站点数成功概率图5-4对称竞争信道获取概率该协议的诀窍是如何向各站分配时隙。在讨论一般情况之前，首先考虑几个特殊的情况。一种极端的情况是每个组只行一个成员，这样可保证没有冲突，因为每个时隙中最多只有一个站点参与竞争，前面已经见过这种协议（比如二进制倒记数法）。第2种特殊的情况是每组拥有2个成员，1个时隙2站向时试图发送的概率为p2，当P较小时可忽略不计。随着组成员的增加，冲突的概率也随之增加，但是位图扫描的长度使每个站点有机会退出竞争，增加的极限情况就是一个级包括了所有的站点（比如分时隙ALOHA）。所以需要找到一种动态分组的方法，在轻载荷时每个组多分一些站点，在重负荷时，每个组少分一些站点（甚至只分1个站点）。适应树搜索协议一个特别简单的分组方法是，采用二次世界大战时期美军设计的用来检测士兵是否感染梅毒的算法该算法的过程简单叙述如下：部队从N个士兵身上抽取血液样本，首先从N个样本中各取一部分倒入同一试管中，然后检测这个混合样本是否带有抗体，如果没有就认为这N个士兵都是健康的。如果发现抗体就准备好两个新的混合样本，一个由1号到N／2号土兵的血液样本混合而成，另一个由剩下的混合而成；重复此过程，直到找出被感染的士兵。为了说明此算法的计算机版本，在此可以像图5-5所示的那样，把站点看作是二叉树的叶，很容易地用计算机来实现该算法：在一次成功传送之后，在第一个竞争时隙（0时隙）内，所有站点都可以尝试获取信道，如果只有一个站点申请使用信道，它会立即获得信道，假如有多个站点同时申请，便会产生冲突，那么在1时隙内，只允许树中位于节点2以下的站点参与竞争。如果它们其中之一获得了信道，那么下一位时隙内将由节点3以下的各站来竞争信道。但如果节点2下有多个站都想发送，那么在时隙1内就会产生冲突，于是下一位时隙（即位时隙2）内将由节点4以下各站点来竞争信道。4567312ABCDEFGH站点图5-5包含8个站点的树实际上，只要0时隙内产生了冲突，就会用深度优先法将整棵树搜索一遍，以确定所有已准备好发送的站点。每个位时隙都与树中某个特点的节点相联系，如果在某个位时隙内发生冲突，则从左到右递归地搜索该节点的子节点；如果位时隙空闲或者在该位时隙内只有一个站点想要发送，那么对该节点的搜索就会停止，因为所有已准备好发送的站点都己确定了（如果位时隙内有多个站点想要发送，就会产生冲突）。当系统载荷很重时，将位时隙0指定给节点1几乎没什么价值。因为只有当仅有一站点想要发送帧时这样做才有意义，类似地，人们可能会说：由于同样原因，节点2和节点3也应跳过。考虑更一般的情形，搜索应该从树的哪一级开始？很明显，载荷越重，搜索开始的级点就应该越低，假定每个站点对已难备好发送的站点数有一个较准确的估计，比如，通过监视网络实时流量，获得估计数为q。首先，从上到下来计算一下整棵树的级数。如图5-5所示，节点1位于0级，节点2，3位于第1级…依次类推。那么，第i级的节点下包含的站点数应为总站数的2-i。如果q个已准备好的站点均匀分布，那么1级中任一节点下准备好发送的站点数应为2-iq，凭直觉，搜索开始的最优级应该是每时隙参与竞争平均站数为3的那一级，即2-iq=1解之得：i=log2q。现在已经发现了许多改进算法，BERTSEKAS和GALLAGER（1992）对此作了比较详细的讨论，例如，考虑只有站点C和H想要发送的情况。在节点1肯定会产生冲突，故尝试节点2并发现其为空（已知节点1下有两个或多个站准备发送，既然没有一个位于节点2下，所以它们一定都在节点3下）。因此应该跳过节点3而去尝试节点6。如果该节点仍为空，那么就可以跳过节点7，而去尝试节点G。