摘要
随着网络技术的发展以及人们对信息共享的需求的不断增长，产生了很多基于数据分发的应用。这些应用的共同需求是将数据源动态产生的各种数据在动态的网络环境中快速准确地分发至有着不同需求的用户群体。因此，这些应用对数据分发技术提出了两种要求：具有适应动态网络环境的鲁棒性、能够快速准确地分发数据。特别对于紧急事件管理、网络中心战以及分布式社交网络服务等应用而言，其网络环境的动态性对数据分发技术的鲁棒性提出了更高的要求。已有的数据分发应用根据用户兴趣的表达形式大致可以分为基于内容的数据分发、基于主题的数据分发以及面向社交网络的数据分发三类，本文围绕在动态网络环境中实现高鲁棒性的数据分发这一目标分别针对基于内容的、基于主题的以及面向社交网络的数据分发技术展开深入研究。
针对已有的基于内容的数据分发方法缺少对数据分发效率与鲁棒性充分权衡的问题，本文提出了一种基于自组织语义覆盖网的基于内容的数据分发方法——SemanticCast，用以实现动态网络环境中高效的基于内容的数据分发。SemanticCast通过节点间的邻居交换维护一个自组织的语义覆盖网Crowd。在Crowd中，每个节点在周期性地交换邻居的过程中尽可能保留与自己兴趣更相似的邻居。通过节点的这些自组织行为，由兴趣相似节点构成的没有明确边界的各种兴趣簇在覆盖网中涌现。SemanticCast在兴趣簇间利用随机行走路由数据，在匹配的兴趣簇内利用泛洪分发数据。实验结果表明，相对于已有方法，SemanticCast能够在不可靠和动态的网络环境中实现更加高效的基于内容的数据分发，而且SemanticCast还具有强大的自修复能力，即使在大量节点瞬时失效的情况下SemanticCast也能迅速恢复正常工作。
针对已有的基于主题的数据分发方法缺少对数据分发效率与鲁棒性充分权衡的问题，本文提出了一种基于混合式覆盖网的基于主题的数据分发方法——Laurel，用以实现动态网络环境中高效的基于主题的数据分发。Laurel根据兴趣对节点进行分簇以减少不必要的数据分发，通过在簇间采用结构化拓扑以实现高效的数据路由，同时通过在簇间采用多重连接及在簇内采用非结构化拓扑以保证较高的鲁棒性。Laurel首先利用簇间结构化拓扑引导数据路由至对其感兴趣的簇，然后再在簇内利用泛洪或gossip的方式将数据分发至所有感兴趣的节点。实验结果表明，相对于基于结构化簇间拓扑的方法，Laurel保证在簇间路由效率相同的同时具有显著更强的鲁棒性，相对于基于非结构化的簇间及簇内拓扑的方法，Laurel则保证在鲁棒性没有显著差距的同时具有显著更高的簇间路由效率，而且Laurel还具有较好的簇内负载平衡效果。
针对已有的基于主题的数据分发方法在单个节点主题数相对较多的情况下开销较大难以扩展的问题，本文提出了一种主题采样引导的基于主题的数据分发方法——TopicCast，用以实现动态网络环境中可扩展的基于主题的数据分发。TopicCast可以分为两个相对独立的部分：基于gossip的主题采样方法TopicSampler以及轻量级的主题连通覆盖网构建维护方法TopicGraph。TopicSampler通过基于gossip的节点采样服务实现对不同主题节点的比例估计并据此为每个节点维护一个主题采样表，主题采样表中包含了对不同主题节点的均匀随机采样。与此同时，TopicGraph利用节点采样服务提供的节点采样周期性地更新每个节点的邻居列表，试图以尽可能小的开销保证具有相同主题的节点及其之间的边构成的所有子图都是连通的（即主题连通）。TopicCast首先利用主题采样表引导数据路由至对其感兴趣的任意节点，然后再基于兴趣匹配的主题连通子图将数据分发至所有感兴趣的节点。理论分析与实验结果表明，TopicSampler能够在动态网络环境中实现较高精度的主题比例估计和近似均匀随机的主题采样，TopicGraph能够在动态网络环境中以较小的存储与通讯开销维护主题连通覆盖网，因而相对于已有方法，TopicCast不仅能够在动态网络环境中实现高效的基于主题的数据分发，而且还具有更好的可扩展性。
针对已有的面向社交网络的分布式数据分发方法要么缺乏应对高度动态的网络环境的鲁棒性要么不能实现集中式社交网络服务提供的数据分发功能的问题，本文提出了一种面向社交网络的P2P数据分发方法——PeerChatter，用以实现面向社交网络的鲁棒高效的分布式数据分发。PeerChatter维护一个基于多层随机图拓扑的覆盖网SkipCluster，而代表社交网络用户的节点基于SkipCluster彼此连接。SkipCluster各层间的规则关系使得SkipCluster能够支持高效的路由，而SkipCluster层内动态维护的随机图拓扑则保证了高度的鲁棒性。在SkipCluster的基础上，PeerChatter利用基于主题的发布/订阅模式实现了同步及异步组播，以支持社交网络用户向自己的友邻及所属群组分发数据。理论分析与实验结果表明，PeerChatter的路由性能能够达到甚至超过典型结构化拓扑的水平，而且在节点剧烈波动以及大量节点瞬时失效的情况下，PeerChatter仍然能保持较高的数据分发可靠性及效率，因而PeerChatter能够满足面向社交网络的分布式数据分发的要求。
With the development of networking technology and the growth of demand forsharing information, many distributed applications based on data distribution aredeveloped. The common demand of these applications is to distribute various datagenerated dynamically by sources to users with different interests rapidly and accuratelyin dynamic network environments. Therefore, two features of the data distributionapproach—the robustness against the dynamic network environment and the abilityof distributing data efficiently—are simultaneously demanded. As for the applicationssuch as emergency management, network-centric warfare and decentralized socialnetworking service, higher robustness is especially needed due to the dynamicity oftheir network environments. According to the different ways the users expressing theirinterests, the existing data distribution approaches can be approximately divided intothree types: content-based approaches, topic-based approaches and approaches oversocial networks. This dissertation deeply studies the techniques for content-based datadistribution, topic-based data distribution and data distribution over social networks inorder to realize highly robust data distribution in the dynamic network environment.
Since the existing content-based data distribution approaches mainly lack ofbalance between efficiency and robustness, this dissertation proposes a content-baseddata distribution approach over self-organizing semantic overlay networks—SemanticCast—to realize the efficient content-based data distribution in the dynamicnetwork environment. SemanticCast maintains a self-organizing semantic overlaynetwork based on view exchange, called Crowd, in which, each node tries to retain theneighbors with more similar interests during the periodical view exchange. Through thisself-organizing behavior of nodes, various interest clusters, which are constituted by thenodes with similar interests and have no clear boundaries, emerge in the overlaynetwork. Over Crowd, SemanticCast adopts random walk to route data between interestclusters, and adopts flooding to disseminate data inside the interested cluster. Theexperimental results reveal that compared with existing approaches, SemanticCastrealizes more efficient content-based data distribution in the unreliable and dynamicnetwork environment. What’s more, the strong self-healing ability of SemanticCast canmake it recover from the major network disaster quickly.
Since the existing topic-based data distribution approaches lack of balance betweenefficiency and robustness, this dissertation proposes a topic-based data distributionapproach over hybrid overlay networks—Laurel—to realize the efficienttopic-based data distribution in the dynamic network environment. Laurel organizesnodes into clusters according to their interests to reduce the unnecessary data dissemination. It adopts the structured inter-cluster topology to route data efficiently,and adopts multiple connections between clusters and unstructured topologies insideclusters to ensure robustness. Laurel firstly routes data to the interested cluster by thestructured inter-cluster topology, and then disseminates data inside the interested clusterby flooding or gossip. The experimental results reveal that compared with theapproaches based on the structured inter-cluster topology, Laurel ensures evidentlyhigher robustness along with the same inter-cluster routing efficiency, and comparedwith the approaches based on the unstructured inter-and intra-cluster topology, Laurelensures evidently higher efficiency for inter-cluster routing along with the comparativerobustness. At the same time, better load balance within clusters is achieved.
Under the circumstance of a single node having relatively large numbers of topics,the existing topic-based data distribution approaches cost a lot and fail to work well.Therefore, this dissertation proposes a topic-based data distribution approach based ontopic sampling—TopicCast—to realize the scalable topic-based data distribution inthe dynamic network environment. TopicCast consists of two relatively independentcomponents: a gossip-based topic sampling approach TopicSampler and a lightweighttopic-connected overlay network protocol TopicGraph. TopicSampler firstly estimatesthe proportions of nodes with various topics through the peer sampling service based ongossip, and then uses the estimated proportions to maintain each node’s topic samplingtable, where the nodes with different topics occur randomly under the same probability.Meanwhile, TopicGraph updates each node’s neighbor list periodically by using nodesamples provided by the peer sampling service, and tries to ensure the connectivity ofeach subgraph induced by the nodes with the same topic (called topic-connected) at alow cost. TopicCast firstly directs data to any interested node by the topic samplingtable, and then disseminates data to all interested nodes over the matchingtopic-connected subgraph. Both of the theoretical and experimental results reveal thatTopicSampler can achieve precise proportion estimation and approximately uniformrandom topic sampling in the dynamic network environment, and TopicGraph canensure topic-connectivity of the overlay network with low storage and communicationcost in the dynamic network environment, which means that TopicCast not only realizesthe efficient topic-based data distribution in the dynamic network environment but alsohas better scalability compared with existing approaches.
The existing decentralized data distribution approaches over social networks eitherlack of robustness against the highly dynamic network environment or the ability toimplement the data distribution function provided by centralized social networkingservices. This dissertation proposes a P2P data distribution approach over socialnetworks—PeerChatter—to realize the robust and efficient decentralized datadistribution over social networks. PeerChatter maintains an overlay network based on multi-level random graphs, called SkipCluster. The nodes represent users in the socialnetwork are organized into SkipCluster. The regular relation between levels enablesSkipCluster to support efficient routing, and the randomness inside the levels ensureshigh robustness against node churn. Over SkipCluster, PeerChatter adopts thetopic-based publish/subscribe model to realize the synchronous and asynchronousmulticast for data distribution between friends and inside groups. Both of the theoreticaland experimental results reveal that PeerChatter’s routing performance achieves andeven exceeds the one of the typical structured topology, and PeerChatter ensures highreliability and efficiency of data distribution in the network environment with a veryhigh node churn or a major network disaster, which means that the demand of thedecentralized data distribution over social networks can be satisfied.
引文
[1]中国互联网络信息中心(CNNIC).第27次中国互联网络发展状况统计报告
[EB/OL].http://www.cnnic.net.cn/dtygg/dtgg/201101/P020110119328960192287.pdf,2011.
[2] Earthquake Early Warning [OL].http://www.jma.go.jp/jma/en/Activities/eew.html,2011.
[3] Shakecast [OL]. http://earthquake.usgs.gov/research/software/shakecast,2011.
[4] National Incident Management System [OL].http://www.fema.gov/emergency/nims/,2011.
[5] U.S Department of Homeland Security. National Incident Management System
[EB/OL]. http://www.fema.gov/pdf/emergency/nims/NIMS_core.pdf,2011.
[6] Network Centric Warfare [OL].http://www.dodccrp.org/html4/research_ncw.html,2011.
[7] Paxson V. End-to-End Internet Packet Dynamics [C]. In: Proc. of SIGCOMM’97.Cannes, France:1997.
[8] Jain M, Dovrolis C. End-to-End Available Bandwidth: MeasurementMethodology, Dynamics, and Relation with Tcp Throughput [C]. In: Proc. ofSIGCOMM’02. New York: ACM,2002.295-308.
[9] Dahlin M, Chandra B B, Gao L, et al. End-to-End Wan Service Availability [J].IEEE/ACM Trans. Netw.2003,11(2):300-313.
[10] Paxson V. End-to-End Routing Behavior in the Internet [J]. ACM SIGCOMMComputer Communication Review.2006,36(5):41-56.
[11] Boyd D M, Ellison N B. Social Network Sites: Definition, History, andScholarship [J]. Journal of Computer-Mediated Communication.2008,13(1):210-230.
[12] Weaver A C, Morrison B B. Social Networking [J]. IEEE Computer.2008,41(2):97-100.
[13] Facebook [OL]. http://www.facebook.com,2011.
[14] Twitter [OL]. http://www.twitter.com,2011.
[15] Saroiu S, Gummadi P K, Gribble S D. Measuring and Analyzing theCharacteristics of Napster and Gnutella Hosts [J]. Multimedia Syst.2003,9(2):170-184.
[16] Sen S, Wang J. Analyzing Peer-to-Peer Traffic Across Large Networks [J].IEEE/ACM Transactions on Networking.2004,12(2):219-232.
[17] Steiner M, En-najjary T, Biersack E W. Long Term Study of Peer Behavior in theKad DHT [J]. IEEE/ACM Trans. Netw.2009,17(5):1371-1384.
[18] Benevenuto F, Rodrigues T, Cha M, et al. Characterizing User Behavior inOnline Social Networks [C]. In: Proc. of the9th ACM SIGCOMM Conference onInternet Measurement (IMC’09). Chicago, Illinois, USA: New York: ACM,2009.49-62.
[19] Gyarmati L, Trinh T A. Measuring User Behavior in Online Social Networks [J].IEEE Network.2010,24(5):26-31.
[20] Clark D. Face-to-Face with Peer-to-Peer Networking [J]. IEEE Computer.2001,34(1):18-21.
[21] Schoder D, Fischbach K. Peer-to-Peer Prospects [J]. Communications of theACM.2003,46(2):27-29.
[22] Androutsellis-theotokis S, Spinellis D. A Survey of Peer-to-Peer ContentDistribution Technologies [J]. ACM Computing Surveys.2004,36(4):335-371.
[23] Cohen B. Incentives Build Robustness in BitTorrent [C]. In: Proc. of FirstWorkshop on Economics of Peer-to-Peer Systems. Berkeley, USA:2003.
[24] Gnutella [OL]. http://rfc-gnutella.sourceforge.net/,2011.
[25] Clarke I, Sandberg O, Wiley B, et al. Freenet: A Distributed AnonymousInformation Storage and Retrieval System [C]. In: Proc. of Int’l Workshop onDesign Privacy Enhancing Technologies. Berkeley, California, USA: New York:Springer-Verlag,2001.46-66.
[26] KaZaA [OL]. http://www.kazaa.com,2011.
[27] eMule [OL]. http://www.emule.org,2011.
[28] Ratnasamy S, Shenker S, Stoica I. Routing Algorithms for DHTs: Some OpenQuestions [C]. In: Proc. of First International Workshop on Peer-to-Peer Systems(IPTPS’02). Cambridge, USA:2002.
[29] Balakrishnan H, Kaashoek M F, Karger D, et al. Looking Up Data in P2PSystems [J]. Communications of the ACM.2003,46(2):43-48.
[30] Eastlake D, Jones P. Rfc3174-US Secure Hash Algorithm1(SHA1)[EB/OL].http://www.faqs.org/rfcs/rfc3174.html,2011.
[31] Rivest R. Rfc1321-The MD5Message-Digest Algorithm [EB/OL].http://www.faqs.org/rfcs/rfc1321.html,2011.
[32] Stoica I, Morris R, Liben-nowell D, et al. Chord: A Scalable Peer-to-Peer LookupProtocol for Internet Applications [J]. IEEE/ACM Transactions on Networking.2003,11(1):17-32.
[33] Ratnasamy S, Francis P, Handley M, et al. A Scalable Content-AddressableNetwork [C]. In: Proc. of the2001Conf. on Applications, Technologies,Architectures, and Protocols for Computer Communications (SIGCOMM’01).San Diego, California, United States: New York: ACM,2001.161-172.
[34] Rowstron A, Druschel P. Pastry: Scalable, Distributed Object Location andRouting for Large-Scale Peer-to-Peer Systems [C]. In: Proc. of IFIP/ACMMiddleware’01. Heidelberg, Germany:2001.329-350.
[35] Zhao B Y, Huang L, Stribling J, et al. Tapestry: A Resilient Global-Scale Overlayfor Service Deployment [J]. IEEE Journal on Selected Areas in Communications(JSAC).2004,22(1):41-53.
[36] Vakali A, Pallis G. Content Delivery Networks: Status and Trends [J]. IEEEInternet Computing.2003,7(6):68-74.
[37] Peng G. Cdn: Content Distribution Network [R]. Technical Report, TR-125,Experimental Computer Systems Lab in Stony Brook University,2004.
[38] Pallis G, Vakali A. Insight and Perspectives for Content Delivery Networks [J].Communications of the ACM.2006,49(1):101-106.
[39] Pathan A K, Buyya R. A Taxonomy and Survey of Content Delivery Networks
[R]. Technical Report, GRIDS-TR-2007-4, The University of Melbourne,2007.
[40] Jamin S, Jin C, Jin Y, et al. On the Placement of Internet Instrumentation [C]. In:Proc. of IEEE INFOCOM2000Conference. Tel-Aviv, Israel:2000.295-304.
[41] Qiu L, Padmanabhan V N, Voelker G M. On the Placement of Web ServerReplicas [C]. In: Proc. of IEEE INFOCOM2001Conference. Anchorage, Alaska,USA:2001.
[42] Bartal Y. Probabilistic Approximation of Metric Space and its AlgorithmicApplications [C]. In: Proc. of37th Annual IEEE Symposium on Foundations ofComputer Science.1996.
[43] Jamin S, Jin C, Kurc A R, et al. Contrained Mirror Placement on the Internet [C].In: Proc. of IEEE INFOCOM2001Conference. Anchorage, Alaska, USA:2001.
[44] Radoslavov P, Govindan R, Estrin D. Topology-Informed Internet ReplicaPlacement [C]. In: Proc. of Sixth International Workshop on Web Caching andContent Distribution. Boston, Massachusetts, USA:2001.
[45] Fujita N, Ishikawa Y, Iwata A, et al. Coarse-Grain Replica ManagementStrategies for Dynamic Replication of Web Contents [J]. Computer Networks:The International Journal of Computer and Telecommunications.2004,45(1):19-34.
[46] Chen Y, Qiu L, Chen W, et al. Efficient and Adaptive Web Replication UsingContent Clustering [J]. IEEE Journal on Selected Areas in Communications.2003,21(6):979-994.
[47] Kangasharju J, Roberts J, Ross K W. Object Replication Strategies in ContentDistribution Networks [J]. Computer Communications.2002,25(4):367-383.
[48] Akamai [OL]. http://www.akamai.com,2011.
[49] Mirror Image [OL]. http://www.mirror-image.com,2011.
[50] Freedman M J, Freudenthal E, Mazieres D. Democratizing Content Publicationwith Coral [C]. In: Proc. of1st USENIX/ACM Symposium on NetworkedSystems Design and Implementation. San Francisco, CA, USA:2004.
[51] Wall D W. Mechanisms for Broadcast and Selective Broadcast [D]. Ph.D. Thesis,Stanford University,1980.
[52] Deering S, Cheriton D. Multicast Routing in Datagram Internetworks andExtended LANs [J]. ACM Trans. Comp. Syst.1990,8(2):85-100.
[53] Deering S E. Multicast Routing in a Datagram Internetwork [D]. Ph.D. Thesis,Stanford University,1991.
[54] Deering S, Estrin D, Farinacci D, et al. The PIM Architecture for Wide-AreaMulticast Routing [J]. IEEE/ACM Trans. Networking.1997:784-803.
[55] Yeo C K, Lee B S, Er M H. A Survey of Application Level Multicast Techniques[J]. Computer Communications.2004,27(15):1547-1568.
[56]章淼,徐明伟,吴建平.应用层组播研究综述[J].电子学报.2004,32(12A):22-25.
[57] Yeo C K, Lee B S, Er M H. A Framework for Multicast Video Streaming over IPNetworks [J]. J. Networks Comput. Applic.2003,26(3):273-289.
[58] Pendarakis D, Shi S, Verma D, et al. ALMI An Application Level MulticastInfrastructure [C]. In: Proc. of the Third Usenix Symposium on InternetTechnologies and Systems (USITS).2001.
[59] Helder D A, Jamin S. End-Host Multicast Communication Using Switch-TreeProtocols [C]. In: Proc. of the2nd Workshop on Global and Peer-to-PeerComputing on Large Scale Distributed Sys.(GP2PC2002).2002.
[60] Zhang B, Jamin S, Zhang L. Host Multicast: A Framework for DeliveringMulticast to End Users [C]. In: Proc. of INFOCOM’02.2002.
[61] Banerjee S, Kommareddy C, Kar K, et al. Construction of an Efficient OverlayMulticast Infrastructure for Real-Time Applications [C]. In: Proc. ofINFOCOM’03.2003.
[62] Jannotti J, Gifford D K, Johnson K L, et al. Overcast: Reliable Multicasting withan Overlay Network [C]. In: Proc. of Operating Systems Design andImplementation (OSDI).2000.
[63] Mathy L, Canonico R, Hutchison D. An Overlay Tree Building Control Protocol
[C]. In: Proc. of the Third International Workshop on Networked GroupCommunication (NGC).2001.
[64] Castro M, Druschel P, Kermarrec A, et al. Splitstream: High-Bandwidth ContentDistribution in Cooperative Environments [C]. In: Proc. of the19th ACMSymposium on Operating System Principles.2003.
[65] Padmanabhan V N, Wang H J, Chou P A. Resilient Peer-to-Peer Streaming [C].In: Proc. of the11th ICNP. Atlanta, Georgia, USA:2003.
[66] Chu Y, Rao S G, Seshan S, et al. A Case for End System Multicast [J]. IEEE J.Select. Areas Commun.2002,20(8):1456-1471.
[67] Jain S, Mahajan R, Wetherall D, et al. A Comparison of Large-Scale OverlayManagement Techniques [R]. Technical Report, UV-CSE02-02-02, University ofWashington,2002.
[68] Chawathe Y D. Scattercast: An Architecture for Internet Broadcast Distributionas an Infrastructure Service [D]. Ph.D. Thesis, Stanford University,2000.
[69] Venkataraman V, Yoshida K, Francis P. Chunkyspread: HeterogeneousUnstructured Tree-Based Peer-to-Peer Multicast [C]. In: Proc. of the14th IEEEInternational Conference on Network Protocols (ICNP’06).2006.
[70] Kostic D, Rodriguez A, Albrecht J, et al. Bullet: High Bandwidth DataDissemination Using an Overlay Mesh [C]. In: Proc. of Usenix Symposium onOperating Systems Principles (SOSP).2003.
[71] Yoid: Your Own Internet Distribution [OL]. http://www.isi.edu/div7/yoid/,2011.
[72] Ratnasamy S, Handley M, Karp R, et al. Application-Level Multicast UsingContent Addressable Networks [C]. In: Proc. of the Third International Workshopon Networked Group Communication (NGC’01).2001.
[73] Zhuang S Q, Zhao B Y, Joseph A D, et al. Bayeux: An Architecture for Scalableand Fault-Tolerant Wide-Area Data Dissemination [C]. In: Proc. of the11th Intl.Workshop on Network and Operating Sys. Support for Digital Audio and Video(NOSSDAV2001).2001.
[74] Castro M, Druschel P, Kermarrec A, et al. Scribe: A Large-Scale andDecentralized Application-Level Multicast Infrastructure [J]. IEEE J. Select.Areas Commun.2002,20(8):100-110.
[75] Zhang J, Liu L, Ramaswamy L, et al. PeerCast: Churn-Resilient End SystemMulticast on Heterogeneous Overlay Networks [J]. Journal of Network andComputer Applications.2008,31(4).
[76] Eugster P T, Guerraoui R, Kermarrec A, et al. Epidemic InformationDissemination in Distributed Systems [J]. IEEE Computer.2004,37(5):60-67.
[77] Kermarrec A, van Steen M. Gossiping in Distributed Systems [J]. ACM SIGOPSOperating Systems Review.2007,41(5):2-7.
[78] Eugster P T, Guerraoui R, Handurukande S B, et al. Lightweight ProbabilisticBroadcast [C]. In: Proc. of IEEE Int’l Conf. Dependable Systems and Networks(DSN2001).2001.
[79] Jelasity M, Kowalczyk W, van Steen M. Newscast Computing [R]. TechnicalReport, IR-CS-006, Department of Computer Science, Vrije Universiteit,Amsterdam,2003.
[80] Voulgaris S, Gavidia D, van Steen M. CYCLON: Inexpensive MembershipManagement for Unstructured P2P Overlays [J]. Journal of Network and SystemsManagement.2005,13(2):197-217.
[81] Jelasity M, Voulgaris S, Guerraoui R, et al. Gossip-Based Peer Sampling [J].ACM Transactions on Computer Systems (TOCS).2007,25(3): Article No.8.
[82] Pereira J, Rodrigues L, Monteiro M J, et al. NEEM: Network-Friendly EpidemicMulticast [C]. In: Proc. of IEEE Intl. Symp. on Reliable Distributed Systems(SRDS’2003).2003.
[83] Zhang X, Liuy J, Liz B, et al. CoolStreaming/DONet: A Data-Driven OverlayNetwork for Efficient Live Media Streaming [C]. In: Proc. of IEEEINFOCOM’05.2005.
[84] Zhang M, Luo J, Zhao L, et al. A Peer-to-Peer Network for Live MediaStreaming Using a Push-Pull Approach [C]. In: Proc. of the13th Annual ACMInternational Conference on Multimedia (MM’05). New York: ACM,2005.287-290.
[85] Deshpande M, Xing B, Lazardis I, et al. CREW: A Gossip-BasedFlash-Dissemination System [C]. In: Proc. of ICDCS’06.2006.
[86] Papadimitriou A, Delis A. Flash Data Dissemination in Unstructured Peer-to-PeerNetworks [C]. In: Proc. of the37th International Conference on ParallelProcessing (ICPP’08).2008.
[87] Eugster P T, Felber P A, Guerraoui R, et al. The Many Faces ofPublish/Subscribe [J]. ACM Computing Surveys.2003,35(2):114-131.
[88]马建刚,黄涛,汪锦岭等.面向大规模分布式计算发布订阅系统核心技术[J].软件学报.2006,17(1):134-147.
[89] Baldoni R, Virgillito A. Distributed Event Routing in Publish/SubscribeCommunication Systems: A Survey [R]. Technical Report,15-05, Universita diRoma,2005.
[90] Baldoni R, Beraldi R, Quema V, et al. TERA: Topic-Based Event Routing forPeer-to-Peer Architectures [C]. In: Proc. of the2007Inaugural Int’l Conf. onDistributed Event-Based Systems (DEBS’07). Toronto, Ontario, Canada: NewYork: ACM,2007.
[91] Chockler G, Melamed R, Tock Y, et al. SpiderCast: A Scalable Interest-AwareOverlay for Topic-Based Pub/Sub Communication [C]. In: Proc. of the2007Inaugural Int’l Conf. on Distributed Event-Based Systems (DEBS’07). Toronto,Ontario, Canada: New York: ACM,2007.
[92] Cugola G, di Nitto E, Fuggetta A. The JEDI Event-Based Infrastructure and itsApplication to the Development of the Opss Wfms [J]. IEEE Transactions onSoftware Engineering.2001,27(9):827-850.
[93] Zhao Y, Sturman D, Bhola S. Subscription Propagation in Highly-AvailablePublish/Subscribe Middleware [C]. In: Proc. of Middleware’04.2004.274-293.
[94] Carzaniga A, Rosenblum D S, Wolf A L. Design and Evaluation of a Wide-AreaEvent Notification Service [J]. ACM Transactions on Computer Systems.2001,19(3):332-383.
[95] Pietzuch P, Bacon J. Hermes: A Distributed Event-Based MiddlewareArchitecture [C]. In: Proc. of the International Workshop on DistributedEvent-Based Systems (DEBS’02).2002.
[96] Eugster P T. Type-Based Publish/Subscribe [D]. Ph.D. Thesis, EPFL,2001.
[97] Myspace [OL]. http://www.myspace.com,2011.
[98]豆瓣网[OL]. http://www.douban.com,2011.
[99]人人网[OL]. http://www.renren.com,2011.
[100]开心网[OL]. http://www.kaixin001.com,2011.
[101] Hua C, Mao Y, Jinqiang H, et al. Maze: A Social Peer-to-Peer Network [C]. In:Proc. of the2004IEEE International Conference on E-Commerce Technology forDynamic E-Business. Los Alamitos, CA, USA:2004.290-293.
[102] Pouwelse J A, Garbacki P, Wang J, et al. Tribler: A Social-Based Peer-to-PeerSystem [J]. Concurr. Comput.: Pract. Exper.2008,20(2):127-138.
[103] Buchegger S, Schi D, Vu L, et al. PeerSoN: P2P Social Networking—EarlyExperiences and Insights [C]. In: Proc. of the Second ACM EuroSys Workshopon Social Network Systems (SNS’09). New York: ACM,2009.46-52.
[104] Cutillo L A, Molva R, Strufe T. Safebook: Feasibility of Transitive Cooperationfor Privacy on a Decentralized Social Network [C]. In: Proc. of IEEEInternational Symposium on World of Wireless, Mobile and MultimediaNetworks (WoWMoM’09).2009.
[105] Kumar R, Novak J, Tomkins A. Structure and Evolution of Online SocialNetworks [C]. In: Proc. of the12th ACM SIGKDD International Conference onKnowledge Discovery and Data Mining (KDD’06). New York: ACM,2006.611-617.
[106] Ahn Y, Han S, Kwak H, et al. Analysis of Topological Characteristics of HugeOnline Social Networking Services [C]. In: Proc. of the16th InternationalConference on World Wide Web (WWW’07). Banff, Alberta, Canada: New York:ACM,2007.835-844.
[107] Mislove A, Marcon M, Gummadi K P, et al. Measurement and Analysis of OnlineSocial Networks [C]. In: Proc. of the7th ACM SIGCOMM Conference onInternet measurement (IMC’07). New York: ACM,2007.
[108] Kwak H, Lee C, Park H, et al. What is Twitter, a Social Network or a NewsMedia?[C]. In: Proc. of the19th International Conference on World Wide Web(WWW’10). New York: ACM,2010.
[109] Watts D J, Strogatz S H. Collective Dynamics of ‘Small-World’ Networks [J].Nature.1998,393:440-442.
[110] Albert R, Baraba A. Statistical Mechanics of Complex Networks [J]. Reviews ofModern Physics.2002,74:48-94.
[111] Jovanovic M, Annexstein F S, Berman K A. Modeling Peer-to-Peer NetworkTopologies through “Small-World” Models and Power Laws [C]. In: Proc. of theIX. Telecommunications Forum TELFOR2001. Belgrade, Yugoslavia:2001.
[112] Maymounkov P, Mazieres D. Kademlia: A Peer-to-Peer Information SystemBased on the XOR Metric [C]. In: Proc. of IPTPS’02.2002.
[113] Plaxton C G, Rajaraman R, Richa A W. Accessing Nearby Copies of ReplicatedObjects in a Distributed Environment [C]. In: Proc. of SPAA’97.1997.
[114] Harvey N J A, Jones M B, Saroiu S, et al. SkipNet: A Scalable Overlay Networkwith Practical Locality Properties [C]. In: Proc. of the4th Conference onUSENIX Symposium on Internet Technologies and Systems (USITS’03). Seattle,WA, USA: Berkeley: USENIX Association,2003.9-9.
[115] Aspnes J, Shah G. Skip Graphs [J]. ACM Trans. Algorithms.2007,3(4):1549-6325.
[116] Pugh W. Skip Lists: A Probabilistic Alternative to Balanced Trees [J]. Commun.ACM.1990,33(6):668-676.
[117] Malkhi D, Naor M, Ratajczak D. Viceroy: A Scalable and Dynamic LookupNetwork [C]. In: Proc. of21st ACM Symposium on Principles of DistributedComputing (PODC). Monterey, CA, USA:2002.
[118] Kaashoek F, Karger D R. Koorde: A Simple Degree-Optimal Hash Table [C]. In:Proc. of2nd International Workshop on Peer-to-Peer Systems (IPTPS’03).Berkeley, CA, USA:2003.
[119] Shen H, Xu C, Chen G. Cycloid: A Constant-Degree and Lookup-Efficient P2POverlay Network [C]. In: Proc. of IPDPS’04.2004.
[120] Li D, Lu X, Wu J. FissionE: A Scalable Constant Degree and Low CongestionDHT Scheme Based on Kautz Graphs [C]. In: Proc. of IEEE INFOCOM’05.Miami, Florida, USA:2005.1677-1688.
[121] Nejdl W, Siberski W, Wolpers M, et al. Super-Peer-Based Routing and ClusteringStrategies for RDF-Based Peer-to-Peer Networks [C]. In: Proc. of WWW’03.2003.
[122]乔百友,王国仁,丁琳琳.TBSN:一种基于分类层次的P2P网络[J].计算机研究与发展.2008,45(5):803-809.
[123] Shin K, Lee S, Lim G, et al. Grapes: Topology-Based Hierarchical VirtualNetwork for Peer-to-Peer Lookup Services [C]. In: Proc. of InternationalConference on Parallel Processing Workshops (ICPPW2002).2002.
[124] Hsiao R, Wang S. Jelly: A Dynamic Hierarchical P2P Overlay Network withLoad Balance and Locality [C]. In: Proc. of24th International Conference onDistributed Computing Systems Workshops (ICDCSW2004).2004.
[125] Chen Y, Deng B, Li X. Canicula: An Improved Hybrid Overlay Networks [C]. In:Proc. of ICON2006.2006.
[126] Darlagiannis V, Mauthe A, Steinmetz R. Overlay Design Mechanisms forHeterogeneous, Large Scale, Dynamic P2P Systems [J]. Journal of Networks andSystem Management.2004,12(3):371-395.
[127] Garces-Erice L, Biersack E W, Felber P A, et al. Hierarchical Peer-to-PeerSystems [C]. In: Proc. of Euro-Par2003.2003.
[128] Yang M, Yang Y. An Efficient Hybrid Peer-to-Peer System for Distributed DataSharing [C]. In: Proc. of the22nd IEEE Int’l Symposium on Parallel andDistributed Processing (IPDPS’08). Miami, FL, USA: IEEE Computer Society,2008.
[129] Peng Z, Duan Z, Qi J, et al. HP2P: A Hybrid Hierarchical P2P Network [C]. In:Proc. of First International Conference on the Digital Society (ICDS2007).2007.
[130] Crespo A, Garcia-Molina H. Semantic Overlay Networks for P2P Systems [C]. In:Proc. of the3rd Int’l Workshop on Agents and Peer-to-Peer Computing (AP2PC2004). Berlin: Springer,2004.
[131] Loser A, Schubert K, Zimmer F. Taxonomy-Based Routing Overlays in P2PNetworks [C]. In: Proc. of IDEAS’04. Washington: IEEE Computer Society,2004.
[132] Voulgaris S, Kermarrec A, Massoulie L, et al. Exploiting Semantic Proximity inPeer-to-Peer Content Searching [C]. In: Proc. of the10th IEEE InternationalWorkshop on Future Trends of Distributed Computing Systems (FTDCS’04).2004.
[133] Ganesh A J, Kermarrec A, Massoulie L. Peer-to-Peer Membership Managementfor Gossip-Based Protocols [J]. IEEE Transactions on Computers.2003,52(2):139-149.
[134] Voulgaris S, van Steen M. Epidemic-Style Management of Semantic Overlays forContent-Based Searching [C]. In: Proc. of Euro-Par2005Parallel Processing(Euro-Par’05). Berlin: Springer,2005.
[135] Ganguly S, Bhatnagar S, Saxena A, et al. A Fast Content-Based Data DistributionInfrastructure [C]. In: Proc. of INFOCOM’06.2006.1-13.
[136] Costa P, Picco G P. Semi-Probabilistic Content-Based Publish-Subscribe [C]. In:Proc. of25th IEEE International Conference on Distributed Computing Systems(ICDCS’05). Washington: IEEE Computer Society,2005.
[137] Eugster P T, Guerraoui R. Probabilistic Multicast [C]. In: Proc. of IEEEInternational Conference on Dependable Systems and Networks (DSN2002).2002.
[138] Terpstra W W, Behnel S, Fiege L, et al. A Peer-to-Peer Approach toContent-Based Publish/Subscribe [C]. In: Proc. of DEBS03.2003.
[139]汪锦岭,金蓓弘,李京.结构化P2P网络上可靠的基于内容路由协议[J].软件学报.2006,17(5):1107-1114.
[140] Triantafillou P, Aekaterinidis I. Content-Based Publish-Subscribe over StructuredP2P Networks [C]. In: Proc. of DEBS2004. Edinburgh, Scotland, UK:2004.104-109.
[141] Gupta A, Sahin O D, Agrawal D, et al. Meghdoot: Content-BasedPublish/Subscribe over P2P Networks [C]. In: Proc. of Middleware.2004.
[142] Castelli S, Costa P, Picco G P. HyperCBR: Large-Scale Content-Based Routingin a Multidimensional Space [C]. In: Proc. of INFOCOM’08. Phoenix, AZ, USA:2008.
[143] Chand R, Felber P. Semantic Peer-to-Peer Overlays for Publish/SubscribeNetworks [C]. In: Proc. of Euro-Par2005Parallel Processing (Euro-Par’05).Berlin: Springer,2005.
[144] Anceaume E, Datta A K, Gradinariu M, et al. A Semantic Overlay for Self-*Peer-to-Peer Publish/Subscribe [C]. In: Proc. of ICDCS’06.2006.
[145] Voulgaris S, Riviere E, Kermarrec A, et al. Sub-2-Sub: Self-OrganizingContent-Based Publish Subscribe for Dynamic Large Scale CollaborativeNetworks [C]. In: Proc. of IPTPS’06.2006.
[146] Matos M, Nunes A, Oliveira R, et al. StAN: Exploiting Shared Interests withoutDisclosing them in Gossip-Based Publish/Subscribe [C]. In: Proc. of the9thInternational Conference on Peer-to-peer systems (IPTPS’10). Berkeley:USENIX Association,2010.
[147] Esposito C, Cotroneo D, Gokhale A. Reliable Publish/Subscribe Middleware forTime-Sensitive Internet-Scale Applications [C]. In: Proc. of the Third ACMInternational Conference on Distributed Event-Based Systems (DEBS’09). NewYork: ACM,2009.
[148] Baehni S, Eugster P T, Guerraoui R. Data-Aware Multicast [C]. In: Proc. of the2004International Conference on Dependable Systems and Networks (DSN2004).2004.233-242.
[149] Chockler G, Melamed R, Tock Y, et al. Constructing Scalable Overlays forPub-Sub with Many Topics [C]. In: Proc. of the Twenty-Sixth Annual ACMSymposium on Principles of Distributed Computing (PODC’07). New York:ACM,2007.
[150] Onus M, Richa A W. Minimum Maximum Degree Publish-Subscribe OverlayNetwork Design [C]. In: Proc. of INFOCOM’09.2009.882-890.
[151] Onus M, Richa A W. Parameterized Maximum and Average DegreeApproximation in Topic-Based Publish-Subscribe Overlay Network Design [C].In: Proc. of2010International Conference on Distributed Computing Systems(ICDCS’10). Genova, Italy:2010.
[152] Patel J A, Riviere E, Gupta I, et al. Rappel: Exploiting Interest and NetworkLocality to Improve Fairness in Publish-Subscribe Systems [J]. ComputerNetworks.2009,53(2009):2304-2320.
[153] Girdzijauskas S, Chockler G, Vigfusson Y, et al. Magnet: Practical SubscriptionClustering for Internet-Scale Publish/Subscribe [C]. In: Proc. of the Fourth ACMInternational Conference on Distributed Event-Based Systems (DEBS’10). NewYork: ACM,2010.
[154] Rahimian F, Girdzijauskas S, Payberah A H, et al. Vitis: A Gossip-Based HybridOverlay for Internet-Scale Publish/Subscribe [C]. In: Proc. of IPDPS’11.Anchorage, Alaska, USA:2011.
[155] Yeung C A, Liccardi I, Lu K, et al. Decentralization: The Future of Online SocialNetworking [C]. In: Proc. of W3C Workshop on the Future of Social Networking.2009.
[156] Wong B, Guha S. Quasar: A Probabilistic Publish-Subscribe System for SocialNetworks [C]. In: Proc. of the7th International Conference on Peer-to-PeerSystems (IPTPS’08). Berkeley: USENIX Association,2008.2-2.
[157]肖明忠,代亚非.Bloom Filter及其应用综述[J].计算机科学.2004,31(4):180-183.
[158] OpenDHT [OL]. http://www.opendht.org,2011.
[159] Mani M, Nguyen A, Crespi N. SCOPE: A Prototype for Spontaneous P2P SocialNetworking [C]. In: Proc. of the8th IEEE International Conference on PervasiveComputing and Communications Workshops (PERCOM Workshops).2010.220-225.
[160] Bamboo [OL]. http://www.bamboo-dht.org,2011.
[161] Abbas A, Hales D, Pouwelse J, et al. A Gossip-Based Distributed SocialNetworking System [R]. Technical Report, PDS-2009-001, Delft University ofTechnology,2009.
[162] PeerSim [OL]. http://peersim.sourceforge.net/,2011.
[163] Jelasity M, Montresor A, Babaoglu O. Gossip-Based Aggregation in LargeDynamic Networks [J]. ACM Transactions on Computer Systems.2005,23(3):219-252.
[164] Bollobas B. Random Graphs [M].2nd ed. Cambridge University Press,2001.
[165] Demers A, Greene D, Hauser C, et al. Epidemic Algorithms for ReplicatedDatabase Maintenance [C]. In: Proc. of the6th Annual ACM Symposium onPrinciples of Distributed Computing. Vancouver, British Columbia, Canada: NewYork: ACM,1987.1-12.
[166] Karp R, Schindelhauer C, Shenker S, et al. Randomized Rumor Spreading [C]. In:Proc. of the41st Annual Symposium on Foundations of Computer Science.2000.