40 results on '"Cheng Zhong"'
Search Results
2. Prepartition: Load Balancing Approach for Virtual Machine Reservations in a Cloud Data Center.
- Author
-
Tian, Wen-Hong, Xu, Min-Xian, Zhou, Guang-Yao, Wu, Kui, Xu, Cheng-Zhong, and Buyya, Rajkumar
- Subjects
VIRTUAL machine systems ,ONLINE algorithms ,RESOURCE allocation ,LOAD balancing (Computer networks) ,PRODUCTION scheduling ,SERVER farms (Computer network management) - Abstract
Load balancing is vital for the efficient and long-term operation of cloud data centers. With virtualization, post (reactive) migration of virtual machines (VMs) after allocation is the traditional way for load balancing and consolidation. However, it is not easy for reactive migration to obtain predefined load balance objectives and it may interrupt services and bring instability. Therefore, we provide a new approach, called Prepartition, for load balancing. It partitions a VM request into a few sub-requests sequentially with start time, end time and capacity demands, and treats each sub-request as a regular VM request. In this way, it can proactively set a bound for each VM request on each physical machine and makes the scheduler get ready before VM migration to obtain the predefined load balancing goal, which supports the resource allocation in a fine-grained manner. Simulations with real-world trace and synthetic data show that our proposed approach with offline version (PrepartitionOff) scheduling has 10%–20% better performance than the existing load balancing baselines under several metrics, including average utilization, imbalance degree, makespan and Capacity_makespan. We also extend Prepartition to online load balancing. Evaluation results show that our proposed approach also outperforms state-of-the-art online algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
3. Algorithmics of Cost-Driven Computation Offloading in the Edge-Cloud Environment
- Author
-
Yang Wang, Mingzhe Du, Cheng-Zhong Xu, and Kejiang Ye
- Subjects
Computer science ,business.industry ,Distributed computing ,Mobile computing ,Cloud computing ,02 engineering and technology ,020202 computer hardware & architecture ,Theoretical Computer Science ,Computational Theory and Mathematics ,Hardware and Architecture ,Algorithmics ,0202 electrical engineering, electronic engineering, information engineering ,Computation offloading ,Resource allocation ,business ,Software ,Edge computing - Abstract
Computation offloading between the edge and the cloud is an effective way for deployed service to fully utilize the resources at both sides for its QoS improvement and overall cost reduction. Although the offloading problem has been intensively studied in the context of mobile computing, existing algorithms in most cases cannot be effectively migrated to the edge-cloud environment because their inter-partition communication costs are always deemed as symmetric, and their intra-partition communication costs are often ignored, which, though reasonable to the traditional case, are not valid to our settings anymore. In this article, we propose a new algorithmic approach to the offloading problem in the edge-cloud environment, where a heterogeneous model is advocated to incorporate the communication cost between co-resident tasks while considering the asymmetry of communication costs between non-coresident tasks. We prove the offloading problem with respect to this model is NP-hard, and thereby designing an efficient algorithm to obtain a sub-optimal solution. Additionally, we also show that in a homogeneous case when the intra-partition and inter-partition communication costs between any pair of interactive tasks are symmetric, an optimal offloading algorithm can be devised by transforming the problem into a classical min-cut problem. We implemented and evaluated the algorithms by offloading a PageRank -based application in a controlled edge-cloud setting. Our empirical results show that the proposed algorithm for the heterogeneous case is always efficient to find a better offloading scheme, compared with the selected existing algorithms, while for the homogeneous case, the proposed solution can efficiently achieve the optimal strategy.
- Published
- 2020
4. Wireless Power-Driven Positioning System: Fundamental Analysis and Resource Allocation
- Author
-
Yuefeng Ji, Cheng-Zhong Xu, Yubin Zhao, and Xiaofan Li
- Subjects
Positioning system ,Computer Networks and Communications ,Computer science ,business.industry ,Distributed computing ,MIMO ,020206 networking & telecommunications ,020302 automobile design & engineering ,02 engineering and technology ,Energy consumption ,Computer Science Applications ,0203 mechanical engineering ,Hardware and Architecture ,Signal Processing ,0202 electrical engineering, electronic engineering, information engineering ,Resource allocation ,Wireless ,Resource management ,Wireless power transfer ,business ,Wireless sensor network ,Information Systems ,Communication channel ,Efficient energy use - Abstract
Using IoT devices to locate targets is widely applied in many scenarios. However, replacing the batteries of these devices is time and labor consuming. In this article, we propose a wireless power-driven positioning system (WP2S) that employs MIMO-based wireless power transfer access points to supply energy to batteryless anchors. In this case, the IoT localization devices will have unlimited power. We formulate the equivalent Fisher information matrix (EFIM) as a fundamental tool to analyze the system performance. Then, we propose resource allocation schemes for optimal location estimation and energy efficiency problems by relaxing the objectives as semidefinite programming problems. In addition, we also analyze the impacts of channel uncertainty, anchor uncertainty, and NLOS for the performances of location estimation and energy consumption. The robust algorithms are developed according to uncertainty models. Both the analysis and simulations demonstrate that the estimation accuracy relies heavily on the transmitted power and the uncertainty models will consume more power to meet the location requirements.
- Published
- 2019
5. Survey on Grid Resource Allocation Mechanisms
- Author
-
Qureshi, Muhammad Bilal, Dehnavi, Maryam Mehri, Min-Allah, Nasro, Qureshi, Muhammad Shuaib, Hussain, Hameed, Rentifis, Ilias, Tziritas, Nikos, Loukopoulos, Thanasis, Khan, Samee U., Xu, Cheng-Zhong, and Zomaya, Albert Y.
- Published
- 2014
- Full Text
- View/download PDF
6. A Data-Driven Method for Dynamic OD Passenger Flow Matrix Estimation in Urban Metro Systems
- Author
-
Jiexia Ye, Kejiang Ye, Liutao Zhang, Cheng-Zhong Xu, Juanjuan Zhao, and Jun Zhang
- Subjects
050210 logistics & transportation ,Computer science ,05 social sciences ,Flow (psychology) ,Inflow ,computer.software_genre ,k-nearest neighbors algorithm ,Data-driven ,Kriging ,0502 economics and business ,Resource allocation ,Data mining ,Baseline (configuration management) ,Intelligent transportation system ,computer - Abstract
Dynamic O-D flow estimation is the basis of metro network operation, such as transit resource allocation, emergency coordination, strategy formulation in urban rail system. It aims to estimate the destination distribution of current inflow of each origin station. However, it is a challenging task due to its limitation of available data and multiple affecting factors. In this paper, we propose a practical method to estimate dynamic OD passenger flows based on long-term AFC data and weather data. We first extract the travel patterns of each individual passenger based on AFC data. Then the passengers of current inflows based on these patterns are classified into fixed passengers and stochastic passengers by judging whether the destination can be inferred. Finally, we design a K Nearest Neighbors (KNN) and Gaussian Process Regression (GPR) combined hybrid approach to dynamically predict stochastic passengers’ destination distribution based on the observation that the distribution has obvious periodicity and randomicity. We validate our method based on extensive experiments, using AFC data and weather data in Shenzhen, China over two years. The evaluation results show that our approach with 85% accuracy surpasses the results of baseline methods and the estimation precision reaches 85%.
- Published
- 2020
7. Co-Locating Online Workload and Offline Workload in the Cloud: An Interference Analysis
- Author
-
Kejiang Ye, Wenyan Chen, and Cheng-Zhong Xu
- Subjects
Online and offline ,020203 distributed computing ,Computer science ,business.industry ,Distributed computing ,020207 software engineering ,Workload ,Cloud computing ,02 engineering and technology ,Interference (wave propagation) ,Scheduling (computing) ,Software deployment ,Container (abstract data type) ,0202 electrical engineering, electronic engineering, information engineering ,Resource allocation ,business ,Resource utilization - Abstract
Workload characterization plays an important role in resource allocation and performance optimization. In order to improve the resource utilization, cloud providers like Google and Alibaba usually co-locate online and offline jobs on the same cluster. However, the characteristics of co-located services running in containers is still not clear. In this paper, we explore various characteristics of micro-architecture and application level of co-located workloads running in containers on the same server via two popular monitor tools: Perf and Prometheus. Our study focuses on quantifying interference of workloads by analyzing the characteristics of workloads running alone and co-located. Based on the interference analysis, we can design more efficient container deployment or scheduling algorithms in the future.
- Published
- 2019
8. Modeling Application Performance in Docker Containers Using Machine Learning Techniques
- Author
-
Cheng-Zhong Xu, Yang Wang, Kou Yanmin, Lu Chengzhi, and Kejiang Ye
- Subjects
Artificial neural network ,Computer science ,business.industry ,020206 networking & telecommunications ,Cloud computing ,02 engineering and technology ,Machine learning ,computer.software_genre ,Support vector machine ,020204 information systems ,Container (abstract data type) ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,Resource allocation ,Resource management ,Artificial intelligence ,business ,Resource management (computing) ,computer - Abstract
Docker container is experiencing a rapid development with the support from industry like Google and is being widely used in large scale production cloud environments. However the performance of applications running in Docker containers is still not clear due to the complex relationship between container resource allocation and application performance. In this paper, we first study the impact of key parameters in container resource allocation that affect the performance of containerized applications. Then, we present modeling techniques over CPU, memory and I/O resources to characterize the performance of applications running in containers. To address this multi-dimensional modeling problem, we propose three machine learning techniques, i.e. Linear Regression (LR), Support Vector Machine (SVM) and Artificial Neural Network (ANN). We implement and evaluate the modeling techniques for four complex benchmark workloads from Spark. Experimental results demonstrate the proposed models can achieve as low as 2.27% prediction error, with an average of 10.13% for most applications. Furthermore, the prediction accuracy of SVM and ANN models are substantially better than LR based approaches, with 48.13% and 29.30% improvement.
- Published
- 2018
9. Imbalance in the cloud: An analysis on Alibaba cluster trace
- Author
-
Kejiang Ye, Guoyao Xu, Tongxin Bai, Lu Chengzhi, and Cheng-Zhong Xu
- Subjects
020203 distributed computing ,Computer science ,business.industry ,Quality of service ,media_common.quotation_subject ,Distributed computing ,Resource efficiency ,020206 networking & telecommunications ,Workload ,Cloud computing ,02 engineering and technology ,Resource (project management) ,Service (economics) ,0202 electrical engineering, electronic engineering, information engineering ,Batch processing ,Resource allocation ,Resource management ,business ,media_common - Abstract
To improve resource efficiency and design intelligent scheduler for clouds, it is necessary to understand the workload characteristics and machine utilization in large-scale cloud data centers. In this paper, we perform a deep analysis on a newly released trace dataset by Alibaba in September 2017, consists of detail statistics of 11089 online service jobs and 12951 batch jobs co-locating on 1300 machines over 12 hours. To the best of our knowledge, this is one of the first work to analyze the Alibaba public trace. Our analysis reveals several important insights about different types of imbalance in the Alibaba cloud. Such imbalances exacerbate the complexity and challenge of cloud resource management, which might incur severe wastes of resources and low cluster utilization. 1) Spatial Imbalance: heterogeneous resource utilization across machines and workloads. 2) Temporal Imbalance: greatly time-varying resource usages per workload and machine. 3) Imbalanced proportion of multi-dimensional resources (CPU and memory) utilization per workload. 4) Imbalanced resource demands and runtime statistics (duration and task number) between online service and offline batch jobs. We argue accommodating such imbalances during resource allocation is critical to improve cluster efficiency, and will motivate the emergence of new resource managers and schedulers.
- Published
- 2017
10. A comparative study on resource allocation and energy efficient job scheduling strategies in large-scale parallel computing systems
- Author
-
Aftab Ahmed Chandio, Nikos Tziritas, Cheng-Zhong Xu, Qingshan Jiang, Samee U. Khan, Kashif Bilal, and Zhibin Yu
- Subjects
Rate-monotonic scheduling ,Job scheduler ,Computer Networks and Communications ,Computer science ,Quality of service ,Workload ,Parallel computing ,Energy consumption ,computer.software_genre ,Job queue ,Resource allocation ,computer ,Software ,Efficient energy use - Abstract
In the large-scale parallel computing environment, resource allocation and energy efficient techniques are required to deliver the quality of services (QoS) and to reduce the operational cost of the system. Because the cost of the energy consumption in the environment is a dominant part of the owner's and user's budget. However, when considering energy efficiency, resource allocation strategies become more difficult, and QoS (i.e., queue time and response time) may violate. This paper therefore is a comparative study on job scheduling in large-scale parallel systems to: (a) minimize the queue time, response time, and energy consumption and (b) maximize the overall system utilization. We compare thirteen job scheduling policies to analyze their behavior. A set of job scheduling policies includes (a) priority-based, (b) first fit, (c) backfilling, and (d) window-based policies. All of the policies are extensively simulated and compared. For the simulation, a real data center workload comprised of 22385 jobs is used. Based on results of their performance, we incorporate energy efficiency in three policies i.e., (1) best result producer, (2) average result producer, and (3) worst result producer. We analyze the (a) queue time, (b) response time, (c) slowdown ratio, and (d) energy consumption to evaluate the policies. Moreover, we present a comprehensive workload characterization for optimizing system's performance and for scheduler design. Major workload characteristics including (a) Narrow, (b) Wide, (c) Short, and (d) Long jobs are characterized for detailed analysis of the schedulers' performance. This study highlights the strengths and weakness of various job scheduling polices and helps to choose an appropriate job scheduling policy in a given scenario.
- Published
- 2014
11. Survey on Grid Resource Allocation Mechanisms
- Author
-
Cheng-Zhong Xu, Maryam Mehri Dehnavi, Nikos Tziritas, Samee U. Khan, Nasro Min-Allah, Muhammad Shuaib Qureshi, Hameed Hussain, Albert Y. Zomaya, Ilias Rentifis, Muhammad Bilal Qureshi, and Thanasis Loukopoulos
- Subjects
Job shop scheduling ,Computer Networks and Communications ,Computer science ,Distributed computing ,Peer-to-peer ,computer.software_genre ,User requirements document ,Grid ,Task (computing) ,Semantic grid ,Grid computing ,Hardware and Architecture ,Resource allocation ,computer ,Software ,Information Systems - Abstract
Grid is a distributed high performance computing paradigm that offers various types of resources (like computing, storage, communication) to resource-intensive user tasks. These tasks are scheduled to allocate available Grid resources efficiently to achieve high system throughput and to satisfy user requirements. The task scheduling problem has become more complex with the ever increasing size of Grid systems. Even though selecting an efficient resource allocation strategy for a particular task helps in obtaining a desired level of service, researchers still face difficulties in choosing a suitable technique from a plethora of existing methods in literature. In this paper, we explore and discuss existing resource allocation mechanisms for resource allocation problems employed in Grid systems. The work comprehensively surveys Gird resource allocation mechanisms for different architectures (centralized, distributed, static or dynamic). The paper also compares these resource allocation mechanisms based on their common features such as time complexity, searching mechanism, allocation strategy, optimality, operational environment and objective function they adopt for solving computing- and data-intensive applications. The comprehensive analysis of cutting-edge research in the Grid domain presented in this work provides readers with an understanding of essential concepts of resource allocation mechanisms in Grid systems and helps them identify important and outstanding issues for further investigation. It also helps readers to choose the most appropriate mechanism for a given system/application.
- Published
- 2014
12. Security, energy, and performance-aware resource allocation mechanisms for computational grids
- Author
-
Ewa Niewiadomska-Szynkiewicz, Joanna Kolodziej, Samee U. Khan, Cheng-Zhong Xu, Albert Y. Zomaya, Sajjad A. Madani, Lizhe Wang, and Marek Kisiel-Dorohinicki
- Subjects
Job scheduler ,Job shop scheduling ,Computer Networks and Communications ,business.industry ,Computer science ,Distributed computing ,Cyber-physical system ,Cloud computing ,Energy consumption ,Grid ,computer.software_genre ,Dynamic voltage scaling ,Scheduling (computing) ,Grid computing ,Hardware and Architecture ,Scalability ,Resource allocation ,business ,computer ,Software ,Efficient energy use - Abstract
Distributed Cyber Physical Systems (DCPSs) are networks of computing systems that utilize information from their physical surroundings to provide important services, such as smart health, energy efficient grid and cloud computing, and smart security-aware grids. Ensuring the energy efficiency, thermal safety, and long term uninterrupted computing operation increases the scalability and sustainability of these infrastructures. Achieving this goal often requires researchers to harness an understanding of the interactions between the computing equipment and its physical surroundings. Modeling these interactions can be computationally challenging with the resources on hand and the operating requirements of such systems. In this paper, we define the independent batch scheduling in Computational Grid (CG) as a three-objective global optimization problem with makespan, flowtime and energy consumption as the main scheduling criteria minimized according to different security constraints. We use the Dynamic Voltage Scaling (DVS) methodology for reducing the cumulative power energy utilized by the system resources. We develop six genetic-based single- and multi-population meta-heuristics for solving the considered optimization problem. The effectiveness of these algorithms has been empirically justified in two different grid architectural scenarios in static and dynamic modes.
- Published
- 2014
13. Leveraging a Compound Graph-Based DHT for Multi-Attribute Range Queries with Performance Analysis
- Author
-
Cheng-Zhong Xu and Haiying Shen
- Subjects
Range query (data structures) ,Computer science ,Distributed computing ,Graph theory ,Peer-to-peer ,computer.software_genre ,Theoretical Computer Science ,Distributed hash table ,Computational Theory and Mathematics ,Grid computing ,Hardware and Architecture ,Server ,Scalability ,Overhead (computing) ,Resource allocation ,computer ,Software - Abstract
Resource discovery is critical to the usability and accessibility of grid computing systems. Distributed Hash Table (DHT) has been applied to grid systems as a distributed mechanism for providing scalable range-query and multi-attribute resource discovery. Multi-DHT-based approaches depend on multiple DHT networks with each network responsible for a single attribute. Single-DHT-based approaches keep the resource information of all attributes in a single node. Both classes of approaches lead to high overhead. In this paper, we propose a Low-Overhead Range-query Multi-attribute (LORM) DHT-based resource discovery approach. Unlike other DHT-based approaches, LORM relies on a single compound graph-based DHT network and distributes resource information among nodes in balance by taking advantage of the compound graph structure. Moreover, it has high capability to handle the large-scale and dynamic characteristics of resources in grids. Experimental results demonstrate the efficiency of LORM in comparison with other resource discovery approaches. LORM dramatically reduces maintenance and resource discovery overhead. In addition, it yields significant improvements in resource location efficiency. We also analyze the performance of the LORM approach rigorously by comparing it with other multi-DHT-based and single-DHT-based approaches with respect to their overhead and efficiency. The analytical results are consistent with experimental results, and prove the superiority of the LORM approach in theory.
- Published
- 2012
14. Filter Design and Analysis in Frequency Domain for Server Scheduling and Optimization
- Author
-
Cheng-Zhong Xu, Le Yi Wang, Minghua Xu, and George Yin
- Subjects
Queueing theory ,business.industry ,Computer science ,Distributed computing ,Workload ,Internet traffic ,Scheduling (computing) ,Service-level agreement ,Filter design ,Computational Theory and Mathematics ,Hardware and Architecture ,Server ,Frequency domain ,Mean value analysis ,Signal Processing ,Resource allocation ,Resource management ,The Internet ,business ,Generalized processor sharing - Abstract
Internet traffic often exhibits a structure with rich high-order statistical properties like self-similarity and long-range dependency (LRD). This greatly complicates the problem of server performance modeling and optimization. Existing tools like queuing models in most cases only hold in mean value analysis under the assumption of simplified traffic structures. In this paper, we present a filter model to characterize the relationship among the factors of server capacity, request scheduling, and service quality for general input traffic. By the model, a server scheduler operates as an finite-duration impulse response (FIR) filter that transforms request processes into workload processes with the objective of minimizing load variation or overload probability, and meanwhile, without violating request response deadlines as defined in service-level agreements. We present a design and analysis of the filter for traffic with strong LRD in the frequency domain. Most Internet traffic has monotonically decreasing strength of variation functions over frequency. For this type of input traffic, we prove that optimal schedulers must have a convex structure. Uniform resource allocation is an extreme case of the convexity and is proved to be optimal for Poisson traffic. We integrate the convex structural principle with the Generalized Processor Sharing (GPS) discipline and show that the enhanced GPS policy improves the service quality significantly. Furthermore, we show that the presence of LRD in the input traffic results in shift of variation strength from high frequency to lower frequency bands and consequently leads to a degradation of the service quality.
- Published
- 2010
15. Elastic Routing Table with Provable Performance for Congestion Control in DHT Networks
- Author
-
Cheng-Zhong Xu and Haiying Shen
- Subjects
Routing protocol ,Virtual routing and forwarding ,business.industry ,Computer science ,Node (networking) ,Distributed computing ,Routing table ,Intrusion detection system ,Load balancing (computing) ,Distributed hash table ,Network congestion ,Load management ,Intelligent Network ,Computational Theory and Mathematics ,Hardware and Architecture ,Signal Processing ,Resource allocation ,business ,Consistent hashing ,Heterogeneous network ,Computer network - Abstract
Distributed hash table (DHT) networks based on consistent hashing functions have an inherent load balancing problem. The problem becomes more severe due to the heterogeneity of network nodes and the non-uniform and timevarying file popularity. Existing DHT load balancing algorithms are mainly focused on the issues caused by node heterogeneity. To deal with skewed lookups, this paper presents an elastic routing table (ERT) mechanism for query load balancing, based on the observation that high degree nodes tend to experience more traffic load. The mechanism allows each node to have a routing table of variable size corresponding to its capacity. The indegree and outdegree of the routing table can also be adjusted dynamically in response to the change of file popularity and network churn. Theoretical analysis proves the routing table degree is bounded. The ERT mechanism facilitates locality-aware randomized query forwarding to further improve lookup efficiency. By relating query forwarding to a supermarket customer service model, we prove a 2-way randomized query forwarding policy leads to an exponential improvement in query processing time over random walking. Simulation results demonstrate the effectiveness of the ERT mechanism and its related query forwarding policy for congestion and query load balancing. In comparison with the existing "virtual-server"-based load balancing algorithm and other routing table control approaches, the ERT-based congestion control protocol yields significant improvements in query lookup efficiency.
- Published
- 2010
16. eQoS: Provisioning of Client-Perceived End-to-End QoS Guarantees in Web Servers
- Author
-
Cheng-Zhong Xu and Jianbin Wei
- Subjects
Web server ,Computer science ,business.industry ,Quality of service ,Real-time computing ,Provisioning ,computer.software_genre ,Fuzzy logic ,Theoretical Computer Science ,File server ,Computational Theory and Mathematics ,Hardware and Architecture ,Web page ,Resource allocation ,The Internet ,business ,computer ,Software - Abstract
It is important to guarantee client-perceived end-to-end quality of service (QoS) under heavy load conditions. Existing work focuses on network transfer time or server-side request processing time. In this paper, we propose a novel framework, eQoS, to monitor and control client-perceived response time in heavy loaded Web servers. The response time is measured with respect to Web pages that contain multiple embedded objects. Within the framework, we propose an adaptive fuzzy controller, STFC, to allocate server resources. The controller assumes no knowledge of the pageview traffic model. It deals with the effect of process delay in resource allocation by its two-level self-tuning capabilities. We also prove the stability of the STFC. We implement a prototype of eQoS in Linux and conduct comprehensive experiments across wide-range server workload conditions on PlanetLab and simulated networks. Experimental results demonstrate the effectiveness of the framework: it controls the deviation of client-perceived pageview response time to be within 20 percent of a predefined target with both synthetic and real Web traffics. We also compare the STFC with other controllers, including static fuzzy, linear proportional integral (PI), and adaptive PI controllers. Experimental results show that, although the STFC works slightly worse than the static fuzzy controller in the environment where the static fuzzy controller is best tuned, because of its self-tuning capabilities, it has better performance in all other test cases by around 25 percent on average in terms of the deviation from the target response time. In addition, due to its model independence, the STFC outperforms the linear PI and adaptive PI controllers by 50 percent and 75 percent on average, respectively
- Published
- 2006
17. Resource Allocation for Session-Based Two-Dimensional Service Differentiation on e-Commerce Servers
- Author
-
Cheng-Zhong Xu, Jianbin Wei, and Xiaobo Zhou
- Subjects
Service (business) ,business.industry ,Computer science ,Quality of service ,Distributed computing ,Session (web analytics) ,Computational Theory and Mathematics ,Hardware and Architecture ,Server ,Signal Processing ,Scalability ,Resource allocation ,Resource management ,business ,Performance metric ,Computer network - Abstract
A scalable e-commerce server should be able to provide different levels of quality of service (QoS) to different types of requests based on clients' navigation patterns and the server capacity. E-commerce workloads are composed of sessions. In this paper, we propose a session-based two-dimensional (2D) service differentiation model for online transactions: intersession and intrasession. The intersession model aims to provide different levels of QoS to sessions from different customer classes, and the intrasession model aims to provide different levels of QoS to requests in different states of a session. A primary performance metric of online transactions is slowdown. It measures the waiting time of a request relative to its service time. We present a processing rate allocation scheme for 2D proportional slowdown differentiation. We then introduce service slowdown as a systemwide QoS metric of an e-commerce server. It is defined as the weighted sum of request slowdown in different sessions and in different session states. We formulate the problem of 2D service differentiation as an optimization of processing rate allocation with the objective of minimizing the service slowdown of the server. We prove that the derived rate allocation scheme based on the optimization guarantees client requests' slowdown to be square-root proportional to their prespecified differentiation weights in both intersession and intrasession dimensions. We evaluate this square-root proportional rate allocation scheme and a proportional rate allocation scheme via extensive simulations. Results validate that both schemes can achieve predictable, controllable, and fair 2D service differentiation on e-commerce servers. The square-root proportional rate allocation scheme provides 2D service differentiation at a minimum cost of service slowdown
- Published
- 2006
18. Robust Processing Rate Allocation for Proportional Slowdown Differentiation on Internet Servers
- Author
-
Jianbin Wei, Xiaobo Zhou, and Cheng-Zhong Xu
- Subjects
Queueing theory ,Web server ,Queue management system ,Computer science ,business.industry ,Distributed computing ,Quality of service ,Internet traffic ,computer.software_genre ,Theoretical Computer Science ,Computational Theory and Mathematics ,Hardware and Architecture ,Queuing delay ,Resource allocation ,The Internet ,business ,computer ,Software ,Computer network - Abstract
A desirable behavior of an Internet server is that a request's queuing delay depends on its service time in a linear fashion. Measuring the quality of service in terms of slowdown, the ratio of a request's queuing delay to its service time, provides a simple way to attain the objective. Moreover, it treats client requests equally regardless of their service time, whereas response time favors requests that need more processing resources. In this paper, we propose a proportional slowdown differentiation (PSD) service model on Internet servers. It aims to maintain prespecified slowdown ratios between different classes of client requests. To provide PSD services, we first derive a closed-form expression of the expected slowdown in an M/G/1 FCFS queuing system with a typical heavy-tailed service time distribution, the bounded Pareto distribution. Based on the closed-form expression, we design a queuing-theoretic strategy of processing-rate allocation. The rate allocation is realized by deploying a virtual server for each class. Simulation results show that the strategy can provide controllable PSD services on Internet servers. It, however, comes along with large variance and weak predictability due to the dynamics of Internet traffic. To address these issues, we design an integral feedback controller and integrate it into the queuing-theoretic strategy. Simulation results demonstrate that the integrated strategy is robust and can deliver predictable PSD services at a superior fine-grained level. We modified the Apache Web server with an implementation of the integrated processing-rate allocation strategy. Experimental results further demonstrate its effectiveness and feasibility in practice.
- Published
- 2005
19. Container-Based Job Management for Fair Resource Sharing
- Author
-
Bibo Tu, Pavan Balaji, Jue Hong, Shengzhong Feng, Junming Yan, Cheng-Zhong Xu, and Gaojin Wen
- Subjects
Job scheduler ,business.industry ,Computer science ,Distributed computing ,computer.software_genre ,Shared resource ,Resource (project management) ,Computer cluster ,Server ,Container (abstract data type) ,Resource allocation ,The Internet ,business ,computer ,Computer network - Abstract
Achieving fair resource sharing is rapidly becoming an essential requirement in cluster computing systems. Although many fair scheduling algorithms have been proposed in recent decades, controlling resource sharing among jobs on servers remains a challenging problem that, if not handled well, may result in chaotic resource contention and service-level agreement violation of jobs. To address this problem, we propose a resource container–based job management approach for fair resource sharing. In our approach, we first design and implement a general container-based job management module, providing lightweight and fine-grained resource allocation and isolation for job execution. With this module, we propose a resource-aware management scheme to enable fair resource sharing in job scheduling and dispatching. We conduct experiments by implementing the proposed module and applying the scheme on TCluster, a self-developed cluster computing system of a worldwide top Internet corporation. Results show that our approach performs well in guaranteeing fair resource sharing with negligible overhead.
- Published
- 2013
20. Mechanism Design for Stochastic Virtual Resource Allocation in Non-cooperative Cloud Systems
- Author
-
Cheng-Zhong Xu, Minyi Guo, and Zhen Kong
- Subjects
business.industry ,Computer science ,Distributed computing ,Cloud computing ,Virtualization ,computer.software_genre ,Shared resource ,Resource (project management) ,Incentive compatibility ,Virtual machine ,Resource allocation ,Resource management ,business ,computer - Abstract
Currently, virtualization technology has been widely adopted by cloud service providers to provide flexible and cost-effective resource sharing among users. On cloud platforms, computing resources are allocated on-demand dynamically and the application hosted on a virtual machine(VM) usually has the illusion of complete control of resources. Thus, a selfish VM may strategically compete for resource with other VMs to maximize its own benefit while at the cost of overall system performance. This problem poses new challenges to cloud providers, who must thwart non-cooperative behavior as well as allocating resource among selfish VMs efficiently. In this paper, we propose to utilize mechanism design to allocate resource among selfish VMs in a non-cooperative cloud environment. Because the accurate relationship between VM's valuation function and allocated resource may not be available in practice and the valuation function parameters may not noise free, we also propose to apply stochastic approximation methods to get stochastic solution for allocation and payment outcomes. We show through theoretical analysis and simulations that the proposed stochastic mechanism is efficient and incentive compatible. That is, the incorporation of mechanism design for virtualized resource allocation is able to enforce cooperation and achieve efficient resource utilization among selfish VMs in non-cooperative cloud systems.
- Published
- 2011
21. Self-adaptive provisioning of virtualized resources in cloud computing
- Author
-
Jia Rao, Xiangping Bu, Cheng-Zhong Xu, and Kun Wang
- Subjects
Cloud management ,business.industry ,Computer science ,Distributed computing ,Autonomous agent ,Testbed ,Cloud computing ,Provisioning ,computer.software_genre ,Autonomic computing ,Virtual machine ,Reinforcement learning ,Resource allocation ,business ,computer - Abstract
In this paper, we propose a distributed learning mechanism that facilitates self-adaptive virtual machines resource provisioning. We treat cloud resource allocation as a distributed learning task, in which each VM being a highly autonomous agent submits resource requests according to its own benefit. The mechanism evaluates the requests and replies with feedback. We develop a reinforcement learning algorithm with a highly efficient representation of experiences as the heart of the VM side learning engine. We prototype the mechanism and the distributed learning algorithm in an iBalloon system. Experiment results on a Xen-based cloud testbed demonstrate the effectiveness of iBalloon.
- Published
- 2011
22. Proactive Resource Management for Failure Resilient High Performance Computing Clusters
- Author
-
Cheng-Zhong Xu and Song Fu
- Subjects
Virtual machine ,Computer science ,Reliability (computer networking) ,Distributed computing ,Control reconfiguration ,Resource allocation ,Dependability ,Resource management ,computer.software_genre ,Supercomputer ,computer ,Abstraction layer - Abstract
Virtual machine (VM) technology provides an additional layer of abstraction for resource management in high performance computing (HPC) systems. In large-scale computing clusters, component failures become norms instead of exceptions, caused by the ever-increasing system complexity. VM construction and reconfiguration is a potent tool for efficient online system maintenance and failure resilience. In this paper, we study how VM-based HPC clusters benefits from failure prediction in resource management for dependable computing. We consider both the reliability and performance status of compute nodes in making selection decisions. We define a capacity-reliability metric to combine the effects of both factors, and propose the Best-fit algorithm to find the best qualified nodes on which to instantiate VMs to run user jobs. We have conducted experiments using failure traces from the Los Alamos National Laboratory (LANL) HPC clusters. The results show the enhancement of system dependability by using our proposed strategy with practically achievable accuracy of failure prediction. With the Best-fit strategies, the job completion rate is increased by 10.5% compared with that achieved in the current LANL HPC cluster. The task completion rate reaches 82.5% with improved utilization of relatively unreliable nodes.
- Published
- 2009
23. Random choices for churn resilient load balancing in peer-to-peer networks
- Author
-
Cheng-Zhong Xu, Haiying Shen, and Song Fu
- Subjects
business.industry ,Computer science ,Node (networking) ,Distributed computing ,Overlay network ,Load balancing (computing) ,Peer-to-peer ,computer.software_genre ,Load management ,Capacity planning ,Resource allocation ,Algorithm design ,business ,Consistent hashing ,Queue ,computer ,Computer network - Abstract
Peer-to-peer (P2P) networks based on consistent hashing functions have an inherent load uneven distribution problem. Things are even worse in unstructured P2P systems. The objective of load balancing in P2P networks is to balance the workload of the network nodes in proportion to their capacity so as to eliminate traffic bottleneck. It is challenging because of the dynamic nature of overlay networks and time-varying load characteristics. Random choices schemes can balance load effectively while incurring only a small overhead, making such schemes appealing for practical systems. Existing theoretical work analyzing properties of random choices algorithms can not be applied in the highly dynamic and heterogeneous P2P systems. In this paper, we characterize the behaviors of randomized search schemes in the general P2P environment. We extend the supermarket model by investigating the impact of node heterogeneity and churn to the load distribution in P2P networks. We prove that by using d-way random choices schemes, the length of the longest queue in P2P systems with heterogeneous nodal capacity and node churn for d ges 2 is clog logn/logd + O(1) with high probability, where c is a constant.
- Published
- 2008
24. LORM: Supporting low-overhead P2P-based range-query and multi-attribute resource management in grids
- Author
-
Cheng-Zhong Xu, Amy Apon, and Haiying Shen
- Subjects
Human resource management system ,Range query (data structures) ,Computer science ,Quality of service ,Distributed computing ,computer.software_genre ,Application software ,Resource (project management) ,Grid computing ,Scalability ,Overhead (computing) ,Resource allocation ,Resource management ,computer - Abstract
Resource management is critical to the usability and accessibility of grid computing systems. Conventional approaches to grid resource discovery are either centralized or hierarchical, and these prove to be inefficient as the size of the grid system increases. The peer-to-peer (P2P) paradigm has been applied to grid systems as a mechanism for providing scalable range- query and multi-attribute resource management. However, most current P2P-based resource management approaches support multi-attribute range queries at a high cost. They either depend on multiple P2P networks with each P2P network responsible for a single attribute, or they keep the resource information of all attributes in a single node. This paper presents a low-overhead range-query multi-attribute P2P-based resource management approach, LORM. Unlike other P2P-based approaches, it relies on a single P2P network and allocates resource information to different nodes based on resource attributes and values. Moreover, it has high capability to handle the large-scale and dynamic characteristics of resources in grids. Simulation results demonstrate the efficiency of LORM in comparison with other resource management approaches in terms of resource management overhead and resource discovery efficiency.
- Published
- 2007
25. Quantitative Service Differentiation: A Square-Root Proportional Model
- Author
-
Cheng-Zhong Xu and Xiaobo Zhou
- Subjects
Service (business) ,Queueing theory ,Service quality ,Mathematical optimization ,Computer science ,business.industry ,Quality of service ,Real-time computing ,Mobile computing ,Context (language use) ,Admission control ,computer.software_genre ,Resource allocation ,The Internet ,Web service ,business ,computer - Abstract
Due to the open and dynamics nature of ubiquitous computing environments and services, quantitative service differentiation is needed to provide controllable quality of service (QoS) levels to meet changing system configuration and resource availability and to satisfy different requirements of applications and users. A proportional differentiation model was proposed in the DiffServ context, which states that QoS factors of certain classes of aggregated traffic be proportional to their differentiation weights. While it provides compelling proportionality fairness to clients, it lacks of the support of a server-side QoS optimization with respect to the resource allocation. In this paper, we propose and promote a square-root proportional differentiation model for delay-sensitive Internet services. Interestingly, both popular QoS factors with respect to delay, queueing delay and slowdown, are reciprocally proportional to the allocated resource usages. We formulate the problem of quantitative service differentiation as a resource allocation optimization towards the minimization of system delay, defined as the sum of weighted responsiveness of client request classes. We prove that the optimization-based resource allocation scheme essentially provides square-root proportional service differentiation to clients. We then propose a generalized rate-based resource allocation approach. Simulation results demonstrate that the approach provides quantitative service differentiation at a minimum cost of system delay
- Published
- 2006
26. Locality-Aware Randomized Load Balancing Algorithms for DHT Networks
- Author
-
Haiying Shen and Cheng-Zhong Xu
- Subjects
Computer science ,business.industry ,Distributed computing ,ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS ,Locality ,Overlay network ,Load balancing (computing) ,Load management ,Scalability ,Resource allocation ,Resource management ,Algorithm design ,business ,Computer network - Abstract
Structured P2P overlay networks based on a consistent hashing function have an aftermath load balance problem that needs to be dealt with. A load balancing method should take into account both proximity and dynamic features of DHTs, Randomized matching between heavily loaded nodes with lightly loaded nodes can deal with the dynamic feature. But current randomized methods are unable to consider physical proximity of the node simultaneously. There are locality-aware methods that rely on an additional logical network to capture the physical locality in load balancing. Due to the cost for network construction and maintenance, these locality-aware algorithms can hardly deal with DHTs with churn. This paper presents a locality-aware randomized load balancing algorithm to deal with both of the proximity and dynamic features of DHTs. We introduce a factor of randomness in the probing process in a range of proximity to deal with the DHT churn. We further improve the randomized load balancing efficiency by d-way probing. Simulation results show the superiority of a locality-aware 2-way randomized load balancing in DHTs, in comparison with other pure random policies and locality-aware sequential algorithms. In DHTs with churn, it performs no worse than the best churn resilient algorithm.
- Published
- 2005
27. Service Migration in Distributed Virtual Machines for Adaptive Grid Computing
- Author
-
Cheng-Zhong Xu and Song Fu
- Subjects
Computer science ,Distributed computing ,Mobile computing ,Thread (computing) ,Application software ,computer.software_genre ,Grid ,Abstraction layer ,Grid computing ,Virtual machine ,Server ,Resource allocation ,Resource allocation (computer) ,Resource management ,computer - Abstract
Computational grids can integrate geographically distributed resources into a seamless environment. To facilitate managing these heterogeneous resources, the virtual machine technology provides a powerful layer of abstraction and allows multiple applications to multiplex the resources of a grid computer. On the other hand, the grid dynamics requires the virtual machine system be distributed and reconfigurable. However, the existing migration approaches only move the execution entities, such as processes, threads, and mobile agents, among servers and leave the runtime services behind. They are not potent to achieve service reconfiguration in face of server overload or failures. In this paper, we propose a service migration mechanism, which moves the computational services of a virtual server, for instance a shared array runtime support system, to available servers for adaptive grid computing. In this way, parallel jobs can resume computation on a remote server without requiring service preinstallation. As an illustration of the service migration mechanism, we incorporated it into a Java-compliant distributed virtual machine, DSA, and formed a Mobile DSA (M-DSA) to accommodate adaptive parallel applications in grids. We measured the performance of M-DSA in the execution of applications from the SPLASH-2 benchmark suite on a campus grid. Experimental results show that service migration can achieve system adaptivity effectively.
- Published
- 2005
28. A Coordinated Spatio-Temporal Access Control Model for Mobile Computing in Coalition Environments
- Author
-
Cheng-Zhong Xu and Song Fu
- Subjects
business.industry ,Computer science ,Distributed computing ,Authorization ,Mobile computing ,Data security ,Access control ,Shared resource ,Server ,Role-based access control ,Resource allocation ,Mobile agent ,Resource management ,business ,Resource management (computing) ,Mobile device ,Computer network - Abstract
A primary concern in mobile computing is security. Mobile clients often relocate between different networks and connect to different data servers at different times. This poses new challenges to the resource access control in mobile computing. The resource sharing in a coalition environment creates certain temporal and spatial requirements for the accesses by mobile devices. However, there is a lack of formal treatment of the impact of mobility to the shared resource access control. In this paper, we introduce the shared resource access language, SRAL, to model the behavior of mobile devices. The language is structured and compositional so that programs of a mobile device can be constructed recursively from primitive accesses. We prove that SRAL is expressive enough for most resource access patterns. In particular, it is complete in the sense that it can specify any program of regular trace model. A constraint language is defined to specify spatial constraints for shared resource accesses. The problem of checking if a mobile object satisfies a given spatial constraint can be solved in a polynomial-time algorithm. We apply duration calculus to express temporal constraints, and show the temporal constraint satisfaction problem is decidable as well. We extend the role-based access control (RBAC) model to specify and enforce spatio-temporal constraints. This coordinated access control model has been implemented in a mobile agent system, which emulates mobile computing by software agents.
- Published
- 2005
29. Consistent proportional delay differentiation: a fuzzy control approach
- Author
-
Cheng-Zhong Xu and Jianbin Wei
- Subjects
Equilibrium point ,Service quality ,Queueing theory ,Dynamic bandwidth allocation ,Computer Networks and Communications ,Network packet ,Computer science ,Quality of service ,Fuzzy set ,Real-time computing ,Fuzzy control system ,Hop (networking) ,Nonlinear system ,Bandwidth allocation ,Differentiated services ,Robustness (computer science) ,Control theory ,Control system ,Proportional delay differentiation ,Resource allocation ,Resource management ,Simulation - Abstract
Proportional delay differentiation (PDD) is an important service model for providing relative differentiated services on the Internet. It aims to maintain pre-specified packet queueing-delay ratios between different classes of traffic at each hop. Existing rate-allocation approaches for PDD services assume the average queueing delay of a class is inversely proportional to its service rate. This assumption is not necessarily valid when the system is not heavily loaded. To provide consistent PDD services under various load conditions, in this paper, we propose a novel rate-allocation approach that applies fuzzy control theory to capture the nonlinear relationship between the queueing delay and the service rate. In the approach, a class's service rate is adjusted according to a set of fuzzy control rules defined over its error (the difference between the target delay ratio and the achieved one), the change of error, and the change of service rate. We prove that the fuzzy control system is stable and the service rate of a class converges to its equilibrium point at steady state. Simulation results demonstrate that, in comparison with other rate-allocation approaches, the fuzzy control approach is able to provide consistent PDD services under wide range load conditions. It is also shown robust under various system conditions, including with multiple classes, changing target delay ratios, changing load conditions, and different traffic patterns.
- Published
- 2005
30. A comparative study on resource allocation and energy efficient job scheduling strategies in large-scale parallel computing systems.
- Author
-
Chandio, Aftab, Bilal, Kashif, Tziritas, Nikos, Yu, Zhibin, Jiang, Qingshan, Khan, Samee, and Xu, Cheng-Zhong
- Subjects
COMPARATIVE studies ,RESOURCE allocation ,QUALITY of service ,PARALLEL programs (Computer programs) ,LOAD balancing (Computer networks) ,COMPUTER power supply management ,ENERGY consumption of computers - Abstract
In the large-scale parallel computing environment, resource allocation and energy efficient techniques are required to deliver the quality of services (QoS) and to reduce the operational cost of the system. Because the cost of the energy consumption in the environment is a dominant part of the owner's and user's budget. However, when considering energy efficiency, resource allocation strategies become more difficult, and QoS (i.e., queue time and response time) may violate. This paper therefore is a comparative study on job scheduling in large-scale parallel systems to: (a) minimize the queue time, response time, and energy consumption and (b) maximize the overall system utilization. We compare thirteen job scheduling policies to analyze their behavior. A set of job scheduling policies includes (a) priority-based, (b) first fit, (c) backfilling, and (d) window-based policies. All of the policies are extensively simulated and compared. For the simulation, a real data center workload comprised of 22385 jobs is used. Based on results of their performance, we incorporate energy efficiency in three policies i.e., (1) best result producer, (2) average result producer, and (3) worst result producer. We analyze the (a) queue time, (b) response time, (c) slowdown ratio, and (d) energy consumption to evaluate the policies. Moreover, we present a comprehensive workload characterization for optimizing system's performance and for scheduler design. Major workload characteristics including (a) Narrow, (b) Wide, (c) Short, and (d) Long jobs are characterized for detailed analysis of the schedulers' performance. This study highlights the strengths and weakness of various job scheduling polices and helps to choose an appropriate job scheduling policy in a given scenario. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
31. Energy-Aware Modeling and Scheduling for Dynamic Voltage Scaling with Statistical Real-Time Guarantee.
- Author
-
Xiliang Zhong and Cheng-Zhong Xu
- Subjects
- *
POWER resources , *ENERGY consumption , *REAL-time computing , *ELECTRONIC data processing , *INFORMATION retrieval , *NONLINEAR theories , *COMPUTER algorithms , *RESOURCE allocation , *HIGH technology industries - Abstract
Dynamic voltage scaling (DVS) is a promising technique for battery-powered systems to conserve energy consumption. Most existing DVS algorithms assume information about task periodicity or a priori knowledge about the task set to be scheduled. This paper presents an analytical model of general tasks for DVS assuming job timing information is known only after a task release. It models the voltage scaling process as a transfer function-based filtering system, which facilitates the design of two efficient scaling algorithms. The first is a time-invariant scaling policy and it is proved to be a generalization of several popular DVS algorithms for periodic, sporadic, and aperiodic tasks. A more energy efficient policy is a time-variant scaling algorithm for aperiodic tasks. It is optimal in the sense that it is online without assumed information about future task releases. The algorithm turns out to be a water-filling process with a linear time complexity. It can be applied to scheduling based on worst-case execution times as well as online slack distribution when jobs complete earlier. We further establish two relationships between computation capacity and deadline misses to provide a statistical real-time guarantee with reduced capacity. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
32. eQoS: Provisioning of Client-Perceived End-to-End QoS Guarantees in Web Servers.
- Author
-
Jianbin Wei and Cheng-Zhong Xu
- Subjects
- *
CUSTOMER services , *QUALITY of service , *INTERNET servers , *REACTION time , *WEBSITES , *COMPUTER operating systems , *PROCESS control systems , *PROGRAMMABLE controllers , *RESOURCE allocation - Abstract
It is important to guarantee client-perceived end-to-end quality of service (Q0S) under heavy load conditions. Existing work focuses on network transfer time or server-side request processing time. In this paper, we propose a novel framework, eQoS, to monitor and controll client-perceived response time in heavy loaded Web servers. The response time is measured with respect to Web pages that contain multiple embedded objects. Within the framework, we propose an adaptive fuzzy controller, STFC, to allocate server resources. The controller assumes no knowledge of the pageview traffic model. It deals with the effect of process delay in resource allocation by its two-level self-tuning capabilities. We also prove the stability of the STFC. We implement a prototype of eQoS in Linux and conduct comprehensive experiments across wide-range server workload conditions on PlanetLab and simulated networks. Experimental results demonstrate the effectiveness of the framework: It controls the deviation of client-perceived pageview response time to be within 20 percent of a predefined target with both synthetic and real Web traffics. We also compare the STFC with other controllers, including static fuzzy, linear proportional integral (PI), and adaptive PI controllers. Experimental results show that, although the STFC works slightly worse than the static fuzzy controller in the environment where the static fuzzy controller is best tuned, because of its self-tuning capabilities, it has better performance in all other test cases by around 25 percent on average in terms of the deviation from the target response time. In addition, due to its model independence, the STFC outperforms the linear P1 and adaptive P1 controllers by 50 percent and 75 percent on average, respectively. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
33. Resource Allocation for Session-Based Two-Dimensional Service Differentiation on e-Commerce Servers.
- Author
-
Xiaobo Zhou, Jianbin Wei, and Cheng-Zhong Xu
- Subjects
CLIENT/SERVER computing ,CUSTOMER services ,ELECTRONIC commerce ,COMMERCE service providers ,RESOURCE allocation ,QUALITY of service ,ONLINE data processing - Abstract
A scalable e-commerce server should be able to provide different levels of quality of service (QoS) to different types of requests based on clients' navigation patterns and the server capacity. E-Commerce workloads are composed of sessions. In this paper, we propose a session-based two-dimensional (2D) service differentiation model for online transactions: intersession and intrasession. The intersession model aims to provide different levels of QoS to sessions from different customer classes, and the intrasession model aims to provide different levels of QoS to requests in different states of a session. A primary performance metric of online transactions is slowdown. It measures the waiting time of a request relative to its service time. We present a processing rate allocation scheme for 2D proportional slowdown differentiation. We then introduce service slowdown as a systemwide QoS metric of an e-commerce server. It is defined as the weighted sum of request slowdown in different sessions and in different session states. We formulate the problem of 2D service differentiation as an optimization of processing rate allocation with the objective of minimizing the service slowdown of the server. We prove that the derived rate allocation scheme based on the optimization guarantees client requests' slowdown to be square-root proportional to their prespecified differentiation weights in both intersession and intrasession dimensions. We evaluate this square-root proportional rate allocation scheme and a proportional rate allocation scheme via extensive simulations. Results validate that both schemes can achieve predictable, controllable, and fair 2D service differentiation on e-commerce servers. The square-root proportional rate allocation scheme provides 2D service differentiation at a minimum cost of service slowdown. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
34. Optimal periodic remapping of bulk synchronous computations on multiprogrammed distributed systems
- Author
-
Le Yi Wang, Cheng-Zhong Xu, and Ngo-Tai Fong
- Subjects
Nondeterministic algorithm ,Hardware_MEMORYSTRUCTURES ,Computer science ,Distributed computing ,Computation ,Resource allocation ,Stochastic optimization ,Transient (computer programming) ,Parallel computing ,Computer multitasking ,Complement (set theory) - Abstract
For bulk synchronous computations that have nondeterministic behaviors, dynamic remapping is an effective approach to ensure parallel efficiency. There are two basic issues in remapping: when and how to remap. This paper presents a formal treatment of the first issue for dynamic computations with a priori known statistical behaviors. We have formulated the problem as two complement sequential stochastic optimization, with an objective of finding optimal remapping frequencies for a given tolerance of load imbalance on multiprogrammed distributed systems. We have developed analytical approaches to precisely characterize the transient statistical behaviors of the workload process and derived optimal remapping frequencies for various random workload change processes.
35. A self-tuning fuzzy control approach for end-to-end QoS guarantees in web servers
- Author
-
Cheng-Zhong Xu and Jianbin Wei
- Subjects
Web server ,Queueing theory ,Adaptive control ,business.industry ,Computer science ,Quality of service ,Real-time computing ,Fuzzy control system ,computer.software_genre ,Fuzzy logic ,Control theory ,Web page ,Resource allocation ,The Internet ,business ,computer - Abstract
It is important to guarantee end-to-end quality of service (QoS) under heavy-load conditions. Existing work focus on server-side request processing time or queueing delays in the network core. In this paper, we propose a novel framework eQoS to monitoring and controlling client-perceived response time in Web servers. The response time is measured with respect to requests for Web pages that contain multiple embedded objects. Within the framework, we propose an adaptive fuzzy controller, STFC, to allocating server resources. It deals with the effect of process delay in resource allocation by its two-level self-tuning capabilities. Experimental results on PlanetLab and simulated networks demonstrate the effectiveness of the framework: it controls client-perceived pageview response time to be within 20% of a pre-defined target. In comparison with static fuzzy controller, experimental results show that, although the STFC has slightly worse performance in the environment where the static fuzzy controller is best tuned, because of its self-tuning capabilities, it works better in all other test cases by 25% in terms of the deviation from the target response time. In addition, due to its model independence, the STFC outperforms the linear proportional integral (PI) and adaptive PI controllers by 50% and 75%, respectively.
36. Modeling and analysis of 2D service differentiation on e-commerce servers
- Author
-
Cheng-Zhong Xu, Xiaobo Zhou, and Jianbin Wei
- Subjects
Service (systems architecture) ,Queueing theory ,Computer science ,business.industry ,Quality of service ,Distributed computing ,Provisioning ,Session (web analytics) ,Server ,Scalability ,Resource allocation ,The Internet ,business ,Computer network - Abstract
A scalable e-commerce server should be able to provide different levels of quality of service (QoS) to different types of requests according to clients' navigation patterns and the server capacity. In this paper, we propose a two-dimensional (2D) service differentiation (DiffServ) model for online transactions: inter-session and intra-session. The inter-session model aims to provide different levels of QoS to sessions from different customer classes, and the intra-session model aims to provide different levels of QoS to requests in different states of a session. We introduce service slowdown as a QoS metric of e-commerce servers. It is defined as the weighted sum of request slowdown in different sessions and in different session states. We formulate the problem of 2D DiffServ provisioning as an optimization of processing rate allocation with the objective of minimizing service slowdown. We derive the optimal allocations for an M/G/1 server under various server load conditions and prove that the optimal allocations guarantees requests' slowdown to be square-root proportional to their pre-specified differentiation weights in both dimensions. We evaluate the optimal allocation scheme via extensive simulations and compare it with a tailored proportional DiffServ scheme. Simulation results validate that both allocation schemes can achieve predictable, controllable, and fair 2D slowdown differentiation on e-commerce servers. The optimal allocation scheme guarantees 2D DiffServ at a minimum cost of service slowdown.
37. Performance evaluation of load distribution strategies in parallel branch and bound computations
- Author
-
S. Tschoke, Cheng-Zhong Xu, and B. Monien
- Subjects
Load management ,Speedup ,Branch and bound ,Computer science ,Computation ,Parallel algorithm ,Concurrent computing ,Resource allocation ,Load distribution ,Parallel computing ,Load balancing (computing) - Abstract
Load distribution is essential for efficient use of available processors in a parallel branch-and-bound computation because the computation generates and consumes non-uniform subproblems at runtime. This paper presents six decentralized load distribution strategies. They are incorporated in a runtime support system, and evaluated in the solution of set partitioning problems on two parallel computer systems. It is observed that local averaging strategies outperform the randomized allocation and the Acwn algorithm significantly in large scale systems. They lead to an almost linear speedup in a PowerPC-based system with up to 32 nodes and to a speedup of 146.8 in a transputer-based system with 256 nodes. It is also observed that the randomized allocation and the Acwn algorithm can be improved by 10% to 15% when the bound information of subproblems is accounted for in the decision-making for load balancing.
38. Filter Design and Analysis in Frequency Domain for Server Scheduling and Optimization.
- Author
-
Xu, Cheng-Zhong, Xu, Minghua, Wang, Le Yi, and Yin, George
- Abstract
Internet traffic often exhibits a structure with rich high-order statistical properties like self-similarity and long-range dependency (LRD). This greatly complicates the problem of server performance modeling and optimization. Existing tools like queuing models in most cases only hold in mean value analysis under the assumption of simplified traffic structures. In this paper, we present a filter model to characterize the relationship among the factors of server capacity, request scheduling, and service quality for general input traffic. By the model, a server scheduler operates as an finite-duration impulse response (FIR) filter that transforms request processes into workload processes with the objective of minimizing load variation or overload probability, and meanwhile, without violating request response deadlines as defined in service-level agreements. We present a design and analysis of the filter for traffic with strong LRD in the frequency domain. Most Internet traffic has monotonically decreasing strength of variation functions over frequency. For this type of input traffic, we prove that optimal schedulers must have a convex structure. Uniform resource allocation is an extreme case of the convexity and is proved to be optimal for Poisson traffic. We integrate the convex structural principle with the Generalized Processor Sharing (GPS) discipline and show that the enhanced GPS policy improves the service quality significantly. Furthermore, we show that the presence of LRD in the input traffic results in shift of variation strength from high frequency to lower frequency bands and consequently leads to a degradation of the service quality. [ABSTRACT FROM PUBLISHER]
- Published
- 2010
- Full Text
- View/download PDF
39. On minimizing the resource consumption of cloud applications using process migrations.
- Author
-
Tziritas, Nikos, Khan, Samee Ullah, Xu, Cheng-Zhong, Loukopoulos, Thanasis, and Lalis, Spyros
- Subjects
- *
CLOUD computing , *RESOURCE allocation , *COMPUTER software , *ALGORITHMS , *STOCHASTIC convergence , *PERFORMANCE evaluation - Abstract
Abstract: According to the pay-per-use model adopted in clouds, the more resources an application running in a cloud computing environment consumes, the greater the amount of money the owner of the corresponding application will be charged. Therefore, applying intelligent solutions to minimize the resource consumption is of great importance. In this paper, we study the problem of identifying an assignment scheme between the interacting components of an application, such as processes and virtual machines, and the computing nodes of a cloud system, such that the total amount of resources consumed by the respective application is minimized. Because centralized solutions are deemed unsuitable for large distributed systems or large-scale applications, we propose a fully distributed algorithm (called DRA) to overcome scalability issues. DRA takes decisions concerning the transition from one assignment scheme to another in a dynamic way, based solely on local information. We also propose and test two modifications of the basic DRA algorithm to deal better with the heterogeneity of cloud servers in terms of capacity constraints. We must note that we capture heterogeneity regarding the network model. Through theoretical analysis, we formally prove that DRA achieves convergence and always provides an optimal solution for tree-based networks in the uncapacitated case. Moreover, we prove through experimental evaluation that DRA achieves up to 55% network cost reduction when compared to the most recent algorithm in the literature. We also show that the proposed modifications of DRA improve the algorithm’s performance considerably in the case where servers have limited capacity. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
40. A survey on resource allocation in high performance distributed computing systems.
- Author
-
Hussain, Hameed, Malik, Saif Ur Rehman, Hameed, Abdul, Khan, Samee Ullah, Bickler, Gage, Min-Allah, Nasro, Qureshi, Muhammad Bilal, Zhang, Limin, Yongji, Wang, Ghani, Nasir, Kolodziej, Joanna, Zomaya, Albert Y., Xu, Cheng-Zhong, Balaji, Pavan, Vishnu, Abhinav, Pinel, Fredric, Pecero, Johnatan E., Kliazovich, Dzmitry, Bouvry, Pascal, and Li, Hongxiang
- Subjects
- *
COMPUTER surveys , *RESOURCE allocation , *HIGH performance computing , *DISTRIBUTED computing , *INDUSTRIAL applications , *COMPUTER software , *COMPUTER network resources - Abstract
Highlights: [•] Classification of high performance computing (HPC) systems is provided. [•] Current HPC paradigms and industrial application suites are discussed. [•] State of the art in HPC resource allocation is reported. [•] Hardware and software solutions are discussed for optimized HPC systems. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.