結構化對等網中一種副本概率選擇算法

摘要:結構化P2P系統常采用為熱點文檔創建副本的方法，降低存有熱點文檔節點的負載。從如何高效利用副本的角度出發，提出了一種副本概率選擇算法(PRS)，采用能者多勞的思想，請求數據包以較大的概率轉發到負載輕的副本節點上。讓輕負載節點分擔更多的負載，充分利用了副本分擔負載的能力。模擬實驗表明，該算法在創建副本數相同的情況下，大大降低了丟包數，提高了副本的利用率。

關鍵詞:對等網絡; 分布式哈希表; 負載平衡; 副本選擇

中圖分類號:TP393文獻標志碼:A

文章編號:1001－3695(2008)02－0543－03

結構化P2P系統在對數據文檔的需求均勻的情況下，表現出良好的負載平衡特點。然而實際網絡對數據文檔的需求常常是不均勻的，這就導致很差的負載平衡和大量丟包現象。特別是當對某一數據文檔的需求特別大時，將產生熱點(hotspot)[1]現象。復制頻繁被訪問的數據文檔到其他負載較輕的節點的技術被廣泛的應用，以減輕過載節點的負載和提高系統的性能。

現有的復制策略有:CFS[2]提出的在查詢請求的沿途路徑上的每個節點存放副本，使得熱點數據的副本很快遍布在整個網絡中;文獻[3]提出對稱復制的方法，解決負載平衡和端對端的容錯問題;文獻[4]提出了在非結構化P2P系統中的路徑隨機復制和路徑自適應復制算法，解決平衡負載的問題;文獻[5，6]提出了根據文件的受歡迎程度進行復制的方法;文獻[7]將反饋機制引入到復制文件解決擁塞問題中。文獻[8]提出自適應復制算法(LAR)，負載過高的節點才需要創建副本，它主要從復制的方法上考慮，隨機選擇副本的路由方法，導致不能充分地利用副本節點。

與以上復制策略的側重點不同，由于復制要耗費網絡帶寬，本文主要從副本的利用率角度出發，考慮如何充分地利用副本，以創建最少的副本達到最好的分擔負載的效果。本文提出的副本概率選擇算法，根據不斷反饋更新的副本負載信息，按照負載輕重的比例，從多個副本中，以較大的概率選擇輕負載節點，作為下一跳路由，充分有效地利用輕副本節點的剩余能力。

本文將結合LAR算法，詳細闡述本文提出的副本概率選擇算法，并給出模擬實驗結果及其分析。

1LAR算法概述

本文主要從副本利用率的方面改進LAR算法。下面詳細介紹LAR算法的副本利用部分。

創建了副本后，LAR算法總把最新創建的副本位置信息發散出去。如圖1，節點14由于副本6被訪問得過多，負載過重，繼續在節點15上創建副本6。最新副本位置15將盡可能地發散出去，而不發散位置14。使得更多的請求轉發到節點15，快速地降低節點14的負載。這種方法僅僅根據副本創建時的負載信息作決策，沒有考慮到節點負載的動態變化。當節點15的負載重到需要創建新副本時，節點14上的老副本卻仍處于負載較輕的狀態，導致了一些不必要的副本創建。轉發查詢請求包時，LAR隨機從多個副本中選擇轉發的下一跳。如圖1，節點2發出對存儲在節點9上的文檔A的查詢請求。按照Chord[9]路由協議，節點2應該把請求轉發到節點6。然而節點6負載過重，在節點14和15上創建了副本，那么節點2將在節點14和15中隨機選擇一個，通過它們路由到目標節點9，以降低節點6的負載。這種隨機選擇的方法沒有考慮到副本節點的實際處理能力。當節點15負載較輕，而節點14過載時，節點14#65380;15仍將為節點6分擔相等的負載量。本文考慮到負載的動態變化性，根據副本節點的實際處理能力，提出了副本概率選擇算法，充分有效地利用副本。

圖1LAR算法

2副本概率選擇算法

本文提出了副本概率選擇算法，把副本節點的負載信息作為路由轉發選擇的權重參數，副本負載重，對應的權重低，被選中作為路由的下一跳的概率也就低，即請求總是優先向負載輕的節點轉發。對于結構化P2P系統Chord， 節點的路由表是默認的復制項目。以下討論都是針對路由表的復制。本章首先描述副本概率選擇的方法，然后說明計算概率所需要的副本負載信息的收集和更新算法。

2.1副本概率選擇算法

轉發查詢請求時，節點需要從多個副本路由表項中選擇路由的下一跳，根據副本負載的大小，為每個副本設定一個權重，負載重的權重小，被選中的概率低。這種選擇策略能夠很好地平衡副本節點之間的負載。具體方法如下:

這種選擇算法使得路由的每一跳都能夠以較大的概率選擇負載較輕的節點。負載輕的節點處理的請求多，而負載重的節點處理的請求少，從而充分地利用了副本節點分擔負載的能力。副本負載信息是不斷更新的，其權重也隨著它的更新而變化，所以該方法具有一定的自適應性。本文采用概率選擇算法，使得副本節點不論負載輕重，均有被選擇的機會，按照副本節點的剩余處理能力來分配負載。假設，總選擇負載最輕的副本節點作為路由的下一跳，那么可能出現很多節點均同時將查詢請求包轉發到該節點，造成該節點負載快速加重。

如圖2，節點4發出對存儲在節點7上的文檔B的查詢請求。由于節點4知道節點6在節點14和15中存有副本，那么根據節點4存儲的副本負載信息算出權重，以較大的概率選擇負載輕的節點14為路由的下一跳。

2.2基于反饋的副本信息的收集和更新算法

每個節點都為它所維護的路由表中的每一個路由表項，記錄相應的副本信息(副本的位置和負載及負載更新的時間)。副本信息的收集和更新是正確計算概率的關鍵。每當創建了新副本或者副本節點的負載發生改變時，要使各個節點存儲的副本信息實時更新，必須發送廣播消息，更新所有相關的副本信息的值。在龐大的P2P系統中，這是一個開銷非常大的過程，這就需要在副本信息實時更新帶來的好處和保證信息的全局一致帶來的巨大開銷間找到一個折中點。由于路由轉發節點的選擇，只存在優化問題，任何一種選擇均不會對查詢請求路由造成致命的影響。基于以上考慮，本文提出了基于反饋的副本信息的收集和更新算法，根據局部可獲得的信息來更新副本信息，不需要耗費太多開銷，副本信息也能夠與真實值比較接近或者保持一致。即使出現了副本信息與真實值不一致的情況，也只對本次路由轉發的決策造成影響，通過訪問反饋更新，副本信息能夠很快地更新為最新值。

具體算法如下:

a)副本創建后，在副本節點到原始節點途中經過的節點上創建相應的副本信息。

b)副本負載信息的訪問反饋更新過程:記錄查詢請求路徑上經過的每個節點的負載，請求成功時，返回一個ACK消息，更新沿途節點的副本負載信息。訪問得越多，反饋的次數就越多，副本負載信息的值就越新，越接近真實負載值。對于未訪問到的副本信息的更新，可以使用c)描述的方法。

c)消息觸發的副本信息隨機更新過程:在消息的發送過程中，每個節點均會隨機選擇兩個副本信息夾帶在消息中發送出去。遇到下一跳節點時，用夾帶的信息進行更新。每個副本負載信息將對應一個負載更新時間的變量，如果夾帶的副本負載信息比節點存儲的要老，那么不進行更新。

如圖2，副本負載信息的創建:節點6在節點14上創建副本，節點14向節點6返回一個ACK消息，讓節點6記錄副本信息14。副本負載信息的消息觸發更新:節點7查詢請求節點4上的數據，請求路徑為(7，15，3，4)。消息轉發到節點15時，夾帶上節點6對應的副本信息14#65380;15。由于節點4的路由表中有表項6，當消息發送到節點4時，在它的路由表項6中添加對應的副本信息:節點14#65380;15中存有路由表項6的副本。副本負載信息的反饋更新過程:節點4查詢請求節點15上的數據，請求路徑為(4，12，14，15)。請求成功后，返回一個ACK消息，更新沿途路徑上存儲的副本負載信息。節點4中14#65380;15的L值和節點14中15的L值被更新。

3實驗結果及分析

模擬實驗使用MIT提供的Chord模擬器[10]。在模擬實驗中，輸入的請求非常不均勻，90%的請求查詢1%的數據文檔，而剩下10%的請求查詢99%的數據文檔。消息產生設定的參數如表1#65380;2所示。

4結束語

本文提出了一種副本概率選擇算法(PRS)，該方法根據節點負載的輕重設定權重。在選擇下一跳路由時，負載重的節點被選中的概率小，負載輕的節點被選中的概率大。節點存儲的負載信息，通過消息觸發和反饋的方式不斷地更新，從而選擇的概率也隨著負載信息的變化而不斷改變。因此該方法有一定的自適應性，能夠根據節點的負載狀況調整路由，使得創建的副本能夠得到最充分的利用。模擬實驗中，在復制開銷差不多的條件下，總丟包數得到了明顯的改善，證明該算法確實能夠充分有效地利用副本。

參考文獻:

[1]STADING T， MANIATIS P， BAKER M. Peer－to－peer caching schemes to address flash crowds[C]//Proc for the 1st International Workshop on Peer－to－Peer Systems. Cambridge:[s.n.]，2002:203－213.

[2]DABEK F， KAASHOEK M F， KARGER D， et al. Wide－area co－operative storage with CFS[C]//Proc of the 18th ACM Symposium on Operating Systems Principles. New York:ACM Press，2002: 202－215.

[3]GHODSI A， ALIMA L O， HARIDI S. Symmetric replication for structured peer－to－peer systems[C]//Proc of the 3rd International Workshop on Databases， Information Systems and Peer－to－Peer Computing. Trondheim， Norway:[s.n.]， 2005.

[4]YAMAMOTO H，MARUTA D， OIE Y. Replication methods for load balancing on distributed storages in P2P networks[C]//Proc of Symposium on Applications and the Internet. Washington DC:IEEE Computer Society， 2005: 264－271.

[5]NOGAMI S，UCHIDA M， ABE T. Replication scheme for traffic load balancing and its parameter tuning in pure P2P communication[C]//Proc of IEEE Autonomous Decentralized Systems. Japan: IEEE Computer Society， 2005:701－706.

[6]TEWARI S， KLEINROCK L. Proportional replication in peer－to－peer networks[C]//Proc of IEEE INFOCOM.2006.

[7]BOSNEAG A，XI M Y，LIX.Adaptive congestion control for hotspot management in structured peer－to－peer systems[C]//Proc of the 4th IEEE/ACM International Symposium on Cluster Computing and the Grid.Chicago，Illinois:IEEE Computer Society，2004:82－89.

[8]GOPALAKRISHNAN V， SILAGHI B， BHATTACHARJEE B， et al. Adaptive replication in peer－to－peer systems[C]//Proc of the 24th International Conference on Distributed Computing Systems. Japan: IEEE Computer Society， 2004: 360－369.

[9]STOICA I，MORRIS R，LIBEN－NOWELL，et al.Chord:a scalable peer－to－peer lookup protocol for Internet applications[C]//Proc of ACM SIGCOMM Conference.New York:ACM Press，2001:149－160.

[10]The Chord project [EB/OL].(2006－08－16).http://www.pdos.lcs.mit.edu/ chord.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”