Browsing by Author "Zhou, Ruiting"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Open Access Efficient Algorithms for Dynamic Cloud Resource Provisioning(2018-04-20) Zhou, Ruiting; Li, Zongpeng; Woelfel, Philipp; Krishnamurthy, Diwakar; Wu, Kui; Williamson, Carey L.Cloud computing has emerged as a new computing paradigm, with data centers proliferating in today’s Internet. Cloud service providers often adopt static resource provisioning to pack cloud resources to fixed types of virtual machines (VM), failing to address user demands efficiently and precisely. In this thesis, we focus on dynamic cloud resource provisioning, which provides realtime, on-demand access to cloud resources. We propose efficient algorithms to guide resource allocation and workload dispatching in cloud systems. We first study dynamic VM provisioning via an online auction algorithm. We generalize the existing literature by introducing computing jobs with completion deadlines. A cloud user bids for future cloud resources to execute its job. Each bid specifies (a) a resource profile of tailor-made VMs, (b) a utility, reflecting the amount that the user is willing to pay for executing its job, and (c) a soft deadline, specifying the preferred finish time of the job, as well as a penalty function that characterizes the cost of violating the deadline. We propose efficient cloud job auctions that execute in an online fashion, provide truthfulness guarantee, and achieve a good competitive ratio. We then discuss cloud container services, a more recent form of cloud resource provisioning. Compared to traditional VMs, cloud containers are more flexible and lightweight. We exploit this new algorithm design space, and study dynamic cloud container provisioning. We design efficient scheduling algorithms for complex computing jobs that are running on cloud containers. Our offline and online schedulers permit partial execution, allow a job to specify its job deadline, desired cloud containers, and inter-container dependence relations, and achieve near-optimal expected objective values. We further extend our study to cloud container clusters. Enterprise users often create clusters of inter-connected containers to provision complex services. Compared to traditional cloud services, key challenges in container cluster (CC) provisioning lie in the optimal placement of containers while considering inter-container traffic in a CC. The challenge further escalates when CCs are provisioned in an online fashion upon CC request arrivals. We investigate dynamic cloud CC provisioning, and propose an online algorithm to address the above challenges. Our online algorithm achieves computational and economical efficiencies.Item Open Access Two Applications of Physical Layer Network Coding in Multi-hop Wireless Networks(2012-09-06) Zhou, Ruiting; Li, Zongpeng; Williamson, CareyPhysical layer network coding (PNC) is a relatively new technique that can perform network coding at the physical layer to boost the capacity of wireless ad hoc networks. By viewing overlapping data transmissions as their linear combinations, PNC can potentially achieve large improvement in physical-layer throughput over traditional transmissions and digital network coding at the higher layers. While existing research on PNC usually focuses on simple network topologies (e.g, the two-way relay channel), it appears natural and promising to further explore the opportunities of applying PNC in a large, general, multi-hop wireless network. This thesis covers two endeavours along this direction. Firstly, we show how PNC can be combined with signal alignment (SA), another technique inspired from interference alignment (IA), for application in MIMO wireless networks. PNC coupled with SA (PNC-SA) has the potential of fully exploiting the precoding space at the senders, and can better utilize the spatial diversity of a MIMO network for higher transmission rates, outperforming existing techniques including MIMO or PNC alone, interference alignment (IA), and interference alignment and cancelation (IAC). We study the optimal precoding and power allocation problem of PNC-SA, for SNR maximization at the receiver. The mapping from SNR to BER is then analyzed, revealing that the throughput gain of PNC-SA does not come with a sacrifice in BER. Furthermore, the maximum throughput for the general N-user M-antenna uplink system is presented. We also demonstrate general applications of PNC-SA beyond a multi-user wireless uplink, and show via network level simulations that it can substantially increase the throughput of unicast and multicast sessions, by opening previously unexplored so- lution spaces in multi-hop MIMO routing. Secondly, we focus on routing algorithm design in NanoNets, which are networks of nanomachines at extremely small dimensions, on the order of nanometers or micrometers. Based on the salient features of a NanoNet, including low node cost and very low available power, we propose a new routing paradigm for unicast and multicast data transmission in NanoNets. Our design, termed Buddy Routing (BR), is enabled by PNC, and argues for pair-to-pair data forwarding in place of traditional point-to-point data forwarding. Through both analysis and simulations, we compare BR with point-to-point routing, in terms of raw throughput, error rate, energy efficiency, and protocol overhead, and show the advantages of BR in NanoNets.