Characterization And Control Of Network Traffic: From Hours To Nanoseconds

by Chiunlin Lim

Institution: Cornell University
Year: 2015
Keywords: Traffic engineering ; Optimization ; Network traffic
Record ID: 2062117
Full text PDF: http://hdl.handle.net/1813/39449


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…