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

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.