Abstract
We consider the problem of estimating set-expression cardinality in a distributed streaming environment where rapid update streams originating at remote sites are continually transmitted to a central processing system. At the core of our algorithmic solutions for answering set-expression cardinality queries are two novel techniques for lowering data communication costs without sacrificing answer precision. Our first technique exploits global knowledge of the distribution of certain frequently occurring stream elements to significantly reduce the transmission of element state information to the central site. Our second technical contribution involves a novel way of capturing the semantics of the input set expression in a boolean logic formula, and using models (of the formula) to determine whether an element state change at a remote site can affect the set expression result. Results of our experimental study with real-life as well as synthetic data sets indicate that our distributed set-expression cardinality estimation algorithms achieve substantial reductions in message traffic compared to naive approaches that provide the same accuracy guarantees.
1 Introduction
The widespread deployment of wireline and wireless networks linking together a broad range of devices has resulted in a new class of distributed data streaming applications. In these applications, rapid update streams originating at tens or hundreds of remote sites are continuously transmitted to a central processing system for online querying and analysis. Examples include monitoring of service provider network traffic statistics, telecommunication call detail records, Web usage logs, financial stock tickers, retail chain transactions, weather data, sensor data, and so on. Proceedings of the 30th VLDB Conference, Toronto, Canada, 2004 An important consideration in the above-mentioned monitoring applications is the communication overhead imposed by the distributed query processing architecture on the underlying network. A naive approach in which every stream update is shipped to the central site for processing can lead to inordinate amounts of message traffic, and thus have a crippling effect on the communication infrastructure as well as the central processor. For instance, monitoring flow level information within AT&T’s IP backbone using Cisco’s NetFlow tool [1] is known to generate in excess of 500 GBytes of data per day [4]. Clearly, transmitting every flow record to the central network operations center of a large ISP can seriously strain its processing and network resources. As another example, consider wireless sensor networks (e.g., for environmentalmonitoring, inventory tracking, etc.), where sensors have a very limited battery life, and radio communication is much more expensive in terms of power consumption compared to processing. In order to ensure longer lifetimes for sensor nodes, it is critical to reduce the amount of data transmitted, even if that implies additional processing at the sensor nodes [13, 12, 10]. Fortunately, for many distributed stream-oriented applications, exact answers are not required and approximations with guarantees on the amount of error suffice. Thus, it is possible to trade answer accuracy for reduced data communication costs. For example, consider the problemof detecting distributed denial-of-service (DDoS) attacks by analyzing network flow information collected from an ISP’s border routers. In a typical DDoS attack scenario, hundreds of compromised “zombie” hosts flood a specific victim destination with large numbers of seemingly legitimate packets. Furthermore, in order to elude source identification, attackers typically forge, or “spoof”, the IP source address of each packet they send with a randomly-chosen address [11]. Consequently, a possible approach for detecting DDoS attacks is to look for sudden spikes in the number of distinct IP source addresses observed in the flows across the ISP’s border routers. Clearly, our DDoS monitoring application does not require IP source address counts to be tracked with complete precision. Approximate counts can be equally effective for the purpose of discerning DDoS activity as long as errors are small enough so as to not mask abrupt changes. Thus, depending on the accuracy requirements of the DDoS application, routers only need to transmit a subset of flow records to the central monitoring site


Download full report
http://googleurl?sa=t&source=web&cd=1&ve...prCard.pdf&ei=arFETvGSMYTrrQfW-ID2Aw&usg=AFQjCNFHxwp1ZtriYs7OlMfvURxPn-zVMg&sig2=EafQ8HyRIOtXaX0r36OyeA