(12) United States Patent
`Azuma et al.
`
`I 1111111111111111 11111 111111111111111 IIIII 1111111111 11111 1111111111 11111111
`US006430150Bl
`US 6,430,150 Bl
`* Aug. 6, 2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) COMMUNICATION NODE, RESTORATION
`METHOD AND COMMUNICATION
`NETWORK
`
`(75)
`
`Inventors: Mitsuhiro Azuma, Kawasaki (JP);
`Haim Kobrinski, Colts Neck; Tsong
`Ho Wu, Englishtown, both of NJ (US)
`
`(73) Assignee: Fujitsu Limited, Kawasaki (JP)
`
`( *) Notice:
`
`This patent issued on a continued pros(cid:173)
`ecution application filed under 37 CFR
`1.53( d), and is subject to the twenty year
`patent term provisions of 35 U.S.C.
`154(a)(2).
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 73 days.
`
`(21) Appl. No.: 08/643,761
`
`(22)
`
`Filed:
`
`May 6, 1996
`
`(30)
`
`Foreign Application Priority Data
`
`Feb. 14, 1996
`
`(JP) ............................................. 8-027126
`
`Int. Cl.7 ........................ H04L 12/407; G0lR 31/08
`(51)
`(52) U.S. Cl. ....................... 370/218; 370/228; 370/255;
`370/400; 340/825.01; 709/239
`(58) Field of Search ............................ 395/181, 182.02,
`395/200.68, 200.69, 200.72, 200.73, 200.52;
`370/216, 217, 221, 225, 400, 406, 410,
`254, 255-256, 409, 392, 227, 228; 709/239-244;
`340/825.01
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4,679,186 A * 7/1987 Lea ............................ 370/218
`4,679,189 A * 7/1987 Olson et al. ................ 370/396
`4,884,263 A * 11/1989 Suzuki ....................... 370/225
`4,933,936 A * 6/1990 Rasmussen et al.
`........ 370/406
`
`5,084,816 A *
`5,093,824 A *
`5,235,599 A
`5,627,822 A *
`5,646,936 A *
`5,732,072 A *
`5,742,820 A *
`5,805,593 A *
`5,883,881 A *
`6,026,077 A *
`6,038,212 A *
`6,069,894 A *
`6,075,766 A *
`
`1/1992 Boese et al. ................ 370/225
`3/1992 Coan et al. ................. 370/228
`8/1993 Nishimura et al.
`........ 371/11.2
`5/1997 Edmaier et al.
`............ 370/390
`7/1997 Shah et al.
`................. 370/228
`3/1998 Thanner et al. ............. 370/255
`4/1998 Perlman et al. ........ 395/200.72
`9/1998 Busche ....................... 370/238
`3/1999 Croslin ....................... 370/221
`2/2000 Iwata ......................... 370/254
`3/2000 Galand et al.
`.............. 370/216
`5/2000 Ho lender et al.
`........... 370/397
`6/2000 Croslin ....................... 370/225
`
`FOREIGN PATENT DOCUMENTS
`
`JP
`64-5246
`JP
`4-88738
`JP
`4-154242
`JP
`4-257143
`JP
`6-37783
`JP
`7-327048
`* cited by examiner
`
`1/1989
`3/1992
`5/1992
`9/1992
`2/1994
`12/1995
`
`Primary Examiner-Seema S. Rao
`(74) Attorney, Agent, or Firm-Katten Muchin Zavis Rosen
`
`(57)
`
`ABSTRACT
`
`In a telecommunication network, each node is provided with
`the same physical topology information relating to a physi(cid:173)
`cal construction of telecommunication paths included in the
`telecommunication network and with the same logical topol(cid:173)
`ogy information relating to routing of telecommunication
`paths. When a failure occurs, restoration is effected by
`transmitting information relating to the failure that has
`occurred in the telecommunication network, throughout the
`network. Each node that receives the information relating to
`the failure determines alternative paths for bypassing the
`failure using the information relating to the failure, the
`physical topology information, and the logical topology
`information. Then service is switched to the alternative
`paths.
`
`16 Claims, 9 Drawing Sheets
`
`34 MAINTENANCEMESSAGETRANSMISSIOHLINE
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 1 of 19
`
`

`

`U.S. Patent
`
`Aug. 6, 2002
`
`Sheet 1 of 9
`
`US 6,430,150 Bl
`
`F I G. 1A
`
`L1 (6, 5)
`
`L3 (5, 6)
`
`L i
`
`(WORKING. SPARE)
`
`PHYSICAL TOPOLOGY TABLE
`
`L W S
`
`6
`
`5
`
`2 3 6
`
`3
`
`5
`
`6
`
`F I G. 1 B
`
`LOGICAL TOPOLOGY TABLE
`
`C
`
`PATHS SET
`
`3 1~ 3~ 2
`
`2 2~1+--,-3
`
`1 ~ 2
`
`4
`?'
`)
`CAPACITY TO BE RESTORED
`
`3
`
`LOGICAL PATHS SET
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 2 of 19
`
`

`

`U.S. Patent
`
`Aug. 6, 2002
`
`Sheet 2 of 9
`
`US 6,430,150 Bl
`
`F I G. 2A
`
`FAILURE
`
`FIG. 2B
`
`ALARM PROCE S SING
`
`B
`
`ALARM
`
`7
`
`l8~~bi~+10N~;~-----~
`~
`7
`/
`,;
`/
`,;
`
`/
`/
`~
`/
`/
`/
`/
`/
`/
`/
`/
`;:;
`,; RESTORED
`CROSS-CONNECTION-~ RESTORED
`/c~~R=AF=F~IC===~~r,~T~R=A=F=F=\~C==:.i⇒
`PHASE
`
`/
`/
`/
`/
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 3 of 19
`
`

`

`U.S. Patent
`
`Aug. 6, 2002
`
`Sheet 3 of 9
`
`US 6,430,150 Bl
`
`<(
`r<)
`.
`CD
`
`LL
`
`w
`(J)
`<!
`I
`0..
`z
`0
`I(cid:173)
`<!
`1-
`::,
`w
`0..
`~ -
`(.'.)
`<I
`O'----
`(/)
`u
`(/)
`w - -~= ; : : _ _ _._
`~
`
`w
`~
`l(cid:173)
`o
`0::
`<!
`::,
`(.'.)
`
`-
`
`~
`a::
`<!
`_J
`<!
`
`(D
`r<)
`
`LL
`
`w
`~
`I-
`
`w
`~
`l-
`o
`0::
`<!
`:::)
`(.9
`
`>(cid:173)
`(.9
`0
`d
`0..
`0
`1-z
`
`LLO o-1-
`
`I- <!
`0::: I(cid:173)
`<! ::,
`I- 0..
`(/)~
`WO
`0:: u
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 4 of 19
`
`

`

`U.S. Patent
`
`Aug. 6, 2002
`
`Sheet 4 of 9
`
`US 6,430,150 Bl
`
`FIG. 4A
`
`OS
`
`CONTROL MESSAGES
`
`A
`
`WORKING
`
`D
`
`F I G. 4 B
`INFORMATION EXCHANGE ABOUT
`NEW TOPOLOGY
`
`OS
`
`A
`
`B
`
`NEW WORKING PATH
`
`D
`
`C
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 5 of 19
`
`

`

`U.S. Patent
`
`Aug. 6, 2002
`
`Sheet 5 of 9
`
`US 6,430,150 Bl
`
`F I G. 5A
`
`PATH RESTORATION ROUTE
`- ~ - - - - - - - - - - - -
`- -,
`-
`• .3
`/ 2. • • e
`:
`: \
`~
`: LINE RESTORATION
`~
`~ ROUTE
`
`• e ••I ••• ••••••• I t I l l I I•
`
`I
`
`9
`
`'
`
`'
`
`. . . . . . . . . . . .
`
`LINK FAILURE
`
`ORIGINAL PATH
`
`F I G. 58
`
`ROUTE
`
`ORIGINAL PATH
`
`ALTERNATE ROUTE
`tENO-TO-ENO OF THE PATH)
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 6 of 19
`
`

`

`U.S. Patent
`
`Aug. 6, 2002
`
`Sheet 6 of 9
`
`US 6,430,150 Bl
`
`F G. 6
`
`SW
`
`s 2 6
`STM NETWORK S 3 0
`ALTERNATE ROUTE
`STORING PART
`,
`
`-
`
`ATM NETWORK S 3 2
`ALTERNATE
`VIRTUAL PATH(VP)
`SETTING PART
`I
`
`S 2 8
`
`k'--
`
`ALTERNATE ROUTE
`AUTOMATING
`~ COMPUTING PART
`
`S 1 8
`CROSS-CONNECTION
`CONFIRMING PART
`
`~
`
`S 1 6
`ALTERNATE ROUTE
`PART
`
`t><
`r I
`- CROSS-CONNECTING
`
`S 1 4
`ALTERNATE ROUTE
`COMPUTING PART
`
`S 1 2
`FAILURE TYPE
`DETERMINING PART "
`
`-
`
`S 1 0
`ALARM MESSAGE
`DETECTING PART
`
`\
`)
`
`S 2 4
`LOGICAL TOPOLOGY
`MAINTAINING PART
`
`S 2 2
`PHYSICAL TOPOLOGY
`MAINTAINING PART
`
`S 2 0
`TOPOLOGY UPDATING
`MESSAGE DETECTING PART
`
`(
`~
`
`)
`
`3 4 MAINTENANCE MESSAGE TRANSMISSION LINE
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 7 of 19
`
`

`

`U.S. Patent
`
`Aug. 6, 2002
`
`Sheet 7 of 9
`
`US 6,430,150 Bl
`
`F
`
`G. 7
`
`START
`
`YES
`
`ALARM MESSAGE
`PROCESS
`
`(3)
`
`RECEIVE ALARM MESSAGE
`
`(4)
`
`(5)
`
`(6)
`
`IDENTIFY LOCATION OF
`FAILURE
`
`START GUARD TIMER
`
`EXECUTE ALTERNATE ROUTE
`COMPUTATION
`
`TOPOLOGY UPDATING
`PROCESS
`
`(11)
`
`(12)
`
`(13)
`
`TOPOLOGY UPDATING
`MESSAGE PROSSES
`
`UPDATE PHYSICAL
`TOPOLOGY
`
`UPDATE LOGICAL
`TOPOLOGY
`
`END
`
`NO
`
`(9)
`
`CROSS-CONNECT PATH
`(CROSS-CONNECT VPI)
`
`(10)
`
`CONFIRM CROSS-CONNECTION
`
`END
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 8 of 19
`
`

`

`U.S. Patent
`
`Aug. 6, 2002
`
`Sheet 8 of 9
`
`US 6,430,150 Bl
`
`F I G. 8
`
`START
`
`YES
`
`ALARM MESSAGE
`PROCESS
`
`(3)
`
`RECEIVE ALARM MESSAGE
`
`(4)
`
`(5)
`
`IDENTIFY LOCATION OF
`FAILURE
`
`START GUARD TIMER
`
`(9)
`
`CROSS-CONNECT PATH
`(CROSS-CONNECT VPI)
`
`(10)
`
`CO~F I RM CROSS-CONNECT I ON
`
`(11)
`
`(12)
`
`(13)
`
`(18)
`
`TOPOLOGY UPDATING
`MESSAGE PROSSES
`
`UPDATE PHYSICAL
`TOPOLOGY
`
`UPDATE LOGICAL
`TOPOLOGY
`
`EXECUTE ALTERNATE
`PATH COMPUTATION
`
`(14)
`
`ATM NETWORK
`
`STM
`NETWORK
`
`(15)
`
`STORE AL TERNA TE
`PATH PATTERN
`
`(1&
`SET AL TERNA TE
`VPI
`
`(17)
`
`EONF I RM
`SETTING
`
`END
`
`END
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 9 of 19
`
`

`

`i,-
`~
`Q
`(1)
`i,-
`
`-..=
`O'I b
`rJ'J.
`e
`
`\0
`0 ....,
`\0
`~ ....
`'JJ. =(cid:173)~
`
`N
`0
`0
`N
`~~
`
`t (tQ
`
`~ =
`......
`~ ......
`~
`•
`rJJ.
`~ •
`
`I / F : INTERFACE
`
`X
`u
`
`1/F
`
`Til-150M
`
`X
`
`u
`M
`
`1/F
`
`6 0 0 M
`
`1/F
`
`2. 5 G
`
`D
`
`VP-SWITCH
`8 X 8
`b a s e d
`2.5Gb/s
`
`4 4
`
`4 6
`
`MEMORY
`
`VPI TABLE
`
`DATA TRANSFER FOR VPI TABLE UPDATE
`
`F G. 9
`
`X
`
`1/F ~~H
`
`l 5 0 M
`
`u
`M
`
`~
`
`6 0 0 M 1/F
`
`2. 5 G 1/F
`
`4 2
`
`CPU
`
`4 0
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 10 of 19
`
`

`

`US 6,430,150 Bl
`
`1
`COMMUNICATION NODE, RESTORATION
`METHOD AND COMMUNICATION
`NETWORK
`
`2
`method and a telecommunication network, wherein a
`prompt restoration is possible using a simple process.
`The aforementioned objects can be achieved by a resto(cid:173)
`ration method in a telecommunication network in which
`5 each node is provided with physical topology information
`relating to a physical construction of telecommunication
`paths included in the telecommunication network and logi(cid:173)
`cal topology information relating to routing of telecommu(cid:173)
`nication paths, said restoration method comprising the steps
`10 of:
`( a) transmitting information relating to a failure that has
`occurred in the telecommunication network, through(cid:173)
`out the network;
`(b) in each node that has received said information
`relating to the failure, determining alternate paths for
`bypassing the failure using said information relating to
`the failure, said physical topology information, and said
`logical topology information; and
`( c) switching services to the alternate paths determined in
`step (b).
`The aforementioned objects can also be achieved by a
`telecommunication node provided with physical topology
`information relating to a physical construction of telecom(cid:173)
`munication paths included in the telecommunication net(cid:173)
`work and logical topology information relating to routing of
`telecommunication paths, said telecommunication node
`comprising:
`first means transmitting information relating to a failure
`that has occurred in the telecommunication network,
`throughout the telecommunication network;
`second means determining alternate paths for bypassing
`the failure using said information relating to the failure,
`said physical topology information, and said logical
`topology information; and
`third means switching services to the alternate paths
`determined by said second means.
`The aforementioned objects can also be achieved by a
`telecommunication network including telecommunication
`nodes each provided with physical topology information
`relating to a physical construction of telecommunication
`paths included in the telecommunication network and logi(cid:173)
`cal topology information relating to routing of telecommu-
`nication paths, wherein each node comprises:
`first means transmitting information relating to a failure
`that has occurred in the telecommunication network,
`throughout the telecommunication network;
`second means determining alternate paths for bypassing
`the failure using said information relating to the failure,
`said physical topology information, and said logical
`topology information; and
`third means switching services to the alternate paths
`determined by said second means.
`According to the restoration method, the telecommunica-
`tion node and the telecommunication network of the present
`invention, restoration from failure is attained by using
`topology tables relating to the entirety of the network. Only
`information (message) relating to a failure needs to be
`60 exchanged for restoration. Therefore, the present invention
`realizes a high-speed restoration from failure with smaller
`volume of messages exchanged as compared with the con(cid:173)
`ventional dynamic restoration method.
`In further accordance with the present invention, recep-
`65 tion of information relating to a failure is properly controlled
`so that cross-connection in a node is prevented from being
`executed in a transient state in which latest information
`
`25
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention generally relates to networks using
`cross-connect units at telecommunication nodes, and more
`particularly to an automatic restoration method in a mesh
`network.
`A synchronous transfer mode (STM) network and an
`asynchronous transfer mode (ATM) network capable of
`transmitting audio and visual data at a high speed have been
`in use in recent years to provide various services. One
`example of such a network is a mesh network in which 15
`telecommunication nodes provided with cross-connect units
`and telecommunication links are arranged in a mesh con(cid:173)
`figuration.
`Such a network should be configured so as to be capable
`of continuing to serve the user in the event of a failure. 20
`Continuation of services requires that a failure occurring in
`the network be automatically detected and telecommunica(cid:173)
`tion paths that enable bypassing of the failure be established.
`An automatic restoration method is an essential algorithm
`specifying a procedure for establishing the paths.
`2. Description of the Prior Art
`There are generally two types of automatic restoration
`methods proposed for mesh networks: the pre-planned res(cid:173)
`toration method and the dynamic restoration method. In the 30
`pre-planned restoration method, a configuration map speci(cid:173)
`fying alternate paths is stored at each cross-connect unit.
`In the event of a failure, alternate paths are set according
`to the configuration map. Hence, a high-speed restoration is
`possible. Information relating to the alternate paths is com- 35
`puted by the central Operation Systems and distributed
`throughout the nodes.
`In the dynamic restoration method, each node is not
`provided with the above-described configuration map. In the
`event of a failure, nodes adjacent to the point of failure 40
`exchange restoration-related messages several times so as to
`find alternate paths.
`However, the above-described conventional technology
`has the following problems. In the pre-planned restoration
`method, the process executed by the central Operation 45
`Systems to distribute the information relating to alternate
`paths to the nodes may be complex and lengthy. Further,
`when an additional failure (i.e., a secondary failure) occurs
`during the computation for finding alternate paths or during
`the distribution of the information, an updating computation 50
`and a distribution of the updated information to the nodes are
`required. Hence, the process required for the restoration
`becomes complex. Further, since each node is required to
`store the information in a memory, restoration capabilities
`for various failure scenarios are limited.
`In the dynamic restoration method, restoration messages
`are exchanged between the nodes to search for alternate
`paths. Hence, a prompt restoration cannot be hoped for in
`comparison with the pre-planned restoration method.
`
`55
`
`SUMMARY OF THE INVENTION
`Accordingly, an object of the present invention is to
`provide a telecommunication node, a restoration method and
`a telecommunication network, wherein the aforementioned
`problems are eliminated.
`Another and more specific object of the present invention
`is to provide a telecommunication node, a restoration
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 11 of 19
`
`

`

`US 6,430,150 Bl
`
`3
`relating to a failure has not arrived yet. Accordingly, it is
`possible to restore from failure using the latest topology
`information.
`According to one preferred embodiment of the present
`invention, topology information is automatically updated so 5
`that the nodes in a network are provided with latest topology
`information relating to the entirety of the network which
`information is necessary for cross-connecting process
`executed in the event of a failure.
`By executing, in each node, computation for finding
`alternate paths adapted for typical scenarios such as those
`involving a single link failure or a single node failure, a
`high-speed restoration from failure is realized.
`According to another aspect of the present invention,
`restoration from failure can take place only by switching
`from a failed path to an alternate virtual path. Thus, a
`high-speed restoration is realized.
`In further accordance with the present invention, alternate
`path selection most suitable for a failure type is employed so
`that a high-speed restoration is realized.
`
`4
`of a failure in the link or the node, the node adjacent to the
`location of the failure broadcasts a message to the other
`nodes in the network to indicate where the failure has
`occurred. Using the received message, each node performs
`computation for finding alternate paths so as to restore the
`telecommunication path for itself. By switching to the
`alternate paths determined as a result of the computation, a
`high-speed restoration based on a simple procedure is
`attained. More specifically, the aforementioned basic algo-
`10 rithm for the restoration process is composed of a broadcast
`phase, a computation phase and a cross-connection phase.
`A description will now be given, with reference to FIGS.
`lA and lB, of the physical topology and the logical topol(cid:173)
`ogy. FIG. lA shows a telecommunication network and
`15 associated physical topology information. The telecommu(cid:173)
`nication network shown has three nodes 1-3 and three
`telecommunication links Ll, L2 and L3 connecting the
`nodes. The physical topology information indicates the
`physical construction of the links Ll-L3, that is, the number
`20 of working (W) channels and the number of spare (S)
`channels formed on the links. In the example shown in FIG.
`lA, L1 (6, 5) indicates that link 1 (Ll) contains six working
`channels and five spare channels. Each of the nodes 1-3
`keeps a table (physical topology table) as shown storing the
`25 physical topology information. Each of the nodes always
`keeps the physical topology information identical to each
`other.
`FIG. lB shows logical paths set and logical topology
`information in the telecommunication network shown in
`3° FIG. lA. The logical topology information is routing infor(cid:173)
`mation for the paths formed between the nodes. For
`instance, the logical topology information may indicate a
`path formed between the node 1 and the node 2 via the node
`3. The logical topology information also indicate the number
`35 of channels ( capacity) to be restored in the path. Each of the
`nodes keeps a table (logical topology table) as shown storing
`the logical topology information.
`A description will now be given of the broadcast phase. In
`40 the event of a failure in a link or a node in the network, nodes
`adjacent to the location of the failure detect the failure. For
`instance, in the SONET network (the standard transport
`network in the United States), a node in the downstream of
`a failed location may receive an L-AIS (line-alarm indica-
`45 tion signal) or an LOF (loss of frame) signal. A node in the
`upstream of the failed location may receive a FERF (far end
`receive failure) signal so as to recognize that a failure has
`occurred. The node that detected the failure prepares an
`alarm message and broadcasts the same in order to notify all
`50 the nodes in the network of the failure.
`A description will now be given of the computation phase.
`The node that receives the alarm message executes compu(cid:173)
`tation (topology computation) for finding alternate paths
`using the topology information common to the nodes and
`stored in the physical topology table and the logical topol(cid:173)
`ogy table. Consistent computation results (alternate paths)
`are obtained at each node, because common topology infor(cid:173)
`mation of the network and a common computation algorithm
`for finding alternate paths are available and used in each
`60 mode. A known algorithm such as Dijkstra's algorithm may
`be used in the computation.
`A description will now be given of the cross-connection
`phase. A node which has completed the topology computa(cid:173)
`tion starts the cross-connection depending on the result of
`65 topology computation so that services are switched from the
`failed path to the alternate path. Some nodes might not
`require cross-connection depending on the result of topology
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Other objects and further features of the present invention
`will be apparent from the following detailed description
`when read in conjunction with the accompanying drawings,
`in which:
`FIG. lA shows a telecommunication network and asso(cid:173)
`ciated physical topology information;
`FIG. lB shows logical paths set and logical topology
`information in the telecommunication network shown in
`FIG. lA;
`FIG. 2A shows a telecommunication network having
`three nodes A, B and C;
`FIG. 2B is a timing chart for the restoration algorithm of
`the present invention;
`FIG. 3A is a timing chart explaining a guard time intro(cid:173)
`duced in the restoration method of the present invention;
`FIG. 3B is a timing chart explaining a guard time intro(cid:173)
`duced in the restoration method of the present invention;
`FIG. 4A shows a part of a process of updating topology
`information;
`FIG. 4B shows another part of the process of updating
`topology information;
`FIG. SA shows a line restoration method and a node
`restoration method;
`FIG. SB shows a 2-hop restoration method;
`FIG. 6 is a block diagram showing the construction of a
`telecommunication node according to an embodiment of the
`present invention;
`FIG. 7 is a flowchart (1) showing the operation of the
`telecommunication node shown in FIG. 6;
`FIG. 8 is a flowchart (2) showing the operation of the 55
`telecommunication node shown in FIG. 6; and
`FIG. 9 is a block diagram showing the construction of a
`node in an ATM network, according to the present invention.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`The basic algorithm for the restoration process according
`to the present invention is as follows. Each node in the
`network retains physical topology information relating to the
`physical construction of the telecommunication links
`included in the network and logical topology information
`relating to routing of paths formed in the links. In the event
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 12 of 19
`
`

`

`US 6,430,150 Bl
`
`15
`
`5
`computation. Dynamic restoration protocols generally
`execute the cross-connection process synchronously in the
`final phase of the restoration. However, in the algorithm of
`the present invention, each node is able to asynchronously
`execute the cross-connection process. When cross(cid:173)
`connection is completed by all nodes in the network, tele(cid:173)
`communication along the restored path becomes possible.
`FIG. 2A shows a telecommunication network provided
`with three nodes A, B and C, and FIG. 2B is a timing chart
`applicable to the restoration executed according to the above
`described scheme composed of three phases. In the example
`of FIG. 2A, a failure has occurred on the link between node
`A and node C. Node A and node C at the respective ends of
`the failed link detect the failure and enter a failure process(cid:173)
`ing mode. Nodes A and C broadcast an alarm message for
`notifying the other nodes that a failure has occurred. The
`process executed so far concerns the broadcast phase.
`Nodes A and C enter the computation phase after broad(cid:173)
`casting the alarm message. Node B receives the alarm
`message broadcast from node A and node C. After recording
`the content of the message, node B broadcasts the alarm
`message. Thereupon, node B enters the computation phase.
`In the computation phase executed in nodes A-C, the
`topology computation is performed using the common
`topology information stored in the physical topology table
`and the logical topology table kept in each node. Consistent
`computation results ( alternate paths) are obtained at each
`node, because common topology information of the network
`and a common computation algorithm for finding alternate
`paths are available and used in each mode.
`Once the computation result is obtained in nodes A-C,
`each node enters the cross-connection phase. Nodes A-C
`switch services to the alternate path asynchronously accord(cid:173)
`ing to the result obtained. Illustration of the alternate path 35
`thus determined is omitted in FIG. 2.
`According to the above-described method, each node
`enters the computation phase after receiving the broadcast
`alarm message. Once the computation result is obtained,
`each node immediately enters the cross-connection phase.
`However, a node may receive a plurality of broadcast alarm
`messages in the event of a failure. If the plurality of alarm
`messages received relate to the same failure, no problem is
`created because the computation results obtained in accor(cid:173)
`dance with the alarm messages are identical to each other. In
`the example shown in FIG. 2A, nodes A and C generate
`alarm messages which produce the same result in the
`topology computation. However, when a secondary failure
`occurs, for example, the plurality of alarm messages
`received successively by a node have different contents. In
`this case, the computation result obtained in accordance with
`the first alarm message received does not reflect the sec(cid:173)
`ondary failure, for example, that is, does not indicate the
`most up-to-date alternate path.
`In order to avoid such an inconvenience, once the alarm
`message indicating the location of the failure has reached a
`node, the old computation process that has been executed in
`the node to find the alternate path is initialized. Thereupon,
`the computation for finding the alternate path is restarted
`using the old alarm message that the node received. In this 60
`way, it is possible to search for the most up-to-date alternate
`path. In addition, allowing for the possibilities of an addi(cid:173)
`tional alarm message arriving after the computation process
`is completed, it is necessary to wait at each node in the
`network until a guard time expires after the last topology 65
`computation is completed, before proceeding to the cross(cid:173)
`connection phase.
`
`6
`FIGS. 3A and 3B are timing charts showing the above(cid:173)
`described process. As shown in FIG. 3A, a node enters the
`computation phase after receiving an alarm message #1.
`Even if the computation is completed, the node does not
`5 execute a cross-connection until a guard time for the alarm
`message #1 expires.
`Referring to FIG. 3B, a node enters the computation phase
`after receiving the alarm message #1, whereupon a guard
`time #1 is started. If another alarm message #2 is received
`10 in the process of computation, the computation is discon(cid:173)
`tinued. A new computation allowing for the alarm message
`#2 is started. Anew guard time #2 is started at the beginning
`of the new computation. When the guard time #2 expires, the
`node enters the cross-connection phase.
`A description will now be given of how the physical
`topology table and the logical topology table maintained by
`each node are updated.
`As has been described, the physical topology table and the
`logical topology table maintained by the nodes must have
`20 the common content. It is also necessary for the tables to
`reflect a secondary failure promptly. The physical topology
`is updated when the system is changed or a failure has
`occurred. This means that the physical topology is updated
`relatively infrequently. In contrast, the frequency that the
`25 logical topology is updated is higher than that of the physical
`topology. For instance, the logical topology must be updated
`whenever the path establishments are changed as requested
`by customers. Each node executes the process for updating
`the physical topology and the logical topology autono-
`30 mously. The physical topology table and the logical topol(cid:173)
`ogy table relating to the network maintained in each node are
`communicated from a node to all the other nodes in the
`network either periodically or at random intervals. In this
`way, the nodes can update the respective topology tables
`autonomously even when the OS issues an instruction that
`forces a change in the path establishments.
`A description of the topology updating process will now
`be given using the logical topology as an example. FIGS. 4A
`and 4B show the process for updating the logical topology.
`40 Referring to FIG. 4A, the original working path goes from
`node A to node C through node B. To reassign the original
`path passing through node D instead of node B, the OS sends
`control messages to corresponding nodes A-D to notify
`them of the change. To update the logical topology table in
`45 each node after this path change, network nodes communi(cid:173)
`cate with each other as shown in FIG. 4B. Asimilar process
`occurs in updating the physical topology table. The OS is not
`participating in the updating process.
`If the entirety of the topology tables that nodes A-D
`50 maintain is to be confirmed by message exchanges between
`the nodes via the network, the information passed in the
`network amounts to an extraordinary volume. Accordingly,
`only the checksum (for example, the CRC checksum) of the
`physical topology table and the logical topology is trans-
`55 mitted instead of the whole table. Thereupon, nodes A-D
`make comparisons of the checksum transmitted. If the
`checksums are different from those received by other nodes,
`the node will then have to communicate with other nodes so
`that the same topology tables are maintained in the nodes.
`A description will now be given of how the speed of the
`topology computation can be increased. As has been
`described, the topology computation is executed in the
`computation phase using a known algorithm adopted to
`search for the shortest path. Each node executes the com(cid:173)
`putation using the physical topology table, the logical topol(cid:173)
`ogy table and the alarm message received, according to the
`same algorithm.
`
`Ex.1010
`CISCO SYSTEMS, INC. / Page 13 of 19
`
`

`

`US 6,430,150 Bl
`
`10
`
`20
`
`7
`It is possible for each node to execute topology compu(cid:173)
`tation adapted for different typical failure scenarios such as
`those involving a single link failure and a single node
`failure, before an actual failure occurs, using the physical
`topology table and the logical topology table maintained in
`each node. This computation (pre-computation) is done
`autonomously and the result thereof is stored in a predeter(cid:173)
`mined part of the node. In this way, it is possible to restore
`services in the event of a typical failure without executing
`the computation. It is advisable to provide a guard time in
`this case, too. However, the guard time in this case may be
`shorter than when the pre-computation is not carried out.
`A description will now be given of selection of the
`restoration method depending on the condition of a failure.
`Three types of alternate path selection may be employed: the 15
`line restoration method; the path restoration method; and the
`2-hop restoration method. It is preferable that a restoration
`method most suitable for the condition of the failure be
`selected.
`FIG. SA shows the line restoration method and the path
`restoration method, and FIG. SB shows the 2-hop restoration
`method. Referring to FIG. SA, when a failure occurs
`between nodes S and 6, a path connecting nodes 6, 2, 3 and
`S and bypassing a failed link connecting nodes S and 6 at its
`ends is set according to the line restoration. The same failure 25
`as above is processed according to the path restoration such
`that an alternate path connecting nodes 1, 2, 3 and 4 is set
`in place of the path on the failed link, that is, the path
`connecting nodes 1, 6, and 4. Referring to FIG. SB, a failure
`indicated by X and occurring in node 3 is processed by the 30
`2-hop restoration method such that an alternate path is set
`between nodes 2 and 4 adjacent to node 3.
`The line restoration method provides a faster restoration
`from a link failure than the path restoration. However, the
`line restoration cannot handle node failures. While the path
`restoration method can handle node failures, it takes longer
`to restore with the path restoration method than with the line
`restoration method. The 2-hop restoration method is a high(cid:173)
`speed restoration method that includes features of these
`restoration methods and can handle node failures. However,
`the 2-hop restoration method cannot handle a plurality of
`successive failures. One of the above-described restoration
`schemes is used depending on the type of failure that has
`occurred.
`FIG. 6 shows a node having the construction that realizes
`the restoration schemes described above. The node shown is
`connected to an STM or ATM network for transporting
`audio and image data, and to a maintenance message trans(cid:173)
`mission line 34 for transmitting control messages and alarm 50
`messages from the OS.
`The node shown in FIG. 6 comprises an alarm message
`detecting part 10, a failure type determining part 12, an
`alternate path computing part 14, an alternate path cross(cid:173)
`connecting part 16, a cross-connection confi