Search

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.

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.

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%.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.