計(jì)算機(jī)網(wǎng)絡(luò)原理-有限競爭協(xié)議

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)計(jì)算機(jī)網(wǎng)絡(luò)原理 有限競爭協(xié)議競爭協(xié)議在輕負(fù)載下可以獲得良好的延遲特性，但重負(fù)載下由于沖突增加信道利用率不高；無沖突協(xié)議在重負(fù)載下可以獲得很高的信道利用率（因?yàn)闆]有沖突），但輕負(fù)載下由于要等待發(fā)送權(quán)而延遲特性不好。有限競爭協(xié)議試圖結(jié)合以上兩類協(xié)議的優(yōu)點(diǎn)和克服各自的缺點(diǎn)，使得在輕負(fù)載時(shí)使用競爭方式減小延遲，而在重負(fù)載時(shí)使用無沖突方法提高信道利用率。前面已經(jīng)討論了電纜網(wǎng)絡(luò)小的兩種基本的信道獲取策略：競爭法，如CSMA和無沖突法。每種策略的性能都可根據(jù)下述兩項(xiàng)重要的指標(biāo)加以評定

2、：輕載荷下的時(shí)延以及重載荷下的信道利用率。在輕裁荷下，競爭法（純ALOHA和分隙ALOHA）由于其時(shí)延短而性能較優(yōu)。但是，隨著載荷的增加，信道仲裁開銷越來越大，競爭法的性能也就越差。無沖突法的情況正好相反，輕載荷時(shí)，其時(shí)延較長，但隨著載荷的增加，信道利用率不僅沒有下降，反而有所改善。很顯然，假如能把競爭法和無沖突法的優(yōu)點(diǎn)糾合起來，產(chǎn)生一種新的協(xié)議，該協(xié)議在低載荷時(shí)采用競爭法使時(shí)延較短，在重載荷時(shí)采用無沖突法，使信道利用率較高，這樣就太好了，事實(shí)上這樣的協(xié)議的確存在，稱為有限競爭協(xié)議（Limited Contention Protocol），我們正好用它對載波偵聽網(wǎng)絡(luò)研究作個(gè)總結(jié)。到目前為止，所

3、討論的競爭協(xié)議都是對稱的，包就是說，每個(gè)站申請使用信道的概率都是相同的，均為P0，但有趣的是，通過給不同站點(diǎn)分配不問的信道獲得概率， 有時(shí)會使整個(gè)系統(tǒng)的性能有所提高。在開始討論非對稱協(xié)議之前， 先快速地回顧一下對稱協(xié)議的性能。假設(shè)共有k個(gè)站點(diǎn)參與信道競爭， 每個(gè)站點(diǎn)在每個(gè)時(shí)隙內(nèi)的發(fā)送概率為p，那么在其一給定時(shí)隙內(nèi)站點(diǎn)成功獲取信道的概率就為Kp(1-p)k-1。為確定P的最優(yōu)值、對P求微分，令結(jié)果為0，求得p最佳值為1/k。將p1/k代入，可得：圖4.8繪出了概率曲線。從圖中可以看出，當(dāng)競爭站點(diǎn)數(shù)較少時(shí)，成功率較高。但是，一旦競爭站點(diǎn)數(shù)達(dá)到5，成功率就降低為接近于1/e。很明顯，只要減少參均競爭

4、的站點(diǎn)數(shù)， 就可以增加站點(diǎn)獲取信道的概率。有限競爭協(xié)議正是這樣做的：首先將站點(diǎn)分組，第0組的成只允許在此0號時(shí)隙內(nèi)競爭，如其中之一成功，它就獲得了信道并傳送它的幀，若該時(shí)隙內(nèi)無人問津或產(chǎn)生沖突，那么第1組的成員就開始競爭1號時(shí)隙。 以此類推； 如果站點(diǎn)分組合理，就可減少每個(gè)時(shí)隙內(nèi)的競爭，從而使每個(gè)時(shí)隙的工作情況接近圖5-4左端的情形。圖5-4 對稱競爭信道獲取概率該協(xié)議的訣竅是如何向各站分配時(shí)隙。在討論一般情況之前，首先考慮幾個(gè)特殊的情況。一種極端的情況是每個(gè)組只行一個(gè)成員，這樣可保證沒有沖突，因?yàn)槊總€(gè)時(shí)隙中最多只有一個(gè)站點(diǎn)參與競爭，前面已經(jīng)見過這種協(xié)議（比如二進(jìn)制倒記數(shù)法）。第2種特殊的情況

5、是每組擁有2個(gè)成員，1個(gè)時(shí)隙2站向時(shí)試圖發(fā)送的概率為p2，當(dāng)P較小時(shí)可忽略不計(jì)。隨著組成員的增加，沖突的概率也隨之增加，但是位圖掃描的長度使每個(gè)站點(diǎn)有機(jī)會退出競爭，增加的極限情況就是一個(gè)級包括了所有的站點(diǎn)（比如分時(shí)隙ALOHA）。所以需要找到一種動態(tài)分組的方法，在輕載荷時(shí)每個(gè)組多分一些站點(diǎn)，在重負(fù)荷時(shí)，每個(gè)組少分一些站點(diǎn)（甚至只分1個(gè)站點(diǎn)）。適應(yīng)樹搜索協(xié)議一個(gè)特別簡單的分組方法是，采用二次世界大戰(zhàn)時(shí)期美軍設(shè)計(jì)的用來檢測士兵是否感染梅毒的算法該算法的過程簡單敘述如下：部隊(duì)從N個(gè)士兵身上抽取血液樣本，首先從N個(gè)樣本中各取一部分倒入同一試管中，然后檢測這個(gè)混合樣本是否帶有抗體， 如果沒有就認(rèn)為這N個(gè)

6、士兵都是健康的。如果發(fā)現(xiàn)抗體就準(zhǔn)備好兩個(gè)新的混合樣本，一個(gè)由1號到N2號土兵的血液樣本混合而成，另一個(gè)由剩下的混合而成；重復(fù)此過程，直到找出被感染的士兵。為了說明此算法的計(jì)算機(jī)版本， 在此可以像圖5-5所示的那樣，把站點(diǎn)看作是二叉樹的葉，很容易地用計(jì)算機(jī)來實(shí)現(xiàn)該算法：在一次成功傳送之后，在第一個(gè)競爭時(shí)隙（0時(shí)隙）內(nèi)，所有站點(diǎn)都可以嘗試獲取信道，如果只有一個(gè)站點(diǎn)申請使用信道，它會立即獲得信道，假如有多個(gè)站點(diǎn)同時(shí)申請， 便會產(chǎn)生沖突，那么在1時(shí)隙內(nèi)，只允許樹中位于節(jié)點(diǎn)2以下的站點(diǎn)參與競爭。如果它們其中之一獲得了信道，那么下一位時(shí)隙內(nèi)將由節(jié)點(diǎn)3以下的各站來競爭信道。但如果節(jié)點(diǎn)2下有多個(gè)站都想發(fā)送，那

7、么在時(shí)隙1內(nèi)就會產(chǎn)生沖突， 于是下一位時(shí)隙（即位時(shí)隙2）內(nèi)將由節(jié)點(diǎn)4以下各站點(diǎn)來競爭信道。圖5-5 包含8個(gè)站點(diǎn)的樹實(shí)際上，只要0時(shí)隙內(nèi)產(chǎn)生了沖突，就會用深度優(yōu)先法將整棵樹搜索一遍，以確定所有已準(zhǔn)備好發(fā)送的站點(diǎn)。每個(gè)位時(shí)隙都與樹中某個(gè)特點(diǎn)的節(jié)點(diǎn)相聯(lián)系，如果在某個(gè)位時(shí)隙內(nèi)發(fā)生沖突，則從左到右遞歸地搜索該節(jié)點(diǎn)的子節(jié)點(diǎn)；如果位時(shí)隙空閑或者在該位時(shí)隙內(nèi)只有一個(gè)站點(diǎn)想要發(fā)送，那么對該節(jié)點(diǎn)的搜索就會停止，因?yàn)樗幸褱?zhǔn)備好發(fā)送的站點(diǎn)都己確定了（如果位時(shí)隙內(nèi)有多個(gè)站點(diǎn)想要發(fā)送，就會產(chǎn)生沖突）。當(dāng)系統(tǒng)載荷很重時(shí)，將位時(shí)隙0指定給節(jié)點(diǎn)1幾乎沒什么價(jià)值。因?yàn)橹挥挟?dāng)僅有一站點(diǎn)想要發(fā)送幀時(shí)這樣做才有意義，類似地，人們可

8、能會說：由于同樣原因，節(jié)點(diǎn)2和節(jié)點(diǎn)3也應(yīng)跳過。考慮更一般的情形，搜索應(yīng)該從樹的哪一級開始？很明顯，載荷越重，搜索開始的級點(diǎn)就應(yīng)該越低，假定每個(gè)站點(diǎn)對已難備好發(fā)送的站點(diǎn)數(shù)有一個(gè)較準(zhǔn)確的估計(jì)，比如，通過監(jiān)視網(wǎng)絡(luò)實(shí)時(shí)流量，獲得估計(jì)數(shù)為q。首先，從上到下來計(jì)算一下整棵樹的級數(shù)。如圖5-5所示，節(jié)點(diǎn)1位于0級，節(jié)點(diǎn)2，3位于第1級依次類推。那么，第i級的節(jié)點(diǎn)下包含的站點(diǎn)數(shù)應(yīng)為總站數(shù)的2-i。如果q個(gè)已準(zhǔn)備好的站點(diǎn)均勻分布，那么1級中任一節(jié)點(diǎn)下準(zhǔn)備好發(fā)送的站點(diǎn)數(shù)應(yīng)為2-iq，憑直覺，搜索開始的最優(yōu)級應(yīng)該是每時(shí)隙參與競爭平均站數(shù)為3的那一級，即2-iq=1解之得：i=log2q?，F(xiàn)在已經(jīng)發(fā)現(xiàn)了許多改進(jìn)算法，BERTSEKAS和GALLAGER（1992）對此作了比較詳細(xì)的討論，例如，考慮只有