Link-state algorithms such as Open Shortest Path First (OSPF) are in common use for providing the routing function in computer networks implementing a connectionless network layer. In such cases, the network routing algorithm builds routing tables as a background task. Information about links is maintained and updated by a topology function replicated in all nodes; as a result, every node owns an image of the network, see e.g. EP 0 348 327 or EP 0 447 725. This image is used with a shortest-path algorithm to compute routes to all destinations. The routing tables, produced by the routing algorithm, normally are used to forward individual packets. With the traditional metrics, optimal paths are "shortest" paths. They are obtained by using the conventional Dijkstra method with a path "length" given by the sum of the "lengths" of the separate links contributing to the path. In such a setting, the "length" of a link is most often not its true geometrical length, but can be a value representing any characteristic of that link. In the following, "weight" will be used as the general term for such values. It could represent e.g. monetary costs for the use of that link, and one goal of the routing algorithm would be to minimize the cost of the network, while maintaining proper connectivity. It could also represent delays on that link, the goal would be to minimize the delays in network data flow. A few examples of metrics in connection with bandwidth or occupancy characteristics can be found in EP 0 276 754 and in U.S. Pat. No. 4,905,233. In EP 0 276 754, a link weight approximately proportional to the occupied capacity is described and used in the Dijkstra method.
A metric that reflects the allocatable capacity available on links is also known from U.S. Pat. Nos. 5,088,032 and 5,067,127. In U.S. Pat. No. 5,067,127, a congestion avoidance control method for communication networks is described, which uses a link weight inversely proportional to the available bandwidth and the path weight is the sum of the link weights. In U.S. Pat. No. 5,088,032 a modified Ford path computation algorithm is described. There, the weight of a link can be inversely proportional to the available bandwidth, and the path weight is determined as the maximum of the weights of its links. Whereas it is stated there that other methods of finding the route with minimum metric may also be used, it is not clear at all that any other method is compatible with the metric proposed. A distance vector method is described; the Dijkstra method is not mentioned at all. As said above, the traditional Dijkstra method uses a path weight, which is determined as the sum of the weights of its links, and therefore it is no substitute for the modified Ford algorithm. Further and in contrast to the distance vector method, the widest-path method (as the Dijkstra method) builds a complete spanning tree of paths from a source to all destinations using a topology database of all nodes, their directly attached links and related link weights. This is especially useful in link-state routing mechanisms and source routing.
In virtual circuit networks, routing is connection-oriented and the routing decision is made at connection setup. If, in addition, connections must have guaranteed bandwidth, e.g. for loss-sensitive communication, a virtual circuit network with bandwidth reservation is necessary. Examples are networks of ST.II routers and ATM networks. There, all packets or cells belonging to a connection follow the same path. In such cases, the routing algorithm applies to the routing of connection setup messages, this is also referred to "call routing".
It is a general object of this invention to avoid the different drawbacks of the prior art and to extend and modify the Dijkstra routing method in a way which allows a determination from the weights of the bottleneck link or links of each path, of the "best" path, which is defined to include the "widest" bottleneck, that is the link with the most favorable (smallest or biggest) weight. It is another object to provide a link-state routing method, especially for virtual circuit networks, with guaranteed bandwidth or bandwidth reservation or with other characteristics which necessitate a bottleneck metric. A further object is to improve a network node by implementing in it a routing function enhancement comprising the widest-path method; improvements to the topology function are proposed to include in its update method a modified dampening method and/or a bandwidth encoding method to enable consideration of dynamically varying available bandwidths. Further disclosed is a network comprising improved nodes which may be mixed with normal nodes not supporting the devised enhancement.