基于位置信息的非結構化ｏｖｅｒｌａｙ匹配方法研究
2008-12-31 00:00:00黃金強彭宇行
計算機應用研究 2008年9期
摘 要：在非結構化overlay中，由于底層物理網絡和overlay的拓撲失配問題，產生了大量冗余網絡負載。為了降低負載，提出了基于位置信息的方法動態構造overlay。通過分布部署用于維護已加入網絡的節點信息的infoNode，在不引入較大冗余網絡負載的情況下，能夠較好地解決拓撲失配問題。實驗表明，基于網絡測量的方法能顯著降低網絡負載和查詢響應時間。
關鍵詞：非結構化overlay； 位置信息； 拓撲失配
中圖分類號：TP393 文獻標志碼：A
文章編號：10013695(2008)09279004
Unstructured overlay construction method based on location information
HUANG Jinqiang， PENG Yuxing
(National key Laboratory for Parallel Distributed Processing， School of Computer， National University of Defense Technology， Changsha 410073， China)
Abstract:In unstructured overlay， a large amount of redundant network traffic is generated because the problem of topology mismatching between physical network and overlay network. In order to alleviate the effect of topology mismatching， this paper proposed a method about unstructured overlay construction method based on location information. With disposing the infoNodes， which maintained information of peers joined network， the topology mismatching problem was handled effectively without caused a large volume of redundant traffic. The simulation shows the proposed method can reduce the network traffic and query response time effectively.
Key words：unstructured overlay; location information; topology mismatch
0 引言
在P2P系統中，overlay網絡是由節點相互連接，構建于底層物理網絡之上的一個抽象的應用層網絡。根據構建方式的不同，overlay網絡拓撲可以分為非結構化與結構化兩種[1]。在非結構化overlay網絡中，Gnutella和KaZaA網絡為典型代表。在這類網絡中，當一個節點P要加入到該網絡時，它首先聯系引導節點（bootstrapping node），引導節點隨機選取并返回給此節點P一組已經加入到該網絡的節點IP地址；然后節點P主動與這些節點連接，如果連接成功，則被連接節點成為節點P的鄰居節點。由于節點隨機加入到系統中，忽略了底層物理網絡拓撲結構，使得構造的overlay網絡拓撲與底層的物理網絡拓撲存在著較大的差異，這帶來了較大的網絡延時和網絡冗余負載的問題。
為了減少因為拓撲失配帶來的問題，本文提出了基于位置信息的非結構化overlay匹配方法。與以往類似的工作不同在于，本文不僅僅考慮節點的地理位置，而且還考慮按照網絡服務提供商的IP分配段來作為劃分節點所屬地理范圍的基本單位。通過引入廣域與域的定義，能夠保證節點不僅優先選擇在地理位置上它所鄰近的，同時還是延時較小的節點作為其鄰居節點，這樣就可以構造出一個整體上與地理位置盡量匹配的overlay網絡，從而達到降低系統的網絡延時、提高網絡利用率的目的。
1 相關工作
為解決拓撲失配問題，目前提出的方法主要有兩類。第一類是將網絡延時作為衡量網絡節點之間的距離進行網絡優化。主要包括自適應的連接建立方法(adaptive connection establishment，ACE)[2]、基于2hop鄰居比較與選擇的overlay優化方法(two hop away neighbor comparison and selection，THANCS)[3]以及基于位置信息的拓撲失配解決方法（locationaware topology matching，LTM）[4]。第二類方法主要是通過IP地址來定位節點的物理位置。主要包括IP2Geo[5]和基于IP地址分配表定位地理位置的方法[6]。
ACE算法核心思想是在overlay網絡中的每個節點都要獲得與其鄰居節點的通信延時，并建立通信代價表。根據此通信代價表，節點建立一棵與鄰居節點通信代價的最小生成樹，然后去掉多余連接，這樣節點與鄰居節點就能以最小的通信代價進行通信。但是當網絡規模比較大時，節點如果僅獲取相鄰節點的通信代價并產生最小生成樹時，僅能保證相鄰節點的通信代價最小，并不能保證不相鄰節點通信的代價最小。為解決這個問題，ACE提出了N跳優化，即節點獲取與它具有N跳以內的節點通信代價表，然后進行優化，這樣就能獲得更大的范圍內局部最優。實驗表明，四跳優化比一跳優化能降低30%的網絡負載，大于四跳時優化效果不明顯。ACE方法在不影響目標搜索效率的前提下，使類Gnutella系統中的通信開銷下降了65%。
THANCS算法是系統內每個節點都收集自己兩跳以內的鄰居信息，它同樣是以節點之間的網絡延時作為衡量節點之間的距離。延時越大，距離越遠；反之，距離越近。THANCS算法使用自定義的Piggy消息協議來獲取網絡延時，使用基于PPB（pure probabilitybased）[3]和NNT（new neighbor triggered）[3]算法作為兩跳鄰居節點的比較與選擇算法。實驗表明，經過THANCS的優化，random walk[7]和index caching[8]這兩種搜索策略的響應時間和通信代價都有了明顯的降低。
LTM算法同樣也是利用基于節點間的延時來作為評價節點之間的相對位置。在LTM算法中定義了三個步驟:探測消息泛洪、去掉延時大的連接以及源節點探測。對網絡的任一節點，為了獲取到各節點的延時，LTM算法中采用了自定義的TTL2Detector消息協議。節點通過向周圍節點泛洪發送TTL2Detector消息來獲取到各節點的延時。由于在泛洪過程中，從一個節點到某一個節點可能有不同的路徑到達，就需要把網絡延時大的連接斷掉以達到優化的目的。源節點的探測是從目的節點反方向獲取到源節點的延時最小的路徑。
上述三種方法都是以網絡延時作為衡量網絡節點之間的距離而進行網絡優化，它們都是以獲取節點之間的通信代價為基礎的。這既要較長的時間來獲取節點間的網絡延時，又要花費較大的網絡開銷。在網絡動態變化時，很難在獲取通信代價的及時性和降低通信代價所需開銷之間作出很好的折中。
依靠IP地址來推測節點的地理位置，目前具有代表性的方法是IP2Geo。IP2Geo技術包含三種不同的技術，即GeoTrack、GeoPing和GeoCluster。GeoTrack是依靠DNS來推測主機所在的地理位置。它首先探測到目的主機的路由。由于有些路由節點具有DNS域名，如某個路由器為corerouter1.SanFrancisco. cw.net，那么可以推測到此路由位于SanFrancisco。當路由的DNS采用其所在地的機場編碼作為DNS域名，也可以用類似的方法推測。GeoPing是使用節點之間的延時來衡量節點之間的距離，從而推測節點的地理位置。第一類優化方法中以延時作為衡量節點之間的距離關系就是以GeoPing方法為基礎的。GeoCluster是依靠先獲取部分節點與地理位置的對應映射關系以及BGP前綴信息來判斷節點所在地理位置。GeoCluster分別利用Hotmail、bCentral 以及FooTV網站獲取用戶的IP與地理位置映射關系。例如Hotmail里有一部分用戶是注冊了他們的地理位置，同時根據網站訪問的日志來獲取用戶的IP，這樣就可以把用戶地理位置與IP地址對應起來。在bCentral 以及FooTV 網站上獲取IP與地理位置映射關系的方法與利用Hotmail獲取IP與地理位置映射關系的方法類似。 IP2Geo的這三種技術各有利弊，如GeoTrack用路由器的域名推測其目的主機的地理位置，但是有些路由器并不使用域名，而僅僅是IP地址；或者有些路由器域名的意義并不直觀，那么有時可能推測不出目的主機的地理位置，或者推測的信息不夠準確。GeoTrack首先獲取節點與地理位置關系，但使用BGP前綴來推測主機的位置往往覆蓋面過大，致使推測的范圍并不準確。這限制了在P2P系統中的應用。
基于IP地址定位地理位置的方法主要依靠互聯網地址指派機構(Internet Assigned Aumbers Authority，IANA)以及五個地區級的Internet注冊機構(Regional Internet Registry，RIR)的IP分配表為基礎來判斷節點所在的地理位置。由于IANA以及RIR的IP地址段的范圍很大，致使定位的地理位置不夠精確，同時由于在1999年之前的IP分配全部是由IANA分配，有很多IP段混合使用，致使定位不夠準確。
2 基于位置信息的非結構化overlay拓撲匹配方法
2.1 問題分析
盡管以網絡延時作為衡量網絡節點之間的距離來進行overlay優化以及基于節點地理位置進行overlay優化的目的都是解決overlay的拓撲失配，但是前者所帶來的網絡開銷較大、優化延時過長。比較而言，利用節點地理位置作為解決overlay拓撲失配問題的基礎，其優化的代價較小，更適合于應用。
利用IANA以及RIR分配的IP地址段來定位其節點的位置，缺點是其分配的IP地址段范圍過大，從而造成節點定位不精確。為使定位更為精確，同時優化節點選擇鄰居節點策略，可以將地理位置細化為更小的范圍，在小范圍內節點的地理位置是相近的。目前ISP的IP地址分配原則一般是以地理位置上的某個機構或用戶等小范圍作為分配單位。因此可以將這樣的小范圍作為一個域(location)，域內的節點是地理位置鄰近的且節點之間的通信代價較小。例如，由于大學內部的節點通信延時要比校內節點與校外用戶之間通信延時小得多，可以將某個大學作為一個域。目前的IP分配表可以通過網絡服務提供商獲取，因此本文研究的重點在于如何通過IP分配表來構造overlay，從而解決拓撲失配的問題。
通過IP分配表則可以將IP地址與某個地理位置上的域對應起來，但是僅靠域的地理位置并不能保證域之間連接是地理位置上的相近連接，從而影響拓撲匹配的準確度。為了標示出域之間的地理位置鄰接關系，本文將包含若干個域的地理范圍稱之為廣域（super location，SL）。由于廣域的地理位置相對穩定，廣域之間的連接可以由人工構造。例如長沙市和湘潭市分別是一個廣域，而中南大學和湖南大學都是長沙市里的域。在一個廣域內，為體現域之間的相鄰關系，避免域互包含的問題，應該保證域之間的交集為空。
如圖1所示有兩個廣域，分別為SL_0和SL_1。每個廣域由若干個域組成。這些域相互連接構成了此廣域的overlay，這樣便構成了具有兩層結構的overlay。在SL_1中的location1放大圖里有多個peer相互構成一個在location1里的overlay。其中某一個節點充當維護節點（infoNode），它維護著location1里其他節點的信息。同時，它還與location0與location2里的infoNode連接。location0、location1和location2構成了SL_1的overlay。
2.2 匹配條件
為了使構造的overlay與物理網絡盡量匹配，需要解決域內節點連接關系、域間連接、廣域與域之間的包含關系以及廣域之間的連接關系。為此需要以下關系：
a)IP地址段與地理位置的映射關系：
其中：Ω為IP段，其元素為IP地址；λ為地理位置。
b)廣域與域之間需要滿足以下關系：
其中：Si為一個域；SL為包含Si(i∈{1，2，…，n})的廣域。
c)廣域之間的相鄰關系是以地理位置為依據劃分的，其相互之間的連接關系固定，因此廣域之間的連接關系可以由人工預定義。其廣域之間連接關系可以用一個稀疏矩陣表示：
SL[i][j]=C，C∈{0，1}且i≠j
當C=1時表示SL_i與SL_ j之間相鄰；C=0表示不相鄰。
d)一個域內的infoNode是由其穩定的節點來承擔，域間連接是通過infoNode來實現的，因此需要引入一個infoNode連接關系矩陣：
infoNode[i][j]=C，C∈{0，1}且i≠j
當域內的兩個infoNode連接成功時，則infoNode[i][j]=1；否則infoNode[i][j]=0。
23 匹配方法
為了達到匹配的目的，系統內需要設置兩種特殊的節點，即infoNode和tracker。InfoNode是由一個用來維護其所在域內的已加入節點的信息，其包含節點的IP地址和端口、節點加入時間等信息。InfoNode一般由其所在域內穩定的節點所承擔。Tracker是一個用來維護全局數據的中心服務器，它用來為要加入系統的節點選擇合適的域，維護infoNode之間的連接關系、廣域與域的包含關系以及infoNode的IP地址。
當某節點P要加入到系統時，此節點首先聯系tracker。Tracker獲得此節點的IP地址，并查找包含這個IP的域S；同時將此S中的infoNode的IP地址發送給節點P。節點P主動聯系域S的infoNode。InfoNode返回給節點P一組已經存在于此域的節點IP與端口號。此節點在獲取到節點列表以后，通過Ping這些節點的方式獲取此節點與這些已在網絡里的節點的延時；此節點挑選若干延時較小的節點，主動連接它們。若連接成功，此節點則成為節點P的鄰居節點。節點P加入系統過程如圖2所示。
若節點P與這些節點連接全部失敗，則返回給tracker一個帶有特殊標記(如peerConnectFailed)的消息，tracker重新根據infoNode的連接關系矩陣選取一組與節點P所在的infoNode相鄰的infoNode列表，并返回給節點P；然后節點P重新與這些infoNode主動聯系，并獲取由這些infoNode所維護的一部分節點；節點P主動使用Ping的方式獲取到這些節點的延時，并挑選延時較小的節點主動連接。
當域S沒有節點加入系統，那么節點P便充當該域的infoNode。同時tracker在infoNode表中增加一條記錄，根據廣域與域的包含關系矩陣獲取該節點P周圍的域列表。Tracker通過infoNode與IP的映射關系以及IP地址與地理位置的映射關系獲取一組在節點P周圍的infoNode列表并發送給該節點P。節點P以Ping的方式獲取到這些infoNode的延時，并挑選出一組延時最小的infoNode列表主動連接。若連接成功，則成為節點P(同時也是infoNode)的鄰居infoNode。如果節點P與所有的infoNode全部連接失敗，則返回給tracker一個帶有特殊標記（如infoNodeConnectFailed）的消息;Tracker重新在infoNode表中隨機挑選一組infoNode返回給節點P;然后節點P使用Ping的方式探測這些infoNode，選擇延遲較小的infoNode并主動連接。
綜上所述，可以得到節點P加入系統是構造overlay的算法如下：
a)節點P主動聯系tracker；
b)Tracker獲取節點P的IP，并判定其IP所屬的域；
c)若域中有已加入節點，則轉d)；否則，轉i)；
d)Tracker將該域的infoNode發送給節點P；
e)節點P主動聯系infoNode；
f)InfoNode選取并返回給節點P一組它所維護的已經加入系統的節點IP與端口號；
g)節點P主動與列表中節點連接；若有連接成功的鄰居節點，則結束；否則轉h)；
h)節點返回給infoNode連接失敗的信息；infoNode返回給節點它所相連的鄰居infoNode并返回給節點P，轉e)；
i)Tracker將節點P設定為其所屬域的infoNode并在infoNode表中增加一條對應的記錄；
j)Tracker根據域的連接關系矩陣，返回給節點P一組相鄰域的infoNode的IP地址與端口；
k)節點P主動與這些infoNode相連接；若有連接成功的infoNode則結束；否則轉l)；
l)節點P向tracker發送連接infoNode出錯信息；Tracker重新隨機挑選一組infoNode返回給節點P；
m)節點P探測到這些infoNode的延時并主動連接若干延時小的infoNode。轉k)。
24 實驗
BRITE[9]是一個被廣泛使用的通用拓撲產生器，它能夠產生AS級和路由器級的具備SmallWorld特征并且節點度符合冪律分布的拓撲結構。本實驗中利用BRITE產生具有兩層拓撲網絡，上層是AS層，下層是包含在AS中的路由器層。兩層結構都采用Waxman模型，節點數為5 000。由于本文構造的是具有兩層結構的overlay，實驗中用AS層來模擬廣域層，用路由器層來模擬域層。在實驗中使用了以下幾種數據結構。
由于在節點加入時要判斷它的地理位置，需要一個IP段與域對照表（IP對照表數據庫可從http://ip.loveroot.com下載），如表1所示。此表的每一行startIP與endIP分別是某一個IP段的起始地址和結束地址。LocationID為此IP段對應的地理位置上的域。如果startIP與endIP相同，表明此域中可能由一個或多個節點使用同一個IP。在這種情況下，應通過網絡地址轉換后的端口號來區分節點。
為了得到域屬于哪一個廣域，需要有一個域與廣域的包含表（表2）。
由于不同廣域之間的連接應該是地理位置上相鄰廣域之間的相互連接，還需要一個廣域互連表（表3）。由于域間的地理位置關系有相對穩定的特征，表2、3可以在初始化時由人工設定。系統運行不改變其值。InfoNode需要與其他若干個域中的infoNode相連接，所以tracker需要維護一個infoNode的ID矩陣（表4）。除此之外，還需要一個infoNode的IP表（表5），用來獲取infoNode的地理位置。
實驗中分別用有代表性的三種算法作對比實驗，即基于網絡延時構造通信代價最小生成樹的ACE算法(ACE)、基于位置信息的overlay構造方法(Location)和基于隨機選取節點的overlay構造方法(Rand)。對應“AVG”前綴的代表相應算法的平均值。
在實驗中，首先讀取BRITE產生的物理拓撲網絡文件，產生一個隨機化的初始網絡。模擬隨著時鐘推進、節點的動態加入與退出，分別按照Rand、Location和ACE算法構造overlay網絡。在時鐘推進的過程中，隨機抽取50對任意兩個節點之間的網絡延時。其結果如圖3所示。從圖中可以看出，由于Rand算法沒有考慮物理網絡與構造overlay網絡的匹配問題，致使網絡延時較大；而基于Location算法盡管考慮到了物理網絡的匹配與構造overlay網絡的匹配，廣域之間并不能保證節點間的延時總是最小。相對應地，ACE算法由于利用鄰居節點之間的網絡延時作為優化基礎，在網絡延時方面ACE最小，平均值為23.2 ms；Location次之，平均值為25 ms；而Rand算法最差，其平均值達到45.6 ms。
當節點加入系統時，不同的算法帶來的overlay調整耗費不同。ACE的節點要與它相鄰的節點交換網絡延時表，構造通信代價表的最小生成樹，以達到降低網絡延時的目的。在獲取通信代價表時，僅僅獲取一跳之內的鄰居網絡延時往往不能有很好的優化效果，所以ACE算法一般是通過獲取N跳以內的鄰居通信代價表來優化通信延時的最小生成樹。但是跳數越多，其探測的范圍就越大，網絡冗余負載就越大。實驗[2]表明，超過四跳以后，優化的效果并不顯著。由于Rand算法是隨機加入到系統中，調整的次數較少。而Location算法是以加入節點的主動測量為基礎的，不需要infoNode采用泛洪的方式來進行網絡測量，因此調整的次數相對較少。
在本實驗中用調整節點連接的次數來衡量調整耗費。實驗中，隨機抽取50個時間點，統計在這些時間點節點加入系統時調整overlay內節點的連接次數。ACE設定的優化深度是2。實驗結果如圖4所示。從圖中可以看出，使用Rand算法時，當有節點加入系統時，系統要不斷調整網絡中節點之間的連接以滿足在優化深度范圍內的通信代價是最小的，所以調整的次數較多，意味著網絡的通信負載就越大。由于使用Location算法加入節點僅僅需要與tracker通信以及加入域時測量到若干個節點的延時值，網絡調整代價較小。Rand算法與Location類似。
在非結構化overlay中，由于拓撲失配問題的存在，查詢會產生大量冗余的網絡通信和查詢延時較大的問題。本實驗中分別用ACE、Location和Rand算法產生的overlay網絡模擬查詢操作。隨機選取50次節點的查詢，統計網絡的響應時間。實驗結果如圖5所示。從圖中看以看到，通信的平均延時從高到低依次為Rand、ACE和Location。其中ACE與Location之間的平均延時相差約2.4 ms。ACE從網絡延時上來看是最優的，但是由于P2P系統有很大動態性，在節點加入時就會因構建新的鄰居節點通信代價表而帶來很大的網絡調整負載。從圖3~5對比來看，基于位置信息來構造overlay的方法在減少網絡冗余負載、降低查詢響應時間方面是最好的。
3 結束語
本文針對現有的解決overlay拓撲失配問題方法的不足，提出了利用IP分配表來定位其地理位置，并構造出具有兩層結構的overlay，從而達到overlay網絡與物理網絡相匹配的目的。由于節點加入后要選擇的鄰居節點是由tracker根據節點的地理位置來選擇鄰近的節點，節點選擇鄰居節點以及優化連接所帶來的調整耗費較小，從而產生的網絡冗余負載較小。通過實驗比較可以看出，基于位置信息構造overlay的方法綜合來看效果最好。
參考文獻：
［1］LUA E K， CROWCROFT J，PIASM，et al. A survey and comparison of peertopeer overlay network schemes [J].IEEE Communications Survey and Tutorial，2005，7(2):7293.
[2]XIAO Li， LIU Yunhao， NI L M. Improving unstructured peertopeer systems by adaptive connection establishment[J].IEEE Trans on Computers，2005，54(9):10911103.
[3]LIU Yunhao， XIAO Li，ESFAHANIAN A H， et al. Approaching optimal peertopeer overlays[C]//Proc ofthe 13th Annual Meeting of IEEE MASCOTS 2005. 2005.
[4]LIU Yunhao，XIAO Li， LIU Xiaomei，et al. Location awareness in unstructured peertopeer systems[J].IEEE Trans on Parallel and Distributed Systems，2005，16(2):163174.
[5]VENKATA， PADM， LAKSHM S. An investigation of geographic mapping techniques for Internet hosts[C]//Proc of ACM SIGCOMM’01.2001.
[6]ZHAO Jia， LU Jiande. Solving overlay mismatching of unstructured P2P networks using physical locality information[C]//Proc of the 6th IEEE International Conference on PeertoPeer Computing. 2006.
[7]LV Qin， CAO Pei， EDITH C， et al. Search and replication in unstructured peertopeer networks[C]//Proc of the 16th International Conference on Supercomputing.2002:8495.
[8]SRIP K. The popularity of Gnutella queries and its implications on scalability[EB/OL]. (200112) [20070810].http://www.cs.cmu.edu/kunwadee/research/p2p/gnutella.html.
[9][EB/OL].http://www.cs.bu.edu/brite/
