A Service Level Agreement Aware Online Algorithm for Virtual Machine Migration

The demand for cloud computing has increased manifold in the recent past.More specifically,on-demand computing has seen a rapid rise as organizations rely mostly on cloud service providers for their day-to-day computing needs.The cloud service provider fulfills different user requirements using virtualization-where a single physical machine can host multiple VirtualMachines.Each virtualmachine potentially represents a different user environment such as operating system,programming environment,and applications.However,these cloud services use a large amount of electrical energy and produce greenhouse gases.To reduce the electricity cost and greenhouse gases,energy efficient algorithms must be designed.One specific area where energy efficient algorithms are required is virtual machine consolidation.With virtualmachine consolidation,the objective is to utilize the minimumpossible number of hosts to accommodate the required virtual machines,keeping in mind the service level agreement requirements.This research work formulates the virtual machine migration as an online problem and develops optimal offline and online algorithms for the single host virtual machine migration problem under a service level agreement constraint for an over-utilized host.The online algorithm is analyzed using a competitive analysis approach.In addition,an experimental analysis of the proposed algorithm on real-world data is conducted to showcase the improved performance of the proposed algorithm against the benchmark algorithms.Our proposed online algorithm consumed 25%less energy and performed 43%fewer migrations than the benchmark algorithms.

Optimal online algorithms for scheduling on two identical machines under a grade of service

This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.

An efficient and impartial online algorithm for kidney assignment network

An online algorithm balancing the efficiency and equity principles is proposed for the kidney resource assignment when only the current patient and resource information is known to the assignment network. In the algorithm, the assignment is made according to the priority, which is calculated according to the efficiency principle and the equity principle. The efficiency principle is concerned with the post-transplantation immunity spending caused by the possible post-operation immunity rejection and patient’s mental depression due to the HLA mismatch. The equity principle is concerned with three other factors, namely the treatment spending incurred starting from the day of registering with the kidney assignment network, the post-operation immunity spending and the negative effects of waiting for kidney resources on the clinical efficiency. The competitive analysis conducted through computer simulation indicates that the efficiency competitive ratio is between 6.29 and 10.43 and the equity competitive ratio is between 1.31 and 5.21, demonstrating that the online algorithm is of great significance in application.

Online algorithms for scheduling with machine activation cost on two uniform machines

In this paper we investigate a variant of the scheduling problem on two uniform machines with speeds 1 and s. For this problem, we are given two potential uniform machines to process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed, the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and the machine activation cost. We design optimal online algorithms with competitive ratio of (2s+1)/(s+1) for every s≥1.

An Online Algorithm Based on Replication for Using Spot Instances in IaaS Clouds

Infrastructure-as-a-Service(IaaS)cloud platforms offer resources with diverse buying options.Users can run an instance on the on-demand market which is stable but expensive or on the spot market with a significant discount.However,users have to carefully weigh the low cost of spot instances against their poor availability.Spot instances will be revoked when the revocation event occurs.Thus,an important problem that an IaaS user faces now is how to use spot in-stances in a cost-effective and low-risk way.Based on the replication-based fault tolerance mechanism,we propose an on-line termination algorithm that optimizes the cost of using spot instances while ensuring operational stability.We prove that in most cases,the cost of our proposed online algorithm will not exceed twice the minimum cost of the optimal of-fline algorithm that knows the exact future a priori.Through a large number of experiments,we verify that our algorithm in most cases has a competitive ratio of no more than 2,and in other cases it can also reach the guaranteed competitive ratio.

An Optimal Online Algorithm for Fractional Scheduling on Uniform Machines with Three Hierarchies

This paper is concerned with the fractional version of online hierarchical scheduling problem on uniform machines.In the problem,the jobs and machines have several different hierarchies and each job can be arbitrarily split between the machines with hierarchies not above the hierarchy of the job.The objective is to minimize the makespan.The authors present an optimal algorithm for the problem with three hierarchies.

An Optimal Online Algorithm for Scheduling on Two Parallel Machines with GoS Eligibility Constraints

We consider the online scheduling problem on two parallel machines with the Grade of Service(GoS)eligibility constraints.The jobs arrive over time,and the objective is to minimize the makespan.We develop a(1+α)-competitive optimal algorithm,whereα≈0.555 is a solution ofα^(3)−2α^(2)−α+1=0.

An Optimal Online Algorithm for Halfplane Intersection

The intersection of N half Planes is a basic problem in computational geometry and computer graphics. The optimal offiine algorithm for this problem runs in time O(N log N). ln this paper, an optimal online algorithm which runs also in time O(N log N) for this problem is presented. The main idea of the algorithm is to give a new definition for the left side of a given line, to assign the order for the points of a convex polygon, and then to use binary search method in an ordered vertex set.The data structure used in the algorithm is no more complex than array.

Two Online Algorithms for the Ambulance Systems

An ambulance system consists of a collection S = {s1,...,sm ) sm} of emergency centers in a metric space M. Each emergency center si has a positive integral capacity ci to denote, for example, the number of ambulances at the center. There are n = =1, ci patients requiring ambulances at different times tj and every patient is associated with a number bj, the longest time during which the patient can wait for ambulance. An online algorithm A will decide which emergency center sends an ambulance to serve a request for ambulance from a patient at some time. If algorithm A sends an ambulance in si to serve a patient rj, then it must be observed that di,j/v < bj, where di,j is the distance between emergency center si and patient rj, and v is the velocity of ambulance. A fault of algorithm A is such that to a request for ambulance at some time tj with j ≤n, for every i with di,j/v < bj, there is no ambulance available in si. The cost of an algorithm A is the number of faults A makes. This paper gives two algorithms B and C, where B is the local greedy algorithm and C is a variant of balancing costs, and proves that both B and C have no bounded competitive ratios. Moreover, given any sequence a of requests for ambulances without optimal faults, the cost of C on σis less than or equal to [n/3] and that of B is less than or equal to [n/2].

ONLINE REGULARIZED GENERALIZED GRADIENT CLASSIFICATION ALGORITHMS

This paper considers online classification learning algorithms for regularized classification schemes with generalized gradient. A novel capacity independent approach is presented. It verifies the strong convergence of sizes and yields satisfactory convergence rates for polynomially decaying step sizes. Compared with the gradient schemes, this al- gorithm needs only less additional assumptions on the loss function and derives a stronger result with respect to the choice of step sizes and the regularization parameters.

Online scheduling of two type parallel jobs on identical machines

In this paper we consider an online scheduling of parallel jobs with preemption on identical machines, where jobs arrive over time. The objective is to minimize the makespan. For the problem that jobs have only two possible widths mj = 1 or m, we present an optimal online algorithm by using ＂temporary schedule＂.

Online Parallel-Batch Machines Scheduling with a Single Server

We consider parallel-batch machines scheduling problem with a single server to minimize the maximum completion time.Jobs arrive over time.Every batch has to be loaded by the sever before being processed on machines.The loading(setup)operation of a batch occurs only when some machine is idle,and the server can perform only one setup operation every time.For some special case,we provide a best possible online algorithm with competitive ratio■.For general case,we give another online algorithm with competitive ratio 3.

Adaptive Control of Discrete-time Nonlinear Systems Using ITF-ORVFL

Random vector functional ink(RVFL)networks belong to a class of single hidden layer neural networks in which some parameters are randomly selected.Their network structure in which contains the direct links between inputs and outputs is unique,and stability analysis and real-time performance are two difficulties of the control systems based on neural networks.In this paper,combining the advantages of RVFL and the ideas of online sequential extreme learning machine(OS-ELM)and initial-training-free online extreme learning machine(ITFOELM),a novel online learning algorithm which is named as initial-training-free online random vector functional link algo rithm(ITF-ORVFL)is investigated for training RVFL.The link vector of RVFL network can be analytically determined based on sequentially arriving data by ITF-ORVFL with a high learning speed,and the stability for nonlinear systems based on this learning algorithm is analyzed.The experiment results indicate that the proposed ITF-ORVFL is effective in coping with nonparametric uncertainty.

Nearly optimal stochastic approximation for online principal subspace estimation

Principal component analysis(PCA) has been widely used in analyzing high-dimensional data. It converts a set of observed data points of possibly correlated variables into a set of linearly uncorrelated variables via an orthogonal transformation. To handle streaming data and reduce the complexities of PCA,(subspace)online PCA iterations were proposed to iteratively update the orthogonal transformation by taking one observed data point at a time. Existing works on the convergence of(subspace) online PCA iterations mostly focus on the case where the samples are almost surely uniformly bounded. In this paper, we analyze the convergence of a subspace online PCA iteration under more practical assumptions and obtain a nearly optimal finite-sample error bound. Our convergence rate almost matches the minimax information lower bound. We prove that the convergence is nearly global in the sense that the subspace online PCA iteration is convergent with high probability for random initial guesses. This work also leads to a simpler proof of the recent work on analyzing online PCA for the first principal component only.

Competitive Analysis of Two Special Online Device Replacement Problems

When a new investment opportunity of purchasing a new device occurs, the investors must decide whether or not and when to buy this device in an online fashion. That is, the online player must make an investment decision while neither future demand for orders nor future investment opportunities are known. This problem which generalizes the basic leasing problem has been introduced by Azar et al., and then two special cases have been studied by Damaschke. In the so-called equal prices model a 2-competitive algorithm is devised and a 1.618 lower bound is given. Here we make use of an averaging technique and obtain a better tight lower bound of 2, in other words, this lower bound cannot be improved. Furthermore, another special case which only considers two-stage device replacement is studied in this paper. Accounting for the interest rate is an essential feature of any reasonable financial model. Therefore, we explore the two-stage model with and without the interest rate respectively. In addition, we introduce the risk-reward model to analyze this problem and improve the competitive ratio performance.

Online Scheduling on Bounded Batch Machines to Minimize the Maximum Weighted Completion Time

We investigate the online scheduling problem on identical parallel-batch machines to minimize the maximum weighted completion time.In this problem,jobs arrive over time and the processing times(of the jobs)are identical,and the batch capacity is bounded.For this problem,we provide a best possible online algorithm with a competitive ratio of(√5+1)/2.Moreover,when restricted to dense-algorithms,we present a best possible dense-algorithm with a competitive ratio of 2.

Digital twin modeling method for lithium-ion batteries based on data-mechanism fusion driving

Lithium-ion batteries have been rapidly developed as clean energy sources in many industrial fields,such as new energy vehicles and energy storage.The core issues hindering their further promotion and application are reliability and safety.A digital twin model that maps onto the physical entity of the battery with high simulation accuracy helps to monitor internal states and improve battery safety.This work focuses on developing a digital twin model via a mechanism-data-driven parameter updating algorithm to increase the simulation accuracy of the internal and external characteristics of the full-time domain battery under complex working conditions.An electrochemical model is first developed with the consideration of how electrode particle size impacts battery characteristics.By adding the descriptions of temperature distribution and particle-level stress,a multi-particle size electrochemical-thermal-mechanical coupling model is established.Then,considering the different electrical and thermal effect among individual cells,a model for the battery pack is constructed.A digital twin model construction method is finally developed and verified with battery operating data.

2-Space Bounded Online Cube and Hypercube Packing

We consider the problem of packing d-dimensional cubes into the minimum number of 2-space bounded unit cubes. Given a sequence of items, each of which is a d-dimensional （d ≥ 3） hypercube with side length not greater than 1 and an infinite number of d-dimensional （d ≥ 3） hypercube bins with unit length on each side, we want to pack all of the items in the sequence into the minimum number of bins. The constraint is that only two bins are active at anytime during the packing process. Each item should be orthogonally packed without overlapping other items. Items are given in an online manner without the knowledge of or information about the subsequent items. We extend the technique of brick partitioning for square packing and obtain two results： a three-dimensional box and d-dimensional hyperbox partitioning schemes for cube and hypercube packing, respectively. We design 32 5.43-competitive and 32/21·2d-competitive algorithms for cube and hypercube packing, respectively. To the best of our knowledge these are the first known results on 2-space bounded cube and hypercube packing.

Online Learning Approaches in Maximizing Weighted Throughput in an Unreliable Channel

We design online algorithms to schedule unit-length packets with values and deadlines through an unreliable communication channel. In this model, time is discrete. Packets arrive over time; each packet has a non-negative value and an integer deadline. In each time step, at most one packet can be sent. The ratio of successfully delivering a packet depends on the channel＇s quality of reliability. The objective is to maximize the total value gained by delivering packets no later than their respective deadlines. In this paper, we conduct theoretical and empirical studies of online learning approaches for this model and a few of its variants. These online learning algorithms are analyzed in terms of external regret. We conclude that no online learning algorithms have constant regrets. Our online learning algorithms outperform online competitive algorithms in terms of algorithmic simplicity and running complexity. In general, these online learning algorithms work no worse than the best known competitive online algorithm for maximizing weighted throughput in practice.

Max-margin based Bayesian classifier

There is a tradeoff between generalization capability and computational overhead in multi-class learning. We propose a generative probabilistic multi-class classifier, considering both the generalization capability and the learning/prediction rate. We show that the classifier has a max-margin property. Thus, prediction on future unseen data can nearly achieve the same performance as in the training stage. In addition, local variables are eliminated, which greatly simplifies the optimization problem. By convex and probabilistic analysis, an efficient online learning algorithm is developed. The algorithm aggregates rather than averages dualities, which is different from the classical situations. Empirical results indicate that our method has a good generalization capability and coverage rate.