Communication-Efficient Tracking of Distributed Triggers
Overview:
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 coordinators'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.
Publications:
Talks:
People: