Flow-based dynamic routing in uncertain network environments

In this dissertation we study flow-based dynamic routing schemes. We propose routing schemes to achieve good network level performance such as flow blocking rate, and user level performance such as flow throughput. The design principle is to route a flow so that we can satisfy its Quality of Service (QoS) requirement, and minimize the negative impact of the routing on the performance of current and future flows of the network. To this end we identify a number of operating regimes in which user demands, network states, and routing decisions interact. We propose different routing mechanisms based on the unique properties of the operating regimes. For the networks operating in a regime in which link states are highly dynamic and traffic demands are bursty, we propose a dynamic multi-path routing scheme to disperse traffic between a source and a destination. We investigate the critical issue of how to select the set of least congested paths over which to disperse traffic, and examine the performance of this routing scheme in a mesh network. The performance of our dynamic multi-path routing scheme is quite robust with respect to various operating parameters and it offers consistent performance improvement over the baseline single path routing scheme. We then study dynamic routing schemes in the networks where network states evolve on a modest timescale which allows a user to predict its performance during its sojourn in the network. We model the link load dynamics and propose a routing scheme that jointly consider the current link load, the flow holding time, the average link load and mean reversion for the load dynamics. This routing scheme is beneficial for a range of applications where efficient fair-sharing of the excess network resources can improve network and user performance. We show our routing scheme, designed to improve users’ average performance during their sojourn in the network, indeed leads to an efficient fair use of network resources. We also investigate routing algorithms for providing failure protection. The objective is to efficiently provision network resources so that when certain failures occur we can re-route the affected traffic with minimal service disruption. We observe that while a protection path for a given failure is constrained since it has to select its detours around the failure, it can nonetheless share the protection resources with protection paths for other failures. We identify a routing metric which effectively captures the sharing potential in the network. This routing metric and the associated routing algorithms, are shown to provide failure protection with significantly reduced resource redundancy.