MIME-Version: 1.0 Server: CERN/3.0 Date: Monday, 06-Jan-97 22:02:39 GMT Content-Type: text/html Content-Length: 2941 Last-Modified: Monday, 05-Aug-96 00:58:09 GMT
Conventional connectionless datagram routing protocols such as IP utilize vector-distance and link-state routing in order to minimize the distance traveled 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 distance and maximize bandwidth. 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 changes in network topology and link capacities.
We consider networks where edges have positive capacities. The flow of a path in a network is the minimum capacity for an edge in that path. A maximum flow path is a path whose flow is greater than or equal to the flow of any other path with the same first and last vertices. We introduce the concept of a maximum flow tree in a network. A maximum flow tree in a network is a rooted spanning tree of the network wherein the path of every vertex to the root is a maximum flow path.
We present a stabilizing protocol for constructing maximum flow trees in networks. We make the following observation: every maximum weight spanning tree is a maximum flow tree, but the reverse is not true. We observe that our maximum flow tree protocol has a number of advantages over any maximum weight spanning tree protocol.
We also present a stabilizing protocol for constructing maximum weight spanning trees in networks. Any maximum weight spanning tree algorithm is alternatively a minimum weight spanning tree algorithm. Minimum weight spanning trees are very useful for implementing multicast on a computer network.
We present a protocol for routing and allocating virtual circuits along a maximum flow tree. As virtual circuits are allocated and freed along the tree, it may lose its maximum flow tree property, and thus it may need to be updated. We present a stabilizing protocol to update the maintained maximum flow tree. The protocol has the following desirable safety property: while the tree is being updated, it always remains a tree.
Finally we present a flexible strategy for routing and allocating virtual circuits that minimizes the length of a circuit with respect to a desired set of flow values. The protocol presented is also stabilizing.