Browse Prior Art Database

Algorithm for Random Selection of Shortest Path

IP.com Disclosure Number: IPCOM000037025D
Original Publication Date: 1989-Nov-01
Included in the Prior Art Database: 2005-Jan-29

Publishing Venue

IBM

Related People

Authors:
Ahmadi, H Guerin, R Hantler, SL [+details]

Abstract

Many networks, including communications networks, can be modelled as weighted graphs [1]; the weights may represent cost, expected delay or expected reliability of the links in the network. It is often necessary to find the shortest path between two nodes in such graphs, for example, to find suitable paths over which to route messages in a communications network. Examples of shortest-path routing in networks can be found in [2-4] while [5] provides additional motivations for its use. In such networks it is desirable to balance the load on the links of the network whenever this is consistent with the primary requirement of routing over the shortest available path. In some architectures, shortest paths are chosen asynchronously and independently many times.