16884480
Overload control in QoS-aware web servers
With the explosive use of Internet, contemporary web servers are susceptible to overloads during which their services deteriorate drastically and often lead to denial of services. Overloads are of more serious concerns for QoS-aware servers. Evaluation of performance of QoS-aware servers in terms of the number of request completion is not very meaningful. A better measure would be the number of completed sessions. In this paper, we proposed two methods to prevent and control overloads in web servers by utilizing session-based relationship among HTTP requests. We first exploited the dependence among session-based requests by analyzing and predicting the reference patterns. Using the dependency relationships, we have derived traffic conformation functions that can be used for capacity planning and overload prevention in web servers. Second, we have proposed a dynamic weighted fair sharing (DWFS) scheduling algorithm to control overloads in web servers. DWFS is distinguished from other scheduling algorithms in the sense that it aims to avoid processing of requests that belong to sessions that are likely to be aborted in the near future. The experimental results demonstrate that DWFS can improve server responsiveness by as high as 50% while providing QoS support through service differentiation for a class of application environment.
22537497
ACES: An efficient admission control scheme for QoS-aware web servers
The unpredictability of server response performance hinders the advance of new application on the Internet. In this paper, we present an efficient admission control algorithm, ACES, based on the server workload characteristics. The admission control algorithm ensures the bounded response time from a web server by periodical allocation of system resources according to the resource requirements of incoming tasks. By rejecting requests exceeding server capacity, the response performance of the server is well maintained even under high system utilization. The resource requirements of tasks are estimated based on their types. A double-queue structure is implemented to reduce the effects caused by estimation inaccuracy, and to exploit the spare capacity of the server, thus increasing the system throughput. The admission control algorithm can be used for server overload control and for QoS provisioning of service differentiating Internet servers. Response delays of accepted tasks are bounded by the desired predefined time period. Theoretical analyses and experimental studies show that the ACES algorithm provides desirable throughput and bounded response delay to the tasks, without any significant impact on the aggregate throughput performance of the system under various workload situations.
8488192
Session-based overload control in QoS-aware Web servers
With the explosive use of the Internet, contemporary Web servers are susceptible to overloads and their services deteriorate drastically and often cause denial of services. In this paper, we propose two methods to prevent and control overloads in Web servers by utilizing the session-based relationship among HTTP requests. We first exploited the dependence among session-based requests by analyzing and predicting the reference patterns. Using the dependency relationships, we have derived traffic conformation functions that can be used for capacity planning and overload prevention in Web servers. Second, we have proposed a dynamic weighted fair sharing (DWFS) scheduling algorithm to control overloads in Web servers. DWFS is distinguished from other scheduling algorithms in the sense that it aims to avoid processing of requests that belong to sessions that are likely to be aborted in the near future. The experimental results demonstrate that DWFS can improve server responsiveness by as high as 50% while providing QoS support through service differentiation for a class of application environment.
14347517
A Tiered System for Serving Differentiated Content
Contemporary Web sites typically consist of front–end Web servers, application servers, and back-end information systems such as database servers. There has been limited research on how to provide overload control and service differentiation for the back-end systems. In this paper we propose an architecture called tiered service (TS) for these purposes. In TS, there are several heterogeneous back-end systems to serve the Web applications. The Web applications communicate with a routing intermediary to intelligently route the queries to the appropriate back-end servers based on various policies such as client profiles and server load. In our system the back ends may store different qualities of data; lower quality data typically requires less overhead to serve. The main contributions of this paper include (i) a tiered content replication scheme that replicates tiered qualities of data on heterogeneous back ends with different capacity to satisfy clients with diverse requirements for latency and quality of data, and (ii) an application-transparent query routing architecture that automatically routes the queries to the appropriate back ends. The architecture was implemented in our test bed, and its performance was benchmarked. The experimental results demonstrate that TS offers significant performance improvement.
6650752
Using Content-Based and Link-Based Analysis in Building Vertical Search Engines
This paper reports our research in the Web page filtering process in specialized search engine development. We propose a machine-learning-based approach that combines Web content analysis and Web structure analysis. Instead of a bag of words, each Web page is represented by a set of content-based and link-based features, which can be used as the input for various machine learning algorithms. The proposed approach was implemented using both a feedforward/backpropagation neural network and a support vector machine. An evaluation study was conducted and showed that the proposed approaches performed better than the benchmark approaches.
6877505
An Algorithm for SAT Above the Threshold
We study algorithms for finding satisfying assignments of randomly generated 3-SAT formula. In particular, we consider distributions of highly constrained formulas (that is, “above the threshold” formulas) restricted to satisfiable instances. We obtain positive algorithmic results, showing that such formulas can be solved in low exponential time.
15293705
Design and evaluation of a multi-agent collaborative Web mining system
Most existing Web search tools work only with individual users and do not help a user benefit from previous search experiences of others. In this paper, we present the Collaborative Spider, a multi-agent system designed to provide post-retrieval analysis and enable across-user collaboration in Web search and mining. This system allows the user to annotate search sessions and share them with other users. We also report a user study designed to evaluate the effectiveness of this system. Our experimental findings show that subjects' search performance was degraded, compared to individual search scenarios in which users had no access to previous searches, when they had access to a limited number (e.g., 1 or 2) of earlier search sessions done by other users. However, search performance improved significantly when subjects had access to more search sessions. This indicates that gain from collaboration through collaborative Web searching and analysis does not outweigh the overhead of browsing and comprehending other users' past searches until a certain number of shared sessions have been reached. In this paper, we also catalog and analyze several different types of user collaboration behavior observed in the context of Web mining.
18742334
Arithmetic Constant-Depth Circuit Complexity Classes
The boolean circuit complexity classes AC 0 ⊆ AC 0[m] ⊆ TC 0 ⊆ NC 1 have been studied intensely. Other than NC 1, they are defined by constant-depth circuits of polynomial size and unbounded fan-in over some set of allowed gates. One reason for interest in these classes is that they contain the boundary marking the limits of current lower bound technology: such technology exists for AC 0 and some of the classes AC 0[m], while the other classes AC 0[m] as well as TC 0 lack such technology.
4274853
Lifting based discrete wavelet transform architecture for JPEG2000
A lifting based 1-D discrete wavelet transform (DWT) core is proposed. It is re-configurable for 5/3 and 9/7 filters in JPEG2000. Folded architecture is adopted to reduce the hardware cost and achieve the higher hardware utilization. Multiplication is realized in hardwired multiplier with coefficients represented in canonic signed-digit (CSD) form. It is a compact and efficient DWT core for the hardware implementation of JPEG2000 encoder.