We consider the auto-scaling problem for application hosting in a cloud, where applications are elastic and the number of requests changes over time. The application requests are serviced by Virtual Machines (VMs), which reside on Physical Machines (PMs) in a cloud. We aim to minimize the number of hosting PMs by intelligently packing VMs into PMs, while the VMs are auto-scaled, i.e., dynamically acquired and released, to accommodate varying application needs. We consider a shadow routing based approach for this problem. The proposed shadow algorithm employs a specially constructed virtual queueing system to dynamically produce an optimal solution that guides the VM auto-scaling and the VM-to-PM packing. The proposed algorithm runs continuously without the need to re-solve the underlying optimization problem “from scratch”, and adapts automatically to the changes in the application demands. We prove the asymptotic optimality of the shadow algorithm. The simulation experiments further demonstrate the algorithm's good performance and high adaptivity.

We consider a shadow routing based approach to the problem of real-time adaptive placement of virtual machines (VM) in large data centers (DC) within a network cloud. Such placement in particular has to respect vector packing constraints on the allocation of VMs to host physical machines (PM) within a DC, because each PM can potentially serve multiple VMs simultaneously. Shadow routing is attractive in that it allows a large variety of system objectives and/or constraints to be treated within a common framework (as long as the underlying optimization problem is convex). Perhaps even more attractive feature is that the corresponding algorithm is very simple to implement, it runs continuously, and adapts automatically to changes in the VM demand rates, changes in system parameters, etc., without the need to re-solve the underlying optimization problem “from scratch”. In this paper we focus on the min-max-DC-load problem. Namely, we propose a combined VM-to-DC routing and VM-to-PM assignment algorithm, referred to as Shadow scheme, which minimizes the maximum of appropriately defined DC utilizations. We prove that the Shadow scheme is asymptotically optimal (as one of its parameters goes to 0). Simulation confirms good performance and high adaptivity of the algorithm. Favorable performance is also demonstrated in comparison with a baseline algorithm based on VMware implementation [7], [8]. We also propose a simplified - “more distributed” - version of the Shadow scheme, which performs almost as well in simulations.

The model is a “generalized switch”, serving multiple traffic flows in discrete time. The switch uses MaxWeight algorithm to make a service decision (scheduling choice) at each time step, depending on the current queue lengths. In some applications, it is not important to keep the queue lengths/delays small (e.g., when queues are virtual, rather than physical), but is important that the service processes provided to each flow remains “smooth” (i.e., without large gaps in service) even when the switch is heavily loaded. Addressing this question reduces to the analysis of the asymptotic behavior of the unscaled queue-differential process in heavy traffic. We prove that the stationary regime of this process converges to that of a positive recurrent Markov chain, whose structure we explicitly describe. This in turn implies “smoothness” of the service processes.

We consider a service system where agents (or, servers) are invited on-demand. Customers arrive as a Poisson process and join a customer queue. Customer service times are i.i.d. exponential. Agents' behavior is random in two respects. First, they can be invited into the system exogenously, and join the agent queue after a random time. Second, with some probability they rejoin the agent queue after a service completion, and otherwise leave the system. The objective is to design a real-time adaptive agent invitation scheme that keeps both customer and agent queues/waiting-times small. We study an adaptive scheme, which controls the number of pending agent invitations, based on queue-state feedback.

The model is a "generalized switch", serving multiple traffic flows in discrete time. The switch uses MaxWeight algorithm to make a service decision (scheduling choice) at each time step, which determines the probability distribution of the amount of service that will be provided. We are primarily motivated by the following question: in the heavy traffic regime, when the switch load approaches critical level, will the service processes provided to each flow remain "smooth" (i.e., without large gaps in service)? Addressing this question reduces to the analysis of the asymptotic behavior of the unscaled queue-differential process in heavy traffic. We prove that the stationary regime of this process converges to that of a positive recurrent Markov chain, whose structure we explicitly describe. This in turn implies asymptotic "smoothness" of the service processes.

We develop shadow routing based online algorithms for the joint problem of application-to-VM and VM-to-PM assignments in a cloud environment. The asymptotic optimality of the shadow algorithm is proved and the performance is evaluated by simulations.

We consider a shadow routing based approach to the problem of real-time adaptive placement of virtual machines (VM) in large data centers (DC) within a network cloud. Such placement in particular has to respect vector packing constraints on the allocation of VMs to host physical machines (PM) within a DC, because each PM can potentially serve multiple VMs simultaneously. Shadow routing is attractive in that it allows a large variety of system objectives and/or constraints to be treated within a common framework (as long as the underlying optimization problem is convex). Perhaps even more attractive feature is that the corresponding algorithm is very simple to implement, it runs continuously, and adapts automatically to changes in the VM demand rates, changes in system parameters, etc., without the need to re-solve the underlying optimization problem “from scratch”. In this paper we focus on the minmax-DC-load problem. Namely, we propose a combined VM-toDC routing and VM-to-PM assignment algorithm, referred to as Shadow scheme, which minimizes the maximum of appropriately defined DC utilizations. We prove that the Shadow scheme is asymptotically optimal (as one of its parameters goes to 0). Simulation confirms good performance and high adaptivity of the algorithm. Favorable performance is also demonstrated in comparison with a baseline algorithm based on VMware implementation [7], [8]. We also propose a simplified - “more distributed” - version of the Shadow scheme, which performs almost as well in simulations.

We consider a large-scale service system model proposed in [14], which is motivated by the problem of efficient placement of virtual machines to physical host machines in a network cloud, so that the total number of occupied hosts is minimized. Customers of different types arrive to a system with an infinite number of servers. A server packing configuration is the vector k = {ki}, where ki is the number of type-i customers that the server "contains". Packing constraints are described by a fixed finite set of allowed configurations. Upon arrival, each customer is placed into a server immediately, subject to the packing constraints; the server can be idle or already serving other customers. After service completion, each customer leaves its server and the system. It was shown in [14] that a simple real-time algorithm, called Greedy, is asymptotically optimal in the sense of minimizing ∑k Xk1+α in the stationary regime, as the customer arrival rates grow to infinity. (Here α > 0, and Xk denotes the number of servers with configuration k.) In particular, when parameter α is small, and in the asymptotic regime where customer arrival rates grow to infinity, Greedy solves a problem approximating one of minimizing ∑k Xk, the number of occupied hosts. In this paper we introduce the algorithm called Greedy with sublinear Safety Stocks (GSS), and show that it asymptotically solves the exact problem of minimizing ∑k Xk. An important feature of the algorithm is that sublinear safety stocks of Xk are created automatically - when and where necessary - without having to determine a priori where they are required. Moreover, we also provide a tight characterization of the rate of convergence to optimality under GSS. The GSS algorithm is as simple as Greedy, and uses no more system state information than Greedy does.

Back-pressure-based adaptive routing algorithms where each packet is routed along a possibly different path have been extensively studied in the literature. However, such algorithms typically result in poor delay performance and involve high implementation complexity. In this paper, we develop a new adaptive routing algorithm built upon the widely studied back-pressure algorithm. We decouple the routing and scheduling components of the algorithm by designing a probabilistic routing table that is used to route packets to per-destination queues. The scheduling decisions in the case of wireless networks are made using counters called shadow queues. The results are also extended to the case of networks that employ simple forms of network coding. In that case, our algorithm provides a low-complexity solution to optimally exploit the routing–coding tradeoff.

A random-access model is introduced and studied, which is a generalization of the classical slotted Aloha model. Unlike in the slotted Aloha, where two or more simultaneous transmissions on any subset of links collide and “erase” each other, a quite general interference structure is considered, where transmission on linkierases a simultaneous transmission on linkjwith some fixed probability φij. In particular, it is allowed that φij≠ φji, which captures possible asymmetric interference in real-most notably wireless-communication networks. Results characterizing the maximum achievable link throughput region and its Pareto boundary are derived. In some cases, the Pareto boundary characterization is almost as simple and explicit as that derived in prior work for the classical slotted Aloha system.

The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its implementation requires that each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. This fact may lead to a poor delay performance even when the traffic load is not close to network capacity. Also, since the number of commodities in the network is usually very large, the queueing data structure that has to be maintained at each node is respectively complex. In this paper, we present a solution to address both of these issues in the case of a fixed-routing network scenario where the route of each flow is chosen upon arrival. Our proposed architecture allows each node to maintain only per-neighbor queues and, moreover, improves the delay performance of the back-pressure algorithm.

The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its delay performance may be quite poor even when the traffic load is not close to network capacity due to the following two reasons. First, each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. Second, the backpressure routing algorithm may route some packets along very long routes. In this paper, we present solutions to address both of the above issues, and hence, improve the delay performance of the back-pressure algorithm. One of the suggested solutions also decreases the complexity of the queueing data structures to be maintained at each node.

Self-optimization of the network, for the purposes of improving overall capacity and/or cell edge data rates, is an important objective for next generation cellular systems. We propose algorithms that automatically create efficient, soft fractional frequency reuse (FFR) patterns for enhancing performance of orthogonal frequency division multiple access (OFDMA) based cellular systems for forward link best effort traffic. The Multi- sector Gradient (MGR) algorithm adjusts the transmit powers of the different sub-bands by systematically pursuing maximization of the overall network utility. We show that the maximization can be done by sectors operating in a semi-autonomous way, with only some gradient information exchanged periodically by neighboring sectors. The Sector Autonomous (SA) algorithm adjusts its transmit powers in each sub-band independently in each sector using a non-trivial heuristic to achieve out- of-cell interference mitigation. This algorithm is completely autonomous and requires no exchange of information between sectors. Through extensive simulations, we demonstrate that both algorithms provide substantial performance improvements. In particular, they can improve the cell edge data throughputs significantly, by up to 66% in some cases for the MGR, while maintaining the overall sector throughput at the same level as that achieved by the traditional approach. The simulations also show that both algorithms lead the system to "self-organize" into efficient, soft FFR patterns with no a priori frequency planning.

A model for wireless networks with slotted-Aloha-type random access and with multihop flow routes is considered. The goal is to devise distributed algorithms for utility-optimal end-to-end throughput allocation and queueing stability. A class of queue back-pressure random access algorithms (QBRAs), in which actual queue lengths of the flows in each node's close neighborhood are used to determine the nodes' channel access probabilities, is studied. This is in contrast to some previously proposed algorithms, which are based on deterministic optimization formulations and are oblivious to actual queues. QBRA is also substantially different from the well-studied ldquoMaxWeightrdquo type scheduling algorithms, even though both use the concept of back-pressure. For the model with infinite backlog at each flow source, it is shown that QBRA, combined with simple congestion control local to each source, leads to optimal end-to-end throughput allocation within the network saturation throughput region achievable by random access, without end-to-end message passing. This scheme is generalized to the case with minimum flow rate constraints. For the model with stochastic exogenous arrivals, it is shown that QBRA ensures stability of the queues as long as nominal loads of the nodes are within the saturation throughput region. Simulation comparison of QBRA and the queue oblivious random-access algorithms, shows that QBRA reduces end-to-end delays.

We study the problem of jointly performing scheduling and congestion control in mobile ad-hoc networks so that network queues remain bounded and the resulting flow rates satisfy an associated network utility maximization problem. In recent years a number of papers have presented theoretical solutions to this problem that are based on combining differential-backlog scheduling algorithms with utility-based congestion control. However, this work typically does not address a number of issues such as how signaling should be performed and how the new algorithms interact with other wireless protocols. In this paper we address such issues. In particular: ldr We define a specific network utility maximization problem that we believe is appropriate for mobile adhoc networks. ldr We describe a wireless greedy primal dual (wGPD) algorithm for combined congestion control and scheduling that aims to solve this problem. ldr We show how the wGPD algorithm and its associated signaling can be implemented in practice with minimal disruption to existing wireless protocols. ldr We show via OPNET simulation that wGPD significantly outperforms standard protocols such as 802.11 operating in conjunction with TCP. This work was supported by the DARPA CBMANET program.

We describe an algorithm for sub-carrier and power allocation that achieves out-of-cell interference avoidance through dynamic fractional frequency reuse (FFR) in downlink of cellular systems based on orthogonal frequency division multiple access (OFDMA). The focus in on the constant-bit-rate (CBR) traffic type flows (e.g., VoIP). Our approach is based on the continuous "selfish" optimization of resource allocation by each sector. No a priori frequency planning and/or inter-cell coordination is required. We show, both analytically (on a simple illustrative example) and by simulations (of a more realistic system), that the algorithm leads the system to "self-organize" into efficient frequency reuse patterns.

We study the stability of the max-weight protocol for combined routingand scheduling in communication networks. Previous work has shownthat this protocol is stable for adversarial multicommodity trafficin subcritically loaded static networks and for single-commoditytraffic in critically loaded dynamic networks. We show: The max-weight protocol is stable for adversarial multicommodity traffic in adversarial dynamic networks whenever the network is subcriticallyloaded. The max-weight protocol is stable for fixed multicommodity trafficin fixed networks even if the network is critically loaded.

We consider the problem of scheduling multiple users sharing a time-varying wireless channel. (As an example, this is a model of scheduling in 3G wireless technologies, such as CDMA2000 3G1xEV-DO downlink scheduling.) We introduce an algorithm which seeks to optimize a concave utility function /spl Sigma//sub i/H/sub i/(R/sub i/) of the user throughputs R/sub i/, subject to certain lower and upper throughput bounds: R/sub i//sup min//spl les/R/sub i//spl les/R/sub i//sup max/. The algorithm, which we call the gradient algorithm with minimum/maximum rate constraints (GMR) uses a token counter mechanism, which modifies an algorithm solving the corresponding unconstrained problem, to produce the algorithm solving the problem with throughput constraints. Two important special cases of the utility functions are /spl Sigma//sub i/log R/sub i/ and /spl Sigma//sub i/R/sub i/, corresponding to the common proportional fairness and throughput maximization objectives. We study the dynamics of user throughputs under GMR algorithm, and show that GMR is asymptotically optimal in the following sense. If, under an appropriate scaling, the throughput vector R(t) converges to a fixed vector R/sup +/ as time t/spl rarr//spl infin/ then R/sup +/ is an optimal solution to the optimization problem described above. We also present simulation results showing the algorithm performance.

Recent years have seen tremendous growth in the deployment of wireless local area networks (WLANs). An important design issue in such networks is that of distributed scheduling. The lack of centralized control leads to multiple users competing for channel access. This leads to significant throughput degradation. Existing approaches, such as the slotted Aloha protocol and IEEE 802.11 DCF, also fail to provide differentiated service to users. The upcoming IEEE 802.11e enhanced DCF incorporates additional mechanisms to provide support for service differentiation. However, the level of differentiation achieved with these mechanisms is difficult to quantify. In this paper, we propose a class of distributed scheduling algorithms, regulated contention medium access control (RCMAC), which provides dynamic prioritized access to users for service differentiation in a quantifiable manner. Furthermore, by regulating multi-user contention, RCMAC achieves higher throughput when traffic is bursty, as is typically the case. In addition to WLANs, the basic concepts of RCMAC have applications in ad hoc networks and emerging sensor networks.

We consider the problem of traffic anomaly detection in IP networks. Traffic anomalies typically arise when there is focused overload or when a network element fails and it is desired to infer these purely from the measured traffic. We derive new general formulae for the variance of the cumulative traffic over a fixed time interval and show how the derived analytical expression simplifies for the case of voice over IP traffic, the focus of this paper. To detect load anomalies, we show it is sufficient to consider cumulative traffic over relatively long intervals such as 5 min. We also propose simple anomaly detection tests including detection of over/underload. This approach substantially extends the current practice in IP network management where only the first-order statistics and fixed thresholds are used to identify abnormal behavior. We conclude with the application of the scheme to field data from an operational network.

A class of distributed scheduling algorithms, Regulated Contention Medium Access Control (RCMAC), which provides dynamic prioritized access to users for service differentiation, is considered in this paper. In addition to WLANs, the basic concepts of RCMAC have applications in multihop cellular and ad hoc networks and emerging sensor networks. Furthermore, by regulating multiuser contention, RCMAC achieves higher throughput when traffic is bursty. In this paper, differential function with two special cases like weight proportional and old base regulation is presented. Arrivals at each user are bursty, generated using standard two-state Markov model and the multiplicative increase/decrease rule are employed.

Cut-through switching has been used as a way to reduce network latency. In particular, with ATM, packets are broken up into fixed length cells, and each cell is forwarded without having to wait for the remaining cells of the packet. However, with the interest in VC-merging, packets from multiple virtual circuits are merged into a single virtual circuit on an output link. In this case, it is critical to retain the fundamental characteristic of ATM to not interleave cells of a packet with that of another. VC-merging arises often, as in the case of a multipoint-to-multipoint or multipoint-to-point connection. We examine the stability of policies for cut-through switching when VCs are merged. We consider a queueing model of a single VC merge point employing cut-through switching. We show that, if subunits of packets cannot be interleaved on the output link, a simple round-robin polling service discipline may make the merge point unstable. Instability means that the input queues have a tendency to build up infinitely even though the total input data rate is less than the output link capacity. We prove that the round-robin discipline is stable if the merge point is symmetric in that packet rates on all input VCs are equal (or at least "almost equal"). We also prove that two simple modifications of the round-robin discipline make the merge point always stable. Simulation results of one of the modifications show improved performance over "pure" cut-through and store-and-forward, at least in some cases.

Lubachevsky [5] introduced a new parallel simulation technique intended for systems with limited interactions between their many components or sites. Each site has a local simulation time, and the states of the sites are updated asynchronously. This asynchronous updating appears to allow the simulation to achieve a high degree of parallelism, with very low overhead in processor synchronization. The key issue for this asynchronous updating technique is: how fast do the local times make progress in the large system limit? We show that in a simple K-random interaction model the local times progress at a rate 1/(K + 1). More importantly, we find that the asymptotic distribution of local times is described by a traveling wave solution with exponentially decaying tails. In terms of the parallel simulation, though the interactions are local, a very high degree of global synchronization results, and this synchronization is succinctly described by the traveling wave solution. Moreover, we report on experiments that suggest that the traveling wave solution is universal; i.e., it holds in realistic scenarios (out of reach of our analysis) where interactions among sites are not random.