EXHIBIT A

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 1 of 35
(19) United States 

US 2003OO63613A1 

(12) Patent Application Publication (10) Pub. No.: US 2003/0063613 A1 

Carpini et al. (43) Pub. Date: Apr. 3, 2003 

(54) LABELSWITCHED COMMUNICATION 

NETWORK AND SYSTEMAND METHOD 

FOR PATH RESTORATION 

(76) Inventors: Walter Joseph Carpini, Stittsville 

(CA); Barry Ding Ken Mark, Kanata 

(CA); Peter Steven Pieda, Kanata (CA) 

Correspondence Address: 

SMART & BIGGAR 

P.O. BOX 2999, STATION D 

55 METCALFE STREET, SUITE 900 

OTTAWA, ON K1P5Y6 (CA) 

(21) Appl. No.: 09/964,766 

22) Filled CC Sep. ep. Z85, 28, 2001 

Publication Classification 

(51) Int. Cl." ........................... H04L 12/28; H04L 12/56 

(52) U.S. Cl. ............................................ 370/401; 370/216 

(57) ABSTRACT 

A communication network is provided which includes a 

primary label Switched path having a plurality of Switching 

routers. The communication network includes a Secondary 

label Switched path which extends from a Selected primary 

path Switching router, bypasses a Section of the primary path 

and rejoins the primary path at a position downstream of the 

Selected Switching router. The Selected Switching router is 

conditioned to re-route data intended for transmission on the 

primary path, onto the Secondary communication path in 

response to a fault on the Section of the primary path which 

is bypassed by the Secondary path to restore data transmis SO. 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 2 of 35
Patent Application Publication Apr. 3, 2003 Sheet 1 of 15 US 2003/0063613 A1 

FIG. 1 23 

FIG. 3 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 3 of 35
Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 4 of 35
LL 180d 'GQ dWMSZ0-Z0ZdST // IHOd 'G0 dWMSZU–80ZdST 

Z4-107dST | 70-8qST) 

US 2003/0063613 A1 

#7 “?IH 

Patent Application Publication 

s D 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 5 of 35
Patent Application Publication Apr. 3, 2003 Sheet 4 of 15 US 2003/0063613 A1 

FIG.SB 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 6 of 35
Patent Application Publication Apr. 3, 2003 Sheet 5 of 15 US 2003/0063613 A1 

FIG. 6 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 7 of 35
Patent Application Publication Apr. 3, 2003 Sheet 6 of 15 US 2003/0063613 A1 

DESTINATION 

SEGMENT 1 

SEGMENT 2 

FG. 7 

SOURCE 217 ? 

SEGMENT 1 DESTINATION 

SEGMENT 2 

FG. 8 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 8 of 35
Patent Application Publication Apr. 3, 2003 Sheet 7 of 15 US 2003/0063613 A1 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 9 of 35
Patent Application Publication Apr. 3, 2003 Sheet 8 of 15 US 2003/0063613 A1 

FIG. 10A 

FIG 10B 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 10 of 35
Patent Application Publication Apr. 3, 2003 Sheet 9 of 15 US 2003/0063613 A1 

FIG. 11 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 11 of 35
Patent Application Publication Apr. 3, 2003 Sheet 10 of 15 US 2003/0063613 A1 

6O1 621 

F.G. 12 

623 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 12 of 35
Patent Application Publication Apr. 3, 2003 Sheet 11 of 15 US 2003/0063613 A1 

FIG. 13 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 13 of 35
Patent Application Publication Apr. 3, 2003 Sheet 12 of 15 US 2003/0063613 A1 

FIG. 14B 

PRIMARY PATH a NODE WINDOW 

SECONDARY PATH ------------- MAGINARY LINKS 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 14 of 35
Patent Application Publication Apr. 3, 2003 Sheet 13 of 15 US 2003/0063613 A1 

FIG. 14C 

F.G. 14D 

 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 15 of 35
Patent Application Publication Apr. 3, 2003 Sheet 14 of 15 US 2003/0063613 A1 

F.G. 14F 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 16 of 35
Patent Application Publication Apr. 3, 2003 Sheet 15 of 15 US 2003/0063613 A1 

725 

FIG. 14G 

 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 17 of 35
US 2003/OO63613 A1 

LABEL, SWITCHED COMMUNICATION 

NETWORK AND SYSTEMAND METHOD FOR 

PATH RESTORATION 

FIELD OF THE INVENTION 

0001. The present invention relates to a label Switched 

communication network, and in particular to a System and 

method for restoring communications on Such a network in 

the event of a fault or failure condition. 

BACKGROUND OF THE INVENTION 

0002. A typical communication network comprises a 

number of nodes interconnected by communication links 

and forms communication paths between different nodes on 

the network. Communication signals are routed over the 

network from a Source node to a predefined destination node 

over a path which may include a number of nodes and linkS. 

Information defining the particular path to be taken and the 

destination may be carried with the data, for example in a 

packet header which is read at each node and controls a 

router at each node to direct the data along the next appro priate communication link of the Specified path. This method 

of data transmission may be referred to as tag or label 

switching of which asynchronous transfer mode (ATM) is a 

well-known example and another is multi-protocol label 

switching (MPLS) which has been proposed more recently. 

0003) A typical requirement of a customer when request 

ing a connection between two nodes in a communication 

network is the provision of a protection or restoration 

Scheme which restores communication in the event of a fault 

or failure in the path carrying the data traffic. In one Such 

protection Scheme, an indication of a fault or failure in the 

communication path is transmitted back to the Source node 

of that path which then discovers an alternative path and 

re-routes the data over that alternative path to the destination 

node. The maximum time allowed to restore a connection 

may be a requirement specified by a standard by the ITU. 

For example, over a long-haul optical network, the ITU 

Standard Specifies a maximum of 10 msec to detect an error 

and a maximum of 50 msec to recover from the error. While 

this may be achievable over a path with relatively few nodes, 

the time needed to recover from a failed connection signifi 

cantly increases with the number of nodes. Therefore, in 

larger metropolitan networks with their mesh-like topolo 

gies, the required restoration times expected from a network 

connection becomes increasingly harder to achieve. 

SUMMARY OF THE INVENTION 

0004. According to one aspect of the present invention, 

there is provided a communication network including a first 

communication path having a plurality of Switching routers, 

a Second communication path having at least one commu 

nication path element different from the first communication 

path and extending from a predetermined one of the Switch 

ing routers to a position on the first communication path located at a distance from the predetermined Switching 

router of less than the length of the first communication path, wherein the predetermined Switching router includes output 

means for outputting data with a label for routing data along 

one of the first and Second communication paths, and routing 

means responsive to a fault in the transmission capability of 

the first communication path between the predetermined 

Apr. 3, 2003 

Switching router and the position for routing data received 

by the predetermined Switching router for transmission 

along the first communication path, along the Second com 

munication path. 

0005 Advantageously, in this arrangement, the commu 

nication network includes a Switching router which is 

responsive to the occurrence of a fault on part of the first 

communication path to route data for transmission over the 

first communication path, along a Second communication 

path which bypasses the part of the first communication path for which the Switching router is responsible, thereby 

bypassing the fault and restoring transmission of data traffic 

to its intended, destination Switching router on the first 

communication path. Advantageously, this restoration path configuration is Scaleable, Since the Switching router is only 

responsible for managing the restoration of data transmis 

Sion over a part or Section of the first communication path. 

Furthermore, in this configuration, the alternative or resto 

ration path which is traditionally required to bypass as many resources between the Source and destination nodes of the 

primary or working path as possible, need only bypass part 

of the primary or working path and therefore fewer 

resources may be required for the Secondary path. 

0006. In one embodiment, the selected Switching router 

includes means for establishing the Second communication 

path. This embodiment is particularly advantageous in the 

case of restoration, where a Secondary path is established 

after the occurrence of a fault on the first communication 

path. In this case, the Switching router need only establish a 

secondary path which bypasses the section of the first 

communication path affected by the fault, and therefore the 

alternative path may be determined from only a Section of 

the whole network topology, which is likely to be consid 

erably faster than determining an alternative path from the 

Source to the destination node involving the whole network 

topology. 

0007. In one embodiment, the selected Switching router 

may be responsive to a direct indication of a fault condition 

on the first communication path to re-route data on the 

Second communication path. Advantageously, Since the 

Selected Switching router is responsible for restoring data 

transmission over part of the primary communication path, 

a signal indicating the occurrence of a fault need only 

propagate over that Section of the first communication path 

for which the Selected Switching router is responsible, and 

therefore propagates through fewer resources of the first 

communication path, each of which has an associated propa gation delay, and therefore the fault signalling time and time 

to restore data transmission can be considerably reduced. 

0008. In one embodiment, the selected Switching router is 

a Switching router intermediate between the Source and 

destination nodes on the first communication path. In 

another embodiment, the predetermined Switching router 

may comprise the Source node of the primary communica 

tion path. 

0009. In another embodiment, the first communication 

path includes a plurality of Switching routers, each having 

routing means responsive to a fault in the transmission 

capability of the first communication path to route data onto 

a respective Second communication path. 

0010. According to another aspect of the present inven 

tion, there is provided a method of conditioning a commu 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 18 of 35
US 2003/OO63613 A1 

nication network for restoring data transmission between a 

first node and a Second node of the network, comprising the 

Steps of Selecting a Switching router on a first communica 

tion path between the first and second node which is 

connected to a Second communication path which adjoins 

the first communication path at a position downstream of the 

Selected Switching router, conditioning the Switching router 

to route data onto one of the first and Second communication 

paths in response to a label associated with the data and to 

respond to a fault in the transmission capability of Said first 

communication path between the Switching router and the 

position to route data intended for transmission along Said 

first communication path, onto Said Second communication 

path. 

0.011) Advantageously, in this configuration, Since the 

intermediate Switching router is responsible for managing 

path restoration over a Section of the first communication 

path, the Secondary path can be Selected to bypass only that 

section of the first communication path for which the 

intermediate Switching router is responsible, and therefore 

requires fewer resources than are required in prior art 

restoration Schemes in which for protection, the Secondary 

path extends between the Source and destination nodes. In 

the case of restoration, this configuration allows a Suitable 

Secondary path, which bypasses the fault, to be discovered 

more quickly, Since fewer resources are involved. 

0012 One embodiment further comprises the step of 

conditioning the Switching router to detect the presence of a 

fault between the Switching router and the position at which 

the Secondary path joins the primary path, and to respond to 

the fault by re-directing data intended for transmission along the primary path onto the Secondary path. This arrangement 

allows faster fault detection and path restoration not possible in prior art restoration Schemes, Since the presence of a fault 

need not be transmitted all the way back to the Source node 

before the intermediate Switching router takes action to 

restore data transmission. 

0013. According to another aspect of the present inven 

tion, there is provided a method of restoring communication 

between an input node and an output node due to failure of 

a first communication path between the nodes, comprising 

the Steps of indicating a fault condition to a Switching router 

on the first path positioned between the location of the fault 

and the input node, re-routing data received at the Switching 

router intended for transmission over the first communica 

tion path along a Second path and returning the data to the 

first path at a position downstream of the fault location. 

0.014. According to another aspect of the present inven 

tion, there is provided a method of restoring communication 

between an input node and an output node in a network due 

to a fault in a first communication path between the nodes, comprising the Steps of indicating a fault condition on the 

first path to the input node, re-routing data at the input node 

intended for transmission over the first communication path along a Second communication path and returning the data 

to the first communication path at a position between the 

fault and the output node. 

0.015 According to another aspect of the present inven 

tion, there is provided a method of evaluating a node for 

redirecting data from a first communication path, having a 

Source node and a destination node, along a Second com 

munication path, comprising the Steps of: Selecting a test 

Apr. 3, 2003 

node on the first communication path between the Source 

node and the destination node, Selecting a test node on the 

Second communication path, determining the value of a 

parameter of a test path between the test nodes, and evalu 

ating the test node on the first path for re-directing data to the 

Second path based on the determined value of the parameter. 

0016. According to another aspect of the present inven 

tion, there is provided a method of Selecting an alternative 

path for carrying data intended for transmission along a 

communication path between a Source node and a destina 

tion node, comprising Selecting a plurality of alternate paths 

connected between an intermediate node of the communi 

cation path and the destination node, and Selecting from the 

plurality of alternate paths, the path which shares the mini 

mum number of links with the communication path between 

the intermediate node and Said destination node. 

BRIEF DESCRIPTION OF THE DRAWINGS 

0017 Examples of embodiments of the present invention 

will now be described with reference to the drawings, in 

which: 

0018 FIG. 1 shows a communication network according 

to a first embodiment of the present invention; 

0019 FIG. 2 shows a schematic diagram of Switching 

router in accordance with an embodiment of the present 

invention; 

0020 FIG. 3 shows a communication network in accor 

dance with another embodiment of the present invention; 

0021 FIG. 4 shows a schematic diagram of a Switching 

router in accordance with another embodiment of the present 

invention; 

0022 FIG. 5A shows a communication network in 

accordance with another embodiment of the present inven 

tion; 

0023 FIG. 5B shows a communication network in accor 

dance with another embodiment of the present invention; 

0024 FIG. 6 shows a communication network in accor 

dance with another embodiment of the present invention; 

0025 FIG. 7 shows a communication network in accor 

dance with another embodiment of the present invention; 

0026 FIG. 8 shows a communication network in accor 

dance with another embodiment of the present invention; 

0027 FIG. 9 shows a communication network in accor 

dance with another embodiment of the present invention; 

0028 FIG. 10A shows a communication network in 

accordance with another embodiment of the present inven 

tion; 

0029 FIG. 10B shows a communication network in 

accordance with another embodiment of the present inven 

tion; 

0030 FIG. 11 shows a communication network in accor 

dance with another embodiment of the present invention; 

0031 FIG. 12 shows a communication network in accor 

dance with another embodiment of the present invention; 

0032 FIG. 13 shows an example of a communication 

network having a bridge link, and 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 19 of 35
US 2003/OO63613 A1 

0033 FIGS. 14A to 14G show an example of a commu 

nication network to which an embodiment of a method of 

Selecting a Segment Switching router is applied. 

DETAILED DESCRIPTION OF EMBODIMENTS 

0034. The applicant's U.S. Provisional Patent Applica 

tion Serial No. 60/290,633 filed on May 15, 2001 and 

entitled Method and Apparatus for Controlling Allocation 

and Stacking or MPLS Labels in Telecommunications Net 

WorkS is incorporated herein by reference. 

0.035 Referring to FIG. 1, a communication network, 

generally shown at 1, comprises a first communication path 

3 which includes a first switching router 5, a second switch 

ing router 7 downstream of the first Switching router and a 

third Switching router 9 downstream of the second Switching 

router 7. 

0.036 The first communication path further includes a 

plurality of intermediate Switching routers 2, 4, 6, and 

communication links 11, 13, 15, 17, 19. 

0037. The communication network 1 further comprises a 

Second communication path 21 extending between the Sec 

ond and third switching routers 7.9, and which includes an 

intermediate Switching router 23 and communication links 

25, 27. 

0038 A first label switched path (LSP) is defined over the 

first communication path 3, and whose length is defined 

between a Source node (e.g. ingress label edge router (LER)) 

and a destination node (e.g. egreSS LER). The first Switching 

router 5 may comprise the Source node, or an intermediate 

node of the label Switched path, and the third Switching 

router 9 may comprise the destination node of the label 

Switched path or an intermediate node of the label Switched 

path. Under normal operation, data Specified for transmis 

sion on the first label Switched path is directed from the first 

Switching router 5 onto the first communication path 3 with 

a forwarding label defining the first LSP and is directed by Successive Switching along first communication path according to labels defining the first LSP. 

0.039 The second communication path 21 provides an 

alternative path for carrying data between the Second and 

third Switching routers 7, 9, and may be used to carry data 

traffic intended for transmission along the first communica 

tion path if the Section of the first communication path 

between the first and Second Switching routerS fails. A label 

Switched path is defined over the secondary path 21 for the 

purpose of re-routing data intended for transmission on the 

first communication path, onto the Second communication 

path. For protection, the LSP on the Second communication 

path may be established before the occurrence of a fault on 

the primary path 3, and for restoration, the LSP on second 

communication path may be established after the occurrence 

of a fault on the primary path. In either case, the Secondary 

path LSP may be established by the second Switching router 

7 or by another Switching router, for example another 

Switching router on the primary communication path Such as 

the ingress LER. 

0040 Advantageously, for the purpose of protection or 

restoration, the first or primary communication path is 

Subdivided into Sections So that an alternative path need only circumvent a Section of the primary path rather than the 

entire primary path in the case of prior art restoration 

Apr. 3, 2003 

Schemes. An alternate path may therefore be discovered and 

established more easily and quickly as it may involve fewer 

resources and may be based on a reduced topology of the 

entire network. This aspect of the Scheme is particularly 

beneficial for restoration, where the alternative path must be 

discovered and established as quickly as possible after the occurrence of a fault. 

0041. In one embodiment, the second Switching router 7 

may be adapted to discover and establish an alternative path 

between itself and the third Switching router 9. The benefit 

of this feature is two fold. Firstly, the resources required to 

discover, establish and Switch data onto an alternative LSP 

which circumvents that Section of the primary path for 

which the Second Switching router is responsible, are main 

tained at and by the Second Switching router rather than the 

Source node, So that fewer resources are required at the 

Source node to provide protection or restoration of the 

primary path. Secondly, Since the Second Switching router is 

closer to the location of a fault on the Second Section of the 

primary path, than the Source node, the occurrence of Such 

a fault may be notified to the second switching router 7 

Sooner than to the Source node, in which case, the Second 

Switching router may be adapted to respond to Such a 

notification to establish and Switch data to an alternative 

path, there by reducing the restoration time in comparison to 

a Scheme in which restoration is initiated only after the occurrence of a fault has been notified to the Source node. 

0042 Preferably, the second Switching router is adapted 

to Switch data from the primary path to the Secondary path 

in response to the occurrence a fault on the Section of the 

primary path for which the Second Switching router 7 is 

responsible. The communication network may be arranged 

Such that a fault is detected by a Switching router in close 

proximity to the fault, and a fault indication is transmitted by the most direct route to the Switching router responsible for 

the Section of the primary path in which the fault occurred. 

For example, referring again to FIG. 1, a fault “F” occurring 

on the primary path between the intermediate Switching 

routerS 4 and 6 may be detected by the upstream interme 

diate Switching router 4 and notified to the immediately 

adjacent Second Switching router 7 over communication link 

15. The second Switching router 7 may itself include a fault 

detector for detecting a fault on the Second Section of the primary path. 

0043 FIG. 2 shows a Switching router according to an 

embodiment of the present invention, and which may be 

incorporated as the Second Switching router 7 in the com 

munication network of FIG. 1. Referring to FIG. 2, the 

Switching router 7 comprises a routing device 51 having an 

input port 53 and first and second output ports 55, 57. The 

input port is connected to a communication link 13 of the 

first communication path, the first output port 55 is con 

nected to a communication link 15 of the first communica 

tion path and the Second output port 57 is connected to a link 

25 of the Second communication path. The Switching router 

7 further includes a memory 59 associated with the routing device 51 for Storing one or more incoming label maps 

(ILM) or forwarding tables 61, 63. 

0044) In the present embodiment, a first label Switch path 

LSP1 is established on the first communication path between 

the first and third switching routers 5, 9 shown in FIG. 1. 

One or more other label Switched paths LSP2, LSP3 may 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 20 of 35
US 2003/OO63613 A1 

also be established over the first communication path or a 

different path which is connected to input port 53 of the 

routing device 51 and includes the Second Section of the 

primary path between the Second and third Switching routers 

7.9. The first incoming label map 61 contains instructions 

enabling the routing device to identify data packets associ 

ated with the first LSP, LSP1, intended for transmission on 

the first communication path and to direct those data packets 

onto the next link of 15 of the first communication path. For 

example, as shown in the expanded view of ILM 61, the first 

entry contains the forwarding label a2, which is received by 

and identifies first LSP data packets, and an associated 

operation which causes the routing device to change label 

“a2” to label “a3” and to output the relabelled data packets 

from the first output port 55. The first incoming label map 61 

also contains Second and third entries which include respec tive forwarding labels “b2” and “c2” used to identify data 

packets associated with the second and third LSPs, LSP2, 

LSP3, and associated labelling and forwarding instructions, 

which causes LSP2 data to be relabelled with the next LSP2 

forwarding label “b3” and output from the first output port 

55, and LSP3 data to be relabelled with the next LSP3 

forwarding label “c3' and again, output from the first output 

port 55. 

0.045. To enable the Switching router 7 to redirect data 

received within each of the first, second, and third LSPs 

from the first communication path to the Second communi 

cation path, a Second incoming label map 63 may be 

provided. Referring to the enlarged view of the second ILM 

63, in this example, the first entry contains the forwarding 

label “a2” used to identify incoming LSP1 data, and an 

asSociated instruction which causes LSP1 data packets to be 

relabelled with the first forwarding label “fl' defining a 

secondary LSP 201 on the second communication path and 

to output the relabelled data packets onto the Second com 

munication path from the second output port 57. The second 

entry contains the forwarding label “b2” which identifies 

LSP2 data packets, and an associated instruction which 

causes the Switching router to relabel LSP2 data packets 

with the first forwarding label “gl” of another LSP 202 

established on the Second communication path and output 

the relabelled LSP2 data on to the second communication 

path from the second output port 57. Similarly, the third 

entry contains the forwarding label “c2” identifying LSP3 

data and a corresponding instruction which causes the 

Switching router to relabel the LSP3 data with the first 

forwarding label “h1” of another secondary LSP established 

on the Second communication path, and to output the rela 

belled data on to the Second communication path from the 

second output port 57. 

0046. In the case of protection, each of the secondary 

LSPs, LSP201, 202,203 on the second communication path 

are established prior to the occurrence of a fault on the 

Section of the primary path protected by the Secondary path, 

and the Second incoming label map 63 may also be gener 

ated and stored in the memory 59 together with the first 

incoming label map 61 in advance of a fault on the primary path. 

0047. In the case of restoration, the routing device may be 

adapted to perform certain functions in response to a signal 

indicative of a fault or resulting from a fault on the Section 

of the primary path for which the Switching router is 

responsible. The Switching router may be adapted to respond 

Apr. 3, 2003 

to a fault indication to discover a Suitable Secondary path over which data traffic can be redirected. In one embodi 

ment, the Switching router may be insensitive to the par 

ticular location of the fault on its Section of the primary path and discover a Secondary path which Simply bypasses the 

entire Section for which it is responsible, So that for example 

the Secondary path meets the primary path at the destination 

node or at or beyond the next segment head Switching router. 

In another embodiment, the Switching router may be Sensi 

tive to the location of the fault on the primary path. The 

location of the fault and/or those resources affected by the 

fault may be identified in the fault indication signal or 

another signal. On receipt of the Signal, the Switching router 

discovers a Secondary communication path which bypasses 

the fault and those resources affected by the fault and which 

may rejoin the primary path at a position beyond the fault 

but within the primary path section for which the Switching 

router is responsible. Advantageously, in this embodiment 

the Selection of an alternative path is predicated on the 

particular location of the fault permitting greater flexibility in Selecting an optimal restoration path. 

0048. Once an alternative path has been selected, the 

Switching router may be adapted to establish a Secondary 

LSP over the secondary path for each LSP which is carried 

on the primary communication path. The Switching router 

may be arranged to generate an incoming label map which 

enables the routing device to direct data carried within each 

LSP on the primary path onto a respective secondary LSP on 

the alternative path. The ILM may be generated as a Second 

ILM or may be generated by over writing or otherwise 

modifying the original ILM for directing data over the 

primary communication path. Generation of the Secondary 

path ILM may commence either before, during or after the 

secondary LSPs are established. The Switching router uses 

the secondary path ILM to redirect data from the primary path onto the Secondary path, thereby restoring data trans 

mission around the failed resource or resources of the 

primary path. 

0049. Where appropriate, the functions of the Switching 

router described above may be implemented either in hard 

ware or in Software, or a combination of both. 

0050 FIG. 3 shows a communication network according 

to another embodiment of the present invention. This com 

munication network is similar to that shown in FIG. 1 and 

like parts are designated by the same reference numerals. 

Referring to FIG. 3, the network includes a first communi 

cation path 3 which includes first, second and third Switch 

ing routers 5, 7 and 9. The network further includes a second 

communication path 21 which extends from the Second 

Switching router 7 and includes an intermediate Switching 

router 23. The main difference between this embodiment and 

that shown in FIG. 1 is that the second communication path 

21 joins the first communication path at a point which is 

intermediate between the Second and third Switching routers 

7,9. In this particular embodiment, the second section 10 of 

the first communication path between the Second and third 

Switching routers 7, 9 includes an additional Switching 

router 29 to which the secondary communication path 21 is 

connected. In this embodiment, the Second Switching router 

7 is responsible for redirecting data traffic intended for the 

primary path onto the Secondary path in response to a fault 

on the section 14 of the primary path between itself and the 

additional Switching router 29. The additional Switching 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 21 of 35
US 2003/OO63613 A1 

router 29 is adapted to recognize primary-path-fault-di 

verted data and to route the data from the Secondary path back onto the primary path. 

0051. This embodiment illustrates an example of an 

implementation of a Secondary communication path which 

functions to divert data around a fault and back onto the first 

communication path for further transmission to the destina 

tion node of the primary path, in contrast to a Secondary path 

which is extended to carry data to the destination node 

without further transmission along the first communication 

path. The embodiment shown in FIG. 3 may be imple 

mented where it is convenient to return data traffic, where 

possible, from the Secondary path to resume transmission 

over the primary path, or where is it is not possible or 

convenient to extend the Secondary path to rejoin the pri 

mary path at a position downstream of the additional Switch 

ing router 29. 

0052) To redirect data from a primary LSP on the first 

communication path, a Secondary LSP may be established 

on the Second communication path 21 between the Segment head Switching router 7 and the additional Switching router 

29. The secondary LSP may terminate at the additional 

Switching router 29, and the additional Switching router 29 

may be conditioned to transfer the diverted data back onto 

the next segment of its primary LSP on the first communi 

cation path. In this case, the additional Switching router 29 

may be adapted to label diverted data received from the 

secondary LSP with the same forwarding label had the data 

been received from the corresponding primary LSP. 

0053. In another embodiment, the secondary LSP may 

extend beyond the additional Switching router 29 over part 

of the remaining Section of the primary communication path 

or over the entire remaining Section of the primary path to 

the destination node. A plurality of secondary LSPs may be 

established on the Secondary communication path 21 and 

each may terminate at a different location on the primary communication path. The Segment head Switching router 7 

may comprise any of the embodiments of the Segment head 

Switching router described above in connection with FIG. 1 

and may be adapted to protect or restore data traffic or a 

combination of both, for example for different primary 

LSPS. 

0.054 An example of an embodiment of the additional or 

intermediate Switching router which Serves to merge 

diverted data back onto the primary path will now be 

described with reference to FIG. 4. Referring to FIG. 4, the 

Switching router 29 comprises a routing device 71 having 

first and second input ports 73, 75 and an output port 77. The 

first input port 73 is connected to communication link 17 of 

the first communication path 3, the second input port 75 is 

connected to the Second communication link 27 of the 

Second communication path 21, and the output port 77 is 

connected to the downstream communication link 18 of the 

primary communication path. The Switching router 29 fur 

ther includes a memory 79 for Storing one or more incoming 

label maps or forwarding tables 81, 83. The incoming label 

map(s) contain instructions for enabling the routing device 

71 to forward data specified for transmission within a 

particular label Switched path to forward the data over the 

next link of the specified LSP. In the present example, a 

plurality of primary LSPs are established over the first 

communication path and a Secondary LSP corresponding to 

Apr. 3, 2003 

each primary LSP is established on the Secondary commu 

nication path, each Secondary LSP terminating at the addi 

tional Switching router 29. Referring to the expanded view 

of the first ILM 81, the ILM contains an entry corresponding 

to each primary LSP including a forwarding instruction. In 

particular, the first entry includes a forwarding label “a4” 

which identifies data associated with a primary path LSP. 

LSP 1. The first entry further includes a forwarding instruc 

tion which causes the routing device 71 to relabel LSP1 data 

with the forwarding label “as” and to output the data from 

the output port 77 onto the next link 18 of the primary 

communication path. Similarly, the Second and third entries 

contain forwarding labels “b4” and “c4” which identify data 

associated with other primary LSPs, LSP2 and LSP3, and an 

asSociated forwarding instruction which causes the data to 

be relabelled with the next appropriate forwarding label and 

output onto the next link 18 of the primary path from the 

output port 77. 

0055. The first incoming label map 81 also includes 

entries for enabling the routing device to direct data which 

is diverted onto the Secondary communication path back 

onto the primary communication path. In the present 

embodiment, a secondary LSP is established for each pri 

mary LSP. Thus, secondary LSPs 201,202 and 203 serve as 

secondary LSPs for primary LSPS 1, 2 and 3, respectively. 

The fourth entry in the first ILM 81 includes a forwarding 

label “f2' which identifies data associated with the second 

ary LSP 201, and an associated instruction which causes the 

routing device to relabel data having label “f2' with the 

LSP1 forwarding label “aS” and to output the data from 

output port 77 onto the next link 18 of the primary com 

munication path. In this way, data originally intended for 

transmission within the primary LSP, LSP1, which is 

diverted onto the corresponding secondary LSP 201, is 

transferred back onto the primary LSP, LSP1 for continued 

transmission along the primary communication path. Simi 

larly, the fifth and sixth entries contained within the first 

ILM 81 include forwarding labels “g2' and “h2" which 

identify data associated with the other secondary LSPs, 202, 

203, and an associated instruction which causes the routing device to relabel the secondary LSP data with the appropri 

ate next forwarding label associated with a respective pri 

mary LSP, LSP2, LSP3 and to output the data from the 

output port 77 onto the next link 18 of the primary com 

munication path. In this way, the Switching router 29 returns 

diverted data associated with each primary LSP back onto a 

respective primary LSP. 

0056. In another embodiment, the forwarding instruc 

tions for each secondary LSP may be contained within a 

separate ILM 83 rather than the same ILM 81 which 

contains forwarding instructions for each primary LSP. This 

arrangement may be implemented where the Second com 

munication path is connected to a port associated with a 

different routing device or interface within the additional 

Switching router 29. 

0057 FIG. 5A shows a communication network accord 

ing to another embodiment of the present invention. This 

embodiment is an extension of the embodiment shown in 

FIGS. 1 and 3 and like parts are designated by the same 

reference numerals. 

0.058 Referring to FIG.5A, the network 1 includes a first 

communication path 3 which includes first, Second and third 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 22 of 35
US 2003/OO63613 A1 

Switching routers 5, 7 and 9 and an additional Switching 

router 29, and intermediate switching routers 2, 4, 6. The 

network further includes a Second communication path 21 

extending from the Second Switching router 7 to the addi 

tional Switching router 29 and which includes an interme 

diate switching router 23. The network also includes a third 

communication path 31 which extends from the additional 

Switching router 29 to the third Switching router 9, and 

which includes an intermediate switching router 33. 

0059. The second Switching router 7 functions to detect 

or otherwise respond to a fault or failure in the transmission 

capability of the Segment 14 of the first communication path 

3 between the second Switching router 7 and the additional 

Switching router 29, and in the event of a fault or failure 

condition, to re-route data intended for transmission along the Segment 14 of the primary path between the Second 

Switching router 7 and the additional Switching router 29, 

along the Second communication path 21, thereby restoring 

data transmission between the Second and additional Switch 

ing routers 7, 29. The second Switching router 7 may 

function in the Same way as any of the embodiments 

described above in connection with FIGS. 1, 2 and 3. 

0060 Referring again to FIG. 5A, the additional Switch 

ing router 29 is conditioned to respond to a fault or failure 

condition in the transmission capability of the Segment 16 of 

the first communication path between the additional Switch 

ing router 29 and the third Switching router 9 and may include a fault detector or otherwise be adapted to respond 

to a Signal resulting from a fault on this Segment 16. The 

additional Switching router 29 further includes re-routing 

means responsive to the fault condition for re-routing data 

intended for transmission over the segment 16 of the first 

communication path, along the third communication path 

31. Thus, in this embodiment, the second Switching router 7 

monitorS faults and manages path restoration over the Seg 

ment 14 of the first communication path between the second 

Switching router 7 and the additional Switching router 29, 

and the additional Switching router 29 monitors the Segment 

16 between the additional Switching router 29 and the third 

Switching router 9 and manages path communication resto 

ration in the event of a fault on that Segment. 

0061. In one embodiment, the flow of data along each of 

the Second and third communication paths, may be con 

trolled according to a predetermined labelling System, for 

example, as described above, in connection with any of 

FIGS. 1 to 4. In one embodiment, one or more respective 

secondary LSP’s may be established on each of the second 

and third communication paths. The labelling System could 

be established either dynamically in response to a fault 

condition, i.e. for restoration, or the Second and third com 

munication paths could be established prior to detecting a 

fault i.e. for protection, to assist in minimizing the data 

transmission recovery time. 

0.062. In the event of a fault condition on the segment 16 

between the additional Switching router 29 and the third 

Switching router 9, data transmission may be restored by 

invoking the third communication path as follows. On 

receipt of data by the additional Switching router 29 which 

is being transmitted over the previous Segment 14 of the first 

communication path 3, the additional Switching router 29 

reads the label associated with the data, assigns a new label 

to the data and routes the data onto the first link 35 of the 

Apr. 3, 2003 

third communication path 31 to the intermediate Switching 

router 33. The label assigned to the data by the additional 

Switching router 29 is previously established by the inter 

mediate router 33 to cause the intermediate Switching router 

33 to route that data over the next link 37 of the third 

communication path 31 to the third Switching router 9. 

0063. In the event of a simultaneous fault condition on 

both segments 14 and 16 of the first communication path, the 

additional Switching router 29 may be further adapted to 

re-route data received from the Second communication path 21 along the third communication path 31. In one Such 

embodiment, the additional Switching router 29 is arranged to recognize, according to the predefined labelling System 

established for the Second communication path, data 

received over the Second communication path intended for 

further transmission over the first communication path, and 

will route data back onto the first communication path 

segment 16 if it can. However, in the event of a fault 

condition on Segment 16, the additional Switching router 29 

recognizes the label which indicates that data received over 

the Second communication path is to be returned to the first 

communication path and assigns to the data an appropriate 

label established for the third communication path and 

re-routes the data over the first link 35 of the third commu 

nication path 31. This functionality may be implemented by 

configuring the Switching router 29 described above and 

shown in FIG. 4, with a specific ILM containing appropriate 

forwarding labels of each secondary LSP associated with 

each primary LSP and a corresponding labelling and for 

warding instruction which causes the additional Switching 

router 29 to route the Specified data over a corresponding 

LSP established on the third communication path. 

0064. The embodiment described above in conjunction with FIG. 5A illustrates an example of a transmission 

recovery Scheme where the primary path includes a number 

of Segments whose boundaries extend from one Segment 

head to the Segment head responsible for the next segment. 

0065 Referring to FIG. 5B, in an alternative embodi 

ment of the communication network of FIG. 6, the second 

ary communication path 21" may rejoin the primary path 3 

at a position between the additional Switching router 29 and 

the third switching router 9. In this example, the second 

communication path 21' rejoins the primary communication 

at a primary path intermediate Switching router 6 between 

the additional and third Switching routers 29, 9. 

0066. In this embodiment, the second Switching router 7 

may serve as the Segment head node responsible for direct 

ing data over the Second communication path 21" in response 

to a fault in the Section 14 of the primary communication 

path 3 between the Second and additional Switching routers 

7, 29. Similarly, the additional Switching router 29 may be 

adapted to Serve as the Segment head node responsible for 

re-directing data traffic over the third communication path 

31 in response to a fault in the section 16 of the primary path 

between the additional Switching router 29 and the third 

Switching router 9. In this case, the Second and additional 

Switching routerS may function in a similar manner to the 

second and additional Switching routers 7, 29 of the embodi 

ment shown in FIG. 5A. 

0067. In another embodiment, the segment of the primary path for which the second Switching router 7 is responsible 

may be extended to include a portion of the next segment 16. 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 23 of 35
US 2003/OO63613 A1 

For example, as shown in FIG. 5B, the second Switching 

router may be adapted to re-direct data traffic in response to 

a fault on the extended section 20 of the primary commu 

nication path between itself and the position at which the 

Second communication path 21' rejoins the primary path, 

which in this example is at the intermediate Switching router 

6. Advantageously, Since the Segment head 29 responsible 

for the next segment 16, and the adjacent communication 

link 18 are included within the segment for which the second 

Switching router 7 is responsible, this configuration also 

provides protection or restoration against failure of either of 

these two resources and therefore provides a more robust 

protection or restoration Scheme. 

0068 The intermediate Switching router 6 may be con 

ditioned to return data received from the Second communi 

cation path 21, intended for transmission on the primary communication path 3, to the primary path for further 

transmission to the third switching router 9. For example, this functionality may be implemented by configuring the 

intermediate Switching router 6 to function in the Same or 

Similar manner to the embodiment described above in con 

nection with FIG. 4. 

0069. In the event of a simultaneous fault or failure of the 

primary communication path in both Section 14 between the 

second and additional switching routers 7, 29 and in the link 

19 between the intermediate Switching router 6 and the third 

Switching router 9, the intermediate Switching router 6 may 

be adapted to route data received over the Second commu 

nication path back to the intermediate Switching router 29 

which then routes the data over the third communication 

path 31 to the third Switching router 9. This alternative path 

may be established as a label Switched path and may be 

established prior to the occurrence of a fault, i.e. for pro 

tection, or after the occurrence of a fault in the link 19 of the 

primary path between the intermediate and third Switching 

routers 6,9. This alternative LSP may be established by for 

example the intermediate Switching router 6 or by the 

additional Switching router 29. 

0070. In another embodiment, the second Switching 

router 7 may be adapted to detect or otherwise respond to a 

fault condition in the segment 16 between the additional 

Switching router 29 and the third switching router 9 and to 

re-route data received from the first Switching router 5 

intended for transmission along the first communication 

path, along a fourth communication path, defined by the 

intermediate Switching router 23 of the Second communica 

tion path 21", the intermediate Switching router 33 of the 

third communication path and the third switching router 9. 

This embodiment assumes a communication path 42 exists 

between the two intermediate Switching routers 23, 33. This 

embodiment is particularly advantageous in restoring trans 

mission in the event of a fault also being detected in the 

Segment 14 between the Second and additional Switching 

routers 7, 29. 

0071 Any of the embodiments of the communication 

network described above and shown in FIGS. 1 to 5B may include a Secondary communication path between the first 

and Second Switching routers to provide an alternative path 

for data transmission in the event of a failure on the primary communication path between the first and Second Switching 

routers 5, 7. Thus, the first Switching router may be condi 

tioned to function as the Segment head responsible for the 

Apr. 3, 2003 

Section of the primary path between itself and the Second 

Switching router, and to re-route data intended for transmis 

Sion on the primary communication path onto the Secondary 

communication path in response to a fault on that Section. 

An example of a Secondary communication path between 

the first and second Switching routers is shown in FIG. 5A 

and includes intermediate Switching routers 43, 45 and 

communication links 47, 48 and 49. One or more secondary label Switched paths may be established over the secondary 

communication path 41, either before the occurrence of a 

fault on the primary path, i.e. for protection, or in response 

to a fault on the primary path, i.e. for restoration. The first 

Switching router may be adapted to establish one or more 

Secondary LSPS over the Secondary communication path 41 

and may function in the same or Similar manner to the 

Second Switching router described above in connection with 

FG, 2. 

0072 Advantageously, the communication restoration 

Scheme described above in connection with FIGS. 1 to 5B 

is fully Scalable into any size of network as restoration is 

monitored and managed over path Segments rather than over 

an entire network from a single, Source node. Path restora 

tion may be managed per path Segment independently of 

other Segments, or may be managed jointly by two or more 

path Segments. The Secondary path for one or more Seg 

ments of the primary path may rejoin the primary path at the 

Segment head node for the next path Segment, an example of 

which is shown in FIG. 5A, or may rejoin the primary path 

at a position beyond the Segment head node of the next 

primary path segment, as shown in FIG. 5B. 

0073. In embodiments of the present invention, the first 

and Second communication paths may share one or more of 

the same resources e.g. communication links and Switching 

elements. In general, the Second communication path will 

have at least one communication element which is different 

to the first communication path So that the Second commu 

nication path provides an alternative route around the 

unshared component(s) should that all those component(s) 

fail. FIG. 6 shows an example of a communication network 

in which the Secondary communication network in which 

the Secondary communication path shares a number of 

resources with the primary path. 

0074 Referring to FIG. 6, a communication network to 

101 comprises a first communication path 103 having first, 

second and third switching routers 105, 107 and 109 and 

intermediate switching routers 102, 104, 106, 108. The 

second Switching router 107 is responsible for restoring data 

transmission between itself and the third Switching router 

109 in the event of a fault on the Section of 113 of the first 

communication path between the first and Second Switching 

routers 107,109. This section 113 of the first communication 

path includes first, Second and third intermediate Switching 

routers 104,106, 108 and intermediate communication links 

115, 117, 119, 121. The communication network further 

includes a second communication path 123 (shown by a 

dashed line for clarity) which is established between the 

second Switching router 107 and the third intermediate 

Switching router 108, and includes communication link 115 

and intermediate switching routers 104 of the first commu 

nication path, and a separate path 125 between the Second 

and fourth intermediate Switching routers 104, 108, which 

includes an intermediate Switching router 123 and commu 

nication links 131, 133 and 135. 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 24 of 35
US 2003/OO63613 A1 

0075. Using restoration as an example, the second 

Switching router 107 establishes a label switched path over 

the Second communication path 123 in response to a fault F 

between the Second and fourth intermediate Switching rout 

ers 104,108. The secondary LSP is established such that a 

path is discovered which is sufficient to bypass the fault but 

which also uses a number of the same resources as the 

primary communication path. A Secondary LSP which 

shares a number of resources with the first communication 

path may also be established prior to the occurrence of a 

fault, for protection. 

0.076. In another embodiment, the secondary communi 

cation path may be arranged to share as many of the same 

resources with the primary path, as possible. For example, 

referring again to FIG. 6, a Secondary path from the Second 

Switching router 107 may be established to bypass a single 

resource, i.e. the resource affected by the failure, for 

example communication link 119 between the third and 

fourth intermediate Switching routers 106, 108. In this 

embodiment, the secondary path 137 (shown by a dashed 

line for clarity) may include the Second and third interme 

diate Switching routers 104,106, communication links 115, 

117 of the primary path and, for example a single commu 

nication link 139 between the third and fourth intermediate 

Switching routers 106, 108. This secondary communication 

path may be established either before or after the occurrence 

of a fault, i.e. for protection or restoration. The topology of 

the Secondary communication path may be determined by 

the second Switching router 107. The second Switching 

router may establish one or more Secondary LSPS over the 

Secondary communication path. In this embodiment, the 

fourth intermediate switching router 108 functions to direct 

data received either over the primary or Secondary commu 

nication path, onto the primary communication path to the 

third switching router 109. 

0077. In order to achieve the required, short data trans 

mission recovery times, embodiments of the present inven 

tion provide protection or restoration acroSS a path Segment 

rather than across the entire path. A primary, or working path 

is divided into one or more path Segments, and each path 

Segment has a Segment head Switching router which may be 

responsible for establishing an alternative path to the next 

Segment head or to the destination node. A segment head 

node may have knowledge of the topology of the portion of 

the network associated with the portion of the primary path 

for which it is responsible and may also have knowledge of 

the topology of an enlarged portion of the network, for 

example a larger portion or the entire communication net 

work with which the primary path is associated. 

0078. In the case of protection services, preferably, the 

alternative path does not share any risks, for example node 

or link with the primary hops in the path Segment being 

protected. However, the alternative path can share risks with 

other resources in other Segments of the primary path. The 

path Segments can be non-overlapping as illustrated in 

FIGS. 1, 3 and 5A, or overlapping, as shown in FIG. 5B. 

Further examples of non-overlapping and overlapping path 

segments will be described below with reference to FIGS. 

7 and 8. 

0079. In a network having non-overlapping segments, a 

Single Segment head joins two adjacent Segments at a single 

node. Advantageously, this provides robust restoration capa 

Apr. 3, 2003 

bilities for each Segment. However, Since the Segment head 

is shared by both Segments, the Segment head constitutes a 

risk for node failures. Another embodiment of a network 

path divided into non-overlapping Segments is shown in 

FIG. 7. Referring to FIG. 7, a communication network 

generally shown at 201 includes a primary communication 

path 203 having a source node 205 and a destination node 

239 and a plurality of intermediate nodes 207,209,210, 211, 

213, 215. The primary path 203 is divided into a first 

segment 217 and a second segment 219 (shown by the 

dashed lines), and one of the intermediate nodes 211 Serves 

as the Segment head for the Second Segment 219 of the 

primary communication path 203. The source node 205 is 

responsible for restoring data traffic between itself and the 

Segment head node 211 and the intermediate Segment head 

node 211 is responsible for restoring traffic between itself 

and the destination node 239. To protect the first segment 217 of the primary path, preferably a secondary path 221 is 

established between the Source node 205 and the interme 

diate Segment head node 211 which does not share any 

resources with the first segment 217 of the primary path. For 

example, the Secondary communication path may be defined 

by intermediate nodes 223, 225, 227 and 229, and the 

Segment head node 211 of the Second Segment. A Secondary 

path is also established to protect the Second Segment of the 

primary path which also preferably does not share any 

resources of the Second Segment of the primary path, and 

may be defined by intermediate nodes 229, 231, 233 and 

235, and the destination node 239. 

0080. In a network having overlapping segments, the 

previous Segment has at least one node downstream of the 

Segment head of the next segment. In other words, the 

Segment head of the next segment is defined as a node 

upstream of the last node of the previous Segment. An 

example of a network in which the path has overlapping 

segments is shown in FIG. 8. 

0081. The network shown in FIG. 8 is similar to that 

shown in FIG. 7, and the like paths are designated by the 

Same reference numerals. The main difference between this 

communication network and that shown in FIG. 7 is that the 

first Segment 217 of the primary path overlaps the Second 

segment 219 of the primary path 203. The source node 205 

is responsible for restoring traffic in the first Segment 

between itself and the last node 211 in that segment. The 

intermediate node 210 which immediately precedes the last 

node 211 in the first Segment is responsible for path resto 

ration over the second segment 219 between itself and the 

destination node 239. In the event of a failure of the last node 

211 in the first segment, the segment head 210 which is 

responsible for restoration over the Second Segment 219, in 

which the last node 211 is included, restores communication 

over its discovered alternate path to the destination node 

239. Conversely, in the event of a failure of the segment 

head node 210 of the second segment 219, which is included 

in the first segment 217, the source node 205 invokes its 

discovered alternate path which circumvents the Segment 

head 210. In addition, the last node 211 of the first segment which is the next node adjacent to the segment head 210 of 

the Second path Segment 219 may now be re-designated as 

the Segment head for the Second Segment. 

0082) The communication network shown in FIG. 8 

having overlapping Segments can be implemented in net 

Works having either uni-directional links or bi-directional 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 25 of 35
US 2003/OO63613 A1 

linkS. In optical networks with uni-directional links, the first 

Segment head restores those links directed towards the 

destination. The other Segment head restores those links 

directed towards the Source. 

0083) Fault or Failure Detection 

0084 Generally, when a fault is detected on a link, one or 

both node(s) adjacent to the fault is (are) responsible for 

announcing the change in State of the link to other nodes in 

the network. Each Segment head end may be arranged to 

asSociate the link fault against any path Segments for which 

it acts as a Segment head end. If the link impacts one or more 

of these path Segments, the Segment head end is responsible 

for redirecting the LSP data over alternate paths. 

0085. A downstream failure may be transmitted in a 

number of ways, including standard OSPF (Open Shortest 

Path First Protocol) LSA's (Link State Advertisement) or 

MPLS path tear signals sent in the upstream direction. To 

address this issue appropriately, an extension is preferably 

made to the path tear message. The explicit route that has 

just failed is added to the path tear message thus informing 

the path segment head end of exactly which link(s) are under 

fault and thus which parts of the primary path to redirect 

around. 

0.086 A downstream failure may be transmitted by a fast 

flooding LSA mechanism as described in copending U.S. 

Patent Application No. 60/290,386, filed on May 14, 2001. 

A fast flooding mechanism is initiated by the node local to 

the fault upon failure detection. This node and all other 

nodes in the network forward the link state advertisement 

(LSA) preferably at wire speed with minimal per-hop delay. 

0.087 Although either of the first two previously men 

tioned approaches will Suffice, the recommended approach 

is to use the fast LSA flooding mechanism to inform all 

nodes of the failure event. This improves scalability by 

informing all nodes in the network of the fault. Each node 

can then determine Simultaneously if it acts in a path 

Segment head end role for any paths running over the link(s) 

that has failed. 

0088 Although in a preferred embodiment, the or each 

Segment head Switching router responsible for a particular 

Segment of the plurality communication path is adapted to 

respond directly to a fault on the Segment for which it is 

responsible, in another embodiment, the communication 

network may be arranged Such that a fault indication is 

relayed to one or more Switching routers other than the 

Segment head Switching router responsible for the Section on 

which the fault occurs. The fault condition is interpreted by 

one or more other Switching routers which Subsequently Signal the Segment head Switching router to establish a 

Secondary communication path around the fault, if neces 

Sary, and to re-route data from the primary communication 

path to the Secondary communication path. An example of an embodiment of Such a communication network is shown 

in FIG. 9. This communication network is similar to that 

shown in FIG. 1, and like parts are designated by the same 

reference numerals. 

0089 Referring to FIG. 9, a communication network 1 

comprises a first communication path 3 which includes first, 

second and third Switching routers 5, 7, 9 and a second 

communication path 21 extending from the Second Switch 

ing router 7 to the third switching router 9. The communi 

Apr. 3, 2003 

cation network further comprises a third communication 

path 51 extending from the first switching router 5 to the 

third switching router 9. The first Switching router 5 may be 

the Source node or an intermediate node of the first com 

munication path. In this embodiment, when a fault, F, occurs 

on the section 10 of the primary path between the second and 

third Switching routers 7, 9, the fault is detected by one or 

both of Switching routers 6, 8 which are nearest the fault, at 

least one of which is arranged to forward an indication of the 

fault to the first Switching router 5 along the third commu 

nication path 51. On receiving the fault indication, the first 

Switching router 5 determines the Segment head from which 

data should be diverted from the first communication path 

onto an alternative path and transmits an appropriate Signal 

to the Second Switching router to perform the required Switching, and if necessary, establish a Secondary path 

around the fault. 

0090 Secondary Path Selection 

0091 For the purpose of protecting the primary or work 

ing path, it is desirable to Select a Secondary path which 

shares as few resources, i.e. nodes and links with the part of 

the primary path being protected, as possible. In this case, 

the Secondary path may be described as "maximally dis 

joint” from the primary path. Preferably, a Secondary path is 

Selected which shares no resources with the part of the 

primary path being protected, if Such an alternative path 

exists. If no Such path exists, a Secondary path may be 

Selected, depending on the relative risk associated with each 

shared resource of the primary path. In one embodiment, a 

Secondary path may be Selected which shares the minimum 

number of links with the primary path. A Secondary path 

which shares no links with the primary path may be referred 

to as “link disjoint'. In another embodiment, a Secondary 

path may be Selected which shares the least number of nodes 

with the primary path. A Secondary path which shares no 

nodes with a primary path may be referred to as "node 

disjoint'. An example of a communication network having 

a plurality of different possible Secondary paths is shown in 

FIG 10A. 

0092 Referring to FIG. 10A, a communication network, 

generally shown at 501, includes a primary communication 

path 503 having a series of nodes A, B, C, D and E and 

interconnecting communication links 507, 509, 511, 513. 

The primary path may comprise a Section of a communica 

tion path between a Source node (e.g. ingreSS LER) and a 

destination node (e.g. egreSS LER), and node A may com 

prise a Source or intermediate node, and node E may 

comprise an intermediate or destination node of the com 

munication path. The communication network 501 further 

comprises a plurality of further nodes, F, G, H, and I and 

communication links 515 to 533 forming a plurality of 

alternative communication paths between nodes A and E. 

Using the above Selection criteria, the alternative path which 

is to protect the primary path between nodes A and E is 

Selected Such that it shares the minimum number of nodes 

and links with the primary path. In this embodiment, an 

alternative path exists which shares no intermediate nodes or 

communication links with the primary path between nodes 

A and E, namely the communication path 522 defined by 

nodes A, G, H, I and E and communication links 515, 517, 

519 and 521. Since all the other possible alternative paths 

share at least one resource with the primary path, this 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 26 of 35
US 2003/OO63613 A1 

alternative path is maximally disjoint from the primary path 

and is therefore preferably Selected to protect the primary 

path between nodes A and E. 

0093. In this embodiment, node A may be selected to 

function as the Segment head of the primary path between 

nodes A and E and may be conditioned or configured to 

direct data packets for transmission over the primary path 

onto the Selected Secondary path defined by nodes A, G, H, 

I, and E, in response to a fault on the primary path between 

nodes A and E. In one embodiment, a Secondary label 

Switched path is established between nodes A and E, and the 

Switching router of node A is adapted to direct data on to the 

secondary LSP by outputting data packets with the first 

forwarding label defining the secondary LSP onto the first 

communication link 515 of the secondary path. The Switch 

ing router of node A may be configured to Select and/or 

establish the Secondary communication path, or the Selection 

and establishment of the Secondary communication path 

may be managed from or by another node or resource of the 

communication network. 

0094. In another embodiment, the Switching router at 

node A may be pre-configured (e.g. by configuring one or 

more Incoming Label Maps (ILMS)) to protect the primary path and invoke one of a plurality of Secondary paths 

contingent on which resource or resources of the primary 

path fail. For example, referring again to FIG. 10A, a first 

protection path defined by nodes A, G, and B may be 

established and invoked to re-route data intended for trans 

mission along the primary path between nodes A and B, in 

the event of a failure F on link 507 between nodes A and B. 

In this case, node B is adapted to merge or route data 

received from the protection path back onto the primary path 

to node C. A Second protection path defined by nodes A, B, 

F and C, may be established and invoked to restore data 

transmission in the case of a failure F associated with link 

509 between nodes B and C of the primary path. In this case, 

node C is adapted to merge or route data intended for 

transmission over the primary path between nodes B and C 

back onto the primary path to node D. 

0.095 A third protection path, for example defined by the 

nodes A, B, F and E, may be established and invoked to 

restore data transmission in the event of a failure F of 

network node C. 

0096. In each case, a Switching router at node A may store 

the necessary instruction(s), ie. forwarding tables or ILM(s), required to re-direct data over the appropriate protection 

path in response to a fault or failure indication which also 

indicates the particular resource(s) of the primary path that 

has failed. The Switching router of node A may also be 

conditioned to establish each alternative protection path. 

0097. In a case of restoration, where the secondary path 

is established after the occurrence of a failure on the primary path, either on an alternative path which is maximally disjoint from the primary path between nodes A and E may 

be established or an alternative path which shares at least 

one resource with the primary path and which bypasses the 

failed resource or resources may be established. The Switch 

ing router at node A may be configured to implement at least 

one of these restoration Schemes. Thus, for example, in 

implementing a maximally disjoint LSP, the Switching 

router at node A may be conditioned to establish the appro priate Secondary LSP in response to a fault or failure of any 

of the resources of the primary path between nodes A and E. 

Apr. 3, 2003 

0098. In another embodiment, the Switching router at 

node A is conditioned to respond to a fault indication which 

Specifies a particular resource or resources which have failed 

by discovering an alternative path which bypasses the failed 

resource(s), and at the same time includes one or more active 

(unfailed) resources of the primary path. In one embodi 

ment, the Segment head Switching router at node A may be 

conditioned to discover a plurality of alternative paths 

around the failed resource, measure or determine the value 

of a parameter describing each alternative path, and Select an 

alternative path based on its determination of the values of 

the parameter for each alternative path. For example, the 

Segment head Switching router may be adapted to Select the 

Shortest or least expensive alternative path. The Switching 

router of node A may be adapted to respond to each of the 

faults F, F, or F in the manner described above in con 

nection with protection of the primary path. 

0099 FIG. 10B shows another embodiment of a com 

munication network, which is similar to the communication 

network shown in FIG. 10A, except that in FIG. 10B, the 

communication link 519 between nodes H and I does not 

exist. In this case, all of the possible alternative paths for 

protection and restoration of the primary path necessarily 

share at least one resource with the primary path. A first 

example of an alternative path between nodes A and E is 

defined by nodes A, G, H, C, D, I and E, and exemplifies a 

path which shares a link 511, and two nodes C and D with 

the primary path. A Second example of an alternative path is 

defined by nodes A, G, B, F and E, and a third example is 

defined by nodes E, G, H, C, F and E. In both cases, the 

alternative path shares a single node (i.e. node B or C, respectively) with the primary path and no communication 

links and, are therefore both “link disjoint'. For protection, the Secondary path may be selected for example from the 

above three possible alternative communication paths on the 

basis of one or more Selection criteria, which may include 

the number of resources shared with the Secondary path, the 

relative risk of failure of each resource, the path link 

transmission characteristics and capacity and the path cost. 

These and any other criteria may be applied in any order and 

with any priority. If the most important criteria is to mini 

mize the number of Shared resources with the primary path, either the Second or third alternative paths may be Selected 

which share only one resource with the primary path. The 

Selection between the Second and third alternative paths may then depend on other criteria, for example path length or 

cost, the relative costs of nodes B and C, their connectivity 

to the network, their relative risk of failure and the Spare capacity of the alternate paths. 

0100 Segment Head Selection 

0101 Another aspect of the present invention is con 

cerned with methods of Selecting one or more Segment head 

nodes along the network path (i.e. primary or working path) 

to improve or optimize the handling of a resource failure. 

0102) The selection of one or more segment heads may 

be based in part by the way the network is planned. For 

example, a network may be divided into a number of cells, 

and one or more nodes at the interface of each cell may be 

Selected to function as a Segment head node for the purpose 

of protection and/or restoration. An example of a network 

which is Subdivided into a plurality of areas or cells as 

shown in FIG. 11, and will be described with reference to an 

optical network. 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 27 of 35
US 2003/OO63613 A1 

0103 Referring to FIG. 11, an optical network generally 

shown at 601 is divided into optically isolated areas or cells 

603, 605. Each optical cell includes a number of nodes 607 

to 627 connected by optical fibre communication links 629 

in a pre-defined manner, preferably to provide route diver 

sity to each node. This division may be required for network 

planning and Scalability So that one area of the network can 

be wavelength planned, or Scaled without impacting the 

wavelength colouring Solution within another area of the 

network. 

0104 For a network incorporating optical cells, candidate 

Segment heads can be designated throughout the network at 

the boundaries of the optical cells. For example, in the 

embodiments shown in FIG. 11, network nodes 617 and 619 

at the boundary between the first and second cells 603, 605 

may be Selected to Serve as Segment head nodes for com 

munication paths which pass from one cell to an adjacent 

cell. This Selection criteria closely matches with the prop erties of the optical cells. In another embodiment, Segment 

heads can be chosen using any other criteria, including those 

described below in connection with an arbitrary network. 

0105 Segments in Arbitrary Networks 

0106. In arbitrary networks, there are many ways to 

determine which nodes should act as Segment head nodes. A 

particular Segment head may be selected to Serve as a 

Segment head for one or more Selected LSP’s on the primary 

path, and where a plurality of LSP’s are established on the 

primary path, each LSP may have one or more different 

segment heads. AS new LSP’s are established, the segment head for a particular LSP may be predefined, or may be 

established dynamically for that particular LSP. 

0107 An example of an embodiment in which different 

segment heads are selected for different LSP’s on the 

primary path is shown in FIG. 12. Referring to FIG. 12, a 

communication network 601 includes a primary path 603 

having a plurality of nodes 605 to 619. First and second label 

Switched paths LSP1 and LSP2 are established on the 

primary path 603. The communication network further 

includes a first Secondary path 621 extending between the 

fourth and eighth nodes 611, 619 and a second secondary 

path 623 extending between the fifth and eighth node 613, 

619. In this example, the fourth node is selected to serve as 

the segment head node for the first LSP, LSP1 and is 

responsible for directing data traffic from the primary path 

onto the first secondary path 621 in the event of a fault on 

the primary path Segment between itself and the destination 

node 619. The fifth node 613 is selected to serve as the 

segment head node for the second LSP, LSP2 and is respon Sible for re-directing data traffic from the primary path onto 

the second secondary path 623 in the event of a fault on the 

primary path between itself and the destination node 619. 

0108 Embodiments of methods for selecting one or more 

Segment head nodes in communication networks will now 

be described below. 

0109. In one embodiment, a segment head node may be 

Selected on the basis of the number of intermediate nodes 

between the Source and destination nodes and a Segment 

head node may be Selected as a node which is Substantially 

equidistant between the Source and destination nodes (i.e. a 

median node), or a segment head node may be selected at 

every certain number of nodes along the primary path 

Apr. 3, 2003 

between the Source and destination nodes. Thus, at one 

extreme, a single intermediate Segment head node may be 

Selected between the Source and destination nodes, and at the 

other extreme, every node between the Source and destina 

tion nodes may be selected to Serve as a Segment head node. 

0110. Another selection criteria which may be used to 

Select a Segment head, is to Select those nodes that divide the 

path into predetermined Segment lengths. 

0111 Another selection criteria is to select the or each 

Segment head Such that the transmission delay between the 

Source node and the Segment head and the Segment head and 

the destination node and between each intermediate Segment head is Substantially the same or as even as possible, or in 

other words So that any difference between the transmission 

delays in the path Segments is minimized. Transmission 

delays are generally attributable to both links and nodes. 

Link delay is generally dependent on the propagation char 

acteristics of the link, and node delay may be dependent on 

the level of node congestion or activity. Advantageously, this 

Selection of criteria assists in minimizing improvements in 

the protection and restoration time Since it can limit the 

maximum time delay between the occurrence of a fault and 

receipt of a fault indication by a Segment head node. 

0.112. Where a plurality of candidate nodes exist for a 

particular Segment head node, the Segment head may be 

Selected depending on a parameter defining the connectivity 

from each of the candidate nodes to the alternative path. For 

example, the Segment head node may be chosen as the node 

which connects to the Secondary path with minimum cost or 

connects to the Secondary path with minimum propagation 

delay and/or via the Shortest route, or may be Selected as the 

node which has the highest degree of connectivity and is 

therefore most likely to find one or more alternate routes. 

0113 Another criteria which may be applied in selecting 

a Segment head is to avoid those nodes with a high level of 

congestion or risk or any nodes which are deemed to be a 

critical resource, for example a node on an edge of a bridge 

link, which is a Set of nodes that provides the only connec 

tivity between two parts of a network. An example of a 

bridge link is shown in FIG. 13. FIG. 13 shows a commu 

nication network 301 which includes a first communication 

path 303 having a source and destination nodes 305,307 and 

intermediate nodes 309, 311, 313 and communication links 

315, 317, 319 and 321. The communication network 

includes a first section 323 having alternate paths 235, 237 

extending from the source node 305 to the first intermediate 

node 309 and a second section 329 having alternative 

communication paths 331, 333 extending between the third 

intermediate node 313 and the destination node 307. In this 

example, the only path which joins the nodes of the first and 

Second Sections of the network extends between the first and 

third intermediate nodes 309, 313, and this path constitutes 

a bridge link 335 (shown by the dotted lines), of which the 

first and third intermediate nodes are located on the edge of 

the bridge link. In segmenting the primary path 303 for 

protection or restoration and Selecting a node to Serve as a 

Segment head node for a Section of the primary path between 

itself and the destination node, neither of the first and Second 

intermediate nodes 309, 311 are particularly suitable candi 

dates Since neither have any access or connectivity to a 

Secondary path which could bypass a fault on the primary. 

However, the third intermediate node 313 on the edge of the 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 28 of 35
US 2003/OO63613 A1 

bridge link at the second section 329 of the network has 

access to alternative paths 331, 333 between itself and the 

destination node 307 and could therefore serve as a Suitable 

Segment head for the Section of the primary path between 

itself and the destination node 307. In this example, the 

Source node could Serve as the Segment head node for the 

section of the primary path between itself and the first 

intermediate node 309. However, the part of the primary path defined by the bridge link 335 cannot be protected by 

a Secondary path, as the bridge link is the only communi 

cation link connecting the first and Second Sections of the 

network. 

0114) Examples of methods of evaluating and selecting a 

Segment head in accordance with embodiments of the 

present invention will now be described with now be 

described with reference to FIGS. 14A to 14G. 

0115 FIG. 14a shows an example of a communication 

network, generally shown at 701, which includes a primary 

path 703 having source and destination nodes 705, 707, 

labelled A and G. The primary path 703 further includes a 

plurality of intermediate nodes B, C, D, E, and F. The 

communication network 701 includes a Secondary commu 

nication path 709 extending from the source node 705 to the 

destination node 707 of the primary communication path. 

The Secondary communication path has a plurality of inter 

mediate nodes H, I, J, K, and L. In this embodiment, a 

number of intermediate nodes C, D, E, F of the primary path 

are connected to a number of intermediate nodes I, J, K of 

the Secondary path through various network linkS repre 

sented by an intermediate network cloud 711. 

0116. In this example, an objective is to divide the 

primary path 703 into two segments for the purpose of 

protection and/or restoration and to Select an intermediate 

node to Serve as the Segment head node of the Second 

Segment between that node and the destination node G 

according to predetermined criteria. It is to be noted that this 

method can be applied to Select a plurality of Segment head 

nodes each from a plurality of candidate intermediate nodes 

(test nodes), for example where the communication path is 

to be divided into three or more Segments. 

0117. In the present example, a first step of the method 

involves Selecting a plurality of candidate intermediate 

nodes (test nodes) on the primary path which could serve as 

the intermediate Segment head node. The candidate nodes 

may be selected in accordance with one or more predeter 

mined criteria, including any of the criteria described above. 

In this example, a plurality of intermediate nodes C, D and 

E shown within the dashed window 710 are selected at or 

near the median of the primary path between the Source and 

destination nodes So that each Segment will be approxi 

mately the same length. The Selection criteria may also 

provide that the data propagation time acroSS each Segment 

is approximately the Same. Candidate nodes on the primary path may be Selected only if their degree of connectivity is 

three or more. 

0118. Once a plurality of test nodes on the primary path 

have been Selected, a parameter describing their relationship 

to the Secondary path is evaluated. In one example, this 

parameter is the physical length of a test path between a test 

node on the primary path and a node on the Secondary path. 

Once the physical length of each test path has been deter 

mined, the test node of the primary path which is connected 

Apr. 3, 2003 

to a node on the Secondary path by the shortest test path may be selected. In other examples, the parameter may comprise 

a parameter which describes the propagation time between 

a test node on the primary path and a test node on the 

Secondary path, for example an actual value of the propa 

gation time, the number of nodes on the test path, the 

characteristics of the nodes on the test path and the propa 

gation characteristics of the communication links on the test 

path. 

0119) An embodiment of a method for evaluating and 

Selecting one or more nodes to Serve as Segment head nodes, and which may conveniently be implemented by a computer 

program will now be described with reference to 14B to 

14G. 

0.120. As shown in FIG. 14B, the primary path is trans 

formed by adding an imaginary node A', and attaching an 

imaginary linka, b, c from each test node C, D, and E to the 

imaginary node A'. A parameter is Selected which describes 

the relationship between a test node on the primary path and 

a test node on the Secondary path (e.g. test path link) which 

is to be evaluated and used to determine which test node to 

use as the Segment head node on the primary path. A value 

of this parameter is assigned to each of the imaginary links 

a, b, and c which is preferably the Same value for each 

imaginary link and may be set to Zero or any other Suitable 

value. 

0121 To evaluate the relationship between each test node 

of the primary path with a plurality of test nodes on the 

Secondary path, a plurality of Secondary path test nodes I, J, 

Kare selected, preferably having a degree of connectivity of 

at least three. As shown in FIGS. 14C and 14D the 

secondary path 709 is transformed by adding an imaginary 

node Z and adding an imaginary link d, e, f from each test 

node I, J and K on the Secondary path to imaginary node Z. 

A value of the Selected parameter used to describe a test path between the primary and Secondary paths is assigned to each 

of the imaginary paths d, e, f and is preferably the same 

value for each of the imaginary paths d, e and f, and may be 

Set to Zero or another Suitable value. 

0.122 The next step in the method is to determine the 

value of the Selected parameter for a plurality of possible 

paths between the two imaginary nodes A and Z. The values 

of the parameter determined for each path may then be 

compared with one another or with a target value and the 

path having the desired value then Selected. For example, the 

parameter may comprise path length and the method deter 

mines the path length for each of a plurality of paths from 

imaginary nodes A to Z which pass through at least one of 

the test nodes on the primary path and at least one test node 

on the Secondary path, and Selects the path with the shortest 

path length. 

0123. Before evaluating the value of the selected param 

eter for each path between the imaginary nodes, one or more 

links 713, 715 between adjacent test nodes on the primary 

path and/or one or more links 717, 719 between adjacent test 

nodes on the Secondary path may be assigned a value of the 

Selected parameter Such that the paths between the imagi 

nary nodes for which the value of the Selected parameter is 

determined excludes those paths which might otherwise 

include a link between adjacent nodes on the primary and/or Secondary paths. 

0.124. Once the path having the desired value of the 

Selected parameter has been determined, the path is exam 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 29 of 35
US 2003/OO63613 A1 

ined and the test node which is to Serve as the Segment head 

node is Selected. In the determination of a feasible Segment 

head node, the following criteria may be applied. 

0.125 If the determined path traverses a primary path 

node which is not one of the Selected test nodes, any one of 

the test nodes, for example the node closest to the median, 

may be Selected as the Segment head node and arranged to 

direct data onto the Secondary path, in response to a fault on 

the primary path downstream thereof, either via the Source 

node or via the primary path node which is connected to the 

Secondary path. An example of this Scenario is illustrated in 

FIG. 14E. In this example, the determined path 721 (shown 

by the dotted line) between the imaginary nodes A and Z 

passes through intermediate nodes C and B of the primary 

path, and intermediate node I of the secondary path 709 via 

communication link 723. In this case, any one of interme 

diate nodes C, D, or E of the primary path may be Selected 

as the Segment head node. For protection or restoration of 

the Segment between the Selected intermediate Segment head 

and the destination node G, the intermediate Segment head 

node may be arranged to direct data back to intermediate 

node B which then routes data onto the Secondary path over 

communication link 723, or to direct data back to the Source 

node A, which may be arranged to route data to node H of 

the secondary path via communication link 725. 

0.126 If the determined path traverses either the source or 

destination nodes, as for example in the case of a ring 

network, any one of the test nodes, for example the node 

closest to the median, on the primary path may be Selected 

to Serve as the Segment head node between that node and the 

destination node. For protection and/or restoration, the 

Selected Segment head node is adapted to direct data back to 

the Source node which Subsequently directs the data onto the 

Secondary path. An example of this Scenario is illustrated in 

FIG. 14F. In this example, the determined path 721 shown 

by the dotted line extending between the imaginary nodes A 

and Z' passes through the Source node A. In this case, any 

one of the test nodes C, D and E may be selected as the 

Segment head node, and for protection and/or restoration, 

may be adapted to route data back to the Source node which 

Subsequently routes data onto the Secondary path Via com 

munication link 725. 

0127. If the primary path node(s) through which the 

determined path between the imaginary nodes A and Z 

passes only includes one or more of the Selected test nodes, 

then one of the test nodes on the primary path may be 

Selected to Serve as the Segment head node. An example of 

this scenario is illustrated in FIG. 14G. In this example, the 

determined path 721 between the imaginary nodes A and Z 

traverses one test node D on the primary path and one test 

node I on the Secondary path. In this case, intermediate test 

node D is preferably Selected as the Segment node for the 

purpose of protection and restoration of the Segment 

between the intermediate node D and the destination node G. 

0128. The segment head end of each segment may be 

selected at the original label edge router (LER) before the 

path is signalled. The LER of the path may select the 

segment head ends for the path to be established. The 

Segment head end may be signalled, via an explicit route 

object (ERO), or other signal, indicating that the appropriate 

node should act as a Segment head end for the path. The or 

Apr. 3, 2003 

each head end node is conditioned to manage path restora 

tion in the event of a failure within its segment of the 

primary path. 

0129. If on selection of a segment head end, an alternate 

path cannot be established, the Segment head end may be 

arranged to inform the LSP head end of the failure to 

establish an alternate path. Depending upon when the alter 

nate Set-up error has occurred, the Source of the path may be 

Signalled of the failure via a path tear or path Signal error. 

0.130. In order to be resilient to failures along the primary 

path, an alternate path is determined and created and this 

alternate path merges again with the primary path either 

upstream of the EgreSS LER (destination node) or at the 

destination node. AS mentioned above, two basic types of 

resiliency are possible and it is to be noted that both may be 

implemented in the same System and may work Side by Side 

without interference. 

0131) A first level of resiliency to faults or failures is 

provided by protection of the primary path. In this case, the 

alternate path which works around any problems in the 

primary path is pre-computed and preselected. In one 

embodiment, the path Segment head end performs routing on 

its understanding of the network topology to determine a 

route that is preferably maximally disjoint from the primary 

route through the Segment. In the case of a pre-computation 

of the alternate path (LSP), the alternate LSP must merge with the primary LSP somewhere outside the path segment being protected. With this approach, the alternate path is 

routed and Set up prior to fault occurrence. The protection path preferably meets at least the Same requirements, e.g. 

data transmission capacity and/or transmission time, as the 

Segment of the primary path which it protects, although in 

other embodiments, the protection path may have a lower 

Specification than the primary path. The protection path may 

be dedicated, in which case it only carries data for trans 

mission on the primary path, or the protection path may 

carry other data traffic, for example traffic with a lower 

priority. If the protection path is dedicated, the protection 

path may be used to carry primary path data traffic only in 

response to a fault on the primary path, or the Segment head 

node may be arranged to duplicate primary path data and 

forward the data over both the primary path and the sec 

ondary path. In this arrangement, in the event of a fault or 

failure on the primary path, primary path traffic which may 

be lost as a result of the fault or failure still continues over 

the protection path. The node or Switching router which 

normally receives data from both the primary and Secondary 

paths is adapted to Select the data traffic transmitted over the 

Secondary path for continued transmission, in response to a 

fault or failure on the primary path. Advantageously, a 

protection Scheme generally provides the fastest fault recov 

ery times. 

0.132. A second level of resiliency to faults or failures is 

provided by restoration or re-connect of primary path data 

transmission. In this case, the alternate path is routed at the 

fault detection time. Since in a preferred embodiment, the 

path Segment head node knows the hopS along the primary 

path that have been impacted, a new route can be calculated 

or determined to re-route traffic from the path Segment head 

end and back onto the primary LSP without using the link(s) 

that have failed. In this case, the alternate LSP must merge with the primary LSP but this merge can occur within the 

path Segment under recovery. 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 30 of 35
US 2003/OO63613 A1 

0133) If the path segment head ends line up to cell 

boundaries, then the alternate route can be calculated from 

a reduced topology which includes those nodes and links in 

the cell. Calculating an alternate route is generally faster 

with a reduced topology. This is one preferred method of 

path Segment head end Selection for those paths that require 

restoration at fault detect time. In another embodiment, the 

alternate route can be determined from a full view of the 

network. For example, this method could be imposed in the 

case where the path Segment head end is Selected arbitrarily 

as described above in the Section: Segments in Arbitrary 

Networks. Although the route determination in this case will 

generally be slower than in the cell-based approach, the 

alternate route will still be correct and valid. 

0134) The step of establishing a path is generally the 

Same whether the alternate path is established prior to fault 

occurrence or after fault occurrence. In one embodiment, the 

alternate LSP is signalled as a normal LSP with an attribute 

that has significance at the merge point. At the merge point, 

(where the alternate and primary LSP’s meet up again) the 

alternate LSP may indicate the LSP with which it will be 

merged (which is a primary LSP). The merge may be 

controlled by the replacement of multiple incoming labels 

for example the replacement of labels for the alternate and 

primary LSPS with a single outgoing label, for example that 

of the primary LSP. It is possible to extend the standard 

merge concept to allow the path Segment head end to Signal 

the explicit routing of an incoming LSP onto an outgoing 

LSP 

0.135 Generally, in the event of a failure, a path segment 

head end redirects the incoming LSP onto an alternate LSP. 

This alternate LSP merges with the primary LSP at some 

point down the stream for failure. The LSP merge insures 

that the data is forwarded correctly to the Egress LER. 

0.136 Each path segment is assigned one or more Seg 

ment heads. The Segment head(s) may be responsible for (1) Setting up and managing alternate paths within a cell or 

Segment area, and are generally responsible for (2) acting on 

failure indications, and (3) Switching traffic over to the 

restoration path on failure. 

0.137 The segment head may be signalled to act as a 

Segment head for a particular flow, e.g. LSP. The Segment 

head may then discover alternate diverse routes within its 

Segment to Satisfy the protection/restoration requirements of 

the flow. This proceSS also distributes the memory require 

ments of the Source node between itself and the other 

Segment heads. 

0.138. When the segment head receives a failure indica 

tion, it will attempt to recover the traffic. If the only backup 

route available is already used, the error may be propagated 

back to the Source node for further processing. 

0139 Embodiments of the invention described herein 

provide Systems which attempt to optimize the completion 

time of protection and restoration Schemes in large arbitrary 

networkS. Generally, a network path is divided into two or 

more Segments, depending on its size, with the Start of each 

Segment assigned the responsibilities of a Segment head. 

Each Segment head is generally responsible for Servicing its 

portion of the path. 

0140 Modifications, changes and alternatives to the 

embodiments described above will be apparent to those 

skilled in the art. 

Apr. 3, 2003 

1. A communication network including a first communi 

cation path having a plurality of Switching routers, a Second 

communication path having at least one communication path 

element different from Said first communication path and 

extending from a Selected one of Said Switching routers to a 

position on Said first communication path located at a 

distance from Said Selected Switching router of less than the 

length of Said first communication path, wherein Said 

Selected Switching router includes output means for output 

ting data with a label for routing data along one of Said first 

and Second communication paths, and routing means 

responsive to a fault in the transmission capability of Said 

first communication path between said Selected Switching 

router and Said position for routing data received by Said 

Selected Switching router for transmission along Said first 

communication path, along Said Second communication 

path. 

2. A communication network as claimed in claim 1, 

wherein Said first communication path includes a first 

Switching router, a Second Switching router downstream of 

Said first Switching router, and a third Switching router 

downstream of Said Second Switching router, and Said 

Selected Switching router comprises Said Second Switching 

rOuter. 

3. A communication network as claimed in claim 2, 

wherein Said Second Switching router includes enabling 

means for enabling Said routing means to output data 

Specified for transmission on Said first communication path, 

onto said second communication path with a label for 

routing Said data along Said Second communication path. 

4. A communication network as claimed in claim 3, 

wherein Said enabling means comprises a machine readable 

instruction. 

5. A communication network as claimed in claim 4, 

wherein Said Second Switching router comprises a memory 

Storing Said machine readable instruction. 

6. A communication network as claimed in claim 3, 

wherein Said Second Switching router is configured to read a 

label associated with received data and to identify therefrom 

data Specified for transmission on Said first communication 

path. 

7. A communication network as claimed in claim 2, 

wherein Said Second Switching router further comprises label 

Switched path establishing means for establishing a label 

Switched path on Said Second communication path for car 

rying data Specified for transmission on Said first commu 

nication path. 

8. A communication network as claimed in claim 7, 

wherein Said label Switched path establishing means is 

adapted to establish Said label Switched path in response to 

a fault in the transmission capability of Said first commu 

nication path. 

9. A communication network as claimed in claim 2, further comprising Secondary path determining means 

responsive to the location of a fault on the first communi 

cation path for determining Said Second communication path 

to bypass Said location. 

10. A communication network as claimed in claim 9, 

wherein Said path determining means includes Selection 

means for Selecting Said Second communication path from a 

plurality of communication paths. 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 31 of 35
US 2003/OO63613 A1 

11. A communication network as claimed in claim 10, 

wherein Said Selection means is adapted to Select as Said 

Second communication path, the path having the shortest 

data transmission time. 

12. A communication network as claimed in claim 2, 

wherein Said Second Switching router further comprises Secondary path determining means for discovering at least 

one Secondary path. 

13. A communication network as claimed in claim 12, 

wherein Said determining means is adapted to determine the 

value of a parameter defining the or each Second commu 

nication path. 

14. A communication network as claimed in claim 13, 

wherein Said determining means is adapted to Select a 

Secondary path based on the determined value(s) of Said 

parameter. 

15. A communication network as claimed in claim 14, 

wherein Said parameter is the data transmission time over 

the Secondary path, and the Selection means is adapted to 

Select as Said Second communication path, the path having 

the shortest data transmission time. 

16. A communication network as claimed in claim 12, 

wherein Said Second Switching router further includes Sig nalling means for Signalling Said first Switching router if said 

Second Switching router fails to determine a Second com 

munication path. 

17. A communication network as claimed in claim 16, 

wherein Said first Switching router is adapted to determine an 

alternative path which bypasses Said location in response to 

said signal. 

18. A communication network as claimed in claim 17, 

wherein Said first Switching router is adapted to establish a 

Second label Switched path over Said alternative path and 

direct data Specified for transmission on Said first commu 

nication path onto Said Second label Switched path. 

19. A communication network as claimed in claim 2, 

wherein Said first communication path includes a plurality of 

intermediate Switching routers between said first Switching 

router and Said third Switching router, a first label Switched 

path is established on Said first communication path which 

originates at Said first Switching router and terminates at Said 

third Switching router, and wherein Said Second Switching 

router is Selected from Said plurality of intermediate Switch 

ing routers as the Switching router Such that the difference in 

the transmission time on each Section of the first commu 

nication path between itself and the first Switching router 

and itself and the third Switching router is a minimum. 

20. A communication network as claimed in claim 2 

comprising a plurality of intermediate Switching routers 

between said first and third Switching routers, a first label 

Switched path established on Said first communication path which originates at Said first Switching router and terminates 

at Said third Switching router, Said intermediate Switching 

routers including a plurality of Said Selected Switching 

routers, each having a Second communication path extend 

ing therefrom to a position on Said first communication path located at a distance from a respective Selected Switching 

router of less than the length of Said first communication 

path, and wherein the Selected Switching routers are Selected 

from Said plurality of intermediate Switching routerS Such 

that any difference in the data transmission time on each 

Section of the first communication path between each pair of 

neighbouring Selected Switching routerS is a minimum. 

Apr. 3, 2003 

21. A communication network as claimed in claim 1, 

wherein Said Second communication path is Selected to share 

the minimum number of communication links with Said first 

communication path. 

22. A communication network as claimed in claim 17, 

wherein Said Second communication path is Selected to share 

the minimum number of Switching routers with said first 

communication path. 

23. A communication network as claimed in claim 2, 

comprising a plurality of intermediate Switching routers 

between Said first Switching router and Said third Switching 

router, each being connected to Said Second communication 

path by a respective intermediate communication path, and 

wherein Said Selected Switching router is that which is 

connected to Said Second communication path by the inter 

mediate communication path having the Shortest data trans 

mission time. 

24. A communication network as claimed in claim 2, 

further comprising a fault detector for detecting a fault on 

the first communication path and transmitting a signal indicating the presence of Said fault to Said Second Switching 

rOuter. 

25. A communication network as claimed as claimed in 

claim 24, wherein Said fault detector further includes means 

for detecting the location of Said fault and transmitting a 

Signal to at least one of Said first and Second Switching 

routers indicating at least one of the location of Said fault and 

the element of Said first communication path at which Said 

fault is located. 

26. A communication network as claimed in claim 2, 

wherein Said Second Switching router includes enabling 

means for enabling Said routing means to output data 

Specified for transmission on Said first communication path, 

onto Said first communication path with a label for routing Said data along Said first communication path. 

27. A communication network as claimed in claim 2, 

comprising a label Switched path on Said first communica 

tion path which originates at Said first Switching router and 

terminates at Said third Switching router, and wherein the 

length of said label Switched path defines the length of said 

first communication path. 

28. A communication network as claimed in claim 2, 

comprising an intermediate Switching router between Said 

Second Switching router and Said third Switching router, Said 

Second communication path adjoining Said first communi 

cation path at Said intermediate Switching router, and 

wherein Said intermediate Switching router includes 

enabling means for enabling Said intermediate Switching 

router to direct data received on Said Second communication 

path intended for transmission on Said first communication 

path onto Said first communication path. 

29. A communication network as claimed in claim 28, 

comprising a label Switched path established on Said first 

communication path, and wherein Said intermediate Switch 

ing router is adapted to label data received from Said Second 

communication path intended for transmission on Said first 

communication path with a label defining Said label 

Switched path on Said first communication path. 

30. A communication network as claimed in claim 1, 

wherein Said first communication path includes a first 

Switching router, a Second Switching router downstream of 

Said first Switching router and a third Switching router 

downstream of Said Second Switching router, and wherein 

Saida Second communication path extends from Said Second 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 32 of 35
US 2003/OO63613 A1 

Switching router to a predetermined point on Said first 

communication path downstream of Said Second Switching 

router, Said Second Switching router being adapted to route 

data over Said first communication path in response to a 

predetermined label associated with Said data, and having re-routing means responsive to a fault condition in the 

transmission capability of Said first communication path 

between Said Second Switching router and Said predeter mined point for re-routing data received by Said Second 

Switching router from Said first Switching router along Said 

Second communication path. 

31. A communication network as claimed in claim 30, 

wherein Said Second communication path includes a Switch 

ing router between said Second Switching router and Said 

predetermined point, and Said Switching router of Said 

Second communication path is adapted to route data received 

by Said Second Switching router intended for further trans 

mission along Said first communication path to Said third 

Switching router, along Said Second communication path in 

response to a predetermined label associated with Said data. 

32. A communication network as claimed in claim 30, 

wherein Said first communication path includes a further 

Switching router between said Second Switching router and 

Said third Switching router, and wherein Said Second com 

munication path joins Said first communication path at Said 

further switching router or downstream of said further 

Switching router. 

33. A communication network as claimed in claim 32, 

further comprising a third communication path between said 

further Switching router and a Second predetermined point 

along Said first communication path downstream of Said 

further Switching router, and wherein Said further Switching 

router includes re-routing means responsive to a fault con 

dition in the data transmission capability of the first com 

munication path between said further Switching router and 

Second predetermined point for re-routing data received by 

Said further Switching router intended for further transmis 

Sion along Said first communication path to Said third 

Switching router, along Said third communication path. 

34. A communication network as claimed in claim 33, 

wherein Said third communication path includes a Switching 

router between Said further Switching router and Said Second 

predetermined point, and wherein Said Switching router of 

Said third communication path is adapted to route data along Said path in response to a label associated with the data 

transmitted from Said further Switching router. 

35. A communication network as claimed in claim 30, including a further communication path extending from Said 

first Switching router and adjoining Said first communication 

path at a predetermined point downstream of Said first 

Switching router, wherein Said first Switching router includes 

re-routing means responsive to a fault condition in the 

transmission capability of Said first communication path between Said first Switching router and Said predetermined point at which Said further communication path joins Said 

first communication path, for re-routing data intended for 

transmission along Said first communication path, along Said 

further communication path. 

36. A communication network as claimed in claim 35, 

wherein Said further communication path includes a Switch 

ing router between said first Switching router and Said 

predetermined point, Said Switching router being adapted to 

direct data from received from Said first Switching router 

intended for transmission along Said first communication 

path along Said further communication path in response to a 

label communicated with Said data by Said first Switching 

rOuter. 

Apr. 3, 2003 

37. A communication network as claimed in claim 30, 

wherein Said first communication path includes a first 

Switching router, a Second Switching router downstream of 

Said first Switching router and a third Switching router 

downstream of Said Second Switching router, a Second 

communication path extending from Said first Switching 

router to Said Second Switching router, Said Second Switching 

router being adapted to route data over Said first communi 

cation path in response to a predetermined label associated 

with Said data, and wherein Said first Switching router 

includes routing means responsive to a fault condition in the 

data transmission capability of Said first communication path 

between Said first Switching router and Said Second Switch 

ing router for re-routing data intended for transmission along Said first communication path, along Said Second commu 

nication path. 

38. A communication network as claimed in claim 37, wherein Said Second Switching router is adapted to route data 

intended for transmission along Said first communication 

path between Said first Switching router and Said Second 

Switching router and received from Said Second communi 

cation path, along Said first communication path, down 

Stream thereof. 

39. A method of conditioning a communication network 

to restore data transmission from a Source node to a desti 

nation node in the event of a fault between an intermediate 

node and Said destination node on a first communication 

path which includes said Source node, Said intermediate 

node and Said destination node and defines a first label 

Switched path originating at Said Source node and terminat 

ing at Said destination node, the method comprising the Steps of establishing a Secondary label SWitched path, originating 

at Said intermediate node, along a Second communication 

path which bypasses Said fault and re-joins Said first com 

munication path, and conditioning Said intermediate node to 

direct data from said first label Switched path to said second 

label Switched path in response to a fault on Said first 

communication path between said intermediate node and 

Said destination node. 

40. A method as claimed in claim 39, comprising estab 

lishing Said Second label Switched path in response to Said 

fault. 

41. A method as claimed in claim 39, comprising estab 

lishing Said label Switched path in response to a signal 

transmitted from Said Source node to Said intermediate node. 

42. A method as claimed in claim 39, comprising a 

plurality of intermediate nodes between Said Source node 

and Said destination node, and each connected to Said Second 

communication path by a respective intermediate commu 

nication path, and establishing Said Secondary label Switched 

path to originate at the intermediate node which is Selected 

based on the value of a parameter defining at least one of (a) 

each of Said intermediate communication paths, and (b) each 

of Said intermediate nodes. 

43. A method as claimed in claim 42, comprising Selecting Said Secondary label Switched path to originate at the inter 

mediate node which is connected to Said Second label 

Switched path by the intermediate communication path having the shortest data transmission time. 

44. A method as claimed in claim 43, further comprising 

determining which of Said intermediate communication 

paths has the Shortest data transmission time. 

45. A method as claimed in claim 42, comprising deter 

mining the values of Said parameter. 

46. A method as claimed in claim 39, wherein said 

communication network comprises a plurality of interme 

diate nodes between Said Source node and Said destination 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 33 of 35
US 2003/OO63613 A1 

node, a respective Second communication path extending 

from each of Said plurality of intermediate nodes, and the 

method further comprises Selecting one of Said intermediate 

nodes and establishing Said Second label Switched path 

originating at Said Selected intermediate node. 

47. A method as claimed in claim 46, wherein the selected 

intermediate node is connected to a Second communication 

path having the Shortest transmission time. 

48. A method as claimed in claim 46, comprising Selecting 

Said intermediate node based on the location of a fault on the 

first communication path. 

49. A method of transmitting data specified for transmis 

Sion on a first communication path between a Source node 

and a destination node in response to a fault on Said first 

communication path, comprising 

labelling Said data with a label associated with a Second 

communication path which adjoins Said first commu 

nication path at first and Second locations and which 

bypasses Said fault, the distance between Said first and 

Second locations being less than the length of Said first 

communication path, and 

outputting Said labelled data onto Said Second communi 

cation path. 

50. A method as claimed in claim 49, further comprising establishing a label Switched path on Said Second commu 

nication path and wherein Said label comprises a forwarding 

label of said label Switched path. 

51. A method as claimed in claim 49, wherein said first 

location is situated between said Source node and Said 

destination node. 

52. A method as claimed in claim 50, comprising an 

intermediate node at Said first location, and establishing a 

label Switched path on Said Second communication path originating at Said intermediate node. 

53. A method as claimed in claim 50, wherein said second 

location is situated between said Source node and Said 

destination node. 

54. A method as claimed in claim 53 comprising an 

intermediate node at Said Second location, and directing data 

intended for transmission on Said first communication path 

and received from Said Second communication path onto 

Said first communication path at the intermediate Switching 

router at Said Second location. 

55. A method as claimed in claim 54, wherein a first label 

Switched path is established on Said first communication 

path, and Said method further comprises labelling Said data 

with a label defining said first label Switched path at said 

intermediate Switching router. 

56. A method of evaluating a node for re-directing data 

from a first communication path, having a Source node and 

a destination node, along a Second communication path, along a Second communication path, comprising the Steps 

of: 

Selecting a test node on Said first communication path 

between said Source node and Said destination node and 

Said destination node, 

Selecting a test node on Said Second communication path, 

determining the value of a parameter of a test path 

between Said test nodes, and evaluating the test node on 

Said first path for re-directing data to Said Second path 

based on the determined value of Said parameter. 

Apr. 3, 2003 

57. A method as claimed in claim 56, further comprising Selecting a plurality of test nodes on Said first communica 

tion path between said Source node and Said destination 

node, determining the value of a parameter of a test path 

from each of Said plurality of test nodes on Said first 

communication path to Said test node on Said Second com 

munication path, and Selecting one of Said plurality of test 

nodes on Said first communication path for redirecting data 

to Said Second path based on the values of Said parameters. 

58. A method as claimed in claim 57, further comprising extending each test path from each of Said plurality of test 

nodes to an imaginary node by a respective imaginary path, 

and for each of Said plurality of test nodes on Said first 

communication path, determining the value of a parameter 

of Said test path from Said imaginary node to the test node 

on Said Second path, and Selecting a node from Said plurality 

of test nodes on Said first communication path based on the 

values of Said parameters. 

59. A method as claimed in claim 58, further comprising Setting equal values of Said parameter for each of Said 

imaginary paths. 

60. A method as claimed in claim 58, further comprising Setting the value of Said parameter for each of Said portions 

of Said first communication path between adjacent Said test 

nodes on Said first communication path at a value which 

excludes the or each portion from each test path. 

61. A method as claimed in claim 57, further comprising Selecting a plurality of test nodes on Said Second commu 

nication path and determining the value of a parameter of a 

test path between each of Said plurality of test nodes on Said 

first communication path and each of Said plurality of test 

nodes on said Second communication path, and Selecting a 

node for re-directing data to Said Second communication 

path from Said plurality of test nodes on Said first commu 

nication path based on the determined values of Said param 

eter. 

62. A method as claimed in claim 61, further comprising extending each of Said test paths from each of Said test nodes 

on Said Second communication path to an imaginary node by 

a respective imaginary path, and for each of Said plurality of 

test nodes on Said Second communication path, calculating the value of a parameter of the test path from Said imaginary 

node to each of the test nodes on Said first communication 

path, and Selecting a node for directing data to Said Second 

communication path from Said plurality of test nodes on Said 

first communication path based on the values of Said param 

eter. 

63. A method as claimed in claim 62, further comprising Step of Setting Substantially equally values of Said parameter 

for each of Said imaginary paths. 

64. A method as claimed in claim 62, further comprising Setting a value of Said parameter for the portion of Said 

Second path between each adjacent test node on Said Second 

communication path Such that the or each portion of Said 

Second communication path is excluded from each test path. 

65. A method as claimed in claim 61, wherein the step of 

Selecting a plurality of test nodes on Said Second commu 

nication path, comprises Selecting a plurality of test nodes 

connected to three or more communication linkS. 

66. A method as claimed in claim 56, wherein said 

parameter is selected from the group consisting of (a) path length, (b) path cost, (c) path capacity, (d) density of data on 

the path, (e) the number of nodes on the path and (f) the 

number of nodes on the path having three or more commu 

nication linkS. 

67. A method as claimed in claim 57, further comprising Selecting a node for re-directing data to Said Second com 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 34 of 35
US 2003/OO63613 A1 

munication path from Said plurality of test nodes if a test 

path excludes all nodes on Said first communication path 

other than Said plurality of test nodes. 

68. A method as claimed in claim 57, comprising Selecting 

a node for re-directing data to Said Second communication 

path from one of Said Source node and one or more other 

nodes, if any between Said Source node and the first of Said 

plurality of test nodes on Said first communication path if 

each of Said test paths include Said Source node or one or more of Said other nodes or Said destination node. 

69. A method as claimed in claim 68, comprising Selecting 

Said Source node as Said node for re-directing data to Said 

Second communication path if each of Said test paths 

includes Said Source node or Said destination node. 

70. A method as claimed in claim 57, further comprising the Step of Selecting a Second communication path from a 

plurality of communication paths connected to Said desti 

nation node, Such that the Selected Second communication 

path shares the minimum number of communication linkS 

with the first communication path. 71. A method as claimed in claim 70, comprising Selecting 

Said Second communication path Such that Said Second 

communication path shares the minimum number of nodes 

with Said first communication path between Said test node on 

Said communication path and Said destination and Said 

destination node. 

Apr. 3, 2003 

72. A communication network comprising a first commu 

nication path having a Source node and a destination node 

and a plurality of intermediate nodes therebetween, a Second 

communication path connected to Said destination node, and 

wherein an intermediate node on Said first communication 

path includes re-routing means for re-routing data intended 

for continued transmission on Said first communication path 

along Said Second communication path, Said intermediate 

node being Selected from a plurality of Said intermediate 

nodes according to the method as claimed in claim 57. 

73. A method of Selecting an alternative path for carrying 

data intended for transmission along a communication path 

between the Source node and a destination node, comprising Selecting a plurality of alternate paths connected between an 

intermediate node of Said communication path and Said 

destination node, and Selecting from Said plurality of alter 

nate paths, the path which shares the minimum number of 

links with Said communication path between Said interme 

diate node and Said destination node. 

74. A method as claimed in claim 73, further comprising Selecting from Said plurality of alternate paths, the path 

Sharing the minimum number of intermediate nodes with 

Said communication path between Said intermediate node 

and Said destination node. 

Case 6:20-cv-00533-ADA Document 50-1 Filed 04/02/21 Page 35 of 35