基于事件空間劃分的高效發布訂閱路由算法

摘要：傳統的逆向路徑轉發的路由效率是O(N)，基于事件空間劃分的貪婪路由技術將效率提高到O(N1/d)。在此基礎上，采用祖先隊列的路由數據結構，建立虛擬層疊網絡中不同路由域之間的相鄰關系，并通過祖先隊列記錄域間代理的相鄰關系，實現了分層分路由域的代理之間的分級跨跳路由，稱為Spanhop路由。通過性能分析表明，使用該路由算法，路由的平均路徑減少到O(ln N)，同時取消了事件空間維度d對路由效率的影響。這種方法通過增加少量的存儲代價，提高了在大規模的面向廣域網的發布訂閱系統當中的路由效率。

關鍵詞：分布式系統;路由;發布訂閱;二叉樹

中圖分類號：TP393．2文獻標志碼：A

文章編號：1001－3695(2007)07－0238－04

0引言

目前，面向廣域網絡的基于內容發布訂閱系統成為分布式通信領域研究的熱點[1~3]，成為路由技術發布訂閱系統研究的核心問題[4]。當前路由技術主要分為泛洪法、匹配優先(Match－First Routing，MFR)和基于多播群組三種[4，5]。泛洪法主要應用于局域發布訂閱系統，如Tibco[6]。MFR是一種優于泛洪的路由，它基于事件內容與過濾狀態的匹配結果確定路由下一跳，限制事件的泛洪。其主要優化策略是限制拓撲結構和改進路由算法。Siena[2]是應用MFR的典型系統，其拓撲為無環圖，并采用RPF(Reverse Path Forwarding)的路由算法。MFR建立狀態簡單，不考慮狀態建立的預處理過程，其平均路徑增長率是O(N)，但路由更新和維護代價高，限制了網絡的可伸縮特性[5]。

基于多播群組的路由是群組劃分技術和路由技術的組合。文獻[8，9]對劃分技術作了研究(也稱為數據聚類技術)，但是沒有給出具體的路由算法。基本思想是將邏輯空間劃分為不同的區域，即群組，將區域委派給代理網絡中相應的代理。路由是兩階段路由的組合，即發布者到區域代理的發布路由和區域代理到訂閱者通知路由。當訂閱者數量較大時，在通知路由階段可以采用多播路由優化路由的性能，其優點是:提高了路由效率、路由表簡單、取消了過濾器優化操作[5]。

文獻[5，6]對基于多播群組的路由算法進行了研究。但文獻[5]將群組假定為單個主題，限定網絡拓撲是固定配置的有限個路由網絡，研究更側重于路由負載均衡；文獻[6]限制了網絡的拓撲結構為層次結構，其路由實際上是通過群組劃分機制優化了MFR算法;文獻[4]對其他典型系統的路由策略進行了概述。

本文主要研究在基于事件空間劃分和更具通用性的網狀拓撲基礎上，優化發布訂閱路由效率。主要的貢獻在于:①基于K－D樹的劃分算法，提出了一種Spanhop路由算法;②提出了一種祖先隊列的路由數據結構；③提出了相關路由更新和維護策略;④給出了Spanhop路由性能分析。

參考文獻：

［1］EUGSTER P T，FELBER P，GUERRAOUI R，et al.The many faces of publish/subscribe[J].ACM Computing Surveys，2003，35(2):114－131.

[2]CARZANIGA A，ROSENBLUM D，WOLF A. Design and evaluation of a wide－area notification service[J].ACM Transactions on Computer Systems，2001，19(3):332－383.

[3]PIETZUCH P，BACON J.Hermes:a distributed event－based middleware architecture[C]//Proc of the 1st International Workshop on Distributed Event－Based Systems(DEBS’02).Washington:IEEE Computer Society，2002:611－618.

[4]薛濤， 馮博琴.內容發布訂閱系統路由算法和自配置策略研究[J].軟件學報，2005，16(2):251－259.

[5]CAO F，JASWINDER P S.Efficient event routing in content－based publish－subscribe service networks[C]//Proc of IEEE INFOCOM 2004.Piscataway:Institute of Electrical and Electronics Engineers Inc.，2004:929－940.

[6]WANG Y M， QIU L，ACHLIOPTAS D，et al .Subscription partitioning and routing in content－based publish/subscribe networks[C]//Proc of the 16th International Symposium on Distributed Computing.Berlin: Springer－Verlag， 2002:28－30.

[7]OKI B， PFLUEGEL M， SIEGEL A，et al.The information bus：an architecture for extensive distributed systems[J].ACM SIGOPS Ope－rating Systems Review，1993，27(5):58－68.

[8]RIABOV A，LIU Zhen，WOLF J，et al.Clustering algorithms for content－based publication－subscription systems[C]//Proc of the 22nd International Conference on Distributed Computing Systems (ICDCS’02) [C]. Berlin: Springer－Verlag， 2002:133－142.

[9]RIABOV A，LIU Zhen，WOlF J，et al.New algorithms for content－based publication subscription systems[C]//Proc of the 23rd International Conference on Distributed Computing Systems (ICDCS’03).Berlin: Springer－Verlag，2002:133－142.

[10]BENTLEY J L.Multidimensional binary search trees used for associative searching[J].Communication of the ACM， 1975，18(9):509－517.

[11]RATNASAMY S， FRANCIS P， HANDLEY M，et al.A scalable content－addressable network[J].ACM SIGCOMM Computer Communication Review，2001，31(4):161－172.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”