We study a robust variant of the online bin packing problem that models reliable cloud resource allocation. In this problem, bins represent servers and items represent jobs of various workloads. Furthermore, to guarantee that the service of each item is available regardless of any η bins turn to be faulty, each item is replicated into η + 1 bins. In the case of bin failures, the faulty replica’s workload is distributed to other bins associated with the same item with ensuring the extra workloads do not cause an overflow in any bins. The key issue is to minimize the total number of activated bins under the demands and robustness constraints. OrthogonFit algorithm, which is proposed, solves this key issue by categorizing replicas into distinct classes based on workloads and packing identical replicas onto the same type of bins. It efficiently reuses those already-activated bins without the need of new ones. Theoretical analysis and simulation results demonstrate its superior performance over existing works.

In support of effectively discovering the market value of resources and dynamic resource provisioning, auction design has recently been studied in the cloud. However, there are limitations due to the inability to accept time-varying user demands or offline settings. These limitations create a large gap between the real needs of users and the services available from cloud providers. In addition, existing auction mechanisms do not consider service interruption due to server failures caused by software or hardware problems. To address the limitations of existing auction mechanisms and to avoid service interruption, this paper targets a more general scenario of online cloud resource auction design where: 1) users can request multiple types of time-varying resources; and 2) at least one server is available for each accepted bid even when one or more servers fail; and 3) profit is maximized over the system execution span. Specifically, we model the profit maximization problem using an Integral Linear Programming (ILP) optimization framework, which offers an elastic model for time-varying user demands. In addition, we design an online, truthful, and time efficient auction mechanism consisting of a price-based allocation strategy and a pricing function. The online allocation strategy allocates multiple types of resource to each user while satisfying the time-varying demands and ensuring at least one server is available for each user in each allocated time slot. Lastly, the efficacy of online auctions is validated through careful theoretical analysis and trace-driven simulation studies.

We study server consolidation problem in clouds under simultaneous failures of multiple servers, where consolidation means that cloud providers put tenants on shared servers to improve resource utilization and thus reduce operation and maintenance costs. With replicas of each tenant put on multiple servers, our objective is to minimize the total number of opened servers and ensure that a particular failure will not result in overload on any remaining server. In this paper, we propose Rotation algorithm. It packs comparable sizes replicas into the same type of servers and adopts a cyclic shift method to quickly reuse those already-opened servers without the need of new ones for new tenants. Through experimental evaluations, we show that the proposed algorithms can achieve a better performance than existing works and produce near-optimal replications allocation.

Distributed multi-controller deployment is a key issue in the innovative Software Defined Network (SDN) to scale network while improving performance and reliability. It is interesting to know how many controllers should be deployed and where to locate under a wide range of performance sensitive and completive constraints, including latency, fair load distribution as well as cost. We solve this problem by minimizing propagation latency and controller cost. The required number of controllers is determined based on requests and controller capacity. Due to the uneven distribution of network load, it is more likely to deploy controllers on nodes with high request density. A clustering algorithm NWDP (Node Weight Deployment Policy) is thus proposed based on node weight to choose location of multi-controller. To achieve effectively, autonomous and dynamic deployment in large-scale networks, we further propose a supervised graph convolution network model with fusion features(FF-GCN). The open network database Internet Topology Zoo is adopted to evaluate the effectiveness of our algorithms. Simulation results show that NWDP efficiently outperforms traditional algorithms in medium-sized topology, and the trained FF-GCN can figure out the deployment in a 702 nodes large-scale topology with an average prediction accuracy of 90%.

Task scheduling in cloud computing is an NP-complete problem. It concerns how to properly arrange task execution process using a set of necessary cloud resources. Existing works assume that tasks can be interrupted without any overhead, based on which task schedules can be optimized to achieve some objectives (e.g., maximize resource utilization). We observe that interrupting tasks, as well as subsequent task recovery process, will inevitably impose overheads in terms of consuming additional CPU time on corresponding physical machines. In addition, not all tasks can be interrupted. Those observations motivate us to consider a more general scenario where a job consists of both interruptible and non-interruptible tasks with specific deadline and resource requirements. Accordingly, we design algorithms to minimize task interruption overhead while ensuring task completion deadline. Specifically, we first formulate an Integer Linear Program (ILP) for offline optimization. A heuristic algorithm is then proposed for online task scheduling, and is compared with the optimal ILP solution. Numerical results confirm the correctness of our ILP and show the efficiency of the proposed heuristic.

Due to the reconfiguration overhead of optical fabrics, batch scheduling method is generally used to schedule an optical packet switch, with a necessary speedup inside the switch to ensure 100% throughput with a bounded packet delay. Existing algorithms take each traffic matrix as a batch, and adopt traffic matrix decomposition techniques to decompose it into the sum of a set of weighted permutation matrices (which are then used as switch configurations). Nevertheless, existing algorithms adopt an equal weight for all switch configurations, meaning that each configuration should be held for the same time duration to transmit packets. We observe that this rigid strategy may limit the flexibility of the scheduling and result in a large speedup requirement due to inefficient time slot utilization. Motivated by this observation, we propose a UWS (Unequal Weight Sequence) algorithm to decompose the traffic matrix. UWS uses a different weight for each switch configuration. It first takes an arithmetic progression as the starting weight sequence, and then adjusts the weights for configurations to ensure 100% throughput with a bounded packet delay (such that QoS can be guaranteed). We theoretically prove that the worst case speedup of UWS will never be larger than that of the best existing ADAPT algorithm. Simulation results indeed demonstrate a speedup improvement of around 15%.