保證服務(wù)質(zhì)量的P2P目標(biāo)節(jié)點(diǎn)路由算法

陳園園 張利紅

摘 要：在深入研究P2P覆蓋網(wǎng)拓?fù)渖煞椒ǖ幕A(chǔ)上，結(jié)合P2P流媒體點(diǎn)播服務(wù)的實(shí)際情況，設(shè)計(jì)了一種基于超級節(jié)點(diǎn)的目標(biāo)節(jié)點(diǎn)路由算法。該算法比一般的P2P路由算法速度更快，通常只需2至3跳路由查詢即可定位到資源節(jié)點(diǎn)。

關(guān)鍵詞：P2P；服務(wù)質(zhì)量；路由算法

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-2163（2015）05-

Target Node Routing Algorithm in P2P based on the Quality of Service

CHEN Yuanyuan， ZHANG Lihong

（School of Physics and Electromechnical Engineering，Zhoukou Normal University， Zhoukou Henan 466001， China）

Abstract： On the basis of in-depth study of P2P overlay network topology generation method， combined with the P2P streaming media on-demand services to the actual situation， the paper presents the design of the destination node routing algorithm based on super nodes. The algorithm than the average P2P routing algorithm is faster， which usually only 2-3 hop routing queries could locate the resource nodes.

Keywords： P2P； QOS； Routing Algorithm

1 路由查詢機(jī)制

P2P（Peer-to-Peer）網(wǎng)絡(luò)中提供節(jié)點(diǎn)定位[1]的方式主要有兩種：（1）基于服務(wù)器目錄。在此定位方法中，目錄存放在服務(wù)器上，用其記錄著網(wǎng)絡(luò)中所有節(jié)點(diǎn)的索引信息和資源分布情況，而某個(gè)節(jié)點(diǎn)需要搜索資源數(shù)據(jù)塊時(shí)，只需查找服務(wù)器目錄即可定位到資源節(jié)點(diǎn)。但是這種方式卻通常易使服務(wù)器成為整個(gè)系統(tǒng)的瓶頸；（2）基于DHT。DHT全稱叫分布式哈希表（Distributed Hash Table），這種定位方式是通過將網(wǎng)絡(luò)中的節(jié)點(diǎn)組織到一個(gè)結(jié)構(gòu)化的P2P網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都存儲著一部分的目錄信息。由此就構(gòu)成了一個(gè)目錄的完整性備份，當(dāng)節(jié)點(diǎn)中目錄內(nèi)容變化較小的時(shí)候，基于DHT方式的路由查詢是高效、完備的。

本文在上述兩種節(jié)點(diǎn)資源定位算法的基礎(chǔ)上設(shè)計(jì)了保證QoS的定位算法——QoSVoD，這一算法的主要思想是將P2P流媒體點(diǎn)播網(wǎng)絡(luò)中的超級節(jié)點(diǎn)作為一個(gè)小型的臨時(shí)目錄服務(wù)器，超級節(jié)點(diǎn)將記錄本簇中普通節(jié)點(diǎn)的數(shù)據(jù)塊位圖信息，同時(shí)在超級節(jié)點(diǎn)的幫助下，目標(biāo)節(jié)點(diǎn)的快速準(zhǔn)確定位也隨即獲得實(shí)現(xiàn)。

在描述本文的路由查詢機(jī)制前，先給出如下3個(gè)定義。

定義1： 請求節(jié)點(diǎn)。是指網(wǎng)絡(luò)中需要某個(gè)數(shù)據(jù)塊，向其他節(jié)點(diǎn)發(fā)出資源請求的節(jié)點(diǎn)。

定義2：資源節(jié)點(diǎn)。是指網(wǎng)絡(luò)中擁有請求節(jié)點(diǎn)所需數(shù)據(jù)塊的節(jié)點(diǎn)。

定義3：目的節(jié)點(diǎn)。請求節(jié)點(diǎn)發(fā)出一個(gè)資源請求后，網(wǎng)絡(luò)中通常會有多個(gè)資源節(jié)點(diǎn)滿足請求節(jié)點(diǎn)的需求，其中最優(yōu)的資源節(jié)點(diǎn)稱為目的節(jié)點(diǎn)。

節(jié)點(diǎn)的路由查詢機(jī)制主要根據(jù)當(dāng)前時(shí)刻點(diǎn)播同一個(gè)流媒體資源的節(jié)點(diǎn)所形成的簇規(guī)模不同而采取如下的兩種辦法。

（1）如果簇中節(jié)點(diǎn)的數(shù)目較少（如只有幾百個(gè)），小于預(yù)先設(shè)定的閾值maxSize，超級節(jié)點(diǎn)維護(hù)簇中所有普通節(jié)點(diǎn)的資源位圖信息。請求節(jié)點(diǎn)查詢某個(gè)數(shù)據(jù)塊時(shí)，首先向超級節(jié)點(diǎn)發(fā)起查詢消息，超級節(jié)點(diǎn)在查詢自己維護(hù)的節(jié)點(diǎn)資源位圖，并定位到資源節(jié)點(diǎn)后，即由資源節(jié)點(diǎn)為請求節(jié)點(diǎn)提供服務(wù)。這種查詢方式在 內(nèi)就可以查詢到資源節(jié)點(diǎn)。

（2）如果簇中的節(jié)點(diǎn)很多（比如上萬個(gè)），即有很多節(jié)點(diǎn)同時(shí)點(diǎn)播某個(gè)流媒體資源，請求節(jié)點(diǎn)則需使用下面描述的VoDMeridian路由算法進(jìn)行資源查找。

2 網(wǎng)絡(luò)中節(jié)點(diǎn)距離預(yù)測度量

節(jié)點(diǎn)在簇內(nèi)查找資源時(shí)，如果簇中的節(jié)點(diǎn)數(shù)很多，需要使用特定的路由算法進(jìn)行查找。在此之前，首先需要度量簇內(nèi)節(jié)點(diǎn)間的距離。但是P2P網(wǎng)絡(luò)的高度動態(tài)性使得精準(zhǔn)度量節(jié)點(diǎn)距離較為困難，因此，本文采用節(jié)點(diǎn)距離預(yù)測技術(shù)[2-3]來近似度量節(jié)點(diǎn)間的距離。常用的節(jié)點(diǎn)間距離預(yù)測技術(shù)可分為：非坐標(biāo)距離預(yù)測方法和網(wǎng)絡(luò)坐標(biāo)計(jì)算方法兩大類。對其給出基本概述如下。

非坐標(biāo)距離預(yù)測方法是通過直接測量網(wǎng)絡(luò)中部分節(jié)點(diǎn)的距離，再根據(jù)相應(yīng)部分測得的距離信息來直接預(yù)測所有節(jié)點(diǎn)之間的距離信息，并不使用任何坐標(biāo)計(jì)算的形式來實(shí)現(xiàn)預(yù)測。但卻常常需要一些特殊節(jié)點(diǎn)（如DNS服務(wù)器等）協(xié)助完成。

網(wǎng)絡(luò)坐標(biāo)方法是通過一定的映射算法，將整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)映射到幾何空間中，網(wǎng)絡(luò)中的節(jié)點(diǎn)位置即以空間坐標(biāo)來提供定義，而且網(wǎng)絡(luò)中的節(jié)點(diǎn)與幾何空間中的節(jié)點(diǎn)對應(yīng)為一一映射，將可通過計(jì)算幾何空間中的節(jié)點(diǎn)距離來反映實(shí)際網(wǎng)絡(luò)中的真實(shí)距離。

本文在估計(jì)簇中節(jié)點(diǎn)間的距離時(shí)，根據(jù)P2P流媒體點(diǎn)播的實(shí)際情況，重點(diǎn)關(guān)注從多個(gè)資源節(jié)點(diǎn)中選取鄰近的節(jié)點(diǎn)，而并非測量出具體的距離值。因此本文設(shè)計(jì)的解決方案是：構(gòu)建了適用于P2P點(diǎn)播網(wǎng)絡(luò)的節(jié)點(diǎn)距離預(yù)測算法，并利用此算法來優(yōu)化節(jié)點(diǎn)的路由查詢，再通過查詢算法尋找到目標(biāo)節(jié)點(diǎn)或目標(biāo)節(jié)點(diǎn)集。

3 環(huán)點(diǎn)播查詢路由算法

3.2.1 VoDMeridian環(huán)點(diǎn)播查詢路由算法

在P2P點(diǎn)播系統(tǒng)模型中，每個(gè)節(jié)點(diǎn)都維護(hù)一個(gè)Meridian同心圓環(huán)結(jié)構(gòu)的鄰居節(jié)點(diǎn)列表。當(dāng)某個(gè)簇中節(jié)點(diǎn)很多時(shí)，就使用VoDMeridian路由查找算法查找目標(biāo)節(jié)點(diǎn)。這里，需將原物理網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)映射為Meridian環(huán)狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

為此，涉及到一個(gè)核心問題，即如何選取映射關(guān)系，也就是物理網(wǎng)絡(luò)中的節(jié)點(diǎn)按照何種規(guī)則對應(yīng)到Meridian環(huán)狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中。為了解決這一問題，本文給出如下定義。

定義4：節(jié)點(diǎn)間的播放距離

假設(shè)當(dāng)前網(wǎng)絡(luò)規(guī)?？倲?shù)為N，集合 ，表示網(wǎng)絡(luò)中點(diǎn)播同一部流媒體資源的m個(gè)節(jié)點(diǎn)的當(dāng)前點(diǎn)播位置，節(jié)點(diǎn)i和節(jié)點(diǎn)j的播放距離本文定義為 。

在進(jìn)行流媒體點(diǎn)播時(shí)，節(jié)點(diǎn)在數(shù)據(jù)傳輸中的滑動窗口大小是有相應(yīng)限制的，假設(shè)最多一次能交換w個(gè)數(shù)據(jù)片，這就使得只有播放距離 在w以內(nèi)的節(jié)點(diǎn)互相交換數(shù)據(jù)才具現(xiàn)實(shí)意義，即對當(dāng)前的節(jié)點(diǎn)i，本文將滿足 的節(jié)點(diǎn)加入到節(jié)點(diǎn)i維護(hù)的Meridian同心圓環(huán)結(jié)構(gòu)中的數(shù)據(jù)交換環(huán)（第1層）中。以此類推，加入節(jié)點(diǎn)i第2層Meridian環(huán)的節(jié)點(diǎn)應(yīng)該滿足 ；加入節(jié)點(diǎn)i第K層Meridian環(huán)的節(jié)點(diǎn)就應(yīng)該滿足 。

物理節(jié)點(diǎn)映射到Meridian環(huán)狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)后，VoDMeridian環(huán)點(diǎn)播查詢路由算法如下：

（1）請求節(jié)點(diǎn)A根據(jù)自己的播放位置確定所需的數(shù)據(jù)片；

（2）請求節(jié)點(diǎn)根據(jù)數(shù)據(jù)片，查找目的節(jié)點(diǎn)T。首先請求節(jié)點(diǎn)從Meridian環(huán)中找到最接近T的節(jié)點(diǎn)。如果最近接近的節(jié)點(diǎn)就是T，則查找成功；否則，跳轉(zhuǎn)到（3）；

（3）最接近節(jié)點(diǎn)查找自己的Meridian環(huán)中最接近T的節(jié)點(diǎn)，以此類推；

（4）返回最終查找的最接近節(jié)點(diǎn)。如果最接近節(jié)點(diǎn)為T，查找成功；否則，查找失敗。

3.2 距離預(yù)測模型

本文所設(shè)計(jì)的距離預(yù)測模型以子午線[4]（Meridian）節(jié)點(diǎn)選擇機(jī)制為基礎(chǔ)，將P2P覆蓋網(wǎng)中的對等節(jié)點(diǎn)根據(jù)其相互間的距離關(guān)系組織在一個(gè)半徑以指數(shù)增長的同心圓環(huán)結(jié)構(gòu)中。具體來說，該模型主要包括3部分：同心圓環(huán)結(jié)構(gòu)、圓環(huán)成員管理、節(jié)點(diǎn)路由查找機(jī)制。此后，將具體描述每一部分的機(jī)理實(shí)現(xiàn)模式。

3.2.1 同心圓環(huán)結(jié)構(gòu)

網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)A都維護(hù)著一個(gè)同心圓環(huán)結(jié)構(gòu)，用以保存一定數(shù)量的節(jié)點(diǎn)信息。這個(gè)同心圓的半徑是以指數(shù)增長，第 個(gè)環(huán)的內(nèi)圓半徑為 ，外圓半徑為 ， 是一個(gè)常數(shù)，而 是一個(gè)指數(shù)增長因子。 表示最里面的圓環(huán)，本文稱為數(shù)據(jù)交換環(huán)，節(jié)點(diǎn)A只能與這里面的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)交換。如果被測量的節(jié)點(diǎn)B與節(jié)點(diǎn)A的距離為 ，且滿足 ，則將節(jié)點(diǎn)B添加到節(jié)點(diǎn)A的第 個(gè)圓環(huán)內(nèi)。為了限制圓環(huán)數(shù)目，本文定義閾值 ，如果圓環(huán)個(gè)數(shù) 達(dá)到 ，則 。

3.2.2 圓環(huán)成員管理

為了有效控制每個(gè)圓環(huán)中節(jié)點(diǎn)的數(shù)量，每個(gè)圓環(huán)中最多能保存L個(gè)節(jié)點(diǎn)。L是查找準(zhǔn)確度和維護(hù)節(jié)點(diǎn)開銷的權(quán)衡值。如果L值越大，節(jié)點(diǎn)A越容易查找到資源節(jié)點(diǎn)，但維護(hù)其他節(jié)點(diǎn)的開銷也相應(yīng)越大；如果L值小，表示節(jié)點(diǎn)A維護(hù)其他節(jié)點(diǎn)的開銷很小，但卻隨之增加了查找到目標(biāo)節(jié)點(diǎn)的路由跳數(shù)。

同心圓環(huán)中目的節(jié)點(diǎn)的查找過程：

（1）請求節(jié)點(diǎn)A從每個(gè)圓環(huán)中隨機(jī)取出一個(gè)節(jié)點(diǎn)，向這些節(jié)點(diǎn)發(fā)出查詢目標(biāo)節(jié)點(diǎn)T消息；

（2）節(jié)點(diǎn)收到A的消息后，在自己維護(hù)的同心圓環(huán)中查詢，測量自己與目標(biāo)節(jié)點(diǎn)T的距離，并對自己維護(hù)圓環(huán)中的節(jié)點(diǎn)進(jìn)行路由轉(zhuǎn)發(fā)查詢，直至找到目標(biāo)節(jié)點(diǎn)T為止；

（3）請求節(jié)點(diǎn)A接受返回的目標(biāo)節(jié)點(diǎn)T。

以查詢到目標(biāo)節(jié)點(diǎn)T 為例，普通節(jié)點(diǎn)向某個(gè)圓環(huán)中的節(jié)點(diǎn)A 發(fā)起查詢請求。節(jié)點(diǎn)A首先判斷自己到T的距離d，然后探測其在 范圍的環(huán)成員節(jié)點(diǎn)，并將該查詢轉(zhuǎn)發(fā)至這些環(huán)成員節(jié)點(diǎn)中距離T最近的節(jié)點(diǎn)B。節(jié)點(diǎn)B 重復(fù)這一查詢過程，直至轉(zhuǎn)發(fā)到某個(gè)節(jié)點(diǎn)后無法再找到更近節(jié)點(diǎn)為止。最后查找到的節(jié)點(diǎn)即為目標(biāo)節(jié)點(diǎn)T。此處 。由于Meridian覆蓋網(wǎng)絡(luò)圓環(huán)半徑以指數(shù)增長，因此，這種迭代查詢算法即會以指數(shù)速度 接近目標(biāo)節(jié)點(diǎn)。

4 實(shí)驗(yàn)仿真及結(jié)果分析

為了驗(yàn)證路由查找算法的性能，本文將QoSVoD模型與經(jīng)典的Kad模型[5]進(jìn)行仿真比較。Kad是一種已經(jīng)應(yīng)用到實(shí)際網(wǎng)絡(luò)中的高效路由查找算法，可通過對網(wǎng)絡(luò)節(jié)點(diǎn)ID值的異或計(jì)算來度量節(jié)點(diǎn)間的距離。仿真實(shí)驗(yàn)室中，QoSVoD模型與Kad模型比較如下性能指標(biāo)數(shù)據(jù)：

（1）查找成功率。節(jié)點(diǎn)發(fā)出查詢，最后成功收到正確回復(fù)的統(tǒng)計(jì)數(shù)據(jù)。

（2）平均路由跳數(shù)。請求節(jié)點(diǎn)查詢到目標(biāo)節(jié)點(diǎn)中間經(jīng)過的路由轉(zhuǎn)發(fā)次數(shù)。

（3）平均時(shí)延。節(jié)點(diǎn)發(fā)出查詢消息直至接收到回復(fù)消息之間的時(shí)間間隔。

圖1、2、3反映了QoSVoD模型與Kad模型在查找成功率，平均路由跳數(shù)，節(jié)點(diǎn)間的查找時(shí)延等方面的性能比較結(jié)果。在此，可做如下分析。

（1） 節(jié)點(diǎn)查找成功率

查找成功率是統(tǒng)計(jì)節(jié)點(diǎn)發(fā)出查詢后成功收到正確的回復(fù)的統(tǒng)計(jì)數(shù)據(jù)，查找成功率越高，說明模型越有效。從圖1可以觀察出，雖然節(jié)點(diǎn)的擾動現(xiàn)象使兩種模型的查找成功率均發(fā)生上下波動，但QoSVoD模型的查找成功率卻一直比Kad算法呈現(xiàn)更高態(tài)勢。這主要是因?yàn)楫?dāng)QoSVoD模型中的節(jié)點(diǎn)通過路由算法查找不到目的節(jié)點(diǎn)時(shí)，流媒體服務(wù)器可向其提供流媒體服務(wù)，從而保證了請求稀有資源的節(jié)點(diǎn)的服務(wù)質(zhì)量。

圖1 節(jié)點(diǎn)的查找成功率

Fig.1 Lookup success rate of node

（2）平均路由查找跳數(shù)

圖2反映了當(dāng)網(wǎng)絡(luò)規(guī)模變化時(shí)，Kad和QoSVoD路由查詢算法的平均查找跳數(shù)的變化情況。路由查找跳數(shù)是反映節(jié)點(diǎn)查找效率的統(tǒng)計(jì)數(shù)據(jù)，平均查找跳數(shù)越少，說明模型查找效率越高。從圖2可以觀察出，QoSVoD模型中路由查詢算法的查找效率比Kad要明顯偏高，Kad網(wǎng)絡(luò)中節(jié)點(diǎn)的平均路由查詢跳數(shù)隨網(wǎng)絡(luò)規(guī)模的增加而增加，而QoSVoD模型中節(jié)點(diǎn)的查詢跳數(shù)相對穩(wěn)定。這是因?yàn)镼oSVoD模型中存在超級節(jié)點(diǎn)，當(dāng)點(diǎn)播某資源的節(jié)點(diǎn)簇中成員較少時(shí)，超級節(jié)點(diǎn)能直接為其他普通節(jié)點(diǎn)提供查詢定位服務(wù)。當(dāng)簇中節(jié)點(diǎn)較多的時(shí)候，請求節(jié)點(diǎn)可在簇內(nèi)使用VoDMeridian算法進(jìn)行定位查詢，查詢效率也可達(dá)到 。

圖2 平均查找路由跳數(shù)

Fig.2 Find average routing hops

（3） 查找延遲

圖3反映了Kad和QoSVoD模型路由查找算法的查詢時(shí)間延遲的對比情況。查詢時(shí)延主要統(tǒng)計(jì)節(jié)點(diǎn)發(fā)出查詢消息到接收到回復(fù)之間的時(shí)間間隔。從圖3可以觀察到，QoSVoD網(wǎng)絡(luò)中節(jié)點(diǎn)的查詢時(shí)延穩(wěn)定在200ms左右，總體上比Kad小，這是因?yàn)橥ㄟ^節(jié)點(diǎn)所維護(hù)的環(huán)狀路由表，節(jié)點(diǎn)搜索當(dāng)前點(diǎn)播位置的臨近資源時(shí)速度更快，從而減小了查詢時(shí)延。

圖3 查詢的時(shí)間延遲

Fig.3 Query time delay

5 結(jié)束語

通過對影響P2P流媒體點(diǎn)播QoS因素的分析，設(shè)計(jì)了保證服務(wù)質(zhì)量的P2P模型中目標(biāo)節(jié)點(diǎn)路由算法，與Kad模型在查找成功率，平均路由跳數(shù)，節(jié)點(diǎn)間的查找時(shí)延等方面的性能比較之后，可以看出該算法在保證服務(wù)質(zhì)量的前提下有很好的定位效果。

參考文獻(xiàn)：

[1] 刑長友，陳鳴.網(wǎng)絡(luò)距離預(yù)測技術(shù)[J].軟件學(xué)報(bào)，2009，20（6）：2470-2482.

[2] LEE S，ZHANG Z，SAHU S， et al. Fundamental effects of clustering on the euclidean embedding of Internet hosts[A]. Proc. of the IFIP Networking [C]. Berlin： Springer-Verlag， 2007. 890?901.

[3] 朱培棟，盧錫城，等.一種網(wǎng)絡(luò)自組織演化的數(shù)學(xué)模型[J].軟件學(xué)報(bào)，2007，18（12）：3071-3079.

[4] WU D， LIANG C， LIU Y， et al. View-upload decoupling： A redesign of multi-channel P2P Video Systems [A]. IEEE INFOCOM[C]. Rio de Janeiro： IEEE， 2009：2007-2018.

[5] 李杰.對等網(wǎng)絡(luò)搭便車行為研究與激勵(lì)機(jī)制的優(yōu)化[D].蘇州：蘇州大學(xué)，2009：28-37.