曲 樺 ，趙季紅 ,2，王麗霞 ，董士奇

（1.西安交通大學(xué)電子與信息工程學(xué)院 西安 710049；2.西安郵電大學(xué)通信與信息工程學(xué)院 西安 710061）

VoIP業(yè)務(wù)在互聯(lián)網(wǎng)上為用戶建立端到端路徑，需保證業(yè)務(wù)的時延小于150 ms[1]。為了保證VoIP業(yè)務(wù)的時延要求，在基于多自治域（autonomous domain，AS）的覆蓋網(wǎng)絡(luò)上為其建立端到端路由是目前發(fā)展趨勢[2]。但覆蓋網(wǎng)絡(luò)中存在反三角現(xiàn)象，導(dǎo)致網(wǎng)絡(luò)中兩條路徑的時延之和小于一條端到端路徑的時延[3～5]，因此，需要在覆蓋網(wǎng)絡(luò)中研究中繼技術(shù)，確定合適的中繼節(jié)點，建立從源節(jié)點通過中繼節(jié)點到目的節(jié)點的路徑，使得該路徑的時延最小，以承載VoIP業(yè)務(wù)，減少VoIP業(yè)務(wù)的時延，滿足用戶的業(yè)務(wù)請求[6]。

覆蓋網(wǎng)絡(luò)是應(yīng)用層網(wǎng)絡(luò)，不考慮或很少考慮物理層網(wǎng)絡(luò)的問題，利用中介機(jī)構(gòu)作為中繼節(jié)點繞過性能下降的網(wǎng)絡(luò)路徑，可以提供多個路徑并選擇維持最好的網(wǎng)絡(luò)條件[7]。目標(biāo)節(jié)點通過中繼節(jié)點到達(dá)目的節(jié)點的路徑即中繼路徑。中繼選擇算法的目的就是搜索合適的中繼節(jié)點以建立性能更優(yōu)的中繼路徑。

中繼選擇算法主要有彈性覆蓋網(wǎng) （resilient overlay network，RON）、基于自治域感知的中繼節(jié)點協(xié)議（AS-aware peer-relay protocol，ASAP）、最早發(fā)散規(guī)則（earliest divergence rule，EDR）、單跳啟發(fā)式中繼節(jié)點選擇算法（heuristic relay node selection algorithm for one-hop overlay routing，HORNS）、基于meridian的中繼選擇算法 （meridian-based relay selection algorithm，MBRS）等。RON[8]算法是在物理路徑發(fā)生故障時，在直連路徑外尋找一個中繼節(jié)點，通過中轉(zhuǎn)路徑恢復(fù)VoIP業(yè)務(wù)，該算法選中的中繼節(jié)點不具有通用性，并不能解決網(wǎng)絡(luò)中的普遍現(xiàn)象且過分依賴中央服務(wù)器，需要全局信息。ASAP[1]算法根據(jù)AS信息尋找合適的中繼節(jié)點，該算法能提升鏈路性能，并能精準(zhǔn)地找到中繼節(jié)點，但依賴于全局網(wǎng)絡(luò)AS分布圖，應(yīng)用中很難部署。EDR[9]算法依據(jù)路由源點發(fā)送探測針獲取的周圍AS級別的路徑時延信息做出路由決策，該算法只需知道源節(jié)點到中繼節(jié)點的時延和AS路徑，無需其他中央服務(wù)器，但它沒有考慮時延、分組丟失率方面的性能。HORNS[10]算法以源節(jié)點到中繼節(jié)點的時延作為尺度，發(fā)現(xiàn)最優(yōu)中繼節(jié)點的分布規(guī)律，并按照這種比例分布在不同時延區(qū)域挑選不同數(shù)量的節(jié)點作為中繼節(jié)點的候選者，該方法能更好地挑選中繼節(jié)點，但沒有考慮路徑的差異性。MBRS[11]算法以meridian為基礎(chǔ)來查找中繼，它能找到一個距離目的節(jié)點較近的中繼節(jié)點，但是路徑時延不是最小，選出來的節(jié)點并不是最合適的中繼節(jié)點。

鑒于現(xiàn)有算法存在的缺陷，提出基于路徑優(yōu)先度的VoIP中繼選擇算法 （a path-priority based relay selection algorithm for VoIP，PPBR）。該算法首先提出路徑優(yōu)先度概念，用以描述時延和與默認(rèn)IP路徑的差異性，再基于路徑優(yōu)先度構(gòu)建中繼路由表，從中選擇最優(yōu)中繼節(jié)點；針對覆蓋網(wǎng)絡(luò)中普遍存在的“反三角現(xiàn)象”[3～5]，提出基于路徑優(yōu)先度的兩跳中繼選擇算法，通過兩個中繼節(jié)點的轉(zhuǎn)發(fā)減少時延。

2 路徑優(yōu)先度

2.1 問題描述

傳統(tǒng)的IP網(wǎng)絡(luò)采取的是盡力而為的傳輸方式，由路由策略決定唯一路徑，而路由策略通常由AS之間的商業(yè)關(guān)系所決定，不同的AS可能采用不同的路由策略，因此存在AS間的路由不是最優(yōu)的情況。而覆蓋網(wǎng)絡(luò)是基于應(yīng)用層構(gòu)建的，不考慮或很少考慮物理網(wǎng)絡(luò)層的問題，可以在應(yīng)用層選擇多個中繼節(jié)點來實現(xiàn)端到端的多路徑傳輸，通過主動探測和監(jiān)視節(jié)點之間的鏈路選擇最優(yōu)的中繼路徑，有效地避免IP網(wǎng)絡(luò)的擁塞和時延抖動問題[12]。研究證明，應(yīng)用層提供的中繼路由能夠得到比默認(rèn)的IP直聯(lián)路由更好的性能[13]。隨機(jī)選擇中繼節(jié)點并不能保證路徑與默認(rèn)路徑之間的差異性，75%的路徑存在較嚴(yán)重的重疊，因此結(jié)合網(wǎng)絡(luò)拓?fù)涞闹欣^節(jié)點選擇算法成為研究重點[14]。

VoIP的通話質(zhì)量主要受兩個因素的影響:時延和分組丟失率。低時延路徑在分組丟失率方面也具有較好的性能參數(shù)，其重要的原因是高時延的路徑由于節(jié)點處于阻塞狀態(tài)，導(dǎo)致時延，并伴隨出現(xiàn)很多分組丟失現(xiàn)象，因此，在改善時延的同時可以改善分組丟失率參數(shù)。通過比較默認(rèn)IP路徑與覆蓋網(wǎng)路由新路徑上的重合節(jié)點數(shù)，可以定量地獲得兩條路徑的差異性。而兩個差異性大的路由同時發(fā)生鏈路失效和鏈路效能下降的概率較小，這樣就可提高端到端路由的傳輸質(zhì)量。同時，這也使得網(wǎng)絡(luò)的流量分布于不同的路徑，實現(xiàn)了網(wǎng)絡(luò)系統(tǒng)的負(fù)載均衡。因此，本文所提基于路徑優(yōu)先度的VoIP中繼選擇算法的核心思想是:在給定的具有固定拓?fù)涞亩鄠€AS互聯(lián)的網(wǎng)絡(luò)環(huán)境下，從源節(jié)點到目的節(jié)點之間的多條覆蓋網(wǎng)端到端路徑中選擇一條時延能達(dá)到最小且與默認(rèn)的IP路徑有差異的路徑。

綜合時延和與默認(rèn)的IP路徑有差異性這兩個指標(biāo)提出路徑優(yōu)先度，依此作為選擇標(biāo)準(zhǔn)。

2.2 路徑優(yōu)先度概念

對于每個VoIP業(yè)務(wù)請求，計算從源節(jié)點途徑中繼節(jié)點再到目的節(jié)點的時延以及這些路徑與默認(rèn)路徑的重合度。依此設(shè)定一個權(quán)值參數(shù)θ，稱其為路徑優(yōu)先度，定義如下:

其中，Ohops表示重合的節(jié)點跳數(shù)，Thops表示總的節(jié)點跳數(shù)。Rlatency表示中繼路徑的時延，Qlatency表示VoIP業(yè)務(wù)QoS參數(shù)中的時延要求，通常是150 ms。

因為時延和路徑差異是中繼路徑選擇的兩個主要因素，θ用來衡量這兩個因素的偏重度。θ越小，說明中繼節(jié)點的時延效果和路徑差異的效果越好。

3 基于路徑優(yōu)先度的VoIP中繼選擇算法

3.1 路由表的構(gòu)建

把有l(wèi)gN個鄰居節(jié)點的節(jié)點作為最有潛力成為中繼節(jié)點的節(jié)點，組織到一個路由表中。逐次查找路由表中的節(jié)點，只要找到符合要求的鄰居節(jié)點，就可以完成中繼節(jié)點的選擇。

遵從貪婪算法，在選擇節(jié)點的時候?qū)τ诓煌瑫r延范圍的節(jié)點選擇的比例也不同。盡可能選擇距離源節(jié)點時延小的節(jié)點，同時還要保證每個時延范圍內(nèi)都有節(jié)點被選到。選取節(jié)點與其所在AS距離源節(jié)點自治域的跳數(shù)和時延有關(guān)[15,16]，為每個節(jié)點選取20個中繼候選節(jié)點。對每個范圍內(nèi)的候選節(jié)點，按照時延由小到大排序，并按照相應(yīng)比例來選擇。由候選節(jié)點的時延、AS和IP地址構(gòu)成一個路由表，格式見表1。

表1 基于時延和路徑差異性的路由表格式

構(gòu)建路由表的算法如下。

其中ASs表示網(wǎng)絡(luò)中所有的 AS，AS（p）表示節(jié)點 p所在的 AS。hop（AS1,AS2）表示自治域 AS1與 AS2之間的跳數(shù)。從距離源節(jié)點AS跳數(shù)為1的AS中選擇3個候選節(jié)點，跳數(shù)為2的AS中選擇2個候選節(jié)點。其他AS，每個選擇一個候選節(jié)點。假設(shè)在每個AS選擇時，先隨機(jī)選擇10個節(jié)點，然后通過一定的測量機(jī)制測量源節(jié)點到這些節(jié)點的時延大小，并且從低到高排序，進(jìn)而按前面的原則選取節(jié)點。

圖1顯示了應(yīng)用上述路由表構(gòu)造算法在大規(guī)模多AS中選擇中繼節(jié)點的一個過程。對自治域AS1節(jié)點在構(gòu)造路由表時，首先從距離 AS1一跳的自治域AS2、AS3、AS4內(nèi)各選3個節(jié)點作為候選中繼節(jié)點，例如從自治域AS3中選擇節(jié)點1、3、4 作為候選。接著從距離AS1兩跳的自治域 AS5、AS6、AS7、AS8中各選兩個節(jié)點加入中繼路由表。最后從距離自治域AS13跳以上的自治域內(nèi)各挑選一個節(jié)點加入中繼路由表，直到路由表設(shè)定的數(shù)目已滿。當(dāng)路由表中存儲的某個中繼失效時，AS會重新選擇一個候選節(jié)點補(bǔ)充，例如AS3中節(jié)點3失效，則會選擇節(jié)點2作為補(bǔ)充加到路由表中。

3.2 中繼路徑的選擇過程

路由表構(gòu)建完成后，即在此表中選擇中繼節(jié)點。首先計算從源節(jié)點到目的節(jié)點的默認(rèn)路徑，并且記錄所經(jīng)過的節(jié)點的ID和IP地址，然后在源節(jié)點路由表中除去，并由路由表中剩余節(jié)點組成一個新節(jié)點集；在新的節(jié)點集中選擇θ最小的節(jié)點作為中繼節(jié)點。具體算法如下。通過該算法，可找到滿足條件的中繼節(jié)點。

圖1 路由表中的候選中繼節(jié)點的選擇示意

其中，Pde表示默認(rèn)路徑，Pr為中繼路徑。ns表示源節(jié)點，nt表示目的節(jié)點，Nrelay表示除去默認(rèn)路徑上節(jié)點的節(jié)點集合。Ohopsr表示默認(rèn)路徑與中繼路徑的重合節(jié)點數(shù)目，Ds,t表示中繼路徑時延。

3.3 基于路優(yōu)先度的兩跳的中繼路徑選擇算法

網(wǎng)絡(luò)有時可能出現(xiàn)“反三角現(xiàn)象”[3～5]，單跳的中繼路徑并不能很好地解決問題，而兩跳的中繼路徑性能更好。兩跳中繼路徑選擇算法基本原理與一跳算法相似，具體算法如下。

4 仿真與性能

本文采用PPBR算法仿真查看算法能夠查找到滿足要求的中繼節(jié)點的成功率，并計算PPBR算法的時延與默認(rèn)路徑的時延差值和時延改善率。仿真數(shù)據(jù)采用King數(shù)據(jù)集的1895個節(jié)點間時延[17]。從原始數(shù)據(jù)選取部分節(jié)點數(shù)據(jù)，根據(jù)IP地址與IP前綴獲得AS號。實驗進(jìn)行50次隨機(jī)選取一對源節(jié)點和目的節(jié)點；假設(shè)中繼路由表節(jié)點數(shù)目為20個，節(jié)點總數(shù)范圍為100～1000個。

4.1 路徑時延

圖2為采用一跳PPBR、兩跳PPBR算法以及默認(rèn)IP路徑所得的時延。圖中PPBR算法相比默認(rèn)IP路徑時延明顯減小。很多情況下兩跳算法的時延又明顯優(yōu)于一跳算法，表明采用兩跳算法解決了“反三角現(xiàn)象”。

4.2 時延改善率

時延改善率指應(yīng)用算法預(yù)測的時延與默認(rèn)路徑的時延相比，時延減少量相對默認(rèn)路徑時延的比率，表示算法性能的優(yōu)劣。時延改善率越大，表示算法相對于默認(rèn)路徑的時延減少越多，性能越優(yōu)。

圖2 PPBR算法路徑與默認(rèn)IP路徑時延的比較

PPBR算法與默認(rèn)路徑的時延差值，如圖3（a）所示。PPBR對默認(rèn)IP路徑的時延減少量維持在5～20 ms。個別情況會出現(xiàn)PPBR算法的時延比較大的情況，這是因為有些自治域位于網(wǎng)絡(luò)的邊緣附近，網(wǎng)絡(luò)連通性不夠大，反而會導(dǎo)致構(gòu)成的中繼候選節(jié)點路由表中的節(jié)點繞路，增加了網(wǎng)絡(luò)的時延。但是可以從圖中看到大部分的實驗都可以找到縮短時延的中繼節(jié)點。圖3（b）則顯示了時延改善率，從圖中可看到網(wǎng)絡(luò)的時延可以改善5%～20%。

圖3 PPBR算法的時延改善

5 結(jié)束語

在覆蓋網(wǎng)絡(luò)中部署VoIP業(yè)務(wù)，計算端到端路由時，需保證其時延要求，一般小于150 ms。鑒于覆蓋網(wǎng)絡(luò)中普遍存在的“反三角現(xiàn)象”且已有算法存在部署難、未考慮路徑差異及結(jié)果不是最優(yōu)等問題，本文通過基于路徑優(yōu)先度的VoIP中繼選擇算法，選擇從源節(jié)點到通過中繼節(jié)點到目的節(jié)點的最優(yōu)路徑。該算法首先提出路徑優(yōu)先度的概念，描述時延和默認(rèn)IP路徑的差異性，再基于路徑優(yōu)先度構(gòu)建中繼路由表，在中繼路由表中挑選最優(yōu)中繼節(jié)點；提出基于路徑優(yōu)先度的兩跳中繼選擇算法中繼進(jìn)一步減少轉(zhuǎn)發(fā)時延。仿真證明所提算法能夠減少VoIP業(yè)務(wù)的傳輸時延，保障VoIP業(yè)務(wù)的QoS，提升VoIP業(yè)務(wù)的用戶體驗。

1 Ren S,Guo L,Zhang X.ASAP:an AS-aware peer-relay protocol for high quality VoIP.Proceedings of the 26th IEEE International Conference on Distributed Computing Systems(ICDCS 2006),Lisboa,Portugal,2006

2 Amir Y,Danilov C,Goose S,et al.1-800-overlays:using overlay networks to improve VoIP quality. Proceedings of the International Workshop on Network and Operating Systems Support for Digital Audio and Video,Stevenson,Washington,USA,2005:51～56

3 Zheng H,Lua E K,Pias M,et al.Internet routing policies and round-trip-times.Passive and Active Network Measurement,Springer Berlin Heidelberg,2005:236～250

4 Lumezanu C,Baden R,Spring N,et al.Triangle inequality variations in the internet.Proceedings ofthe 9th ACM SIGCOMM Conference on Internet Measurement,Chicago,Illinois,USA,2009:177～183

5 Lumezanu C,Baden R,Spring N,et al.Triangle inequality and routing policy violation in the internet.Proceedings of the 10th International Conference on Passive and Active Network Measurement,Seoul,Korea,2009:45～56

6 Liu Y,Gu Y,Zhang H,et al.Application level relay for high-bandwidth data transport.Proceedings of GridNets,San Jose,CA,USA,2004

7 Wang G,Zhang C,Qiu X,et al.An efficient relay node selection scheme to improve the performance of P2P-based VoIP applications in Chinese internet. Multimedia Tools and Applications,2013,64(3):1～27

8 Andersen D,Balakrishnan H,Kaashoek F,et al.Resilient overlay networks.ACM SIGCOMM Computer Communication Review,2002,32(1)

9 Fei T,Tao S,Gao L,et al.Light-weight overlay path selection in a peer-to-peer environment.Proceedings of the 25th IEEE International Conference on Computer Communications,Barcelona,Catalunya,Spain,2006:1～6

10 Chen Y,Tang L,Li J.Heuristic relay node selection algorithm for one-hop overlay routing.Proceedings of the 28th International Conference on Distributed Computing Systems Workshops,Beijing,China,2008:465～470

11 Wang H,Zhang C,Qiu X,et al.MBRS:a meridian-based relay selection algorithm for P2P VoIP.Proceedings of the 3rd IEEE International Conference on Broadband Network and Multimedia Technology(IC-BNMT),Beijing,China,2010:965～969

12 Zhang X,Lei W,Zhang W.Using P2P network to transmit media stream in SIP-based system.Proceedings of the 9th International Conference for Young Computer Scientists,Zhangjiajie,China,2008:362～367

13 Baset S A,Schulzrinne H.An analysis of the skype peer-to-peer internet telephonyprotocol.Proceeding soft he 25th IEEE International Conference on Computer Communications,Barcelona,Spain,2006:1～11

14 Han J,Watson D,Jahanian F.An experimental study of internet path diversity.IEEE Transactions on Dependable and Secure Computing,2006,3(4):273～288

15 Chen Y,Tang L,Li J.Heuristic relay node selection algorithm for one-hop overlay routing.Proceedings of the 28th International Conference on Distributed Computing Systems Workshops,Beijing,China,2008:465～470

16 Bui Q D,Jennings A.Relay path selection approaches in peer-to-peer VoIP systems. Proceedings of Australasian Telecommunication Networks and Applications Conference,Adelaide,Australia,2008:361～366

17 Network coordinate research at Harvard.http//www.eecs.harvard.edu/～syrah/nc/,2014