Abstract
We develop a framework for minimizing the communication overhead of monitoring global system parameters in IP networksand sensor networks. A global system parameter is defined as a function of local properties of different network elements. Identifyingwhen the total amount of interface out traffic from an organization’s sub-network exceeds some threshold is an example parameter tomonitor. Our main idea is to optimize the scheduling of local event reporting across network elements for a given network traffic loadand local event frequencies. Our system architecture consists of N distributed network elements coordinated by a central monitoringstation. Each network element monitors a set of local properties, and the central station is responsible for identifying the status of globalparameters registered in the system. We design an optimal algorithm when the local events are independent; whereas, when they aredependent, 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 techniquesin terms of communication cost.Index Terms—Network Monitoring, Push Pull techniques, Bayesian Networks
1 INTRODUCTION
Reactive network monitoring consists of measuring the propertiesof the network to ensure that the system operates withdesirable parameters. The management station queries the stateof the network in order to react to alarm conditions that maydevelop in the network [7]. Information about the network stateis collected using two different techniques: event reportingand polling. In event reporting, network elements distributedacross the network push alarms and detailed event reports tothe station. In polling, the station sends requests to obtainthe status of network elements. Typically, polling is doneperiodically with a fixed frequency, determined by a criticaltime window within which the alarm condition has to bedetected.In many situations, there is a need to monitor a globalsystem parameter, which is defined as a function of localproperties of different network elements. In such cases, afterdetecting local changes, each network element has to continuouslyemit alarms in order to ensure that global parametersare not violated. In sensor networks, a typical example isa monitoring system which determines whether the averagetemperature of a particular region exceeds a certain threshold.In IP networks, consider the monitoring of the amount oftraffic from an organization subnetwork to the Internet. Asubnetwork is connected to the outer world via a number of interfaces. The goal is to determine whether the total outboundtraffic exceeds a predefined threshold. One solution to thisproblem, referred to as all-pull scheme, is to poll the statusof network elements continuously. As long as the cumulativesum is below the threshold, no alarms are generated. Anotherapproach to the same problem is to allocate a fixed budget(a small proportion of the threshold) to each node. Eachtime the amount of local traffic exceeds the local budget, areport containing event details and some application specificinformation is sent to the station. We refer to this solutioninstance as all-push.Given a set of n network elements, where the decisionat each element is either “to push” or “to pull”, one canobserve that the solution space of schedules is exponentialin the number of elements (2n), and the all-push and all-pullschemes correspond to two specific solutions in this space. Themajor disadvantage of the all-pull and all-push schemes is thatthey are oblivious to the environment characteristics. All-pullscheme does not take local event frequencies into account, andincurs cost continuously especially if the transmission networkis congested. All-push scheme considers this aspect, but sinceit functions on local information only, there is no globalcoordination. An efficient approach to tackle this problem is tocombine event reporting with aperiodic polling such that onlya subset of elements are chosen as watch-dogs for monitoring agiven global parameter. When reports from all watch-dogs arereceived, then the status of remaining elements are obtainedusing polling. Therefore, the problem of interest becomes howto select the set of elements that will push. A simple greedyheuristic, which selects to push from elements with a low eventfrequency, performs very well in practice. One has to identifythe top-k least frequent event set continuously.


Download full report
http://cs.ucsb.edu/research/tech_reports...007-01.pdf