p2p網絡中基于動態(tài)our算法的負載均衡技術

p2p網絡中基于動態(tài)our算法的負載均衡技術

1結構與非結構化p2p系統(tǒng)p2p系統(tǒng)越來越多地用于數據處理、資源交換、信息管理、共享等領域。然而，隨著問題的普及，這種負荷補償也出現了。節(jié)點之間如何均勻組織負載？系統(tǒng)性能的質量取決于問題的答案。由于不平衡，p2p系統(tǒng)帶來了許多性能問題，如此期間的延誤。因此，負荷補償已成為p2p系統(tǒng)研究的一個重要問題。一些p2p系統(tǒng)，如燒香、幻燈片和胡同，通過提供一組有序的噪聲補償機制來平衡噪聲，并且在理想的環(huán)境中提供了相同的性能。所有文件都具有相同的訪問頻率，因此生成的節(jié)點是統(tǒng)一的。然而，現實系統(tǒng)是不同的。事實上，由于節(jié)點性能的不同結構和熱點文件的存在，負荷仍然存在。對于一些非結構的p2p系統(tǒng)，如gilla，節(jié)點沒有顯示身份的唯一標識，并且沒有與其他節(jié)點相關的信息。它只能通過網絡上的洪水信息來定位資源，這大大增加了網絡負荷。為了解決這些問題，許多文獻在非結構pm系統(tǒng)的基礎上引入了超級節(jié)點。超級節(jié)點是能力強的節(jié)點，每個超節(jié)點管理著一些普通節(jié)點。這些普通節(jié)點和管理的普通節(jié)點構成一個群體（或組）。每個普通節(jié)點都是唯一的身份標識符，并且每個普通節(jié)點都管理著一些普通節(jié)點。超級節(jié)點和他們管理的普通節(jié)點構成一個群體（或組）。每個普通節(jié)點都有一個唯一的身份標識符，并且希望向組織中的超節(jié)點提供信息。通過定期溝通，超節(jié)點之間交換彼此的信息。本文提出了兩種通過副本策略處理負載平衡的技術:周期性的副本策略(PeriodicReplicationPolicy,簡稱PRP)和基于需求的副本策略(Demand-basedReplicationPolicy,簡稱DRP).在PRP中,超節(jié)點周期性地傳遞那些全局被訪問頻率高的文件副本到遠程的超節(jié)點,從而降低了搜索文件的跳數.當一個超節(jié)點收到一個文件副本時,它會在一定范圍內通知它的鄰居超節(jié)點.與PRP不同,DRP是基于當地的訪問頻率的,而不是像PRP那樣從全局來考慮的.如果一個超節(jié)點所在組對某個文件的訪問頻率超過了一定的值,那么這個超節(jié)點將會保留這個文件副本在本組內.2理想的副本策略近來已經有很多文獻提出了P2P環(huán)境下的副本策略,如文獻.它們主要討論的副本策略如下:·統(tǒng)一分配策略:在P2P網絡中,所有的文件的副本數目都是相同的.·正比策略:每個文件的副本數目與它被查詢的概率成正比關系.·平方根策略:每個文件的副本數目與它被查詢的概率的平方根成正比關系.統(tǒng)一分配策略沒有考慮文件流行程度,對于熱門文件來說,系統(tǒng)中存儲的副本數可能并不能滿足查詢的需求,容易造成瓶頸問題.而對于訪問量比較少的文件來說,它們副本的利用率很低,浪費了存儲空間.正比策略和平方根策略考慮了文件流行度的差別,使得副本的利用率得到了提高,但是為了存儲流行度的相關信息,每個節(jié)點的負擔大大加重了.在P2P網絡中,負載平衡是衡量其性能的一個重要因素,越來越多的文獻,如針對這個方面進行了研究.提出了一種通過副本策略來達到負載平衡的策略.它通過文件的流行程度來確定副本數目,并且通過定義多個哈希函數來使得每個副本被訪問的頻率盡量接近,從而達到負載平衡.但是因為它引入了多個哈希函數,在選擇副本的時候就要付出更多的代價.3副策略本節(jié)主要來討論副本策略的兩種算法的實現策略—周期性的副本策略和基于需求的副本策略.3.1周期流特征在文件副本策略下的展現在周期性的副本策略里,每個超節(jié)點都保存著該組里所有文件被訪問頻率的信息.如果一個文件被訪問的頻率超過了某一個預先定義的值,那么該文件的一個副本就會被拷貝到一個訪問此文件頻率最高的超節(jié)點所在的組內.當這個超節(jié)點接收到文件副本后,它將根據當前組內節(jié)點的空間剩余情況,選擇一個剩余存儲空間最大的普通節(jié)點來存儲該文件副本,然后通知它的鄰居節(jié)點這個文件副本所在地的信息.為了減輕網絡的負擔,它只通知一定范圍內的鄰居超節(jié)點.在這種副本策略里,超節(jié)點之間需要周期性地更新彼此的信息,如圖1所示.圖1顯示了周期性副本策略的操作過程.超節(jié)點SP1,SP5等請求某個文件i,假定該文件在超節(jié)點SP6所在組內命中,SP6將檢查該文件i的訪問頻率是否超過了預先定義的閾值,如果檢測到文件i的訪問頻率高于這個閾值,那么SP6將拷貝一個副本發(fā)送給訪問文件i頻率最高的超節(jié)點(這里我們假定SP1訪問文件i的頻率最高).SP1收到這個文件副本后,將把該文件副本保存在本組內剩余空間最多的普通節(jié)點Pi上,并在一定范圍內通知其鄰居超節(jié)點.3.2基于需求副本策略在基于需求的副本策略里,每個超節(jié)點都記錄著本組內所有普通節(jié)點對每個文件的訪問頻率信息.當一個普通節(jié)點發(fā)送對某個文件F的請求到它所在組內的超節(jié)點SPi時,SPi首先檢查一下本組內對該文件的請求頻率是否已經超過了一個預先定義的值,如果超過了,SPi將發(fā)送一個副本請求到該文件所在組內的超節(jié)點SPj.SPj接收到請求后就會把文件副本發(fā)給SPi,SPi收到文件副本后,將把該副本保存在本組內剩余空間最多的普通節(jié)點上,并通知自己的鄰居節(jié)點.當然,為了節(jié)省網絡代價,它也只通知一定范圍內的鄰居超節(jié)點,如圖2所示.圖2顯示了基于需求的副本策略的操作過程.超節(jié)點SP1檢查到本組內頻繁的發(fā)送對文件i的請求,并且其頻率已經超過事先定義的閾值,假定該文件在SP6所在組內命中,那么SP1將給SP6發(fā)送對文件i副本的請求.SP6收到請求后就會把文件i的副本發(fā)給SP1.SP1收到文件副本后,將把該文件副本保存在本組內剩余空間最多的普通節(jié)點Pi上,并在一定范圍內通知其鄰居超節(jié)點.4獲取文件的概率在這節(jié),我們將分析上面提出的兩種副本策略的平均訪問代價和副本負載大小.首先我們來看一下它們的平均訪問代價.在這里我們把命中分為兩種,一種是本地命中(節(jié)點請求的文件在它所在組內命中),另一種是遠程命中(節(jié)點請求的文件在其他組內命中).每個請求的平均代價計算如下:AvgCost=P(local)*LocalCost+P(remote)*RemoteCost(1)其中P(local)表示請求被本地命中的概率,P(remote)表示請求被遠程命中的概率,LocalCost是從組內取得文件所需的代價,RemoteCost是從其它組內取得文件所需的代價.P(local)和P(remote)之和為1,并且它們的值能通過查詢請求的分布被計算出來.一般文件共享系統(tǒng)中,文件的請求服從Zipf分布,那么文件i被訪問的概率如下式:P(i)=1∑x=1D1x*1i(DΡ(i)=1∑x=1D1x*1i(D為系統(tǒng)中不相同文件的數目)(2)P(local)=∑i=1mP(i)(mΡ(local)=∑i=1mΡ(i)(m為本地不同文件的數目)(3)P(remote)+P(local)=1(4)4.1節(jié)點平均網絡地理位置在PRP方法中,超節(jié)點根據組內文件的全局訪問頻率來決定是否發(fā)送文件副本到其他發(fā)送請求的超節(jié)點.我們用λ來表示一個預先定義好的閾值,當文件的訪問次數超過這個值的時候,一個文件副本將會發(fā)送給某個訪問此文件頻率最高的超節(jié)點.一個文件i被訪問的頻率在公式(2)中已經定義了.我們定義每個普通節(jié)點發(fā)出查詢請求的頻率為Q,超節(jié)點的數目為N,每個超節(jié)點平均和k個普通節(jié)點連接,在一個周期t內,請求文件i被請求的次數可以計算為:NumberAccess(i)=t*N*k*Q*P(i)(5)P(NumberAccess(i)>λ)表示文件i被訪問的次數高于預先定義的值λ的概率,那么在一段時間T內產生的平均副本數量為:NumberReplica?PRP=Tt*∑i=1D(P(NumberAccess(i)＞λ))(6)ΝumberReplica-ΡRΡ=Τt*∑i=1D(Ρ(ΝumberAccess(i)＞λ))(6)副本的負載代價為:Overhead-PRP=NumberReplica-PRP*AverageHops*TransferCost(7)AverageHops表示副本在超節(jié)點間傳輸過程中平均經過的跳數,TransferCost表示每跳的傳輸所需要的代價.4.2生成的副本數量及負載代價在DRP方法中,超節(jié)點Si根據組內對文件i請求的情況來決定是否需要請求拷貝副本到本組內.如果組內對文件i的請求超過了預先定義的閾值θ,那么Si就會發(fā)送副本請求到擁有該文件i的超節(jié)點Sj.在一段時間T內,每組對文件i發(fā)出請求的次數可以計算為:NumberAccess(i)=T*k*Q*P(i)(8)P(NumberAccess(i)>θ)表示文件i被訪問的次數高于預先定義的值θ的概率,那么在時間T內產生的副本數量為:NumberReplica?PRP=N*∑i=1D(P(NumberAccess(i)＞θ))(9)ΝumberReplica-ΡRΡ=Ν*∑i=1D(Ρ(ΝumberAccess(i)＞θ))(9)副本的負載代價為:Overhead-DRP=NumberReplica-DRP*AverageHops*TransferCost(10)5性能評價這節(jié)將通過模擬實驗來驗證我們提出的副本策略的有效性,實驗參數如表1所示.5.1spsize對平均跳數的影響由第4節(jié)的分析,可以得知在網絡結構一定的情況下,影響PRP性能的重要參數是周期t,閾值λ,超節(jié)點緩存大小SPSize,而評價PRP性能好壞的標準就是副本負載及獲得查詢結果需要的平均跳數AverageHops.因此在本小節(jié)我們將通過實驗分析這些參數之間的關系.表2顯示了PRP方法中,在其它值固定(取表1中的值)的情況下,平均跳數AverageHops隨閾值λ變化而變化的情況.從表中我們可以得知,隨著λ值的增大,AverageHops并沒有太明顯的變化.這是因為節(jié)點發(fā)出的請求服從Zipf分布,一般請求偏向于比較熱門的文件,而這些文件的訪問量很快可以達到預定的λ值,所以隨著λ值的增加,AverageHops的值并沒有明顯的變化,而只是略微有點升高的趨勢.表3顯示了PRP方法中,在其它值固定(取表1中的值)的情況下,平均跳數AverageHops隨周期t變化而變化的情況.隨著t從1增加到4分鐘時,平均跳數有明顯的減少,而當它從4增加到6時,平均跳數又開始了慢幅度的增加,這是因為如果t過小,則在一個周期內的請求數也相對比較少,很多相對熱門的文件的訪問量也沒有達到預先定義的閾值λ,因此產生的副本數就很少,平均跳數也就比較高了.我們可以看到,當t=1時,平均跳數接近8,這和沒有采用副本策略的情況下的跳數幾乎差不多.而當t過大時,一個周期內產生的副本并不會有明顯的增加,反而在一定的時間T內產生的副本數會略微下降.表4顯示了PRP方法中,在其它值固定(取表1中的值)的情況下,平均跳數AverageHops隨SPSize變化而變化的情況.隨著SPSize的增加,其存儲能力越強,能夠存儲的副本數越多,當然平均跳數也就會下降了.當超節(jié)點的緩存大小從1MB升到2MB時,平均跳數有著明顯的降低,繼續(xù)上升到3MB時,上升的趨勢有所減退,繼續(xù)增加SPSize時,平均跳數幾乎保持不變了.5.2drp過程中平均跳數隨超節(jié)點緩沖溶液的變化表5顯示了DRP方法中,平均跳數AverageHops隨閾值θ變化而變化的情況.顯然,隨著θ的增加,AverageHops的值會越來越大,當θ達到30以上時,AverageHops的值幾乎不再發(fā)生變化,并且接近沒有采用副本策略情況下的平均跳數值.當然,如果θ的值越小,AverageHops的值就會越小,但是整個系統(tǒng)中的副本負載就會加重.表6顯示了DRP方法中,平均跳數隨著超節(jié)點緩存大小SPSize變化而變化的情況.從圖中,我們可以看到,隨著緩存的增加,平均跳數并沒有明顯的下降趨勢.這