  It is accepted wisdom that changes in the traffic matrix entail capacity
over-provisioning, but there is no simple measure of just how much
over-provisioning can buy. In this Thesis, we aim to provide the network
designer with a simple view of the network robustness to traffic matrix
changes. We first present the Traffic Load Distribution Plots, or T-Plots, a
class of plots illustrating the percentage of traffic matrices that can be
serviced as a function of the capacity over-provisioning. For instance, from a
simple look at their T- Plots, network designers can guarantee that their
network services all admissible traffic matrices, or 99% of permutation traffic
matrices, or all traffic matrices with ingress/egress load at most half the
maximum. We further show that, unfortunately, in the general case plotting
T-Plots is #P-Complete, i.e., that it is impossible to plot a T-plot in a
polynomial time by the noon tools. However, we show that T-Plots can sometimes
be closely modeled as Gaussian, thus only using two values (mean and variance)
to quantify the robustness of a capacity allocation to traffic matrix changes.
We further utilize these Gaussian T-Plots to provide a more robust capacity
allocation. Finally, we demonstrate the benefits of using T-Plots by showing
results of extensive Monte Carlo simulations in a real backbone network. This
Thesis was submitted in 2007. Since then, the results that appeared in it were
applied in various networking environments. In this newer version, we revisit
the results 13 years later and explain their relevance to state-of-the-art
problems in network design.
