We develop a framework for minimizing the communication overhead of monitoring global system parameters in IP networks and sensor networks. A global system parameter is defined as a function of local properties of different network elements. Identifying when the total amount of interface out traffic from an organization's sub-network exceeds some threshold is an example parameter to monitor. Our main idea is to optimize the scheduling of local event reporting across network elements for a given network traffic load and local event frequencies. Our system architecture consists of N distributed network elements coordinated by a central monitoring station. Each network element monitors a set of local properties, and the central station is responsible for identifying the status of global parameters registered in the system.
We design an optimal algorithm when the local events are conditionally independent; whereas, when they are dependent, we show that the problem is NP-complete and develop two efficient heuristics: the SPA (Sample, Partition, and Aggregate), and Ada (Adaptive) algorithms which adapt well to changing network conditions, and outperform the current state of the art techniques in terms of communication cost.