Optimal resource allocation in synchronized multi-tier Internet services

Modern Internet systems have evolved from simple monolithic systems to complex multi-tiered architectures. For these systems, providing good response time performance is crucial for commercial success. In practice, the response-time performance of multi-tiered systems is often degraded by severe synchronization problems, causing jobs to wait for responses from different tiers. Synchronization between different tiers is a complicating factor in the optimal control and analysis of performance. In this paper, we study a generic multi-tier model with synchronization in a queuing-theoretical setting. The system is able to share processing capacity between arriving jobs that need to be sent to other tiers and the responses that have arrived after processing from these tiers. We provide structural results on the optimal resource allocation policy and provide a full characterization of the policy in the framework of Markov decision theory. We also highlight important effects of synchronization in the model. We validate our expressions through extensive experimentations for a wide range of resource configurations.     

Temporal isolation in real-time systems: the VBS approach

Temporal isolation in real-time systems allows the execution of software processes isolated from one another in the temporal domain. Intuitively, the execution of a process is temporally isolated if the real-time behavior of the process is independent of the execution of the other concurrently scheduled processes in the system. The article provides a comprehensive discussion of temporal isolation through variable-bandwidth servers (VBSs). VBS consists of an EDF-based uniprocessor scheduling algorithm and a utilization-based schedulability test. The scheduling algorithm runs in constant time modulo the time complexity of queue management. The schedulability test runs in time linear in the number of processes and enables admission of an individual process in constant time. The test is a sufficient condition for VBS to provide temporal isolation through lower and upper response-time bounds on processes. We present the VBS design, implementation, proofs, and experiments, followed by condensed versions of results on scheduler overhead accounting with VBS and on reducing power consumption in VBS systems.     

Approximation techniques for response-time analysis of static-priority tasks

We consider sporadic tasks with static priorities and constrained deadlines to be executed upon a uniprocessor platform. Pseudo-polynomial time algorithms are known for computing worst-case response times for this task model. Some applications require to evaluate efficiently upper bounds of response times. For this purpose, we propose parametric algorithms that allow to make a tradeoff between quality of results and computational effort according to an input accuracy parameter. In this paper, we present a parametric polynomial-time algorithm for computing upper bounds of worst-case response times, that is based on an improved fptas (Fully Polynomial Time Approximation Scheme). Then, we show that our bound does not achieve constant error bound in comparison with the exact worst-case response time. However, using the resource augmentation technique, we obtain a performance guarantee that allows to define a compromise between our response-time bound and processor capacity requirements. The algorithm average behavior is then analyzed through numerical experimentations.     

多层服务器集群容量规划启发方法研究

本文研究了多层服务器集群系统的容量规划问题,提出以吞吐优化为目标的增量式服务器资源配置算法SHISA.该方法基于闭环排队网络模型求解系统的稳态性能指标,利用请求队列长度、资源利用率及有效响应时间等启发信息指导服务器的增量配置过程.对不同启发信息下算法的求解能力进行了敏感性分析.     

Fast symbolic computation of the worst-case delay in tandem networks and applications

Computing deterministic performance guarantees is a defining issue for systems with hard real-time constraints, like reactive embedded systems. In this paper, we use burst-rate constrained arrivals and rate-latency servers to deduce tight worst-case delay bounds in tandem networks under arbitrary multiplexing. We present a constructive method for computing the exact worst-case delay, which we prove to be a linear function of the burstiness and latencies; our bounds are hence symbolic in these parameters. Our algorithm runs in quadratic time in the number of servers. We also present an application of our algorithm to the case of stochastic arrivals and server capacities. For a generalization of the exponentially bounded burstiness (EBB) model, we deduce a polynomial-time algorithm for stochastic delay bounds that strictly improve the state-of-the-art separated flow analysis (SFA) type bounds.     

An Energy Efficient Clustering Scheme for Data Aggregation in Wireless Sensor Networks

In wireless sensor networks, a clustering scheme is helpful in reducing the energy consumption by aggregating data at intermediate sensors. This paper discusses the important issue of energy optimization in hierarchically-clustered wireless sensor networks to minimize the total energy consumption required to collect data. We propose a comprehensive energy consumption model for multi-tier clustered sensor networks, in which all the energy consumptions not only in the phase of data transmissions but also in the phase of cluster head rotations are taken into account. By using this new model, we are able to obtain the solutions of optimal tier number and the resulted optimal clustering scheme on how to group all the sensors into tiers by the suggested numerical method. This then enables us to propose an energy-efficiency optimized distributed multi-tier clustering algorithm for wireless sensor networks. This algorithm is theoretically analyzed in terms of time complexity. Simulation results are provided to show that, the theoretically calculated energy consumption by the new model matches very well with the simulation results, and the energy consumption is indeed minimized at the optimal number of tiers in the multi-tier clustered wireless sensor networks.     

Performance evaluation of an efficient multiple copy updatealgorithm

A well-known algorithm for updating multiple copies is the Thomas majority consensus algorithm. This algorithm, before performing an update, needs to obtain permission from a majority of the nodes in the system. We study the response-time behavior of a symmetric (each node seeks permission from the same number of other nodes and each node receives requests for update permission from the same number of other nodes) distributed update-synchronization algorithm where nodes need to obtain permission from only O(√N) (N being the number of database copies) other nodes before performing an update. The algorithm we use is an adaptation of Maekawa's O(√N) distributed mutual exclusion algorithm to multiple-copy update-synchronization. This increase in the efficiency of the update-synchronization algorithm enhances performance in two ways. First, the reduction in transaction service time reduces the response time. Second, for a given arrival rate of transactions, the decrease in response time reduces the number of waiting transactions in the system. This reduces the probability of conflict between transactions. To capture the interaction between the probability of conflict and the transaction response time, we define a new measure called the conflict response-time product. Based on the solution of a queueing model we show that optimizing this measure yields a different and more appropriate choice of system parameters than simply minimizing the mean transaction response time     

PLEIADES: An Internet‐based parallel/distributed system

The use of LAN‐based clusters of computers for computational purposes has been in use for several years with significant success and acceptability. The introduction of the Internet infrastructure as the interconnection medium of the cluster allows for additional flexibility and transparency of such systems. PLEIADES is an Internet‐based parallel/distributed system whose purpose is to allow users to use distant computational resources in order to form virtual clusters. In addition, PLEIADES can be used as a computational infrastructure service provider for applications in need of computational resources. PLEIADES uses a tiered architecture with particular emphasis on the existence of a middle tier, whose task is to assist in the communication between the interface and the resource management tiers. The existence of the middle tier allows for the creation of an open system that is able to easily integrate with new resource management platforms and tools. Since the use of a mature resource management system for parallel/distributed computing was a prerequisite of the PLEIADES architecture, the Condor resource management environment was used. The design and implementation characteristics of PLEIADES together with some experimental uses of the system are also presented. Copyright © 2002 John Wiley & Sons, Ltd.     

A Truthful Mechanism for Value-Based Scheduling in Cloud Computing

We introduce a novel pricing and resource allocation approach for batch jobs on cloud systems. In our economic model, users submit jobs with a value function that specifies willingness to pay as a function of job due dates. The cloud provider in response allocates a subset of these jobs, taking into advantage the flexibility of allocating resources to jobs in the cloud environment. Focusing on social-welfare as the system objective (especially relevant for private or in-house clouds), we construct a resource allocation algorithm which provides a small approximation factor that approaches 2 as the number of servers increases. An appealing property of our scheme is that jobs are allocated non-preemptively, i.e., jobs run in one shot without interruption. This property has practical significance, as it avoids significant network and storage resources for checkpointing. Based on this algorithm, we then design an efficient truthful-in-expectation mechanism, which significantly improves the running complexity of black-box reduction mechanisms that can be applied to the problem, thereby facilitating its implementation in real systems.     

应用服务器的安全性研究

良好的软件部署大多采用N层体系结构，将软件逻辑分成多个层面。应用服务器为商务逻辑层组件提供了运行的容器环境和数据库访问的底层环境，并提供了核心的中间件服务和基础架构，同时要求提供足够的安全性服务。结合分析比较了现有主流应用服务器平台，探讨了实施应用服务器安全性的方案。     

Secure Overlay Network Design

Due to the increasing security threats on the Internet, new overlay network architectures have been proposed to secure privileged services. In these architectures, the application servers are protected by a defense perimeter where only traffic from entities called servlets are allowed to pass. End users must be authorized and can only communicate with entities called access points (APs). APs relay authorized users’ requests to servlets, which in turn pass them to the servers. The identity of APs are publicly known while the servlets are typically secret. All communications are done through the public Internet. Thus all the entities involved form an overlay network. The main component of this distributed system consists of n APs and m servlets. A design for a network is a bipartite graph with APs on one side, and the servlets on the other side. If an AP is compromised by an attacker (or fails), all the servlets that are connected to it are subject to attack. An AP is blocked, if all servlets connected to it are subject to attack. We consider two models for the failures: In the stochastic model, we assume that each AP i fails with a given probability p _i . In the adversarial model, we assume that there is an adversary that knows the topology of the network and chooses at most k APs to compromise. In both models, our objective is to design the connections between APs and servlets to minimize the (expected/worst-case) number of blocked APs. In this paper, we give a polynomial-time algorithm for this problem in the stochastic model when the number of servlets is a constant. We also show that if the probability of failure of each AP is at least 1/2, then in the optimal design each AP is connected to only one servlet (we call such designs star-shaped), and give a polynomial-time algorithm to find the best star-shaped design. We observe that this statement is not true if the failure probabilities are small. In the adversarial model, we show that the problem is related to a problem in combinatorial set theory, and use this connection to give bounds on the maximum number of APs that a perfectly failure-resistant design with a given number of servlets can support. Our results provide the first rigorous theoretical foundation for practical secure overlay network design.     

M-GRASP: A GRASP With Memory for Latency-Aware Partitioning Methods in DVE Systems

A necessary condition for providing quality of service to distributed virtual environments (DVEs) is to provide a system response below a maximum threshold to the client computers. In this sense, latency-aware partitioning methods try to provide response times below the threshold to the maximum number of client computers as possible. These partitioning methods should find an assignment of clients to servers that optimizes system throughput, system latency, and partitioning efficiency. In this paper, we present a new algorithm based on greedy randomized adaptive search procedure with memory for finding the best solutions as possible to this problem. We take into account several different alternatives in order to design both the constructive phase and the local search phase of this multistart metaheuristic for combinatorial problems. Additionally, we enhance this basic approach with some intensification strategies that improve the efficiency of the basic search method. Performance evaluation results show that the new algorithm increases the performance provided by other metaheuristics when applied to solve the latency-aware partitioning problem in DVE systems.     

Optimal Load Distribution for Multiple Heterogeneous Blade Servers in a Cloud Computing Environment

Given a group of heterogeneous blade servers in a cloud computing environment or a data center of a cloud computing provider, each having its own size and speed and its own amount of preloaded special tasks, we are facing the problem of optimal distribution of generic tasks over these blade servers, such that the average response time of generic tasks is minimized. Such performance optimization is important for a cloud computing provider to efficiently utilize all the available resources and to deliver the highest quality of service. We develop a queueing model for a group of heterogeneous blade servers, and formulate and solve the optimal load distribution problem of generic tasks for multiple heterogeneous blade servers in a cloud computing environment in two different situations, namely, special tasks with and without higher priority. Extensive numerical examples and data are demonstrated and some important observations are made. It is found that server sizes, server speeds, task execution requirement, and the arrival rates of special tasks all have significant impact on the average response time of generic tasks, especially when the total arrival rate of generic tasks is large. It is also found that the server size heterogeneity and the server speed heterogeneity do not have much impact on the average response time of generic tasks. Furthermore, larger (smaller, respectively) heterogeneity results in shorter (longer, respectively) average response time of generic tasks.     

On Taylor series expansions for waiting times in tandem queues: an algorithm for calculating the coefficients and an investigation of the approximation error

Recently, a Taylor series expansion was developed for expected stationary waiting times in open (max,+)-linear stochastic systems with Poisson input process; these systems cover various instances of queueing networks.As an application, we present an algorithm for calculating the coefficients for infinite capacity tandem queueing networks with discrete service-time distributions. The algorithm works quite efficiently if the random vector of the service times of all servers is concentrated at a small number of atoms. We investigate the relative error of the Taylor approximation by simulation; in many cases, it follows very well a simple expression which holds exactly for independent, exponentially distributed servers.     

虚拟机资源分配的非合作博弈标价模型

基于非合作博弈理论,提出虚拟机资源分配的标价模型,该模型设计了各虚拟机的效益函数,同时利用该函数的最优反应函数,优化各博弈参与者对资源的标价。在效益函数零点无定义下,给出虚拟机标价最优解的唯一性和最优性证明。在满足服务质量条件下,利用优化后的标价按比例分配资源,使资源在各虚拟机之间公平分配,以提高虚拟资源利用率,保证用户的响应时间。仿真实验表明,提出的模型是有效合理的。     

A framework for robust active super tier systems

The scenario in which services are obtained by combining sub services is of a great importance. Reliability and fault tolerance are important concerns in the design of such distributed systems. This paper proposes a framework for designing robust client–server tier systems. First, we suggest implementing robust tier automata for each tier τ _i used by the processors that the tier contains. The robust tier automata are useful abstractions that allow distribution of the tier’s tasks (and its stubs) in a way that ensures availability, consistency, and recovery in the presence of faults. Then we suggest an active tier framework in which the computation of a user request progresses on several paths in the tier system; those paths may intersect, leaving footprints for each other. And last, we propose the super tier architecture, which correlates equivalent tiers in order to gain more robustness and load balancing. We present and analyze optimistic, pessimistic, and semi-optimistic approaches for computing over the active tier system with super tiers.     

P2P模式在电子商务资源管理中的应用

对电子商务系统与网格技术进行了分析,提出了一种基于P2P的B2B电子商务资源管理方案。采用应用层、服务层和资源层三个不同的层次进行电子商务资源管理。基于网格技术OGSA架构,实现了cnXML电子商务中用户注册、信息发布与查询过程。     

ITRA: Inter-Tier Relationship Architecture for End-to-end QoS

The importance of guaranteed end-to-end quality of service (QoS) increases as business-to-business (B2B) interactions become increasingly sophisticated, lengthy, and involve more sites. The collaboration between tiers to supply functionality can be extended to provide QoS. In this paper, we focus on end-to-end availability. In multi-tier computation, support for transparent failovers is often required, even if failures occur in more than one tier at the same time. One of the obstacles in achieving a transparent failover is determining the status of outstanding operations, some of which span several tiers. Such determination of outstanding operations status upon failure requires collaboration of neighboring tiers. In this paper, we present inter-tier relationship architecture (ITRA). ITRA describes mechanisms, the role of each tier with respect to its predecessor and successor tiers, programming model and inter-tier relationship protocol. eServices following the ITRA architecture can collaborate to transparently recover from failures in multiple tiers, as well as better exploit mutual resources to provide the required availability and failover transparency aspects of an end-to-end QoS. We have exercised the architecture by mapping it to enterprise java beans (EJB) and implemented a prototype.     

石化企业MES数据集成平台的设计与实现

论文结合石化企业的数据组织现状和应用需求,提出了由数据转换层、数据集成层和数据接口层组成的石化企业数据集成平台的三层体系结构,三层体系结构的划分使得数据集成平台具有良好的开放性和可扩展性。设计了基于消息中间件、XML技术和适配器技术的数据集成平台的技术架构。论文提供了一个石化企业数据集成平台的整体解决方案,它对企业数据集成平台的建立具有很大的指导意义。     

Call Control in Rings

The call control problem is an important optimization problem encountered in the design and operation of communication networks. The goal of the call control problem in rings is to compute, for a given ring network with edge capacities and a set of paths in the ring, a maximum cardinality subset of the paths such that no edge capacity is violated. We give a polynomial-time algorithm to solve the problem optimally. The algorithm is based on a decision procedure that checks whether a solution with at least k paths exists, which is in turn implemented by an iterative greedy approach operating in rounds. We show that the algorithm can be implemented efficiently and, as a by-product, obtain a linear-time algorithm to solve the problem in chains optimally. For the weighted version of call control in rings, where each path is associated with a weight and the goal is to maximize the total weight of the paths in the solution, we present a simple 2-approximation algorithm and a polynomial-time approximation scheme. While the complexity of the weighted version remains open, we show that it is at least as hard as the bipartite exact matching problem, which has not been resolved to be in P or NP-hard. This latter result follows from recent work by Hochbaum and Levin.