H-GAP: Estimating Histograms of Local Variables with Accuracy Objectives for Distributed Real-Time Monitoring
2010 (English)In: IEEE Transactions on Network and Service Management (TNSM), Vol. 7, no 2, 83-95 p.Article in journal (Refereed) Published
We present H-GAP, a protocol for continuous monitoring,which provides a management station with the valuedistribution of local variables across the network. The protocolestimates the histogram of local state variables for a givenaccuracy and with minimal overhead. H-GAP is decentralizedand asynchronous to achieve robustness and scalability, and itexecutes on an overlay interconnecting management processesin network devices. On this overlay, the protocol maintains aspanning tree and updates the histogram through incrementalaggregation. The protocol is tunable in the sense that it allowscontrolling, at runtime, the trade-off between protocol overheadand an accuracy objective. This functionality is realized throughdynamic configuration of local filters that control the flow ofupdates towards the management station. The paper includes ananalysis of the problem of histogram aggregation over aggregationtrees, a formulation of the global optimization problem, anda distributed solution containing heuristic, tree-based algorithms.Using SUM as an example, we show how general aggregationfunctions over local variables can be efficiently computed withH-GAP. We evaluate our protocol through simulation using realtraces. The results demonstrate the controllability of H-GAP ina selection of scenarios and its efficiency in large-scale networks.
Place, publisher, year, edition, pages
IEEE Communications Society, 2010. Vol. 7, no 2, 83-95 p.
Real-time monitoring, distributed aggregation, adaptive protocols
Computer Systems Communication Systems Telecommunications
IdentifiersURN: urn:nbn:se:kth:diva-86063DOI: 10.1109/T-WC.2008.I8P0292ScopusID: 2-s2.0-77952922715OAI: oai:DiVA.org:kth-86063DiVA: diva2:500387
© 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-132014-09-22Bibliographically approved