Failure restoration system suitable for a large-scale network

• US 6,026,077 A
• Filed: 11/10/1997
• Issued: 02/15/2000
• Est. Priority Date: 11/08/1996
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iwata, Atsushi
• Primary Examiner(s): Patel, Ajit
• Assistant Examiner(s): NGUYEN, BRIAN D
• Application Number:
  US08/967,045
• Time in Patent Office: 827 Days
• Field of Search: 370/254, 370/255, 370/238, 370/225, 370/228, 370/400, 370/389, 370/216, 370/217, 370/221, 370/227, 340/827
• US Class Current: 370/254
• CPC Class Codes: H04L 2012/5621 Virtual private network [VPN]; Private-network - network-interface (P-NNI)
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04Q 3/0062 Provisions for network management
• CPC Class Codes: H04Q 3/0079 involving restoration of networks, e.g. disaster recovery, self-healing networks

Abstract

In a failure restoration system comprising a distributed hierarchical routing section which is adapted to set up a main path and previously determine an alternate path for the main path in a network, an alternate path selection section is adapted to obtain complete source route information for the main path when it attempts to set up the main path. The alternate path selection section adds the complete source information to a SETUP signaling message for setting up the alternate path, thereby provides a physical alternate path as much different as possible from the main path.

Claims

1. A failure restoration system comprising distributed hierarchical routing means capable of exchanging, in a distributed and hierarchical manner, link state parameters between nodes in a connection-oriented network having a plurality of subnetworks, the link state parameter including information about a bandwidth of a link and delay to discover a hierarchical topology, the routing means being adapted to set up a main path and previously determine an alternate path for the main path, wherein:

the failure restoration system further comprises alternate path selection means adapted to obtain complete source route information for the main path when it attempts to set up the main path, said alternate path selection means adding the complete source information to a SETUP signaling message for setting up the alternate path, thereby providing said alternate path as much different as possible from the main path.

2. A failure restoration system as claimed in claim 1, wherein said alternate path selection means comprises:

link state routing protocol means for exchanging the link state parameters in a distributed and hierarchical manner among nodes;

a link state database for storing hierarchical topology information obtained by said link state routing protocol means and information about quality of communication via links and nodes;

signaling means for obtaining, to set up a connection for the main path, the complete source route information after reception of a message indicating that the connection setup is completed, to notify main path discovery means of the completion of the connection setup, the signaling means also storing the complete source route information obtained into a main path database; and

alternate path computing means for computing, when said signaling means attempts to set up the alternate path for the main path, a hierarchical alternate path that passes through the physical nodes/physical links different from those on the main path according to said link state database and said main path database;

the hierarchical alternate path being designated to the SETUP signaling message, the SETUP signaling message being added with the complete source route information for setting up the connection, thereby setting up said alternate path as much different as possible from the main path.

3. A failure restoration system comprising distributed hierarchical routing means capable of exchanging, in a distributed and hierarchical manner, link state parameters between nodes in a connection-oriented network having a plurality of subnetworks, the link state parameters including information about a bandwidth of a link and delay to discover a hierarchical topology, the routing means being adapted to set up a main path and previously determine an alternate path for the main path, wherein:

the failure restoration system further comprises alternate path selection means adapted to flood a combination of hierarchical source route information for the main path assigned for each subnetwork and a unique connection ID for identification of the main path throughout the network, among all nodes other than the flooding source node within the same subnetwork for each subnetwork on the main path when it attempts to set up the main path, said alternate path selection means also being adapted to add the connection ID of the main path to a SETUP signaling message for setting up the alternate path, thereby providing said alternate path as much different as possible from the main path.

4. A failure restoration system as claimed in claim 3, wherein said alternate path selection means comprises:

link state routing protocol means for exchanging the link state parameters in a distributed and hierarchical manner among nodes;

a link state database for storing hierarchical topology obtained by said link state routing protocol means and information about quality of communication via links and nodes;

signaling means for setting up a connection for the main path by using the unique connection ID for identification of the main path throughout the network;

main path discovery means for flooding, after reception of a message indicating that the connection setup is completed, a combination of the hierarchical source route information for the main path and the connection ID of the main path for each subnetwork on the main path, thereby exchanging hierarchical main path information to obtain the main path information;

a main path database for storing the main path information obtained; and

alternate path computing means for computing, when said signaling means attempts to set up the alternate path for the main path, a hierarchical alternate path that passes through the physical nodes/physical links different from those on the main path according to information stored in said link state database and in said main path database;

the hierarchical alternate path being designated to the SETUP signaling message, the SETUP signaling message being added with the connection ID for the main path for setting up the connection, thereby setting up said alternate path as much different as possible from the main path.

5. A failure restoration system comprising distributed hierarchical routing means capable of exchanging, in a distributed and hierarchical manner, link state parameters between nodes in a connection-oriented network having a plurality of subnetworks, the link state parameters including information about a bandwidth of a link and delay to discover a hierarchical topology, wherein:

each node comprises alternate path selection means that floods or advertises, among other nodes, the link state parameters with the addition of a reliability factor obtained depending on a degree of reliability of nodes/links, thereby selecting a route based on the reliability factor.

6. A failure restoration system as claimed in claim 5, wherein said alternate path selection means comprises:

link state routing protocol means for exchanging the link state parameters in a distributed and hierarchical manner among nodes;

a link state database for storing hierarchical topology information obtained by said link state routing protocol means and information about quality of communication via links and nodes;

reliability discovery means for obtaining reliability information by means of exchanging, among nodes, the link state parameters with the addition of the reliability factor;

a reliability database for storing the reliability information obtained; and

alternate path computing means;

said alternate path computing means having logical topology generating means for generating a logical topology depending on the reliability factor, in accordance with information stored in said link state database and information stored in said reliability database, said alternate path computing means selecting a route based on the logical topology.

7. A failure restoration system as claimed in claim 5, wherein said alternate path selection means is for setting up an alternate path for the main path after the main path has established, said alternate path selection means being adapted to obtain complete source route information for the main path when it attempts to set up the main path, said alternate path selection means adding the complete source information to a SETUP signaling message for setting up the alternate path, thereby providing a physical alternate path as much different as possible from the main path.

8. A failure restoration system as claimed in claim 7, wherein said alternate path selection means comprises:

reliability discovery means for obtaining reliability information by means of exchanging, among nodes, the link state parameters with the addition of the reliability factor;

a reliability database for storing the reliability information obtained;

a main path database for storing the complete source route information for the main path;

alternate path computing means having logical topology generating means for generating a logical topology depending on the reliability factor, in accordance with information stored in said link state database and information stored in said reliability database;

logical alternate path computing means for obtaining the main path information from said main path database to compute a logical alternate path that passes through physical nodes/physical links different from those on the main path; and

physical alternate path computing means that degenerates the logical alternate path into the physical path; and

signaling means for designating the physical hierarchical alternate path to the SETUP signaling message and adding to the SETUP signaling message the complete source route information for the main path for setting up the connection, thereby setting up a physical alternate path as much different as possible from the main path.

9. A failure restoration system as claimed in claim 5, wherein said alternate path selection means is for setting up an alternate path for the main path after the main path has established, said alternate path selection means being adapted to flood a combination of hierarchical source route information for the main path assigned for each subnetwork and a unique connection ID for identification of the main path throughout the network, among all nodes other than the flooding source node within the same subnetwork for each subnetwork on the main path when it attempts to set up the main path, said alternate path selection means also being adapted to add the connection ID of the main path to a SETUP signaling message for setting up the alternate path, thereby providing a physical alternate path as much different as possible from the main path.

10. A failure restoration system as claimed in claim 9, wherein said alternate path selection means comprises:

reliability discovery means for obtaining reliability information by means of exchanging, among nodes, the link state parameters with the addition of the reliability factor;

a reliability database for storing the reliability information obtained;

a main path database for storing the hierarchical main path information;

alternate path computing means having logical topology generating means for generating a logical topology depending on the reliability factor, in accordance with information stored in said link state database and Information stored in said reliability database;

logical alternate path computing means for obtaining the hierarchical main path information from the information stored in said main path database by means of designating the connection ID of the main path, to compute a logical alternate path that passes through physical nodes/physical links different from those on the main path; and

physical alternate path computing means that degenerates the logical alternate path into the physical path; and

signaling means for designating the physical hierarchical alternate path to the SETUP signaling message and adding to the SETUP signaling message the connection ID of the main path for setting up the connection, thereby setting up a physical alternate path as much different as possible from the main path.