A Gossiping Protocol for Detecting Global Threshold Crossings
2010 (English)In: IEEE Transactions on Network and Service Management (TNSM), Vol. 7, no 1, 42-57 p.Article in journal (Refereed) Published
We investigate the use of gossip protocols for the detection of network-wide threshold crossings. Our design goals are low protocol overhead, small detection delay, low probability of false positives and negatives, scalability, robustness to node failures and controllability of the trade-off between overhead and detection delay. Based on push-synopses, a gossip protocol introduced by Kempe et al., we present a protocol that indicates whether a global aggregate of static local values is above or below a given threshold. For this protocol, we prove correctness and show that it converges to a state with no overhead when the aggregate is sufficiently far from the threshold. Then, we introduce an extension we call TG-GAP, a protocol that (1) executes in a dynamic network environment where local values change and (2) implements hysteresis behavior with upper and lower thresholds. Key elements of its design are the construction of snapshots of the global aggregate for threshold detection and a mechanism for synchronizing local states, both of which are realized through the underlying gossip protocol. Simulation studies suggest that TG-GAP is efficient in that the protocol overhead is minimal when the aggregate is sufficiently far from the threshold, that its overhead and the detection delay are largely independent on the system size, and that the tradeoff between overhead and detection quality can be effectively controlled. Lastly, we perform a comparative evaluation of TG-GAP against a tree-based protocol. We conclude that, for detecting global threshold crossings in the type of scenarios investigated, the tree-based protocol incurs a significantly lower overhead and a smaller detection delay than a gossip protocol such as TG-GAP.
Place, publisher, year, edition, pages
IEEE , 2010. Vol. 7, no 1, 42-57 p.
Distributed monitoring, threshold detection, gossip protocol
Computer Systems Communication Systems Telecommunications
IdentifiersURN: urn:nbn:se:kth:diva-86051DOI: 10.1109/TNSM.2010.I9P0329ScopusID: 2-s2.0-77249131803OAI: oai:DiVA.org:kth-86051DiVA: diva2:500379
© 2010 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
QC 201202152012-02-152012-02-132012-03-22Bibliographically approved