Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Vitis: A Gossip-based Hybrid Overlay for Internet-scale Publish/Subscribe Enabling Rendezvous Routing in Unstructured Overlay Networks
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101). Swedish Institute of Computer Science (SICS), Stockholm.
Swedish Institute of Computer Science (SICS), Stockholm. (LCN)ORCID iD: 0000-0003-4516-7317
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101). Swedish Institute of Computer Science (SICS), Stockholm.
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101). Swedish Institute of Computer Science (SICS), Stockholm.ORCID iD: 0000-0002-6718-0144
2011 (English)In: Proceedings - 25th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2011, 2011, 746-757 p.Conference paper, Published paper (Refereed)
Abstract [en]

Peer-to-peer overlay networks are attractive solutions for building Internet-scale publish/subscribe systems. However, scalability comes with a cost: a message published on a certain topic often needs to traverse a large number of uninterested (unsubscribed) nodes before reaching all its subscribers. This might sharply increase resource consumption for such relay nodes (in terms of bandwidth transmission cost, CPU, etc) and could ultimately lead to rapid deterioration of the system's performance once the relay nodes start dropping the messages or choose to permanently abandon the system. In this paper, we introduce {\em Vitis}, a gossip-based publish/subscribe system that significantly decreases the number of relay messages, and scales to an unbounded number of nodes and topics. This is achieved by the novel approach of enabling rendezvous routing on unstructured overlays. We construct a hybrid system by injecting structure into an otherwise unstructured network. The resulting structure resembles a navigable small-world network, which spans along clusters of nodes that have similar subscriptions. The properties of such an overlay make it an ideal platform for efficient data dissemination in large-scale systems. We perform extensive simulations and evaluate Vitis by comparing its performance against two base-line publish/subscribe systems: one that is oblivious to node subscriptions, and another that exploits the subscription similarities. Our measurements show that Vitis significantly outperforms the base-line solutions on various subscription and churn scenarios, from both synthetic models and real-world traces

Place, publisher, year, edition, pages
2011. 746-757 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-92088DOI: 10.1109/IPDPS.2011.75Scopus ID: 2-s2.0-80053271646ISBN: 978-1-61284-372-8 (print)OAI: oai:DiVA.org:kth-92088DiVA: diva2:511999
Conference
25th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2011. Anchorage, AK. 16 May 2011 - 20 May 2011
Funder
ICT - The Next Generation
Note

QC 20120327

Available from: 2012-03-26 Created: 2012-03-26 Last updated: 2014-05-19Bibliographically approved
In thesis
1. Gossip-based Algorithms for Information Dissemination and Graph Clustering
Open this publication in new window or tab >>Gossip-based Algorithms for Information Dissemination and Graph Clustering
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Decentralized algorithms are becoming ever more prevalent in almost all real-world applications that are either data intensive, computation intensive or both. This thesis presents a few decentralized solutions for large-scale (i) data dissemination, (ii) graph partitioning, and (iii) data disambiguation. All these solutions are based on gossip, a light weight peer-to-peer data exchange protocol, and thus, appropriate for execution in a distributed environment.

For efficient data dissemination, we make use of the publish/subscribe communication model and provide two distributed solutions, one for topicbased and one for content-based subscriptions, named Vitis and Vinifera respectively. These systems propagate large quantities of data to interested users with a relatively low overhead. Without any central coordinator and only with the use of gossip, we build a novel topology that enables efficient routing in an unstructured overlay. We construct a hybrid system by injecting structure into an otherwise unstructured network. The resulting structure resembles a navigable small-world network that spans along clusters of nodes that have similar subscriptions. The properties of such an overlay make it an ideal platform for efficient data dissemination in large-scale systems. Our solutions significantly outperforms their counterparts on various subscription and churn scenarios, from both synthetic models and real-world traces.

We then investigate how gossiping protocols can be used, not for overlay construction, but for operating on fixed overlay topologies, which resemble graphs. In particular we study the NP-Complete problem of graph partitioning and present a distributed partitioning solution for very large graphs. This solution, called Ja-be-Ja, is based on local search and does not require access to the entire graph simultaneously. It is, therefore, appropriate for graphs that can not even fit into the memory of a single computer. Once again gossip-based algorithms prove efficient as they enable implementing light-weight peer sampling services, which supply graph nodes with partial knowledge about other nodes in the graph. The performance of our partitioning algorithm is comparable to centralized graph partitioning algorithms, and yet it is scalable and can be executed on several machines in parallel or even in a completely distributed peer-to-peer overlay. It can be used for both edge-cut and vertex-cut partitioning of graphs and can produce partition sizes of any given distribution.

We further extend the use of gossiping protocols to find natural clusters in a graph instead of producing a given number of partitions. This problem, known as graph community detection, has extensive application in various fields and communities. We take the use of our community detection algorithm to the realm of linguistics and address a well-known problem of data disambiguation. In particular, we provide a parallel community detection algorithm for cross-document coreference problem. We operate on graphs that we construct by representing documents’ keywords as nodes and the co-location of those keywords in a document as edges. We then exploit the particular nature of such graphs, which is coreferent words are topologically clustered, and thus, can be efficiently discovered by our community detection algorithm.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2014. x, 22 p.
Series
TRITA-ICT-ECS AVH, ISSN 1653-6363 ; 14:09
National Category
Computer Systems
Identifiers
urn:nbn:se:kth:diva-145361 (URN)978-91-7595-108-9 (ISBN)
Public defence
2014-05-22, Sal/Hall D, KTH - ICT, Isafjordsgatan 39, Kista, 13:00 (English)
Opponent
Supervisors
Note

QC 20140519

Available from: 2014-05-19 Created: 2014-05-19 Last updated: 2014-05-19Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Haridi, Seif

Search in DiVA

By author/editor
Rahimian, FatemehGirdzijauskas, SarunasPayberah, Amir H.Haridi, Seif
By organisation
Software and Computer Systems, SCS (Closed 20120101)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 75 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf