Designing a predictable backbone network using valiant load-balancing

The backbones form the core of the Internet and carry large volumes of data across long distances. Designing a backbone network with performance guarantees is important but difficult due to the uncertainty in the traffic matrix, the need to accommodate component failures, and the desire to avoid congestion. Backbone networks today are highly over-provisioned but cannot guarantee to support all traffic matrices. In this thesis we propose using Valiant Load-Balancing (VLB, named after L.G. Valiant) to design backbone networks that can support all traffic matrices efficiently, even under a number of failures. Chapter 2 shows that VLB is efficient for any network. A simple scheme, the Gravity Full Mesh, requires a total capacity no more than twice the theoretical lower bound, and another scheme, Minimum Network Fanout, requires a total capacity at most 20% more than the theoretical lower bound. The path diversity in VLB enables the network to tolerate failures efficiently. Chapter 3 shows that in order to tolerate k arbitrary failures, the fraction of extra capacity required is only approximately kN . In addition, VLB provides fast rerouting after failure. In Chapter 4 we first argue that most applications will not be affected by the extra propagation delay caused by VLB. Then we propose adaptive VLB, which adjusts the amount of load-balancing according to the traffic condition in order to minimize packet delay. In Chapter 5 we propose using VLB to route traffic between two networks. VLB can efficiently utilize the peering links so that there is no congestion unless the total peering traffic rate exceeds the total peering capacity. It can further ensure that peering packets receive the same quality of service as non-peering tragic. We derive the optimal load-balancing parameters for routing local traffic and peering traffic. We finally apply VLB to designing circuit-switched networks with performance guarantees. Current circuit-switched networks use heuristics to minimize average blocking probability. The heuristics require parameters that depend on the traffic metrics, are hard to analyze, and cannot give performance guarantees. Valiant Load-Balancing, on the other hand, can give theoretical bounds on blocking probabilities for all flows under worst case traffic.