Item Details

Distributed Routing in Networks With Time-Variant Edge Capacities: A Modified Multicommodity Flow Approach

Lafferty, Kelli
Format
Thesis/Dissertation; Online
Author
Lafferty, Kelli
Advisor
Cogill, Randy
Abstract
This research is focused on creating an efficient and effective network flow framework for applications in routing protocols for mobile, unicast communications networks with limited delay tolerance in urban canyons. Urban canyons are environments in which man-made objects interfere with the dependability of network reception. To account for fluctuations in reception, networks in this type of environment are modeled with time-variant edge capacities. To limit delays, algorithms implemented for these types of networks must be distributed. Specifically, we focus on modifying multicommodity flow problems to find routing protocols that can (1) effectively send flow through a network with time-varying edge capacities and (2) operate in a distributed setting. To achieve this, we developed candidate algorithms by both manipulating existing fully polynomial time approximation schemes for multicommodity flow for a time-varying setting and developing new algorithms that can produce a static, robust invariant allocation of flow. These candidate algorithms were initially evaluated through simulations in MATLAB. Then, promising algorithms were assessed through a theoretical analysis that validated performance and suitability observations made during the MATLAB simulations. Finally, a distributed implementation plan was developed.
Language
English
Date Received
20130803
Published
University of Virginia, Department of Systems Engineering, MS (Master of Science), 2013
Published Date
2013-07-23
Degree
MS (Master of Science)
Collection
Libra ETD Repository
Logo for In CopyrightIn Copyright

Availability

Read Online