Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Patent
1996-09-12
2000-01-18
Olms, Douglas W.
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
370400, 39520071, G06F 1300, H04L 1256
Patent
active
060163062
DESCRIPTION:
BRIEF SUMMARY
TECHNICAL FIELD
The present invention concerns the routing function in information networks, e.g. switch-based computer networks. In such a network it is necessary to determine paths from source nodes to destination nodes. This invention enhances and expands the known Dijkstra routing method to support additional types of service, e.g. reserved bandwidth service, which are not possible with the Dijkstra method. The invented method will also be called "widest-path method" throughout this description. A specific path metric is used, called "bottleneck metric" in the sequel, which was found to be compatible with the algebraic rules that govern the routing method. With this metric, it is possible to reflect realistically enough at least the bandwidth characteristics of the paths, but other characteristics may also be represented. The widest-path method can be used e.g. in connection-oriented networks as Asynchronous Transmission Mode (ATM) or Internet Stream Protocol Version II (ST.II) networks, where the routing decisions are made at connection setup, but it is not limited thereto. It can be used to precompute paths from any source to any destination and prestore all paths until a respective one is used for a connection request. Such precomputed routing trees are advantageous in source routing methods, where the local source node tree is used to produce a source vector, which describes the path as a sequence of nodes to be covered during packet transmission. The present invention is especially useful in link-state routing mechanisms for networks, but it could be used in the context of any routing problem for which the widest-path method is applicable and for which the bottleneck metric is an appropriate representation of the respective path characteristic.
BACKGROUND OF THE INVENTION
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
REFERENCES:
patent: 5088032 (1992-02-01), Bosack
patent: 5115495 (1992-05-01), Tsuchiya et al.
patent: 5163042 (1992-11-01), Ochiai
patent: 5218676 (1993-06-01), Ben-Ayed et al.
patent: 5521910 (1996-05-01), Matthews
patent: 5596719 (1997-01-01), Ramakrishnan et al.
patent: 5596722 (1997-01-01), Rahnema
patent: 5600794 (1997-02-01), Callon
patent: 5606669 (1997-02-01), Bertin et al.
patent: 5608721 (1997-03-01), Natarajan et al.
Le Boudec Jean-Yves
Przygienda Antoni B.
Sultan Robert
International Business Machines - Corporation
Olms Douglas W.
Rao Seema S.
Woods Gerald R.
LandOfFree
Routing bandwidth-reserved connections in information networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Routing bandwidth-reserved connections in information networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing bandwidth-reserved connections in information networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-567593