Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-12-22
2001-11-20
Maung, Zarni (Department: 2152)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S244000, C370S351000
Reexamination Certificate
active
06321271
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods and systems for routing data paths in highspeed data networks. More particularly, the present invention relates to methods and systems for selecting preferred routing paths in such networks employing private network node interface (PNNI) protocols.
BACKGROUND OF THE INVENTION
High capacity data networks, such as those using high-speed asynchronous transfer mode (ATM) switches offer promise not only of high-speed data delivery, but also a variety of quality of service (QoS) guarantees. An important element of establishing paths interconnecting nodes in a such high-speed data networks is an efficient, reliable routing mechanism.
Recently, the ATM Forum has standardized on certain PNNI protocols. As defined, these protocols provide for signaling and routing protocols that permit connection setup and release with multiple QoS parameters between nodes. These protocols also provide for exchange of topology state information between nodes. See further,
Traffic Management Specification
, Version 4.0, ATM Forum af-tm-0056.000, April, 1996; and
Private Network-Network Interface Specification Version
1.0 (
PNNI
1.0), af-pnni-0055.000, March 1996.
Many implementations of the PNNI protocols have been proposed, with a variety of performance and QoS features. An important consideration in many networks, such as those using the PNNI protocols, is interconnecting desired nodes while employing a minimum of network resources. In particular, it is desired to interconnect nodes using the shortest interconnecting paths. Additionally, it has become ever more important—especially for many time-dependent applications (such as multimedia applications)—to seek to achieve low or minimum delay time for transmission between selected nodes. QoS criteria based on such reduced or minimum delay are therefore of great importance for critical applications, and provide important competitive differentiation for service providers.
There are many solutions for selecting the shortest path (or minimum defined cost) between selected nodes, even in a network having a large number of interconnected nodes. Prominent among these shortest path algorithms is the well-known Dijkstra algorithm. Solutions based on the Dijkstra and other algorithms may often be modified to permit the inclusion of certain conditions relating to various QoS criteria. Experience with Dijkstra algorithm solutions and corresponding coding implementations have proven reliable in many cases and have been adopted for real-time network implementations. It is desirable, therefore, to reuse existing code and maintain functional compatibility between delay-constrained solutions and existing shortest path implementations. As is well known in the art, however, network solutions of the shortest path problem subject to an additive delay condition is a so-called “NP hard” problem that proves intractable in real-time network contexts using current implementation technologies.
SUMMARY OF THE INVENTION
The limitations of the prior art are overcome and a technical advance is made in the network routing arts in accordance with illustrative embodiments of the present invention, as described in the following detailed description.
In accordance with an illustrative embodiment of the present invention, determinations are made at a source node in a network of the short weight paths to each other node in the network, subject to satisfying an acceptable delay constraint. Advantageously, these determinations are performed in a two-phase method employing a modified Dijkstra's algorithm at each phase.
In an illustrative first phase, the Dijkstra SPF algorithm is used in seeking the shortest cumulative delay from the destination to the source, thereby generating cumulative delay labels from a node j to the destination node k. The delay results are then employed in the second phase, where the Dijkstra SPF algorithm is illustratively employed for determining administrative weight (AW) as the link metric subject to modification in accordance with another aspect of the present invention. More specifically, in an illustrative embodiment it proves advantageous to (i) label a node i with cumulative AW from the source node, (ii) track cumulative delay (D
s,i
) from the source during forward AW labeling, and (iii) labeling neighboring nodes j of a permanently labeled node i only if (D
s,i
+d
j,k
+&dgr;
i,j
) is less than the specified end-to-end delay constraint (where &dgr;
i,j
is the delay for the link between nodes i and j).
REFERENCES:
patent: 5317566 (1994-05-01), Joshi
patent: 5430727 (1995-07-01), Callon
patent: 5548581 (1996-08-01), Makrucki
patent: 5561790 (1996-10-01), Fusaro
patent: 5596719 (1997-01-01), Ramakrishnan et al.
patent: 5668800 (1997-09-01), Stevenson
patent: 5754543 (1998-05-01), Seid
patent: 5831982 (1998-11-01), Hummel
patent: 5933425 (1999-08-01), Iwata
patent: 5995503 (1999-11-01), Crawley et al.
patent: 6038509 (2000-03-01), Poppen et al.
patent: 6055561 (2000-04-01), Feldman et al.
patent: 6147969 (2000-01-01), Benmohamed et al.
patent: 6256295 (2001-07-01), Callon
Ahuja et al. “Fater Algorithms for the Shortest Path Problem”, JACM, vol. 37.2, pp. 213-223, Apr. 1990.*
Orda et al. “Shortest-Path and Min.-Delay Algorithm in Networks with Time-Dependent Edge-Length”, JACM, vol. 37.3, pp. 607-625, Jul. 1990.*
Solka et al. “Fast Computation of Optimal Paths using a Parallel Dijkstra Algorithm with embedded Constrainst” Elsevier SBV, vol. 8, pp. 195-212, 1995.*
Parsa, M, et al: “An Iterative Algorithm for Delay-Constrained Minimum-Cost Multicasting,” IEEE/ACM Transactions on Networking, vol. 6, No. 4 Aug. 1998, pp. 461-474.
Logothetis, D., et al.,: “Delay sensitive routing in PNNI-based ATM networks” IEEE Globecom 1998, Sydney, Australia, Nov. 8-12, 1998, pp. 604-612.
Widyono, R.: “The design and evaluation of routing algorithms for real-time channels,” Internet Article, 'oNLINE!, Jun., 1994, pp. 1-37 (no page 2 available); retrieved from <URL: ftp://ftp.icsi.berkeley.edu/pub/techreports/19994/tr-94-024.ps.gz>.
Kodialam Muralidharan Sampath
Lau Wing Cheong
Yan Anlu
Cardone Jason D.
Lucent Technologies - Inc.
Maung Zarni
Ryan William
LandOfFree
Constrained shortest path routing method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Constrained shortest path routing method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constrained shortest path routing method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2617740