Dissertation Defense/Hongqiang Liu
Dissertation Title: Traffic Planning under Network Dynamics
Advisor: David Gelernter
Other committee members:
Bryan Ford
David Wolinsky
Ming Zhang (Microsoft Research)
Abstract: 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 severe congestion, which significantly undermines the performance of latency sensitive applications, such as search engines, online retails, online games, video conferences and so forth.
This dissertation demonstrates that smart traffic planning can prevent congestion and application performance degradation caused by network dynamics with low cost.
Specifically, we provide systematic understandings on two critical questions:
First, why should and how could network providers carefully spread traffic so that spare capacity in a network can be efficiently utilized to accommodate rerouted packets and traffic spikes under network dynamics? Second, why should and how could applications allocate traffic adaptively among multiple infrastructures to boost their robustness with uncertainties within individual infrastructures. Moreover, this dissertation designs, implements and evaluates practical algorithms and systems based on the preceding understandings to achieve smart traffic planning at different levels: intra-infrastructure (intra- and inter-datacenter) and inter-infrastructure.
Around the theme of smart traffic planning, this dissertation includes following three pieces of work:
First, to handle the network dynamics caused by faults, we propose and practically realize the concept – Forward Fault Correction (FFC) – which requires that a traffic engineering (TE) guarantees no congestion without re-configuring the network if only the number of faults is under k. 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 the 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 maintenance. For example, before rebooting a switch, an operator will drain the switch first. SDT provides a common functionality that is needed during diverse types of network maintenance. The key challenge to realize SDT is 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.
Finally, for content service applications, e.g. video on demand and live streaming, we present a framework – Content Multihoming Optimization (CMO) – which uses multiple infrastructures, like 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. We also show how we can use joint optimizations with both global and local views to minimize the cost for utilizing multiple infrastructures while still guaranteeing users’ QoE.
A complete draft can be read here.