基于路徑優先度的VoIP中繼選擇算法*

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

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

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

覆蓋網絡是應用層網絡，不考慮或很少考慮物理層網絡的問題，利用中介機構作為中繼節點繞過性能下降的網絡路徑，可以提供多個路徑并選擇維持最好的網絡條件[7]。目標節點通過中繼節點到達目的節點的路徑即中繼路徑。中繼選擇算法的目的就是搜索合適的中繼節點以建立性能更優的中繼路徑。

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

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

2 路徑優先度

2.1 問題描述

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

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

綜合時延和與默認的IP路徑有差異性這兩個指標提出路徑優先度，依此作為選擇標準。

2.2 路徑優先度概念

對于每個VoIP業務請求，計算從源節點途徑中繼節點再到目的節點的時延以及這些路徑與默認路徑的重合度。依此設定一個權值參數θ，稱其為路徑優先度，定義如下:

其中，Ohops表示重合的節點跳數，Thops表示總的節點跳數。Rlatency表示中繼路徑的時延，Qlatency表示VoIP業務QoS參數中的時延要求，通常是150 ms。

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

3 基于路徑優先度的VoIP中繼選擇算法

3.1 路由表的構建

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

遵從貪婪算法，在選擇節點的時候對于不同時延范圍的節點選擇的比例也不同。盡可能選擇距離源節點時延小的節點，同時還要保證每個時延范圍內都有節點被選到。選取節點與其所在AS距離源節點自治域的跳數和時延有關[15,16]，為每個節點選取20個中繼候選節點。對每個范圍內的候選節點，按照時延由小到大排序，并按照相應比例來選擇。由候選節點的時延、AS和IP地址構成一個路由表，格式見表1。

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

構建路由表的算法如下。

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

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

3.2 中繼路徑的選擇過程

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

圖1 路由表中的候選中繼節點的選擇示意

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

3.3 基于路優先度的兩跳的中繼路徑選擇算法

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

4 仿真與性能

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

4.1 路徑時延

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

4.2 時延改善率

時延改善率指應用算法預測的時延與默認路徑的時延相比，時延減少量相對默認路徑時延的比率，表示算法性能的優劣。時延改善率越大，表示算法相對于默認路徑的時延減少越多，性能越優。

圖2 PPBR算法路徑與默認IP路徑時延的比較

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

圖3 PPBR算法的時延改善

5 結束語

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

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