Performance modeling and optimization solutions for networking systems

Abstract

This thesis targets at modeling and resolving practical problems using mathematical tools in two representative networking systems nowadays, i.e., peer-to-peer (P2P) video streaming system and cloud computing system. In the first part, we study how to mitigate the following tussle between content service providers and ISPs in P2P video streaming systems: network-agnostic P2P protocol designs bring lots of inter-ISP traffic and increase traffic relay cost of ISPs; in turn, ISPs start to throttle P2P packets, which significantly deteriorates P2P streaming performance. First, we investigate the problem in a mesh-based P2P live streaming system. We use end-to-end streaming delays as performance, and quantify the amount of inter-ISP traffic with the number of copies of the live streams imported into each ISP. Considering multiple ISPs at different bandwidth levels, we model the generic relationship between the volume of inter-ISP traffic and streaming performance, which provides useful insights on the design of effective locality-aware peer selection protocols and server deployment strategies across multiple ISPs. Next, we study a similar problem in a hybrid P2P-cloud CDN system for VoD streaming. We characterize the relationship between the costly bandwidth consumption from the cloud CDN and the inter-ISP traffic. We apply a loss network model to derive the bandwidth consumption under any given chunk distribution pattern among peer caches and any streaming request dispatching strategy among ISPs, and derive the optimal peer caching and request dispatching strategies which minimize the bandwidth demand from the cloud CDN. Based on the fundamental insights from our analytical results, we design a locality-aware, hybrid P2P-cloud CDN streaming protocol. In the second part, we study the profit maximization and cost minimization problems in Infrastructure-as- a- Service (IaaS) cloud systems. The first problem is how a geo-distributed cloud system should price its datacenter resources at different locations, such that its overall profit is maximized over long-term operation. We design an efficient online algorithm for dynamic pricing of VM resources across datacenters, together with job scheduling and server provisioning in each datacenter, to maximize the cloud's profit over the long run. Theoretical analysis shows that our algorithm can schedule jobs within their respective deadlines, while achieving a time-averaged overall profit closely approaching the offline maximum, which is computed by assuming perfect information on future job arrivals is freely available. The second problem is how federated clouds should trade their computing resources among each other to reduce the cost, by exploiting diversities of different clouds' workloads and operational costs. We formulate a global cost minimization problem among multiple clouds under the cooperative scenario where each individual cloud's workload and cost information is publicly available. Taking into considerations jobs with disparate length, a non-preemptive approximation algorithm for leftover job migration and new job scheduling is designed. Given to the selfishness of individual clouds, we further design a randomized double auction mechanism to elicit clouds' truthful bidding for buying or selling virtual machines. The auction mechanism is proven to be truthful, and to guarantee the same approximation ratio to what the cooperative approximation algorithm achieves.