eCommons

 

Characterization And Control Of Network Traffic: From Hours To Nanoseconds

Other Titles

Abstract

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.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

2015-01-26

Publisher

Keywords

Traffic engineering; Optimization; Network traffic

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Tang, Ao

Committee Co-Chair

Committee Member

Avestimehr, Amir Salman
Weatherspoon, Hakim

Degree Discipline

Electrical Engineering

Degree Name

Ph. D., Electrical Engineering

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record