Technical report detail

Probabilistic FIFO Ordering in Publish/Subscribe Networks

by A. Malekpour, A. Carzaniga, G. Toffetti Carughi, F. Pedone

In a best-effort publish/subscribe network, publications may be delivered out of order (e.g., violating FIFO order). We contend that the primary cause of such ordering violations is the parallel matching and forwarding process employed by brokers to achieve high throughput. In this paper, we present an end-to-end method to improve event ordering. The method involves the receiver (and minimally the sender) and otherwise uses the broker network as a black box. The idea is to analyze the dynamics of the network, and in particular to measure the delivery delay and its variation, which is directly related to out-of-order delivery. With these measures, receivers can determine a near-optimal latch time to defer message delivery upon the detection of a hole in the message sequence number. We evaluate the performance of this ordering scheme empirically in terms of the reduction in out-of-order deliveries, the delay imposed by the latch time, and its self-adjustment with variable network conditions and input loads.

Technical report 2011/04, March 2011

BibTex entry

@techreport{11probabilistic, author = {A. Malekpour and A. Carzaniga and G. Toffetti Carughi and F. Pedone }, title = {Probabilistic FIFO Ordering in Publish/Subscribe Networks}, institution = {University of Lugano}, number = {2011/04}, year = 2011, month = mar }