一種無標(biāo)度網(wǎng)絡(luò)上的局部路由策略
加入技術(shù)交流群
2 路由方法分析
考察scale-free網(wǎng)絡(luò)路由策略性能的最主要指標(biāo)是網(wǎng)絡(luò)容量，通常用網(wǎng)絡(luò)不擁塞時可以達(dá)到的最大信息包產(chǎn)生速率Rc(又稱臨界速率)來衡量。
在任一信息包產(chǎn)生速率下，如果只是每次進(jìn)入部分節(jié)點(diǎn)的信息包隊(duì)列長度超過了節(jié)點(diǎn)發(fā)送能力，使信息包堆積，導(dǎo)致了擁塞的發(fā)生(后文稱之為節(jié)點(diǎn)過飽和)，那么只需把這部分業(yè)務(wù)轉(zhuǎn)移到尚未飽和的節(jié)點(diǎn)中去，就可以緩解這種局部負(fù)載過重帶來的擁塞，并且可以進(jìn)一步擴(kuò)大產(chǎn)生速率。只有當(dāng)全部節(jié)點(diǎn)均達(dá)到了飽和，整個網(wǎng)絡(luò)擁塞的發(fā)生才是無可避免的。所以目的就是避免局部節(jié)點(diǎn)擁堵帶來網(wǎng)絡(luò)擁塞，盡量提高網(wǎng)絡(luò)容量，最后全部節(jié)點(diǎn)可以同步地達(dá)到飽和狀態(tài)。
設(shè)定節(jié)點(diǎn)發(fā)送能力等于其連接度，首先使度大節(jié)點(diǎn)有較大的偏好概率，以大業(yè)務(wù)流進(jìn)入速率把負(fù)載優(yōu)先分配給度大的節(jié)點(diǎn)進(jìn)行存儲轉(zhuǎn)發(fā)，搜索目的地；當(dāng)度大節(jié)點(diǎn)的負(fù)載等于甚至超過發(fā)送能力(后文稱之為飽和)后，自適應(yīng)地調(diào)整其信息進(jìn)入速率，把業(yè)務(wù)向尚未飽和的度較小的節(jié)點(diǎn)轉(zhuǎn)移，避免度大的節(jié)點(diǎn)過早進(jìn)入擁塞狀態(tài)。
注意到在本策略定義的自適應(yīng)傳輸機(jī)制下，l(ki)的長度從0開始逐漸增長，當(dāng)l(ki)≤ki時，每次發(fā)送完成后不會有信息包在節(jié)點(diǎn)內(nèi)滯留，所以節(jié)點(diǎn)處于未飽和平穩(wěn)狀態(tài)；反之，若l(ki)>ki，信息包會不斷在節(jié)點(diǎn)堆積，節(jié)點(diǎn)就處在過飽和擁塞狀態(tài)。所以稱l(k)=k為節(jié)點(diǎn)未飽和與過飽和的相分界線。
在自適應(yīng)策略下，選取任何非負(fù)的偏好因子上限amax都能得到相同的最大網(wǎng)絡(luò)容量Rc_max。這是因?yàn)樽赃m應(yīng)策略根據(jù)節(jié)點(diǎn)的負(fù)載與發(fā)送能力的關(guān)系不斷變化偏好因子ai，進(jìn)而調(diào)整信息流的進(jìn)入速率，不斷向未飽和的節(jié)點(diǎn)分流信息包，從而使信息包不會在飽和節(jié)點(diǎn)處不斷積累增加，避免節(jié)點(diǎn)達(dá)到過飽和造成全局擁塞。未飽和節(jié)點(diǎn)，由于隊(duì)列長度一直滿足l(ki)≤ki，其偏好因子ai均會隨時間不斷增長，直至等于其上限amax，不會減小；達(dá)到相分界線的飽和節(jié)點(diǎn)，其偏好因子不再保持等于上限amax，而是隨負(fù)載的變化波動。在自適應(yīng)調(diào)整偏好因子的反饋?zhàn)饔孟拢柡凸?jié)點(diǎn)的信息包進(jìn)入速率將基本等于發(fā)送能力，即平均隊(duì)列長度穩(wěn)定在相分界線l(ki)=ki上，由于相分界線斜率為1，參考式(1)，得出飽和節(jié)點(diǎn)的偏好因子接近于0。同時考慮到，當(dāng)所有節(jié)點(diǎn)都達(dá)到飽和，偏好因子ai均接近于0時，網(wǎng)絡(luò)達(dá)到最大容量。因此在任何偏好因子的界限amax下，網(wǎng)絡(luò)均有惟一相同的最大容量Rc_max。
圖1反映的是不同發(fā)送速率下，節(jié)點(diǎn)平均隊(duì)列長度的變化情況。圖中粗直線代表的就是相分界線。節(jié)點(diǎn)均未飽和時，反映在圖中就是l(ki)未接觸相分界線，此時l(ki)服從式(1)。隨著R增加，部分節(jié)點(diǎn)接觸相分界線后開始進(jìn)入飽和狀態(tài)，l(ki)也開始分為兩段。度較大的一部分飽和節(jié)點(diǎn)的平均隊(duì)列長度與相分界線完全重合，平均隊(duì)列長度變?yōu)閘(ki)=ki；另一部分節(jié)點(diǎn)未達(dá)到飽和狀態(tài)，平均隊(duì)列長度保持原來的斜率，即
。本文引用地址：http://www.biyoush.com/article/155867.htm
評論