Flow routing in computer networks
M. Schneider, Mohamed G. Gouda · 1997
Conventional connectionless datagram routing protocols such as OSPF and RIP utilize link-state and distance-vector routing in order to minimize the latency encountered when routing a datagram from one location to another. Motivated by the requirements of the many types of emerging multimedia applications that will require dedicated virtual circuits, we investigate fault-tolerant protocols for routing virtual circuits that both minimize latency and maximize bandwidth as well as optimize a broad class of other routing metrics. The protocols we present are self-stabilizing: starting from an arbitrary and possibly illegitimate initial state, they converge to a legitimate state. As a consequence of this property they can tolerate arbitrary changes in network topology and link capacities, as well as arbitrary corruption of state variables. In this thesis we identify several important structures for resource-based routing including the maximum flow tree. Define the flow of a path as the minimum capacity of an edge along that path. A maximum flow tree in a network is a rooted spanning tree of the network wherein the path from any vertex to the root is a maximum flow path. We present a stabilizing protocol for constructing maximum flow trees in networks. As virtual circuits are allocated and freed along a maximum flow tree, it may lose its maximum flow property and thus it may need to be updated. We present an enhanced stabilizing protocol to update a maintained maximum flow tree with respect to the set of available capacities. This protocol has the following desirable safety property: while the tree is being updated, it always remains a tree. We also provide the necessary and sufficient conditions for a routing metric to be optimizable along a tree. Based on these conditions, we present a generalization of the maximum flow tree which we call the maximum metric tree, and we present a stabilizing protocol for constructing maximum metric trees. Our protocol demonstrates that the distance-vector routing paradigm may be extended to any tree optimizable metric. Finally, we note that several of our protocols are silently stabilizing. A self-stabilizing protocol is silent if starting from an arbitrary state it converges to a state after which the values stored in its communication registers are fixed. Silent stabilization is a desirable property both in terms of simplicity and communication overhead. We demonstrate a lower bound of $\Omega$(log n) bits per communication register for silent stabilizing solutions to constructing a spanning tree, electing a leader and finding the centers of a graph.