📄 http:^^www.cs.utexas.edu^users^marco^abstract.html
字号:
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
<HTML><!-- This document is in HyperText Markup Language. HTML tags are enclosed -- in angle brackets. This is a comment tag and won't be displayed as part -- of your document. --><!-- ====================================================================== --><HEAD><TITLE>Flow Routing in Computer Networks</TITLE></HEAD><!-- ====================================================================== --><BODY><p>Conventional connectionless datagram routing protocols such as IPutilize vector-distance and link-state routing in order to minimizethe 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 areself-stabilizing: starting from an arbitrary and possibly illegitimateinitial state, they converge to a legitimate state.As a consequence of this property they can tolerate changes in network topology and link capacities. <p>We consider networks where edges have positive capacities.The flow of a path in a network is the minimum capacity for an edge in thatpath. A maximum flow path is a path whose flow is greater than or equalto 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 networkwherein the path of every vertex to the root is a maximum flow path.<p>We present a stabilizing protocol for constructing maximum flowtrees in networks. We make the following observation: every maximum weightspanning tree is a maximum flow tree, but the reverse is not true.We observe that our maximum flow tree protocol has a number of advantagesover any maximum weight spanning tree protocol.<p>We also present a stabilizing protocol for constructingmaximum weight spanning trees in networks. Any maximum weight spanning tree algorithm is alternatively a minimumweight spanning tree algorithm. Minimumweight spanning trees are very useful for implementingmulticast on a computer network. <p>We present a protocol for routing and allocating virtual circuits along a maximum flow tree. As virtual circuits are allocated and freedalong the tree, it may lose its maximum flow tree property, and thus it mayneed 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.<p>Finally we present a flexible strategy for routing and allocatingvirtual circuits that minimizes the length of a circuit with respectto a desired set of flow values. The protocol presented is alsostabilizing.⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -