Cloud service providers (CSPs) need effective ways to distribute content across wide area networks. Providing large-scale, geographically-replicated online services presents new opportunities for coordination between server selection (to match subscribers with servers), traffic engineering (to select efficient paths for the traffic), and content placement (to store content on specific servers). Traditional designs isolate these problems, which degrades performance, scalability, reliability and responsiveness. We leverage the theory of distributed optimization, cooperative game theory and approximation algorithms to provide solutions that jointly optimize these design decisions that are usually controlled by different institutions of a CSP.

This dissertation proposes a set of wide-area traffic management solutions, which consists of the following three thrusts:

(i) Sharing information: We develop three cooperation models with an increasing amount of information exchange between the ISP's (Internet Service Provider) traffic engineering and the CDN's (Content Distribution Network) server selection. We show that straightforward ways of sharing information can be quite sub-optimal, and propose a Nash bargaining solution to reduce the efficiency loss. This work sheds light on ways that different groups of a CSP can communicate to improve their performance.

(ii) Joint control: We propose a content distribution architecture by federating geographically or administratively separate groups of “last-mile” CDN servers (e.g., nano data centers) located near end users. We design a set of mechanisms to solve a joint content placement and request routing problem under this architecture, achieving both scalability and cost optimality. This work demonstrates how to jointly control multiple traffic management decisions that may have different resolutions (e.g., inter vs. intra ISP), and may happen at different timescales (e.g., minutes vs. several times a day).

(iii) Distributed implementation: Today's cloud services are offered to a large number of geographically distributed clients, leading to the need for a decentralized traffic control. We present DONAR, a distributed mapping service that outsources replica selection, while providing a sufficiently expressive service interface for specifying mapping policies based on performance, load, and cost. Our solution runs on a set of distributed mapping nodes for directing local client requests, which only requires a lightweight exchange of summary statistics for coordination between mapping nodes. This work exemplifies a decentralized design that is simultaneously scalable, reliable, and accurate.

Collectively, these solutions are combined to provide a synergistic traffic management system for CSPs who wish to offer better performance to their clients at a lower cost. The main contribution of this dissertation is to develop new design techniques to make this process more systematic, automated and effective.