Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Communication-Efficient Tracking of Distributed Cumulative Triggers

Ling Huang, Minos Garofalakis, Anthony D. Joseph and Nina Taft

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-139
October 30, 2006

http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-139.pdf

There has been growing interest in large-scale distributed monitoring systems, such as Dynamic Denial of Service attack detectors and sensornet-based environmental monitors. Recent work has posited that these infrastructures lack a critical component, namely a distributed-triggering mechanism that fires when an aggregate of remote-site behavior exceeds some threshold. For several scenarios, the trigger conditions of interest are naturally cumulative, they continuously monitor the accumulation of threshold infractions (e.g., resource overuse) over time. In this paper, we develop a novel framework and communication-efficient protocols to support distributed cumulative triggers. In sharp contrast to earlier work focusing on instantaneous violations, we introduce a general model of threshold conditions that enables us to track distributed cumulative violations over time windows of any size. In our system, a central coordinator efficiently tracks aggregate time-series data at remote sites by adaptively informing the sites how to locally filter their data and when to ship new information. Our proposed algorithmic framework allows us to: (1) provide guarantees on the coordinator's triggering accuracy; (2) flexibly tradeoff communication overhead versus accuracy; and, (3) develop an analytic solution for computing local filtering parameters. Our work is the first to solve the problem of communication-efficient monitoring for distributed cumulative trigger conditions using principled solutions with accuracy guarantees. We evaluate our system using time-series data generated from SNORT logs on PlanetLab nodes and demonstrate that our methods yield significant communication overhead reductions while simultaneously achieving high detection accuracy, even for highly variable data streams.


BibTeX citation:

@techreport{Huang:EECS-2006-139,
    Author = {Huang, Ling and Garofalakis, Minos and Joseph, Anthony D. and Taft, Nina},
    Title = {Communication-Efficient Tracking of Distributed Cumulative Triggers},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Oct},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-139.html},
    Number = {UCB/EECS-2006-139},
    Abstract = {There has been growing interest in large-scale distributed monitoring systems, such as Dynamic Denial of Service attack detectors and sensornet-based environmental monitors. Recent work has posited that these infrastructures lack a critical component, namely a distributed-triggering mechanism that fires when an aggregate of remote-site behavior exceeds some threshold. For several scenarios, the trigger conditions of interest are naturally cumulative, they continuously monitor the accumulation of threshold infractions (e.g., resource overuse) over time. 

In this paper, we develop a novel framework and communication-efficient protocols to support distributed cumulative triggers. In sharp contrast to earlier work focusing on instantaneous violations, we introduce a general model of threshold conditions that enables us to track distributed cumulative violations over time windows of any size. In our system, a central coordinator efficiently tracks aggregate time-series data at remote sites by adaptively informing the sites how to locally filter their data and when to ship new information. Our proposed algorithmic framework allows us to: (1) provide guarantees on the coordinator's triggering accuracy; (2) flexibly tradeoff communication overhead versus accuracy; and, (3) develop an analytic solution for computing local filtering parameters. Our work is the first to solve the problem of communication-efficient monitoring for distributed cumulative trigger conditions using principled solutions with accuracy guarantees. We evaluate our system using time-series data generated from SNORT logs on PlanetLab nodes and demonstrate that our methods yield significant communication overhead reductions while simultaneously achieving high detection accuracy, even for highly variable data streams.}
}

EndNote citation:

%0 Report
%A Huang, Ling
%A Garofalakis, Minos
%A Joseph, Anthony D.
%A Taft, Nina
%T Communication-Efficient Tracking of Distributed Cumulative Triggers
%I EECS Department, University of California, Berkeley
%D 2006
%8 October 30
%@ UCB/EECS-2006-139
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-139.html
%F Huang:EECS-2006-139