14175949
GATES: a grid-based middleware for processing distributed data streams
Increasingly, a number of applications rely on, or can potentially benefit from, analysis and monitoring of data streams. Moreover, many of these applications involve high volume data streams and require distributed processing of data arising from a distributed set of sources. Thus, we believe that a grid environment is well suited for flexible and adaptive analysis of these streams. This paper reports the design and initial evaluation of a middleware for processing distributed data streams. Our system is referred to as GATES (grid-based adaptive execution on streams). This system is designed to use the existing grid standards and tools to the extent possible. It flexibly achieves the best accuracy that is possible while maintaining the real-time constraint on the analysis. We have developed a self-adaptation algorithm for this purpose. Results from a detailed evaluation of this system demonstrate the benefits of distributed processing, and the effectiveness of our self-adaptation algorithm.
1252625
Supporting self-adaptation in streaming data mining applications
There are many application classes where the users are flexible with respect to the output quality. At the same time, there are other constraints, such as the need for real-time or interactive response, which are more crucial. This paper presents and evaluates a runtime algorithm for supporting adaptive execution for such applications. The particular domain we target is distributed data mining on streaming data. This work has been done in the context of a middleware system called GATES (grid-based adaptive execution on streams) that we have been developing. The self-adaptation algorithm we present and evaluate in this paper has the following characteristics. First, it carefully evaluates the long-term load at each processing stage. It considers different possibilities for the load at a processing stage and its next stages, and decides if the value of an adaptation parameter needs to be modified, and if so, in which direction. To find the ideal new value of an adaptation parameter, it performs a binary search on the specified range of the parameter. To evaluate the self-adaptation algorithm in our middleware, we have implemented two streaming data mining applications. The main observations from our experiments are as follows. First, our algorithm is able to quickly converge to stable values of the adaptation parameter, for different data arrival rates, and independent of the specified initial value. Second, in a dynamic environment, the algorithm is able to adapt the processing rapidly. Finally, in both static and dynamic environments, the algorithm clearly outperforms the algorithm described in our earlier work and an obvious alternative, which is based on linear-updates.
6229211
Resource allocation in a middleware for streaming data
Increasingly, a number of applications rely on, or can potentially benefit from, analysis and monitoring of <i>data streams.</i> To support processing of streaming data in a grid environment, we have been developing a middleware system called GATES (Grid-based AdapTive Execution on Streams). Our target applications are those involving high volume data streams and requiring distributed processing of data arising from a distributed set of sources.
 This paper addresses the problem of resource allocation in the GATES system. Though resource discovery and resource allocation have been active topics in grid community, the pipelined processing and real-time constraint required by distributed streaming applications pose new challenges. We present a resource allocation algorithm that is based on minimal spanning trees. We evaluate the algorithm experimentally and demonstrate that it results in configurations that are very close to optimal, and significantly better than most other possible configurations.
6427165
Self-adaptation in a middleware for processing data streams
Many stream-based applications share a common set of characteristics, which makes grid-based and adaptive processing desirable or even a necessity. We view the problem of flexible and adaptive processing of distributed data streams as a grid computing problem. We have been developing a middleware for processing of distributed data streams. Our system is referred to as GATES (grid-based adaptive execution on streams). It is designed to use the existing grid standards and tools to the extent possible. Because of the real-time requirements, there is a need for adapting the processing in such a distributed environment, and achieving the best accuracy of the results within the real-time constraint. For this purpose, our system flexibly achieves the best accuracy that is possible while maintaining the real-time constraint on the analysis. We have developed and implemented a self-adaptation algorithm. This paper focuses on describing and evaluating this algorithm.
16022661
Monitoring access link capacity using TFRC probe
Accurate estimation of network characteristics based on end-to-end measurements is an important and challenging problem. With the increasing variety and sophistication of Internet access methods, the mobility of the users and the need for seamless handoff across them, monitoring access link capacity becomes critical for efficient multimedia delivery. In fact, this allows the multimedia server to properly adjust its sending rate to the rapidly changing access speed of the mobile client. This problem is challenging because most of the existing capacity monitoring schemes are active, like Pathrate (and therefore, introduce extra overhead on the bandwidth limited access link). Moreover, the access link is often asymmetric (e.g. ADSL, 1xRTT, etc.) thus preventing the use of round-trip monitoring schemes such as Pathchar and CapProbe. In this study, we propose and evaluate a passive, one-way link capacity monitoring tool called TFRC Probe. With TFRC Probe the source can monitor the forward direction capacity of both asymmetric and symmetric access links, and can rapidly and accurately adapt its transmissions rate accordingly. We validate TFRC Probe with both simulation and testbed experiments, and show that TFRC Probe is a very flexible tool that can accurately track frequent changes in access capacity.
17373350
VLSI architecture design of MPEG-4 shape coding
This paper presents an efficient VLSI architecture design of MPEG-4 shape coding, which is the key technology for supporting the content-based functionality of the MPEG-4 video standard. The real-time constraint of MPEG-4 shape coding leads to a heavy computational bottleneck on today's computer architectures. To overcome this problem, design analysis and optimization of MPEG-4 shape coding are addressed. By utilizing the RISC-based model, computational behaviors of the MPEG-4 shape coding tool are carefully examined and analyzed. The characteristic of a large amount of bit-level data processing and data transfer of MPEG-4 shape coding motivates the optimization of bit-level data operations. Applying data-flow optimization and data reuse techniques, bit-level computation-efficient architectures, such as data-dispatch-based binary-shaped motion estimation, the delay-line model, and configurable context-based arithmetic coding, are designed to accelerate bit-level processing. These hardware blocks are integrated and scheduled in a very efficient data flow to achieve real-time performance for MPEG-4 CPL2 (core profile level 2) specification at 23.5 MHz clock rate. The system architecture is implemented using Verilog HDL and synthesized with a 0.35 /spl mu/m four-layer CMOS standard library.
206977606
Priority Based Overlay Multicast for Distributed Interactive Applications
Distributed Interactive Applications (DIAs) is different with other network-based applications, since the data should be delivered to the receiver node according to its priority. Among the existing overlay multicast protocols the "priority-based directed minimum spanning tree" (PST) is designed for DIAs. But in PST the available bandwidth (avail-bw) is used inefficiently and the system becomes unstable when its scale increases. This paper proposed a novel overlay multicast protocol named Priority Based Overlay Multicast (POM), which uses the entities’ priority, links’ delay and node’s avail-bw to build multicast tree. By using POM the nodes with high priority receive the data in short delay, while the nodes with low priority tolerate a long delay in order to balance the available bandwidth usage among the nodes. The simulation results show that POM uses the avail-bw efficiently and keeps the system stable when its scale increases. Keywords: DIAs; Priority; Available bandwidth.
4784687
SERF: ODMG-based generic re-structuring facility
The age of information management and with it the advent of increasingly sophisticated technologies have kindled a need in the database community and others to re-structure existing systems and move forward to make use of these new technologies. Legacy application systems are being transformed to newer state-of-the-art systems, information sources are being mapped from one data model to another, a diversity of data sources are being transformed to load, cleanse and consolidate data into modern data-warehouses [CR99].
Re-structuring is thus a critical task for a variety of applications. For this reason, most object-oriented database systems (OODB) today support some form of re-structuring support [Tec94, Obj93, BKKK87]. This existing support of current OODBs [BKKK87, Tec94, Obj93] is limited to a pre-defined taxonomy of simple fixed-semantic schema evolution operations. However, such simple changes, typically to individual types only, are not sufficient for many advanced applications [Bré96]. More radical changes, such as combining two types of redefining the relationship between two types, are either very difficult or even impossible to achieve with current commercial database technology [Tec94, Obj93]. In fact, most OODBs would typically require the user to write ad-hoc programs to accomplish such transformations. Research that has begun to look into the issue of complex changes [Bré96, Ler96] is still limited by providing a fixed set of some selected (even if now more complex) operations.
To address these limitations of the current restructuring technology, we have proposed the SERF framework which aims at providing a rich environment for doing complex user-defined transformations flexibly, easily and correctly [CJR98b]. The goal of our work is to increase the usability and utility of the SERF framework and its applicability to re-structuring problems beyond OODB evolution. Towards that end, we provide re-usable transformations via the notion of SERF Templates that can be packaged into libraries, thereby increasing the portability of these transformations. We also now have a first cut at providing an assurance of consistency for the users of this system, a semantic optimizer that provides some performance improvements via enhanced query optimization techniques with emphasis on the re-structuring primitives [CNR99]. In this demo we give an overview of the SERF framework, its current status and the enhancements that are planned for the future. We also present an example of the application of SERF to a domain other than schema evolution, i.e., the web restructuring.
4781375
SERFing the web: The Re-Web approach for web re-structuring
In our emerging digital paper-less society, massive amount of information is being maintained in on-line repositories and diverse web site representations of this information must be served over the Internet to different user groups. E-commerce and digital libraries are two representative sample applications with such needs. In this paper we present a database-centric approach called Re-Web that addresses this need for flexible web site generation, re-structuring, and maintenance. Re-Web is based on two key ideas. First, we exploit the web site structure by associating web semantics (XML equivalents) with the modeling constructs of the ODMG object model to aid the web site generation process. By capturing the logical structure of web views within the OODB system, we can efficiently maintain the web views using standard database techniques. Secondly, to ease the process of specification and construction of multiple customized web view sites, we also propose the notion of generic web view transformations that are encapsulated into re-usable templates. Thus desired new web view sites can be generated simply by applying the corresponding transformations on the underlying database to produce web view classes and then by applying the web semantics on the newly built view classes. The Re-Web system has been implemented using PSE by Object Design Inc. as object repository, ODMG as object model, OQL as transformation language, SERF as OODB evolution facility and IBM XML parser and LotusXSL processor to aid the web site generation. A case study using Re-Web is also presented to illustrate the working of the system. To the best of our knowledge, Re-Web is the first web site management system focusing on the issue of re-usable view generation templates at the content and not at the presentation style level of abstraction.