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

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

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

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

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

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

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

7、么在時(shí)隙1內(nèi)就會(huì)產(chǎn)生沖突， 于是下一位時(shí)隙（即位時(shí)隙2）內(nèi)將由節(jié)點(diǎn)4以下各站點(diǎn)來(lái)競(jìng)爭(zhēng)信道。圖5-5 包含8個(gè)站點(diǎn)的樹實(shí)際上，只要0時(shí)隙內(nèi)產(chǎn)生了沖突，就會(huì)用深度優(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ā)送，那么對(duì)該節(jié)點(diǎn)的搜索就會(huì)停止，因?yàn)樗幸褱?zhǔn)備好發(fā)送的站點(diǎn)都己確定了（如果位時(shí)隙內(nèi)有多個(gè)站點(diǎn)想要發(fā)送，就會(huì)產(chǎn)生沖突）。當(dāng)系統(tǒng)載荷很重時(shí)，將位時(shí)隙0指定給節(jié)點(diǎn)1幾乎沒(méi)什么價(jià)值。因?yàn)橹挥挟?dāng)僅有一站點(diǎn)想要發(fā)送幀時(shí)這樣做才有意義，類似地，人們可

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