Araneola: A scalable reliable multicast system for dynamic environments ?
This paper presents Araneola (Araneola means little spider in Latin.), a scalable reliable application-level multicast system for highly dynamic wide-area environments. Araneola supports multi-point to multi-point reliable communication in a fully distributed manner, while incurring constant load (in terms of message and space complexity) on each node. For a tunable parameter k?3 k ? 3 , Araneola constructs and dynamically maintains a basic overlay structure in which each nodes degree is either k k or k+1 k + 1 , and roughly 90% of the nodes have degree k k . Empirical evaluation shows that Araneolas basic overlay achieves three important mathematical properties of k k -regular random graphs (i.e.,random graphs in which each node has exactly k k neighbors) with N N nodes: (i) its diameter grows logarithmically with N N ; (ii) it is generally k k -connected; and (iii) it remains highly connected following random removal of linear-size subsets of edges or nodes. The overlay is constructed and maintained at a low cost: each join, leave, or failure is handled locally, and entails the sending of only about 3k 3 k messages in total, independent of N N . Moreover, this cost decreases as the churn rate increases. The low degree of Araneolas basic overlay structure allows for allocating plenty of additional bandwidth for specific application needs. In this paper, we give an example for such a need  communicating with nearby nodes; we enhance the basic overlay with additional links chosen according to geographic proximity and available bandwidth. We show that this approach, i.e.,a combination of random and nearby links, reduces the number of physical hops messages traverse without hurting the overlays robustness, as compared with completely random Araneola overlays (in which all the links are random) with the same average node degree. Given Araneolas overlay, we sketch out several message dissemination techniques that can be implemented on top of this overlay. We present a full implementation and evaluation of a gossip-based multicast scheme, with up to 10,000 nodes. We show that compared with a (non-overlay-based) gossip-based multicast protocol, gossiping over Araneola achieves substantial improvements in load, reliability, and latency.
c.2.4 [computer-communication networks] distributed systemsdistributed applications