Traffic Planning under Network Dynamics

Networks are constantly dynamic because of various types of faults (e.g. link failures) and maintenance ( e.g. device upgrades). Such network dynamics could result in severe congestion which significantly undermines the performance of latency sensitive applications, such as search engines, online retail, online games, live streaming and so forth.;This dissertation asks a fundamental question -- how does one efficiently protect latency sensitive applications against network dynamics? The solution it proposes, reasons out, and realizes is to plan traffic strategically in networks and applications..;Specifically, this dissertation provides systematic understandings on the motivations and methodologies of strategic traffic planning. First, for network providers, it shows why they should, and how they could, spread traffic over their networks tactically so that spare capacity in the networks can be efficiently utilized to accommodate rerouted packets and traffic spikes under network dynamics. Second, for application owners, it shows why they should, and how they could, allocate traffic loads among multiple infrastructures (e.g. clouds) adaptively to boost their robustness to uncertainties within individual infrastructures. Moreover, this dissertation designs, implements, and evaluates practical algorithms and systems based on the preceding understandings to achieve strategic traffic planning at different levels: intra-infrastructure (intra- and inter-datacenter) and inter-infrastructure.;Around the theme of strategic traffic planning, this dissertation makes the following three main contributions. First, to handle the network dynamics caused by faults, we propose and practically realize a concept -- Forward Fault Correction (FFC) -- which requires a traffic engineering (TE) that guarantees no congestion without reconfiguring the network as long as the number of faults is under k. The challenges to realize FFC lie in the overhead in network throughput and the computational complexity to prepare for a huge number of fault cases. We develop an efficient and uniform method to obtain a TE with FFC under diverse kinds of faults on both control- and data-plane.;Next, to make sure the network dynamics aroused by maintenance cause no harm, we introduce a concept -- Smooth traffic Distribution Transition (SDT) -- which means that a network is configured in a congestion-free way to achieve some traffic distribution that is needed by specific maintenance. For example, before rebooting a switch, an operator will drain the traffic on switch first. SDT provides a common functionality that is needed during various types of network maintenance. The key challenge to realize SDT stems from the inherent difficulty in synchronizing the changes to many devices, which may lead to unforeseen transient link load spikes or even congestion. We present one primitive, zUpdate, which performs SDT via a multi-step and progressive network re-configuration scheduling.;While FFC and SDT are designed for avoiding congestion on network links, congestion inside overloaded servers is also crucial especially for applications that are both traffic intensive and latency sensitive, e.g. live streaming and video on demand. Therefore, we finally present a framework -- Content Multihoming Optimization (CMO) -- which uses multiple infrastructures, e.g. clouds and/or content delivery networks (CDNs), and adaptive download scheduling among these infrastructures from client-side to protect users' quality of experience (QoE) against performance fluctuations in individual infrastructures. The key challenge to realize CMO resides in the expensive and complex usage prices of infrastructures and the overhead of establishing connections to multiple servers. We show how these applications can use joint optimizations and algorithms with both global and local views to minimize the cost for utilizing multiple infrastructures and reduce overhead.