基于Ｐ２Ｐ的ＣＤＮ網絡中緊急消息廣播技術
2007-01-01 00:00:00閆正航楊宇航王暉靳爭團
計算機應用研究 2007年5期
摘要：向基于P2P方式連接的CDN網絡中的所有節點廣播緊急消息，泛洪技術可以滿足快速和可達這兩個指標，但同時會在網絡中產生大量冗余的消息廣播，效率低下，使網絡負荷產生一個短時的波峰。提出泛洪技術的兩種改進方案，即WFES和WFESN技術，在不降低泛洪技術快速和可達的前提下提高了廣播效率，改善了網絡負荷的性能。關鍵詞：內容分發網絡；對等網絡；內容發布；泛洪技術
中圖分類號：TP393文獻標志碼：A
文章編號：1001－3695(2007)05－0287－03
0引言
互聯網的發展日新月異，以流媒體為代表的新一代多媒體視頻技術顯示出巨大的潛力。在多媒體新聞發布、網上演示、在線直播、網絡廣告、電子商務、視頻點播、網上租賃、遠程教育、實時視頻會議等互聯網信息服務領域都有廣闊的應用前景[1]。
由于需要傳輸的流媒體的量越來越多，用戶對多媒體業務的傳輸速率、接入準確度和內容適用性等質量要求越來越高。基于IP的傳統流媒體服務模型無法提供可與有線電視、衛星電視和寬帶電視相比擬的質量。此外，在當前的電視廣播技術下，用戶的選擇很少，無法在自己喜歡的時間接入到喜歡的電視節目上觀看。在這種背景下，內容分發網絡(Content Deli－very/Distributed Networks，CDN)[2]很自然地被應用到網絡多媒體業務上面[3]。CDN通過在網絡中靠近終端用戶的地方增設邊緣服務器，將網站的內容發布到最接近用戶的網絡邊緣， 使用戶可以就近取得所需的內容而不必從源服務器那里獲得所需要的內容，解決了Internet擁塞問題，提高了用戶訪問網站的響應速度，縮短了接入的時間和傳輸的延時，改善了服務的性能[4]。在傳統的C/S接入模式下，CDN仍舊無法滿足不斷增長的用戶數量和多媒體業務需求。與傳統的C/S系統不同，Peer－to－Peer系統中每個節點既是客戶端，又可以作為其他請求節點的服務器。節點從一個服務器端取得所需內容的同時，又可以把內容分發給其他請求同一服務的節點，這樣可以使系統在不增加服務器負擔的同時支持更多的用戶[5，6]。當前流行的MYSEE直播網、PPlive、PPSsteam、CoolStreaming等公司支持的網絡視頻直播都是基于P2P方式的CDN網絡。
1問題描述
隨著社會的發展，公共安全問題在人們的日常生活中顯得日益突出。針對一些突發的事件，如預測到某地將要發生地震、海嘯，或者遭遇到禽流感、大樓遭到恐怖襲擊、水或空氣遭到嚴重污染、觀測到小的空間物體有可能撞擊地球等緊急事件發生時，必須要盡快地把消息發布給廣大受眾。雖然這些類型的事情發生的概率很小，但一旦發生而未能及時作出應對措施，其危害會特別嚴重，有可能喪失了寶貴的逃生機會，給大眾的生命和財產造成難以估計的損失。
鑒于許多用戶經常使用網絡多媒體服務，研究一種通過基于該體系的快速信息發布系統。基于P2P的內容發布方面有其得天獨厚的優勢：發布深度大，理論上可以到達在線的每一個終端；延遲少，終端接收到消息的延時不受服務器帶寬限制和處理能力的影響，可以在極短的時間里覆蓋全網。這些特點特別適用于對一些緊急事件的消息，為應對突如其來的災難事件贏得寶貴的時間。對此類緊急事件的消息發送，①要做到盡可能地快，在這種情況下往往時間就是生命；②范圍要廣，需要盡可能地把消息發送到在線的每一個節點那里；③在滿足及時和可達的基礎上盡可能地提高消息發送過程的效率，不至于讓發送該消息的負荷對現網業務造成過多的影響；④節點的計算和存儲的開銷要小[7，8]。
目前用于信息發布大多采用泛洪(Water Flooding，WF)技術發送。在網絡中每個節點傳輸開銷相同的前提下，WF技術能夠保證經過最短路徑（Hops）發送的消息第一個到達目的節點，也能夠把消息發送到網絡中在線的每一個終端。每個節點的計算和存儲開銷都比較小，但其致命的缺陷是在發送的過程中網絡存在大量的冗余發送。每一個節點都會多次重復收到同一個消息，效率很低，造成網絡的瞬時載荷出現尖峰，占用大量的帶寬資源，影響了網絡中的業務。
針對基于P2P的CND和緊急消息發送的特點提出了WF技術的兩種改進方案。其在保證及時和可達的基礎上提高了發送的效率，并通過仿真比較了三種技術的優劣。
2P2P方式連接的網絡模型
以P2P方式連接的各個節點在網絡中的作用都是對等的，每個節點都是同時作為客戶端和服務器存在的。如圖1所示，在網絡中的每一個節點都與距離自己最近的三個節點建立連接，把與自己有連接的節點加入到自己的鄰居節點集中，這樣每個節點至少有三個鄰居節點。例如節點Nd5就與{Nd2，Nd3，Nd4}這三個節點建立連接。這三個節點都是Nd5的鄰居節點。網絡中節點ES為邊緣服務器(Edge Server)，CDN將客戶端所需點播的內容先放在ES上。與ES直接相連的節點可以直接從ES那里獲得點播的內容，距離ES較遠的節點可以通過網絡中其他已經獲得相同內容的節點那里獲取文件。
3三種不同的消息發送技術比較
3．1WF技術發布
每個節點都維護一個鄰居節點集的表，表中包括該節點所有鄰居節點的地址。當一個節點收到一個內容發布包(ID為MsgID)后，如果該節點在之前一段時間RT(Reserved Time)內沒有收到ID為MsgID的同一個數據包，便向所有的鄰居節點廣播發布包。如果此節點在之前一段時間RT內已經收到ID為MsgID的同一個數據包，則忽略該包，不做任何操作。
WF技術的優點是實現最簡單，節點在內容發布的過程中不需要進行比較運算；缺點是在發布的過程中會有大量的重復發包，一個節點會多次收到同一個發布包，造成系統負荷在短時間內有波峰。RT的大小與網絡中的節點數目有關，RT取大于從ES開始發送數據包到網絡中最后一個節點接收到數據包的時間加上從一個節點傳送到下一個節點所需要的平均時間。網絡的規模越大，RT的取值也越大。
3.2WFES(Water Flooding Excluding to the Sender)技術發布
每個節點都維護一個鄰居節點集的表，表中包括該節點所有鄰居節點的地址。當一個節點收到一個內容發布包(ID為MsgID)后，如果該節點在之前一段時間RT內沒有收到ID為MsgID的同一個數據包，便向除給自己發送消息的節點之外的其他鄰居節點廣播發布包。如果此節點在之前一段時間RT內已經收到ID為MsgID的同一個數據包，則忽略該包，不做任何操作。例如當圖1中節點Nd4從Nd1接收到一個數據包后，因為可以肯定Nd1已經接收到該數據包，便只向其鄰居節點集{Nd1，Nd2，Nd5}中的{Nd2，Nd5}兩個節點廣播數據包。這樣每個節點向鄰居節點發送數據包的個數都比WF技術少1次，并且不影響發送的效果。
WFES技術發布的優點是實現簡單，發布包的內容也不需要附加其他數據內容；如果在對等網中有M個節點，每個節點平均與N個節點相鄰，在所有節點收到發布的內容的過程中至多需要進行M×N次比較運算，與WF技術相比少傳送M次重復的包。缺點是WFES技術在發布過程中仍然會有大量的重復發包，一個節點會多次收到同一個發布包，造成系統負荷在短時間內有波峰，但效率優于WF技術。
3.3WFESN(Water Flooding Excluding to the Sender and its Neighbors)技術發布
當需要從ES向每一個節點發布內容時，ES會先向與它相連的節點發送數據包。當一個節點收到一個內容發布包(ID為MsgID)后，如果該節點在之前一段時間RT內沒有收到ID為MsgID的同一個數據包，便從自己的鄰居節點集中除去向自己發送數據的節點，然后除去在向自己發送數據的節點的鄰居節點中也存在的那些節點，然后向其他的節點廣播發布包。如果此節點在之前一段時間RT內已經收到ID為MsgID的同一個數據包，則忽略該包，不做任何操作。例如當圖1中節點Nd4從Nd1接收到一個數據包后，因為可以肯定Nd1已經接收到該數據包，在Nd4接收到數據包的同時，Nd1的其他鄰居節點{Nd2，Nd3，Nd4}也都收到數據包，所以在Nd4的鄰居節點集{Nd1，Nd2，Nd5}中{Nd1，Nd2}都已經接收到了數據包，便只向其鄰居節點集{Nd1，Nd2，Nd5}中的{Nd5}節點發送數據包。這樣每個節點向鄰居節點發送數據包的個數都比WF技術和WFES技術少，并且不影響未接收到數據節點的接收效果。
WFESN技術的優點是可以避免許多重復發送，減輕廣播時系統的總負荷。因為一個節點不需要給向它發送數據包的節點發，并且此源節點的相鄰節點也收到了數據包，考慮到在組網過程中往往是按照距離的遠近或者跳數的多少進行組網的。對該節點而言，向它發送數據包的節點的鄰居節點往往也是自己的鄰居節點，所以減少了向這些已經收到發布數據的節點重復發送數據的次數。其缺點是在發布的過程中，每個節點都要進行多次的比較運算，需要維護的鄰居節點信息的內容也比前兩種技術多。但對網絡發送的效率有很大的提高。
3．4三種技術的性能比較
在圖2的仿真實驗中，每個節點與距離最近的四個節點相連，改變網絡中節點的個數進行實驗。從仿真的結果可以看出，內容發布的效率與網絡中節點的數目沒有關系，一旦確定每個節點和距離其最近節點連接的個數，內容發布的效率保持不變。其中WF技術的效率最低，只有五分之一。也就是說在WF技術下，網絡中每五次數據傳輸過程中，僅僅有一次是有效的傳輸，其他四次都是往一個節點發布重復的內容，造成很大的浪費。WFES技術與WF技術相比，每個節點在發送數據時少發送一次，效率有所提高，但提高的量比較少。使用WFESN技術使發送效率有了很大提高。
保持網絡的規模不變，網絡中節點的總數為1 000個，改變每個節點的鄰居節點個數。當節點主動連接的節點個數從3~9時，從圖3可以看出，仿真的結果表明三種技術的效率都與節點主動連接的個數有緊密的關系。每個節點主動連接的節點個數越多，每個節點的鄰居節點數也越多，每個節點向鄰居節點廣播的次數就增加，單個節點重復收到同一個包的概率增加，發送的效率下降，且下降的速度與連接節點的個數近似反比關系。這樣帶來的一個好處在于網絡中鏈路的冗余大，當有部分鏈路或節點不能正常工作時，仍有很多的備用鏈路可以把數據包傳送到相應的節點。另外發送的效率也與網絡中具體的拓撲結構有關。
仿真的結果還表明，三種發送技術對節點首次收到數據包的延遲是相同的。因為WFES和WFESN技術只是減少了在網絡中向已經收到數據的節點的重復發送，對那些未曾收到數據的節點沒有影響。
(3)WFESN技術。其發送效率受網絡的拓撲結構影響很大。當網絡中任意一個節點到ES的最短路徑唯一時，如圖4所示，網絡中發送數據包的效率為1，沒有節點重復收到數據包。當網絡中任意一個節點到ES的最短路徑不唯一時，發送的效率小于1。
從圖5中可以看出，仿真結果與理論的上界還有一定的距離，主要是由于在實際仿真系統中沒有做到每個節點都與相鄰的Num個節點相連；相連節點的個數往往大于Num，造成在系統中有更多的冗余發送過程。在每種方式的信息發布過程中有更多的數據包經過不同的鏈路發送，重復發送的次數增加，最后導致仿真結果中實際發送的效率小于理論分析值。
4結束語
通過仿真表明WF、WFES和WFESN三種技術在緊急消息的發布中具有同樣的延遲，能夠達到相同的發布范圍。理論上三種方法數據包總能經過最短的距離到達每一個接收的節點，當距離短的鏈路發生阻塞或者延遲過長時才有可能發生經過非最短距離的鏈路上傳送的數據包先到達節點。在發送效率方面，WF技術的效率最低，網絡中存在大量重復發送的消息；WFES比WF技術在效率上有所改善；WFESN發送的效率遠遠高于上述兩種技術的發送效率。WFESN發送技術節點需要的存儲量大于其他兩種技術；WF和WFES技術節點需要存儲的信息相同。WFESN技術計算量最大；WF技術需要節點的計算量最小。考慮到能夠降低整個網絡在短時間內的峰值負荷，WFESN技術仍是這三種技術中最優的。
無線P2P已經在很多場合付諸實踐，WFESN技術可以經過修改應用到無線P2P網絡中的信息發布。因為無線P2P網絡中的節點具有移動性，網絡的拓樸結構和節點的鄰居節點隨時都可能發生變化，用于維護節點關系的代價太大，固定地保存鄰居節點的信息存儲方式不適合無線P2P網絡。此時WFESN技術在每個節點僅保留自己鄰居節點集的信息，但是節點在向鄰居節點發送廣播消息的同時把自己的鄰居節點集的信息附加到發送的數據包中，接收的節點收到數據包后從中解出發送節點的鄰居節點集，刪除數據包中的鄰居節點集的信息，把自己的鄰居節點集的信息附加到數據包中向目的節點發送。這樣減輕了維護網絡中節點位置移動造成的拓撲結構變化的代價，仍達到與WFESN相同的發送效率。
參考文獻：
［1］中國信息產業網—人民郵電報. 當前互聯網技術發展趨勢分析[EB/OL].（2004－09－02). http://tech.sina.com.cn/i/w/2004－09－02/1102417315.shtml.
［2］DOUGLIS F， KASSHOEK M F. Scalable Internet services [J]. IEEE Internet Computing，2001，5（4）：36－37.
［3］VAKALI A，PALLIS G. Content delivery networks: status and trends[J]. IEEE Internet Computing，2003，7(6):68－69.
［4］CRANOR C D， GREEN M， et al. Enhanced streaming services in a content distribution network[J].IEEE Internet Computing， 2001，5(4):66－67.
［5］ABERER K， PUNCEVA M. Improving data access in P2P systems[J]. IEEE Internet Computing， 2001，5(4):58－62.
［6］LIENHART R， HOLLIMAN M， et al. Improving media services on P2P networks [J]. IEEE Internet Computing，2002， 6(1):73－74.
［7］謝勇均. P2P模式的流媒體服務技術[J]. 現代電視技術，2004(7): 63－65.
［8］夏啟志， 謝高崗. 無結構網絡搜索方法及其改進[J]. 計算機應用研究，2005，22(9): 256－260.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
