On the benefit of network coding for timely and reliable event dissemination in WAN
Christian Esposito, Stefano Russo Dipartimento di Informatica e Sistemistica (DIS)
Universit´a degli studi di Napoli “Federico II”
via Claudio 21, 80125 - Napoli, Italy {christian.esposito, sterusso}@unina.it
Roberto Beraldi, Marco Platania Dipartimento di Informatica e Sistemistica (DIS)
Universit´a degli studi di Roma “La Sapienza”
via Ariosto 25, 00185 - Roma, Italy {beraldi, platania}@dis.uniroma.it
Abstract—Many interoperable software systems atop of large- scale critical infrastructures are based on the publish/subscribe paradigm. They are developed using data dissemination mid- dleware services, which are required to provide reliability and timeliness in multicast communications. The literature of event dissemination and the market of publish/subscribe middleware technologies are rich of solutions; however, they hardly achieve the goal of providing fault-tolerance without violating the time- liness requirements.
In this paper we present an analysis of the related work on this topic and propose an approach for combining two different approaches, namely coding and gossiping, able to satisfy timeliness and reliability requirements, respectively. We evaluate the potential benefit of coding on the information delivery performance, even when the sender introduces a redundancy to improve reliability.
Keywords-Publish/Subscribe Middleware; Forward Error Cor- rection; Gossiping
I. INTRODUCTION
With the increasing use of the Internet, we are noticing a growing trend in developing applications over Wide Area Networks (WAN). Typical examples are Large-scale Complex Critical Infrastructures(LCCIs), such as Air Traffic Control (ATC) systems, financial infrastructure, stock market, business intelligence, that federate geographically-distributed systems in a “system of systems” manner. A key element in the design of such infrastructures is the event dissemination service used to convey data over a WAN. Due to its implicit decoupling properties, which are suitable for satisfying the scalability requirements exhibited by large-scale infrastructures, the pub- lish/subscribe paradigm is facing a growing interest in the design of LCCIs. However, the non-functional requirements of such infrastructures are not only limited to scalability, but, due to their critical nature, LCCIs also demand reliable and timely communications. This means that exchanged data have to be guaranteed to reach the interested destinations despite possible failures and that latency has to always be within strict temporal constraints.
The research community on publish/subscribe services has investigated proper methods to implement a reliable event dissemination, and several approaches, such as [1], [2], [3]
have been already proposed in the last decade. Most of such solutions to reliable event dissemination only focused on techniques to provide fault-tolerance by means of retransmis- sions, and any reliability improvement is always gained at the expenses of severe performance fluctuations. Therefore, such
techniques are not suitable for critical infrastructures where timeliness matters as much as fault-tolerance.
The work presented in this paper aims to fill this gap by proposing a strategy to achieve both reliability and timeliness in event dissemination performed by publish/subscribe services over the Internet. Since several works, such as [4], have showed that the Internet exhibits a non negligible probability to lose several messages in a row (bursty losses), and the analysis presented in [5] has proved that available reliable publish/sub- scribe services have paid less attention to handle losses, we have decided to focus our work on tolerating message losses.
To this aim, we have combined coding and gossiping, each known to be timely and reliable respectively, so to achieve the best from both. We consider a scenario where a source sends coded information to a set of destinations over Internet links that exhibit a non negligible probability to have bursty losses.
Then, destinations apply a gossiping strategy to recover from possible lost packets, with the possibility to exchange coded information, too. We evaluate the potential benefit of coding on the information delivery performance, even when the sender introduces redundancy to improve reliability. In particular, we evaluate the trade-off between redundancy overhead and gossiping rounds in order to fully reconstruct information while preserving timeliness.
The reminder of this paper is organized as follows: in Sec- tion II we discuss approaches available in the current literature of reliable publish/subscribe and multicasting, noticing that none of them are able to jointly provide fault-tolerance and timeliness. In Section III we motivate the use of coding as a mean to mitigate the performance fluctuations implied by the massive use of retransmissions by the gossiping protocols.
Section IV describes the proposed strategy to combine gos- siping and coding, and explains why coding is useful in data dissemination. In Section V we evaluate information delivery performance by means of a custom time-driven simulator; we also compare obtained results on reliability improvement in coding and no coding cases. Final Remarks are discussed in Section VI that concludes the paper.
II. RECOVERYSTRATEGIES
In our work, we have analyzed several recovery strategies for multicast services, which can be used within the context of publish/subscribe services, and Figure 1 provides a taxonomy of the described solutions. Due to limited space, in this paper we only provide a quick overview of such strategies, and discuss their pros and cons (the interested reader can refer to [6] for a more detailed description). Approaches for reliable
Figure 1: Classification of all the approaches available in the literature to tolerate dropped messages.
publish/subscribe services can be briefly grouped as follows:
(i) Automatic Repeat reQuest (ARQ); (ii) Forward Error Correction(FEC) and (iii) Path Redundancy.
ARQ schemes comprises approaches that detect any possible message omission due to the manifestation of some kinds of faults, and ask for a retransmission. Depending to the contacted node for retransmissions, we can have a further classification of the ARQ schemes [7]: sender-based, i.e., all the nodes always contact the multicaster; parent-based, i.e., a nodes always contacts its parent within the multicasting tree;
and neighbor-based, i.e., retransmission duties are distributed among any neighboring nodes. The last one is further divided in the following techniques:
1) Lateral Error Recovery (LER) [8]: all the nodes are randomly grouped in distinct planes, and node selects as its neighbor a certain node per each plane that is different than its own;
2) Cooperative Error Recovery (CER) [9]: nodes are clus- tered in groups whose members are characterized by a negligible loss correlation (i.e., if a node experiences a message loss, it is unlikely that all the nodes loose the same message), and a node selects its neighbors between the members of its group;
3) Gossiping [10]: a node stores a received message in a buffer with a size b, and forwards it a limited number of times t (called fanin) to a randomly-selected set of nodes of size f (called fanout). Many variants of gossiping algorithms exist [11]:
a) Push Approaches: messages are forwarded to the other nodes as soon as they are received;
b) Pull Approaches: nodes periodically send to other nodes a list of recently-received messages; if a lost message is detected by comparing the received list with the history of messages received by the given
message, then it makes an explicit pull request.
FEC schemes contains approaches based on the generation of additional information by encoding message content, so that lost data can be recovered by decoding all the packets received by the node. There are three different approaches, which differ from where the encoding is performed [12], [13]:
1) End-to-End FEC: encoding is done by the multicaster;
2) Link-by-Link FEC: every node in the overlay performs encoding and decoding, in order to protect the delivery on each link;
3) Selective Network-Embedded FEC: only a subset of nodes, which includes the multicaster, perform encoding.
The last group includes approaches based on path redundancy, where there is more than one link interconnecting two nodes.
Such redundancy can be used in two different manners. In the first case, there is a primary link to forward messages to an other node and back-up links to use in case the primary has experienced a loss. On the other hand, several copies of a given message can be sent using the redundant links. Since the first one is simply a form of distributed ARQ scheme, we have focused on the second kind of path redundancy, which can be realized by different approaches, depending on the organization of the nodes in a mesh or a tree. Mesh routing can implement path redundancy by choosing more that one neighbor node to communicate with or using swarning content delivery by combining push content reporting and pull content requesting [14]. On the other hand, in tree-based multicast services there are three alternative approaches [15]:
1) Cross-link: it consists of connecting random peers via extra cross-cutting links;
2) In-tree: extra links among different “families” of nodes are established in addition to the one between the parent and its children;
3) Multi-trees: multiple disjoint trees, namely forest, are formed among the members of a multicast group.
Figure 2 provides a graphical representation of the out- come of our study of the achievable quality, with respect to scalability, reliability and timeliness. In general, we can characterize the previous strategies as proactive or reactive.
The former (indicated by purple boxes in figure) actively sends out redundant packets by using spatial redundancy, which will help nodes to recover dropped packets at the moment of detection of the drop, without requiring any external recovery action. Concrete examples are FEC schemes that reconstruct lost information by using the received one. On the other hand, the reactive approaches (indicated by green boxes in figure) adopt temporal redundancy where a node that detects a loss is unable to resolve it and asks for lost packets to the other nodes. Practical examples are ARQ schemes, where the help provided by the other nodes consists of retransmissions.
From a close scrutiny of Figure 2, we can notice that there is no approach that exhibit the highest level in all the three quality aspects. If we consider only reliability and timeliness (respectively, lines in red and yellow), we notice that there is
Figure 2: Analysis of the quality of loss-tolerance for multicast services in terms of scalability, reliability and timeliness.
a clear separation between proactive and reactive approaches.
The first approaches exhibit a low and more stable recovery latency due to the loss resolution at the detection phase with informations already hold by the node, but the amount of redundancy needed to recover messages under any kind of failure load is hard to perfectly tune, so failing to provide perfect reliability has a not negligible probability. On the other hand, reactive approaches are easy to implement and they guarantee strong reliability properties due to the closed loop control between receivers and sources; however, they also present serious performance fluctuations when failure occurs. In fact, the delivery time is directly related to the number of retransmissions to successfully recover a dropped message, which depends on the network dynamics, known to be unpredictable and highly variable over time [16]. With respect to the scalability, distributed approaches obtain the highest score with the exception of LER, which require a detailed knowledge of the overall system topology, which is impractical for large scale systems.
Since none of the investigated approaches is jointly reliable and timely, we propose to apply a combination of proactive and reactive strategies to take advance of the best of both worlds, in a similar way as done for transport-level multicast by means of hybrid ARQ and FEC schemes [17]. Specifically, we have considered the use of gossiping as reactive approach, since it is the one exhibiting the highest quality, and FEC as proactive one (we will focus on end-to-end FEC, leaving application of more advanced approaches to future work).
Throughout the paper, we will consider three kinds of protocols: (i) gossip; (ii) coding, and (iii) gossip + coding.
III. NETWORKCODING: MOTIVATIONS
Network coding [18] is a technique that allows to convey the information content of n original packets, x1, x2, ...xn, as a set n linearly independent combinations (encoded packets) and to easily generate redundancy virtually for any lost packets by means of linear combinations of business data. Each linear
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
1 2 3 4 5 6 7 8 9
Probability a packet is useful
Number of missed chunks
no coding q=2 q=4 q=8 q=16 q=32 q=64 q=128 q=256
Figure 3:Probability of an additional random chunk of data is useful as a function of the missed chunks for n = 10.
combination is given by yi=
n
X
i=1
cixi
where coefficients ci are taken uniformly at random over 0, ..., q − 1, but the all zero coefficients case being excluded.
All operations are performed over the Galois Field GF (2w), with 2w = q. Each coded packets yi is equipped with the coefficients ci used to produce that packet and that will be used by destinations in the decoding phase.
Our proposed protocol exploits a distributed recovery mech- anism that allows a destination node to pull the missed information content from other nodes. To get a better insight of the benefit of coding on this recovery operation let us compare a recovery protocol that uses coding against a plain protocol.
First of all, the power of network coding with respect to a plain data dissemination is particularly evident when a node introduces a redundancy. Let us consider two different cases:
• a node sends n + a encoded packets, with a < n, generated as previously described;
• a node sends n + a plain packets, with a < n.
Now let us consider a receiver that receives just n0 out of the n packets (i.e., n − n0 packets have been dropped by the network); in addition, it receives all redundant packets, such that the total number of received packets is l ≥ n + a. In case of coding, if coefficients ci are independent, then any of the a additional packets can be useful to fully reconstruct the information. On the contrary, without coding, the a packets could be just a copy of the n0 packets; in this case, the redundancy is not useful to reconstruct the whole information.
This characteristic of network coding also allows a node to generate redundancy (i.e., linear combinations) even if it has received just a partial information.
Hence, the reason why coding is expected to highly improve a gossip based recovery protocol has its root in the following simple property. Consider the n-dimensional vector space V over a Galois Field with base q, namely GF (q). The number of elements in V is qn− 1, i.e., it is given by the number of ways we can multiply a base of V with n coefficients, excluding the all zero cases. For the same reason, a k-dimensional V ’s subspace Vk has qk− 1 elements. Hence the ratio between the number of elements in Vk and the number of elements in Vn is qqkn−1−1 ≈ qn−k1 . This is also the probability that a random
issemination
Recovery
Plain Data Coded Data
Figure 4:Simplified ALM topology that directly connects the sender to all destinations.
vector of V belongs to Vk.
Now, consider the case when a single event E is divided into n chunks of data, which are transmitted to a set of destinations using different overlay channels. Suppose that, due to packet losses, a destination gets k out of the n packets, i.e., the destination has missed m = n − k packets. For reconstructing the whole event the destination starts to retrieve the missed m packets through a simple gossip mechanism consisting in contacting another destination and pulling one random packet from it.
If the packets are sent without coding and assuming the contacted destination experienced an independent packet loss pattern, the probability that the pulled packet is useful is clearly
m
n = 1 − nk. However, if the source node sends random linear combinations of the original packets, then, due to the aforementioned property, the probability that the pulled linear combination is independent from the already received ones is the the probability that the pulled linear combinations does not belong to Vk, i.e., ≈ 1 − q−m. Figure 3 shows the probability as a function of m for n = 10, q = 8 in the two cases (coding and no coding).
While in the no coding case this probability increases linearly with the number of missed chunks m, under a coding scheme the probability increases exponentially. In addition, for the coding case the probability to retrieve the last chunk is as small as 1 − q−1 and can then be made very close to one by setting q to some convenient value, i.e., q = 1024. It is also worth noticing that, under our independence assumption, the problem of retrieving the m missed chunks is the classical Coupon Collector’s Problem [19], and, hence, the expected number of gossip rounds required to retrieve all the chunks is Θ(m log(m)), whereas using coding it is easy to see that the average number of rounds is Θ(m).
Finally, we remark that due to the linearity of the operations, encoded packet can also be obtained by linearly combining already encoded packets. This allows for intermediate nodes in a multicasting tree to add redundancy exploiting the partial information content received so far thus reducing the end to end delay.
Encoding
Decoding
Event(i) Complete?
Yes! No!
Not(2) Not(1)
. . . Not(N)
LOSS
Gossip(i)
Encoding
Not(2) Not(1)
. . . Not(N) LOSS
Decoding
Event(i) Complete?
STEP I
STEP II
Complete?
Yes!
Yes!
Figure 5: Protocol schema. Note that at the second Complete operation (the one with *), if the data has not been completely recovered, another gossiping round has to be issued.
IV. PROPOSEDPROTOCOL
We consider the system model illustrated in Figure 4, where a multicaster is directly connected to several destinations. Such interconnection can be concretely implemented by means of an Application Level Multicast (ALM), by building a tree rooted at the multicaster, where each destination can be both a leaf node or even an interior node within the tree.
The protocol we propose combines coding and gossiping for timely and reliable data dissemination in WAN. It consists of two steps, as depicted in Figure 5:
1) the sender application passes to the publisher the event (indicated in figure as Event(i)) to be disseminated. The publisher fragments the event in K packets and sends them to all destinations as notifications (indicated in figure as Not(i)). In particular, as illustrated in figure, the publisher does not only forward the packets with the business data received from the application, but is also constructs N − K additional coded packets as the linear combination of the previous K packets, that represent the redundancy of the original message. This redundancy is also sent to all destinations, as evident is figure.
0 0.2 0.4 0.6 0.8 1
0 2 4 6 8 10 12 14 16
Success rate
Redundancy degree coding no coding
Figure 6: Comparison on reliability im- provement between coding and no coding cases by varying the redundancy degree.
0 0.2 0.4 0.6 0.8 1
0 1 2 3 4 5
Success rate
Number of rounds no coding, PLR=0.2, ABL=2
coding, PLR=0.2, ABL=2 no coding, PLR=0.3, ABL=3 coding, PLR=0.3, ABL=3
Figure 7:Impact of the number of gossiping rounds on success rate in coding and no cod- ing cases by varying the network conditions.
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 1 2 3 4 5
Success rate
Number of rounds no coding, fan out=1 no coding, fan out=2 no coding, fan out=3 coding, fan out=1 coding, fan out=2 coding, fan out=3
Figure 8: Effect of fanout on success rate in coding and no coding cases.
2) at receiver side, the subscriber collects all the notifica- tions related to a given event, and then applies a decoding action to obtain the original event. If the original event has not been completely reconstructed (i.e., there are some missing packets that prevent the decoding of that event), then the subscriber triggers a gossiping round.
In detail, the receiver tries to reconstruct the original event with the collected packets. If all the first K packets are received, then the information can be fully reconstructed; how- ever, if some of these packets are lost, the received additional one can be used to reconstruct the dropped ones. In general, if enough additional packets are received, then all the dropped business data can be successfully reconstructed and we can have the original event. In case such an event is available, it can be passed to the application, otherwise we have a drop that the coding failed to tolerate and gossiping has to be used, as illustrated in the lower part of Figure 5. There are different gossiping mode, as specified in the previous section; however, without loss of generality, we describe here a very simple one.
Specifically, the node selects randomly another node, or even more than one, to whom it asks the retransmission of the necessary data to obtain the original event; to this end, we assume the presence of a peer sampling service [20], [21]
that a node uses to obtain a random sample from the set of all destinations. If the contacted node has the requested information (as illustrated in figure), then it forwards the requested packets and their combinations; otherwise, it does not provide a response to the received request (not illustrated in figure). The gossiper then receives the additional packets provided by the contacted node and retries a decoding putting together these packets and the previous ones. Such decoding tentative can return the original notification (as illustrated in figure), which is passed to the application, otherwise, another gossip round has to be commenced (not illustrated in figure).
V. EXPERIMENTALRESULTS
In this section, we show a preliminary experimental analysis performed through a custom time-driven simulator. We eval- uate the success rate, i.e., the fraction of system nodes that fully recovers a message, where the system size is 100 nodes.
This value is the mean of 100 different publications, averaged on all nodes. The network failure model is defined in terms of:
(i) Packet Loss Rate (PLR), i.e., the rate at which packets are
dropped by the network; (ii) Average Burst Length (ABL), i.e., the number of consecutive packets dropped by the network.
Figure 6 compares the success rate in coding and no coding cases, by varying the number of redundancy packets. PLR and ABL are set to 0.2 and 2 respectively. We can see how coding exponentially improves the reliability by augmenting the number of redundant packets. This is direct consequence of the high probability for a linear combination to be independent from all the others.
Figure 7, instead, shows how reliability augments in pres- ence of gossip, with the PLR varying in the set {0.2; 0.3} and ABL in the set {2; 3}. In case of coding, 2 rounds are enough to fully recover the whole event. The figure thus confirms that coding is expected to improve the delay performance as a consequence of a less number of rounds required to get the missed packets in case of loss.
Finally, Figure 8 shows the effect of fan-out for PLR=0.2 and ABL=2. By Increasing the fan-out, a node pulls a larger amount of data per round, thus making a round more effective.
VI. FINALREMARKS
The inherent scalability provided by the publish/subscribe paradigm makes it appealing for the design of geographically distributed systems over wide area networks. However, the crit- ical nature of LCCIs requires that all information has to reach the interested destinations within strict temporal constraints.
Recently, researchers started to investigate how to improve reliability in publish/subscribe systems, but this improvement, often obtained through retransmission techniques, is typically gained at the expenses of performance penalties.
A. Lesson learnt
In this paper, we provided a strategy that combines coding and gossiping for reliable and timely data distribution over WAN. We conducted a simulation-based analysis to evaluate the potential benefit of coding on delivery performance, even when the sender introduces redundant information to improve reliability. We have observed that the introduction of coding is able to lower the number of retransmissions required to achieve a successful delivery of a given notification. This allows im- proving the timeliness guarantees of the dissemination protocol and reduce the dependency of the dissemination latency from the experienced network behaviour.
behavioural model by using the OMNET++ event simulator, and to experimentally assess the different styles of gossip- ing with our approach by varying the network conditions, and using network topologies similar to the one deployed in Internet. In addition, we are studying enhancements to our approach by introducing various adaptation means, i.e., customizing redundancy between root and destinations and among destinations to the experienced loss patterns or even introducing a biased gossip partner selection (destinations of a gossiping message are not randomly selected, but proper selection is introduced to improve the success rate).
ACKNOWLEDGMENT
This work has been partially supported by the Italian Min- istry for Education, University, and Research (MIUR) in the framework of the Project of National Research Interest (PRIN)
“DOTS-LCCI: Dependable Off-The-Shelf based middleware systems for Large-scale Complex Critical Infrastructures”, and by the BLEND Eurostar European Project.
REFERENCES
[1] P. Pietzuch and J. Bacon, “Hermes: A Distributed Event-Based Middleware Architecture,” Proceedings of 22nd International Conference on Distributed Computing Systems Workshops (ICD- CSW ’02), pp. 611–618, July 2002.
[2] S. Bhola, R. Strom, S. Bagchi, Z. Yuanyuan, and J. Auerbach,
“Exactly-once Delivery in a Content-based Publish-Subscribe System,” Proceedings of the IEEE International Conference on Dependable Systems and Networks (DSN 02), pp. 7–16, June 2002.
[3] R. Kazemzadeh and H.-A. Jacobsen, “Reliable and Highly Available Distributed Publish/Subscribe Service,” Proceedings of the 28th IEEE International Symposium on Reliable Dis- tributed Systems (SRDS 09), pp. 41–50, September 2009.
[4] A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C.-N.
Chuah, Y. Ganjali, and C. Diot, “Characterization of Failures in an Operational IP Backbone Network,” IEEE/ACM Transactions on Networking (TON), vol. 16, no. 4, pp. 749–762, August 2008.
[5] C. Esposito, D. Cotroneo, and A. Gokhale, “Reliable Publish/- Subscribe Middleware for Time-sensitive Internet-scale Appli- cations,” Proceedings of the 3rd ACM International Conference on Distributed Event-Based Systems (DEBS 09), July 2009.
[6] C. Esposito, “Reliable Event Dissemination for Time-Sensible Applications over Wide-Area Networks,” PhD Thesis, available at www.mobilab.unina.it/tesiDottorato.html, December 2009.
[7] X. Jin, W. P. K. Yiu, and S. H. G. Chan, “Loss Recovery in Application-Layer Multicast,” IEEE MultiMedia, vol. 15, no. 1, pp. 18–27, January 2008.
[8] W.-P. K. Yiu, K.-F. S. Wong, S.-H. G. Chan, W.-C. Wong, Q. Zhang, W.-W. Zhu, and Y.-Q. Zhang, “Lateral Error Cor- rection for Media Streaming in Application-Level Multicast,”
IEEE/ACM Transactions on Multimedia (T-MM), vol. 8, no. 2, pp. 219–232, April 2006.
[10] A.-M. Kermarrec, L-Massouli´e, and A. J. Ganesh, “Probabilistic Reliable Dissemination in Large-Scale Systems,” IEEE Trans- actions on Parallel and Distributed Systems (TPDS), vol. 14, no. 2, pp. 1–11, February 2003.
[11] A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry, “Epidemic algorithms for replicated database maintenance,” in Proceedings of the sixth annual ACM Symposium on Principles of distributed computing. ACM, 1987, pp. 1–12.
[12] M. Ghaderi, D. Towsley, and J. Kurose, “Reliability Gain of Network Coding in Lossy Wireless Networks,” Proceedings of the 27th Conference on Computer Communications (INFOCOM 08), pp. 2171–2179, April 2008.
[13] M. Wu, S. S. Karande, and H. Radha, “Network-embedded FEC for Optimum Throughput of Multicast Packet Video,” Journal on Signal Processing: Image Communication, vol. 20, no. 8, pp.
728–742, September 2005.
[14] N. Magharei and R. Rejaie, “PRIME: Peer-to-Peer Receiver- driven Mesh-based Streaming,” Proceedings of the 26th IEEE International Conference on Computer Communications (INFO- COM 07), pp. 1415–1423, May 2007.
[15] S. Birrer and F. Bustamante, “A Comparison of Resilient Overlay Multicast Approaches,” IEEE Journal on Selected Areas in Communications (JSAC), vol. 25, no. 9, pp. 1695–1705, December 2007.
[16] V. Paxson, “End-to-End Routing Behavior in the Internet,” ACM SIGCOMM Computer Communication Review, vol. 36, no. 5, pp. 41–56, October 2006.
[17] J. Nonnenmacher, E. W. Biersack, and D. Towsley, “Parity- Based Loss Recovery for Reliable Multicast Trasmission,”
IEEE/ACM Transactions on Networking (TON), vol. 6, no. 4, pp. 349–361, August 1998.
[18] C. Fragouli, J. Le Boudec, and J. Widmer, “Network coding:
an instant primer,” Computer Communication Review, vol. 36, no. 1, p. 63, 2006.
[19] P. Flajolet, D. Gardy, and L. Thimonier, “Birthday para- dox, coupon collectors, caching algorithms and self-organizing search,” Journal Discrete Applied Mathematics, vol. 39, no. 3, November 1992.
[20] M. Jelasity, S. Voulgaris, R. Guerraoui, A. Kermarrec, and M. Van Steen, “Gossip-based peer sampling,” ACM Transactions on Computer Systems, vol. 25, no. 3, p. 8, 2007.
[21] L. Massouli´e, E. Le Merrer, A. Kermarrec, and A. Ganesh,
“Peer counting and sampling in overlay networks: random walk methods,” in Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing. ACM, 2006, pp. 123–132.
