Characterization and control of network traffic: From hours to nanoseconds.

摘要

This thesis covers the challenges faced by network operators and network users either individually or jointly on different timescales. In the first part of the thesis, we investigate the interaction between traffic engineering and TCP. In the network layer, a network operator directly controls the traffic via traffic engineering and indirectly influences the user offered traffic via feedback signals. In the transport layer, users send traffic into the network using the TCP protocol, which adjusts offered traffic according to the received feedback. We investigate how current traffic engineering practice interact with congestion control under the network utility maximization framework. We show that the current interaction is stable, increases network utility, but does not necessarily improve the traffic engineering objective. To jointly optimize the non-convex congestion control and multipath routing problem, we note the mismatch in incentive and take on a more holistic view using game theory. With change of variables, we obtain an equivalent convex optimization problem and with suitable modification of the feedback, we show that the interaction converges to the globally optimal solution of the equivalent convex problem for users running either primal or dual algorithms. We further show that the results hold even when traffic engineering is performed at any irregular intervals. More generally, we show via heterogeneous feedback the same optimality result for a mix of users running primal and dual algorithms.;In the second part of the thesis, we first lay down the framework of network traffic dynamics by specifying the governing equations for the time evolutions, dynamics and associated delays of the network elements. We next specialize the framework to study how a centrally controlled network could reconfigure its routing as quickly as possible while not incurring any congestion. As switches may update at different times and update to different traffic flows take different times to propagate through the network, transient congestion could occur when links contain a mix of traffic flows following old and new routing configurations. Using propagation delay information from the framework and incorporating timing uncertainty, we figure out which congestion scenario could occur and how long it would take any update to properly propagate through the network. We formulate a mixed-integer linear program to find fast congestion-free routing reconfiguration using timing information. We explore how we could fasten the update process as we do not have to wait for an update to fully propagate through the network. For heavily congested network, we show a fast update solution by trading off the minimal amount of traffic demand. Experiments on Mininet verify our approach and show that it outperforms prior method with no timing information.;In the final part, we investigate router's inherent variation on packet processing time and its effect on interpacket delay and packet clustering. We propose a simple pipeline model incorporating the inherent variation, and two metrics, one to measure packet clustering and one to quantify inherent variation. To isolate the effect of the inherent variation, we begin our analysis with no cross traffic and step through setups where the input streams have different data rate, packet size and go through different number of hops. We show that a homogeneous input stream with a sufficiently large interpacket gap will emerge at the router's output with interpacket delays that are negatively correlated with adjacent values and have symmetrical distributions. For an input with smaller interpacket gap, the change in packet clustering is smaller while for a more clustered input, the change is also smaller and could actually go negative. We generalize our results by adding cross traffic and show how the understanding gained could be applied to engineer traffic with minimal jitter. The model analysis is validated with experiments using SoNIC, a highly precise instrument providing real-time access to the physical layer.