Multiplex communications – Network configuration determination
Reexamination Certificate
1997-09-25
2001-07-03
Chin, Wellington (Department: 2664)
Multiplex communications
Network configuration determination
C370S396000, C370S256000, C709S238000
Reexamination Certificate
active
06256295
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to networks and more particularly to the calculation of paths between nodes in a network having a mesh topology.
BACKGROUND
In a network having a mesh topology, there may be multiple paths or “routes” between any two nodes of the network, wherein each path may include one or more intermediate nodes. Typically, a single “best” path between two nodes is calculated by a routing algorithm of a routing protocol such as Routing Information Protocol (RIP), Intermediate System-to-Intermediate System (IS-IS), Open Shortest Path First (OSPF), Private Network-to-Network Interface (PNNI), or Integrated PNNI (I-PNNI). Many routing protocols use a variation of the well-known Dijkstra algorithm to determine the best path between two network nodes.
For connection-oriented packet and cell switching, which may be implemented in Asynchronous Transfer Mode (ATM) networks, the best path calculated by the routing algorithm is used to define a dedicated path or “virtual circuit” (VC) for transferring information between the two nodes. As is well-known, ATM networks support both permanent virtual circuits (PVCs) and switched virtual circuits (SVCs), both of which are hereafter referred to generically as VCs.
Only a single VC is typically provided between any two nodes, but for some applications it may be desirable to provide multiple VCs for a particular source and destination pair of nodes. For example, a secondary VC may be used as a redundant connection should a primary VC fail or otherwise become unavailable. Multiple VCs may also be used to increase the amount of network traffic that may be exchanged between the source and destination nodes.
When a redundant VC is provided, it is desirable to provide a minimum amount of overlap between the redundant VC and the primary VC such that the possibility of a single point of failure for the redundant VC and the primary VC is reduced. If two non-overlapping paths are provided between a particular pair of nodes, any failure along one path will not cause the second path to fail. Therefore, a method for determining multiple minimally-overlapping paths between two nodes is needed.
SUMMARY OF THE INVENTION
Embodiments of the present invention provide a system for determining multiple minimally-overlapping paths between a source node and a destination node.
In a particular embodiment of the invention, a first path is determined between the source node and the destination node. Next, a second path is determined between the source node and the destination node. If the first path and the second path overlap, at least one path is modified to minimize the overlap between the first path and the second path.
In specific embodiments of the invention, both the first path and the second path contain multiple path elements. The path elements include nodes and links between nodes such that a cost is assigned to both nodes and links.
Another aspect of the invention provides for the establishment of a first circuit between the source and destination nodes along the first path and the establishment of a second circuit between the source and destination nodes along the second path.
Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description which follows below.
REFERENCES:
patent: 4736363 (1988-04-01), Aubin et al.
patent: 5115495 (1992-05-01), Tsuchiya et al.
patent: 5233604 (1993-08-01), Ahmadi et al.
patent: 5251205 (1993-10-01), Callon
patent: 5253248 (1993-10-01), Dravida et al.
patent: 5577030 (1996-11-01), Oki et al.
patent: 5649108 (1997-07-01), Spiegel et al.
patent: 5699347 (1997-12-01), Callon
patent: 5754543 (1998-05-01), Seid
patent: 5825772 (1998-10-01), Dobbins
patent: 5923646 (1999-07-01), Mandhyan
patent: 5933425 (1999-08-01), Iwata
patent: 6016306 (2000-01-01), Le Boudec et al.
patent: 6044075 (2000-03-01), Leboudec
Ogier, Distributed Algorithms for computing Shortest Pairs of disjoint paths, IEEE, pp. 443-455, Aug. 1993.*
Torrieri, Algorithms for finding an optimal set of short disjoint paths in communication network, IEEE, pp. 11-15, 1991.*
Ishida, Multiple node disjoint paths protocol for VP in ATM networks, IEEE, pp. 91-97, Feb. 1997.*
Shaikh, Span Disjoint Paths for physical Diversity in networks, IEEE, pp. 127-133, Apr. 1995.*
Callon, Jeffords, Sandick, and Halpern, Issues and Approaches for Integrated PNNI, The ATM Forum Technical Committee, Apr. 15, 1996, Anchorage, Alaska.
Private Network-Network Interface Specification Version 1.0 (PNNI 1.0), The ATM Forum Technical Committee, af-pnni-0055.00, Mar. 1996.
Blakely , Sokoloff, Taylor & Zafman LLP
Chin Wellington
Nguyen Steven
Nortel Networks Limited
LandOfFree
Method and apparatus for determining multiple... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining multiple..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining multiple... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2522093