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

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

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

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

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

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

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

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)用層選擇多個(gè)中繼節(jié)點(diǎn)來實(shí)現(xiàn)端到端的多路徑傳輸，通過主動(dòng)探測(cè)和監(jiān)視節(jié)點(diǎn)之間的鏈路選擇最優(yōu)的中繼路徑，有效地避免IP網(wǎng)絡(luò)的擁塞和時(shí)延抖動(dòng)問題[12]。研究證明，應(yīng)用層提供的中繼路由能夠得到比默認(rèn)的IP直聯(lián)路由更好的性能[13]。隨機(jī)選擇中繼節(jié)點(diǎn)并不能保證路徑與默認(rèn)路徑之間的差異性，75%的路徑存在較嚴(yán)重的重疊，因此結(jié)合網(wǎng)絡(luò)拓?fù)涞闹欣^節(jié)點(diǎn)選擇算法成為研究重點(diǎn)[14]。

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

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

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

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

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

因?yàn)闀r(shí)延和路徑差異是中繼路徑選擇的兩個(gè)主要因素，θ用來衡量這兩個(gè)因素的偏重度。θ越小，說明中繼節(jié)點(diǎn)的時(shí)延效果和路徑差異的效果越好。

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

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

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

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

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

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

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

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

3.2 中繼路徑的選擇過程

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

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

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

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

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

4 仿真與性能

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

4.1 路徑時(shí)延

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

4.2 時(shí)延改善率

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

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

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

圖3 PPBR算法的時(shí)延改善

5 結(jié)束語(yǔ)

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

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