Date of Award

2013

Document Type

Thesis

Degree Name

Master of Science (MS)

Department

Electrical Engineering

First Advisor

Bikdash, Marwan U.

Abstract

The main focus of this thesis is to understand how congestion that is due to link failure propagates to successive upstream links, and how well the network maintains system flow under abnormal conditions. Alleviating network failures depends on how congestion propagates through the network. In general, units of traffic can move from their origin to their destination quite rapidly, but the change in flow rates tends to propagate slowly. We develop novel capacity collapse propagation models that extends significantly the concept of cell-transmission used to partition links into sections. The sampling is done in such a way that density wave propagates through a section of the link in one time interval. A general framework to model interaction between merging and diverging flow patterns is developed. The models considered for the nodes take into consideration the different types of intersections that may exist in the network. The capacity collapse propagation models can better represent networks with substantial propagation delay. The speed of the capacity collapse waves will be shown to depend on the magnitude of the failure. We integrate our models within the multicommodity flow framework, in which each commodity (origin-destination pair) uses k 2N link-disjoint paths to satisfy flow-rate demands. The congestion in the links is used to update the prices of the links, thus affecting the cost of travelling. We solve several minimum-cost linear-programming problems to control path flow-rate routing decisions triggered by the changes in the cost coefficients. We conclude that proposed path flow-rate rerouting in response to the congestion in the links could contribute significantly to network survivability. Numerical simulations of the proposed models are used to illustrate the concepts.

Share

COinS