Adaptive, Robust, Real-time Monitoring for Large-scale Networks and Networked Systems - MONITORAcademic coordinator: Mads Dam (FM) Project leader: Dan Jurca (LCN) Other project members: Aurell (CB), Dam (FM), Johansson (CT), Stadler (LCN), Krishnamurthy (SICS, not funded by this project) SummaryThe objective of the MONITOR project is to study protocols and principles of information aggregation in large-scale and dynamic networks under strong performance, security, and real-time constraints. The primary application domain is distributed network management. A key function that a distributed management layer must provide is estimating aggregates of local variables in real time. Examples of aggregates include sums, averages, extremal values, percentiles and histograms of device counters, to provide management information concerning distribution of flows, node utilization, etc. The project will examine and compare various approaches to distributed information aggregation, propose new solutions where applicable, and evaluate them according to a range of criteria including accuracy, scalability, privacy, robustness to node and link failures, including both random (crash) failures, malicious failures, and node corruption, (self-) configurability, and tunability. Besides theoretical results, the outcome of the project will include new protocol designs, and experimental evaluation in terms of simulations and testbed implementations. DeliverablesBelow we list a set of work topics including names of senior researchers we expect to be involved. Students and postdocs will also be involved. Each work topic is expected to result in 1-3 publications including at least one journal publication within the 2 year span of the project. Lead scientist for each deliverable is underlined.
Researchers: Dam, Johansson, Stadler Spanning trees is a common technique for robust aggregation. We examine the use of spanning trees for distributed threshold detection.
Researchers: Dam, Stadler. Efficient solutions for threshold detection using gossiping are not currently known. We will propose and evaluate solutions for this.
Researchers: Aurell, Dam, Johansson, Krishnamurthy, Stadler. We examine analytic methods to evaluate performance characteristics of different aggregation schemes, and to trade off performance parameters against each other.
Researchers: Dam, Stadler Privacy is an important concerning, for instance in multidomain management. We will explore the applicability of secure multiparty computation for this.
Researchers: Dam, Stadler. We examine ways of extending existing gossiping protocols to harden them against crash failures.
Researchers: Aurell, Dam, Johansson, Krishnamurthy, Stadler As yet, little work has been done to analyze the behaviour of state aggregation protocols under churn, i.e. under dynamic failures and topology changes. This work topic extends previous work by Krishnamurthy and Aurell on this topic.
Status per mid 2008
Title: Service Middleware for Self-Managing Large-Scale Systems Journal: IEEE Transactions on Network and Service Management (TNSM) Volume: 4 Number: 3 Date: December 2007
Title: A Randomized Incremental Subgradient Method For Distributed Optimization In Networked Systems, Journal: Date: July 2008, Note: Submitted This paper develops a new incremental subgradient method for distributed optimization which relies on peer-to-peer communication only. Such methods are useful for a wide range of distributed management problems, including distributed computation of averages and rankings.
Title: Methods and Consensus Algorithms for Solving Separable Distributed Control Problems Booktitle: Proceedings IEEE Conference on Decision and Control Date: December 2008 Note: Submitted Detailed packet-level simulations of a selection of distributed optimization methods are performed for resource-constrained wireless sensor networks, and an evaluation and comparison of the convergence speed and signaling requirements is presented.
Title: On
Distributed Optimization using Peer-to-Peer Communications in Wireless Sensor
Networks Report: IT-EE-RT_2008_017 This paper presents a novel distributed optimization scheme which combines consensus iterations with subgradient optimization. Similar to the Markov randomized subgradient method developed by the authors, the novel scheme relies on peer-to-peer communication only. Theoretical convergence results are combined with numerical simulations.
Title: “Key Research Challenges in Network Management,” Journal: IEEE Communications Magazine, Vol.45, Issue 10, October 2007.
Title: Controlling Performance Trade-offs in Decentralized Network Monitoring Institution: Royal Institute of Technology (KTH) Date: May 2008 Note: Submitted to the
19th IFIP/IEEE Distributed Systems: Operations and Management (DSOM 2008),
Title: Monitoring Flow Aggregates with Controllable Accuracy In: Proceedings 10th
IFIP/IEEE International Conference on Management of Multimedia and Date: October 2007
Title: “A-GAP: An Adaptive Protocol for Continuous Network Monitoring with Accuracy Objectives,” Journal: IEEE Transactions on Network and Service Management
(TNSM), Vol. 4, No. 1, June 2007
Title: Decentralized Detection of Global Threshold Crossings Using Aggregation Trees Journal: Computer Networks Date:
February 2008 We propose a tree-based algorithm for
distributed, scalable threshold detection for dynamic networks. The algorithm
uses hysteresis to reduce management overhead when aggregates are far from the
relevant thresholds.
Title: Gossiping for Threshold Detection Date: September 2008 Note: Submitted The paper explores several candidate
protocols which uses hysteresis-like mechanisms to reduce overhead for the case
of threshold detection
Title: Robust monitoring of network-wide aggregates using gossiping Journal: IEEE Transactions on Network and Service Management Date: March 2008 Note: Submitted We propose versions of the Push-Synopses
protocol due to Kempe, Dobra, and Gehrke, FOCS'03, hardened against crash
failures. |
,