idnits 2.17.1 draft-papadimitriou-ccamp-srlg-processing-02.txt: -(1098): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document is more than 15 pages and seems to lack a Table of Contents. == There are 6 instances of lines with non-ascii characters in the document. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 22 longer pages, the longest (page 2) being 59 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The abstract seems to contain references ([CCAMP-SRG], [IPO-FRM]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: Therefore, the proposed SRLG sub-TLVs defined in this document (and included in the top level TE Link TLV) MUST not exceed the maximum OSPF packet size. This limits the number of SRLG identifiers that a sub-TLV can include to approximately 125 (also this number largely depends on the other sub-TLVs included in the corresponding TE opaque LSA constraining to take for the sake of this application a conservative approach). -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 2003) is 7614 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'CCAMP-SRG' is mentioned on line 41, but not defined -- Looks like a reference, but probably isn't: '1' on line 511 -- Looks like a reference, but probably isn't: '3' on line 199 -- Looks like a reference, but probably isn't: '2' on line 511 -- Looks like a reference, but probably isn't: '4' on line 237 == Missing Reference: 'N' is mentioned on line 511, but not defined == Unused Reference: 'IEEE-ORL' is defined on line 740, but no explicit reference was found in the text == Unused Reference: 'MPLS-BDL' is defined on line 766, but no explicit reference was found in the text == Unused Reference: 'RFC-2370' is defined on line 777, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'CROCH' -- Possible downref: Non-RFC (?) normative reference: ref. 'IEEE-ORL' == Outdated reference: A later version (-19) exists of draft-ietf-isis-gmpls-extensions-16 ** Downref: Normative reference to an Informational draft: draft-ietf-isis-gmpls-extensions (ref. 'GMPLS-ISIS') == Outdated reference: A later version (-12) exists of draft-ietf-ccamp-ospf-gmpls-extensions-08 == Outdated reference: A later version (-09) exists of draft-ietf-ccamp-gmpls-routing-05 == Outdated reference: A later version (-05) exists of draft-ietf-ipo-framework-04 ** Downref: Normative reference to an Informational draft: draft-ietf-ipo-framework (ref. 'IPO-FRM') ** Downref: Normative reference to an Informational draft: draft-ietf-ipo-impairments (ref. 'IPO-IMP') == Outdated reference: A later version (-06) exists of draft-ietf-mpls-bundle-04 ** Obsolete normative reference: RFC 2370 (Obsoleted by RFC 5250) Summary: 9 errors (**), 0 flaws (~~), 14 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CCAMP Working Group Dimitri Papadimitriou (Alcatel) 3 Internet Draft Fabrice Poppe (EPO) 4 Expires: December 2003 Sudheer Dharanikota (Consult) 5 Riad Hartani (Caspian) 6 Raj Jain (Nayna) 7 Jim Jones (Alcatel) 8 Senthil Venkatachalam (OPNet) 9 Yong Xue (WorldCom) 11 June 2003 13 Shared Risk Link Groups Inference and Processing 15 draft-papadimitriou-ccamp-srlg-processing-02.txt (*) 17 Status of this Memo 19 This document is an Internet-Draft and is in full conformance with 20 all provisions of Section 10 of RFC2026. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF), its areas, and its working groups. Note that 24 other groups may also distribute working documents as Internet- 25 Drafts. Internet-Drafts are draft documents valid for a maximum of 26 six months and may be updated, replaced, or obsoleted by other 27 documents at any time. It is inappropriate to use Internet-Drafts as 28 reference material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 (*) Formerly draft-many-inference-srlg-02.txt 38 Abstract 40 The Shared Risk Link Group (SRLG) concept introduced in [IPO-FRM] 41 and extended in [CCAMP-SRG] is considered as one of the most 42 important criteria concerning the constraint-based path computation 43 of optical channel routes. By applying the SRLG disjointness 44 criteria to the constraint-based path computation, one can select a 45 route taking into account both resource and logical structure 46 disjointness. That implies a lower probability of simultaneous 47 optical channel failure. 49 This document describes the various physical and logical resource 50 types considered in the SRLG concept. The proposed method focuses on 52 D.Papadimitriou et al. - Expires December 2003 1 53 the inference of SRLG information between the network physical and 54 logical layers. The main applications of the proposed model are 55 related to the Constraint-based Shortest Path First (CSPF) algorithm 56 for optical channel route computation and the aggregation of the 57 SRLG information flooded throughout traffic engineering extensions 58 of the IGP routing protocols (such as OSPF and IS-IS). 60 1. Introduction 62 Many proposals include the Shared Risk Link Group (SRLG) concept 63 when considering the disjointness for the constraint-based path 64 computation of optical channel routes. In the optical domain, the 65 SRLG concept is used for deriving a path, which is disjoint with 66 respect to physical (or passive) and logical (or active) resources. 67 [CROCH] describes algorithms that can use the SRLG information 68 inferred using the mechanisms described in this document, in order 69 to determine survivable logical topologies on top of a given 70 physical topology. 72 The corresponding requirements have already been described in [IPO- 73 IMP] while considering physical network topology and associated 74 risks. In the scope of this document, these requirements can be 75 summarized as follows: 76 1. The SRLG encoding mechanism should reduce the path computation 77 complexity. 78 2. The SRLG information flooding should be scoped to reduce the 79 amount of information that is exchanged across domains. 80 3. The SRLG encoding should accommodate the physical and logical 81 restrictions imposed on the diversity requirements. 83 However, the definition of SRLG in the current format described in 84 [GMPLS-OSPF] and [GMPLS-ISIS] does not provide: 85 1. The relationship between physical (or logical) resources and 86 between physical and logical resources. For example, a fiber 87 could be part of a sequence of fiber segments or an optical 88 channel may cover several fibers links. 89 2. The risk assessment during path computation implying the 90 assignment of a conditional failure probability to the SRLGs. 91 3. The analysis of the specifics aspects of constraint-based path 92 computation and path re-optimization taking SRLG information into 93 account. 95 This document proposes among others a technique to compute the SRLG 96 with respect to a given risk type. This is achieved by identifying 97 for a given physical layer the resources belonging to an SRLG. The 98 proposed model also permits to compute the dependencies of these 99 resources to the lower (passive) physical layers. The result of the 100 computation also enables to determine the risk associated to each of 101 the SRLGs, that is, the probability that two entities (both using 102 network resources belonging to a given SRLG) go simultaneously down 103 if one of them goes down (thus defining a conditional failure 104 probability). 106 D.Papadimitriou et al. - Expires December 2003 2 107 The remainder of this memo is organized as follows. In section 3, we 108 present the hierarchical model of the network resources and the 109 corresponding SRLG encoding. In section 4, we discuss the use of the 110 proposed approach for risk assessment during path computation and 111 selection. Considerations on topology summarization and path 112 disjointness with respect to SRLG are proposed in section 5. 114 2. Conventions used in this document 116 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 117 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 118 this document are to be interpreted as described in RFC-2119 [1]. 120 The reader is assumed to be familiar to the terminology and concepts 121 detailed in [GMPLS-RTG], [GMPLS-OSPF] and [GMPLS-ISIS]. 123 3. Hierarchical Model 125 The proposed approach is based on a representation of the network 126 resources in terms of a hierarchy. This hierarchical structure is 127 related to the fiber topology (or more generally the physical 128 resources) of the optical network and the channels built on top of 129 this physical topology. 131 The encoding of the SRLG could be either mapped on this hierarchical 132 model or simply use a flat encoding scheme. Difference between both 133 encoding relies on the extended usage of the SRLG identifiers in the 134 context of diverse route computation (i.e. path disjointness). Since 135 a link can belong to more than one SRLG, an SRLG identifier list (in 136 the SRLG Sub-TLV), as described in [GMPLS-OSPF] and [GMPLS-ISIS] is 137 associated with each link (i.e. the SRLG Sub-TLV is defined as a 138 Sub-TLV of the TE Link TLV). This results in a linear, unordered and 139 non-structured information from which the underlying structure 140 cannot be deduced. 142 Consequently, either a type field indicating the type of network 143 resource (or logical structure) to which this SRLG identifier refers 144 extends the flat encoding scheme or the encoding itself translates 145 the underlying hierarchical structure. Worth mentioning here is that 146 a hierarchical encoding (since depending on the physical layer which 147 is static by definition) needs an additional mapping structure in 148 order to keep the relationship with link identifiers. 150 3.1 Network Resource Hierarchy 152 The network (physical and logical) resource model considered in the 153 inference of the Shared Risk Link Groups (SRLGs) is based on 154 premises detailed in [IPO-FRM] and [IPO-IMP]. The network resource 155 hierarchy includes the logical resources built on top of the 156 physical resource hierarchy belonging to the optical network. 158 The concepts around network resource hierarchy are based on the 159 following logical resource definitions: 161 D.Papadimitriou et al. - Expires December 2003 3 162 - Sub-Channel: a dedicated container included within a given optical 163 channel uniquely identifies a sub-channel. 165 - Channel(*): an optical channel is uniquely identified by its 166 corresponding and dedicated wavelength (sub-)interface identifier. 168 (*) when conversion or amplification is non-collocated with the 169 corresponding interface capability, the passive components are 170 logically embedded into the fiber link (see below definition). 172 These resources are built on top of the physical resource hierarchy 173 composed by the following physical resources considered as a common 174 denominator of most Optical Transport Network (OTN) environments: 176 - Fiber Link: a fiber connects two node ports communicating through 177 one or more optical channel if their interfaces support (Dense) 178 Wavelength Division Multiplexing � (D)WDM, also a fiber link can 179 be decomposed as a sequence of fiber spans separated by optical 180 amplifiers 182 - Fiber Segment: a group of fiber links, any fiber link of a 183 segment start and terminates at the same physical location 185 Moreover, one can consider sequences of fiber segment starting and 186 terminating at the same node and defined them as fiber trunks (also 187 referred to as cable or fiber duct). 189 Thus, the approach developed here extends the definition and 190 concepts given in [IPO-FRM] and [IPO-IMP] by enabling fiber 191 topologies not strictly limited to point-to-point physical inter- 192 connections between nodes. 194 As represented in Figure 1, the fiber trunk going from location N[1] 195 to location N[3] is composed by the fiber segments A and B and the 196 fiber trunk from location N[1] to location N[2] includes the fiber 197 segments A, C and D. 199 Location N[1] Location N[3] 201 Segment A[1] Segment B[1] 202 --------------------------------------------------------------- 203 === . . . ====== Fiber Fiber ====== . . . ==== 204 === . . . ====== Fiber Fiber ====== . . . ==== 205 -------------------------------------------------------------- 206 Segment A Segment B 207 ------------------------------ ----------------------------- 208 === . . . ====== Fiber | | Fiber ====== . . . ==== 209 === . . . ====== Fiber | | Fiber ====== . . . ==== 210 ------------------------- | | ------------------------- 211 Segment A[n] | | | | Segment B[n] 212 | | | | 213 | | | | Segment C 215 D.Papadimitriou et al. - Expires December 2003 4 216 | | | | 217 Segment D[1] | | | | Segment E[1] 218 ------------------------- | | ------------------------- 219 === . . . ====== Fiber | | Fiber ====== . . . ==== 220 === . . . ====== Fiber | | Fiber ====== . . . ==== 221 ------------------------------ ------------------------------ 222 Segment D Segment E 223 --------------------------------------------------------------- 224 === . . . ====== Fiber Fiber ====== . . . ==== 225 === . . . ====== Fiber Fiber ====== . . . ==== 226 --------------------------------------------------------------- 227 Segment D[n] Segment E[n] 229 Location N[2] Location N[4] 231 Figure 1. Example of Physical Topology 233 In this figure, the Segment A is composed by the fiber segments 234 A[1], A[2], ..., A[i], ..., A[n]. The same terminology applies for 235 the segments B, C, D and E. 237 Consequently, the fiber trunk from location N[2] to location N[4] 238 includes the segments D[2] to D[n] and their corresponding segments 239 within the segment E: E[2] to E[n]. The fiber trunk from location 240 N[1] to location N[2] includes the fiber segments A[n], C[1] and 241 D[1]. 243 3.3 SRLG Definition and Properties 245 A SRLG is defined as the set of links (or optical lines) sharing a 246 common physical resource (including fiber links and segment) i.e. 247 sharing a common risk. For instance, a set of links L belongs to the 248 same SRLG s, if established over the same fiber link l. 250 3.3.1 SRLG Properties 252 The SRLG properties can be summarized as follows: 254 1) A link belongs to more than one SRLG if and only if it crosses 255 (at least) one of the resources covered by each of these SRLGs 257 For instance: fiber link l belongs to the SRLG s1 and s2, if and 258 only if it crosses the fiber segment A[1] and B[1] 260 2) Two links belonging to the same SRLG can belong individually to 261 other (one or more) SRLGs 263 For instance: fiber links l1 and l2 belong to SRLG s3 (segment A) 264 while l1 belongs to SRLG s1 (since it covers segment A[1]) and l2 to 265 SRLG s4 (since it covers segment D[1]) 267 3.4.2 SRLG Disjointness 269 D.Papadimitriou et al. - Expires December 2003 5 270 To define the LSP SRLG disjointness notion, we first introduce the 271 following definition: an LSP (i.e. sequence of links) covers an SRLG 272 if and only if it crosses one of the links belonging to that SRLG. 273 For instance: LSP p1 covers SRLG s1 (since it crosses link l1) 275 LSP SRLG disjointness can then be defined as follows. 277 1) Two LSPs are disjoint with respect to an SRLG s1 if and only if 278 at most one of them covers this SRLG. 280 For instance: LSPs p1 and p2 are disjoint with respect to SRLG s1 281 since only p1 covers SRLG s1. 283 2) Two LSPs are disjoint with respect to a set of SRLG S if and only 284 if the sets of SRLGs they individually cover are completely disjoint 286 For instance: LSP p1 and p3 are disjoint with respect to set of SRLG 287 S = {s1, s2, s3} since only p1 covers SRLG set S. 289 3.5 Computational Model Capabilities 291 This section briefly describes guidelines for an SRLG computational 292 model described in appendix A and based on the above definitions. 293 The main features of this model are: 295 - Support Constraint-based Shortest Path First (CSPF) algorithm for 296 explicit route (or path) computation by considering SRLG 297 disjointness with respect to one or more risk types 299 - Encompass hierarchical dependencies between physical resources 300 (inference of SRLG sets using bottom-up computation) 302 - CSPF computation including the relationship between physical 303 resources and topological structures. For instance: 304 . a fiber link can be part of given fiber trunk 305 . a fiber cable passing through an earthquake region 307 - Provide risk assessment during path computation implying 308 allocation of conditional failure probabilities with SRLGs 310 - SRLG information flooding well-scoped to reduce the amount of 311 link-state advertisements by using summarization 313 Consequently, the above features suggest an SRLG encoding mechanism 314 that enables: 315 - Accommodation of the physical and topological hierarchies 316 - Reduction of the path (i.e. explicit route) optimality 318 3.6 SRLG Encoding 320 Using the above definitions and properties, the objective of the 321 hierarchical encoding is to achieve aggregation of the SRLG 322 Identifiers on top of the (passive) optical network topology. For 324 D.Papadimitriou et al. - Expires December 2003 6 325 this purpose, we propose a linear encoding scheme including a type 326 field. This provides abstraction of the physical layer structure and 327 should facilitate the management of the SRLG Identifiers. 329 The proposed SRLG sub-TLV of the TE Link top level TLV includes the 330 following SRLG Identifier (64-bit field): 332 0 1 2 3 333 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 334 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 335 | Type | Weight | 336 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 337 | Identifier | 338 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 340 Within the SRLG Identifier field (64 bits), the Type field (8 bits) 341 defines the resource type (also generically referred to as the link 342 type) to which the Identifier (32 bits) integer value refers. The 343 weight field (24 bits) assigned on a per-SRLG basis along with the 344 Identifier is defined in Section 4. 346 The following Type field values are currently defined for physical 347 resources, any other value being reserved: 349 Type Value 350 -------------------- ------ 351 Reserved 0x00 352 Fiber Trunk 0x10 353 Fiber Segment 0x20 354 Fiber Link 0x30 355 Node(*) 0xFF 357 (*) represents a non-GMPLS capable switching elements 359 Logical resources such as optical channels, high order and low order 360 TDM circuits (or optical sub-channels) can take one of the following 361 values: 363 Type Value 364 ------------------- ------ 365 Optical Channel 0x50 366 Optical Sub-Channel (High) 0x60 367 Optical Sub-Channel (Low) 0x70 369 Since a given physical or logical resource (for instance a fiber 370 link) can belong to more than one SRLG, the SRLG Identifier 371 structure is defined in the general case as a list of SRLG 372 Identifier (n x 64-bit): 374 0 1 2 3 375 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 376 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 377 | Type | Weight | 379 D.Papadimitriou et al. - Expires December 2003 7 380 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 381 | Identifier | 382 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 383 | | 384 // ... // 385 | | 386 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 387 | Type | Weight | 388 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 389 | Identifier | 390 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 392 Therefore, though we propose a linear encoding, the aggregation of 393 the SRLG is still possible. This encoding also enables to perform 394 summarization (which is not equivalent to aggregation) at the 395 boundaries of structures defining the spatial coverage of an SRLG 396 Identifier list while overcoming the drawbacks of full hierarchical 397 encoding schemes. In this context, the weight value follows the 398 rules defined in the Section 4. 400 4. Risk Assessment 402 Risk assessment is defined as the quantification process of the 403 potential risk associated to the inclusion of a given resource 404 (belonging to a given resource type) located within a given logical 405 structure such as a geographical location for a given logical 406 network resource such as an optical channel. 408 4.1 Rationale for Risk Assessment 410 Consider the following example, where the client device makes the 411 following connection requests to the optical network: 413 - Request for a persistent connection with 99.999 % percent of 414 availability or equivalently a downtime less than X minutes per 415 year. 417 - Request for protection for a portion of the traffic (at the 418 expense of more charging) compared to other portion of the 419 traffic left unprotected and considered as extra traffic by the 420 server. 422 Such requirements will be translated into path specific requests. 423 Such path specific requests can be grouped into path selection 424 requirements and path characterization requirements. 426 1. Path selection requirements 428 These typically dictate which physical path should be taken to 429 achieve the availability requirements of the client request. These 430 requirements are typically related to the logical and physical 431 diversity as mentioned in Section 3. 433 D.Papadimitriou et al. - Expires December 2003 8 434 2. Path characterization requirements 436 Path characterization requirements typically dictate the recovery 437 mechanisms as specified by the client connection request. This can 438 be achieved in the form of section and/or path recovery but also 439 depending on the ring or meshed topology of the optical network. 440 However, these considerations are out of the scope of this document. 442 The components that need formalization in this example are: 443 - Step 1. Specification of the client requirements (service level). 444 - Step 2. Configuration of the network that helps in assessing the 445 service specifics such as the availability. 446 - Step 3. Propagation of the above-configured information. 447 - Step 4. Processing of the above-propagated information. 449 Step 1 of specifying the requirements is not in the scope of this 450 document. Steps 2 to 4 are discussed in the following sections where 451 we elaborate on the risk assessment during path selection. 453 4.2 Risk Assessment 455 Risk (the complementary of availability) assessment is defined as 456 the evaluation of the potential risk associated to the inclusion for 457 a given path of a specific network resource (i.e. belonging to a 458 given resource type). Given that an SRLG Identifier list is used to 459 encode the group of logical and physical resources, if a mechanism 460 is devised to assign the risk of failure associated with the 461 corresponding resource, the availability of the path using these 462 resources can be computed. This, in order to meet the connection 463 availability as requested by the client request. 465 A simple approach is to assign the conditional failure probability 466 to each of the SRLG Identifiers. This information is encoded in the 467 weight (24 bits) field along with the SRLG information as defined in 468 Section 3.3. The associated weights can be used to either increase 469 or decrease the potential usage of the resource (i.e. inclusion into 470 the selected route). The Weight field is defined as a 24-bit length 471 encoded integer number (maximum value 2^24 - 1) to be divided by 472 (2^24 � 1) and multiplied by 100 to get the corresponding value in 473 percents. For instance a conditional failure probability of 0.99999 474 corresponds to a weight of 16.777.047 and 0.00005 to 839. 476 For instance, we can associate a conditional failure probability of 477 25% (weight = 4.194.304) to any fiber segment. It means that by 478 selecting two (or more than two) different optical channel paths 479 including the same SRLG identifier with respect to fiber segment 480 failure, if one of these connections fails, then the probability 481 that the other connection fails is 25%. 483 The failure probability of a fiber can also depend on the length of 484 the fiber. In addition, a fiber can pass across different regions 485 with different failure probabilities. In this case, we need to 487 D.Papadimitriou et al. - Expires December 2003 9 488 consider an aggregated failure probability per fiber taking into 489 account each of the failure probabilities of its sub-components. 491 For instance, if we refer to our previous example and by considering 492 1. a conditional failure probability of 5% is associated to any 493 fiber link 494 2. a conditional failure probability of 1% is associated to any 495 fiber segment 497 Then by selecting two different optical channels included within the 498 same SRLG with respect to fiber segment failure, we obtain a 499 simultaneous connection failure probability of 1%. Consequently, 500 when a protected connection service is requested, by choosing fiber 501 segment path disjointness, the simultaneous connection failure 502 probability is also of 1%. However, if two optical channels flowing 503 through the same fiber link are selected, then we have a probability 504 of 5% that both optical channels fail simultaneously. 506 More generically, if one assigns a conditional failure probability 507 c[i] to each SRLG Identifier i, the resulting conditional failure 508 probability C for a logical resource (a connection, for instance) 509 using these N resources is given by: 511 C = 1 - (1 � c[1]) x (1 � c[2]) x . . . x (1 � c[N]) 513 When all the conditional failure probabilities c[i] are small (i.e. 514 c[i] << 1) C can be approximated by (1 - Sum[i]c[i]). 516 4.3 Risk Assessment Application 518 The relationship between the availability of the service requested 519 by the client (i.e. a working and a protection connection) and the 520 conditional failure probabilities of the physical resource elements 521 included within the corresponding paths can be described as follows. 523 If we consider for instance 1) a conditional failure probability of 524 1% if fiber links are selected within the same fiber trunk 2) a 525 conditional failure probability of 1% if fiber links are selected 526 within the same fiber segment and 3) the corresponding failure are 527 independent events. 529 Then the availability of a connection whose backup is established 530 over fiber links (in same fiber segment) and within the same fiber 531 trunks as the primary connection itself is approximately 98% (by 532 using the above formula). 534 Note that the initial value of the conditional failure probability 535 needs to be statically encoded; however, based on the history of the 536 failures these values could be dynamically re-evaluated. The 537 corresponding mechanism needs to be specified and is left for 538 further study. 540 5. Applications 542 D.Papadimitriou et al. - Expires December 2003 10 543 The SRLG method developed here results in applications related to 544 the CSPF explicit route computation and the SRLG identifier sets 545 summarization. The latter enables in turn, intra- and inter-area 546 diverse path computation. For that purpose we first extend the SRLG 547 concept for logical resources such as optical channels and optical 548 sub-channels (i.e. TDM connections). 550 5.1 Extension to the Logical Resources 552 The SRLG concept can be extended to logical structures and resources 553 by taking into account the following: 555 1. Given the physical decomposition of the optical network 556 topology, the SRLG encoding can be hierarchically structured. 557 The hierarchical encoding helps in constructing the logical 558 topology abstraction, which in turn can be used in SRLG 559 summarization and loose-path computation. The link semantic may 560 also be extended to accommodate virtual links. 562 2. Propagate the SRLG information related to these logical 563 (structures and resources) links, for instance (a set of) 564 optical channels using IGP flooding for intra- and inter-area 565 routing purposes. 567 3. Reduce the amount of the flooded information and hence explicit 568 route computation optimality and extend the flooding scope of 569 the propagated information to accommodate logical resources 570 (i.e. optical channels and TDM circuits). 572 5.2 SRLG Information Flooding 574 The SRLG set of each link (i.e. physical and logical resources) is 575 encoded as described in Section 3.3. This information is propagated 576 once at initial configuration between the various nodes using the 577 GMPLS Traffic Engineering extensions to IGPs (see [GMPLS-OSPF] and 578 IS-IS [GMPLS-ISIS]). After this initial SRLG identifier exchange, 579 corresponding values do not change over time. 581 Nevertheless, the propagation of SRLG information will be necessary 582 whenever a new link is added or an existing link is removed. 583 Initially, it is assumed that the failure probabilities of the 584 various resources are (statically) configured. However, it is 585 envisioned that after a certain running period, the failure 586 probability associated to the SRLG and propagated along with the 587 SRLG sub-TLV itself (as described in Section 3.3) will change over 588 time and thus give rise to a dynamic metric. 590 5.3 Bottom-Up Computation of SRLG Relationships 592 Once nodes receive the TE link information, the corresponding SRLG 593 relationships can be computed on a regular basis. 595 D.Papadimitriou et al. - Expires December 2003 11 596 The fiber trunk SRLG relationships are used to compute the fiber 597 segment SRLG relationships, which in turn are used to compute the 598 fiber segment SRLG relationships and finally the fiber SRLG 599 relationships. To each SRLG relationship (at each level), which 600 defines the membership of a resource to a particular SRLG, we 601 associate the conditional failure probability between two resources 602 belonging to this level (for instance, between two fibers that have 603 a common fiber segment). 605 5.4 Topology Summarization and Route Computation 607 A direct application of this model is the Constraint-based Shortest 608 Path First (CSPF) algorithm used for explicit route computation 609 (i.e. traffic-engineered LSP creation) to maximize the connection 610 disjointness and so decrease their common failure probability. Given 611 an existing set of connections across the network, the objective is 612 to compute, for a newly requested connection, an explicit route 613 across the optical network topology such that this connection is 614 diversely routed from an existing given set of connections. 616 The diversity requirement is a routing constraint, that can be 617 expressed in terms of a conditional failure probability with respect 618 to an existing (set of) connections and more generally any kind of 619 resources. Hence, in addition to the other traffic-engineering 620 constraints, the diversity constraint requires that the conditional 621 failure probability does not exceed a given threshold. The CSPF 622 algorithm needs to be updated to take the routing diversity 623 constraint into account. 625 The SRLG concept generates another dimension to the existing 626 constraint-based path computation methods traditionally used in 627 hierarchical networks. The SRLG constraints comes in addition to the 628 common traffic-engineering constraints such as bandwidth 629 availability, link metrics and TE attributes (see [OSPF-TE]). The 630 specificity of the routing diversity constraint requires the use of 631 a path computation algorithm that provides not only complete multi- 632 path disjointness but also partial multi-path disjointness with 633 respect to various risk factors. In a similar way, appropriate 634 mechanisms should also be used in order to perform path re- 635 optimization following various recovery strategies. 637 The specific aspect of complete and partial multi-path disjointness 638 is related to the fact that a path may with respect to SRLG be fully 639 or partially disjoint from a given set of path. In brief, one speaks 640 about SRLG partial or full multi-path disjointness. This means that 641 a connection may be disjoint from another but only to some extent 642 with respect to some risk factors. Thus when referring to path 643 disjointness with respect to SRLG one may also include the ratio of 644 disjointness with respect to various risk type assigned to their 645 component resources. Consider for instance the LSPs p1 and p2 using 646 j1 and j2 resources respectively, m of these resources having an 647 SRLG in common, with m =< j1 and m =< j2, then [(j1-m) + (j2- 648 m)]/(j1+j2) provides the disjointness ratio. For instance, if j1=13, 650 D.Papadimitriou et al. - Expires December 2003 12 651 j2=7 and m=1, this ratio equals 0.90, thus corresponding path p1 and 652 p2 are SRLG disjoint at 90%. 654 As such, this feature differentiates path disjointness constraint 655 from any other constraint commonly considered in path computation. 657 6. Scalability Considerations 659 6.1 OSPF Scalability Considerations 661 A node SHOULD minimize the amount of routing information it floods. 662 Each time a SRLG sub-TLV is configured or removed that information 663 shall be flooded (not necessarily immediately) to all nodes in the 664 routing domain. This results in updating an existing LSA or flushing 665 an existing LSA. Removing an LSA from the (TE) Link State DataBase 666 (TE LSDB) can be accomplished in OSPF by prematurely aging the LSA. 667 The LSA is re-flooded with an LSA age equal to MaxAge. Each node 668 receiving an existing LSA with MaxAge removes it from its link state 669 database. 671 Also, the usage of OSPF implies each LSA must be refreshed 672 periodically (when the LSA age field reaches the LSRefreshTime, see 673 [RFC-2328]) to avoid age timeout and removal from the link state 674 database. This periodical LSA flooding and processing applies 675 particularly to the TE link capability sub-TLVs defined in this 676 document since their variation period is expected to be much larger 677 than the LSRefreshTime. 679 An Opaque LSA has a length field of 16 bits indicating the length of 680 the LSA, including the header. Thus, the length of OSPF packets can 681 be up to 65535 octets (including the IP header). Moreover, an OSPF 682 packet can contain several (Opaque) LSAs. OSPF relies if necessary 683 on the IP fragmentation to transmit large packets without any loss 684 of functionality. However this is not recommended and it is 685 suggested to split packets that are too large into several smaller 686 packets. 688 Therefore, the proposed SRLG sub-TLVs defined in this document (and 689 included in the top level TE Link TLV) MUST not exceed the maximum 690 OSPF packet size. This limits the number of SRLG identifiers that a 691 sub-TLV can include to approximately 125 (also this number largely 692 depends on the other sub-TLVs included in the corresponding TE 693 opaque LSA constraining to take for the sake of this application a 694 conservative approach). 696 6.2 IS-IS Scalability Considerations 698 TBD. 700 7. Compatibility Considerations 702 7.1 OSPF Compatibility Considerations 704 D.Papadimitriou et al. - Expires December 2003 13 705 There should be no interoperability issues with GMPLS-capable nodes 706 that do not implement the proposed SRLG extensions since the sub- 707 TLVs proposed in this document is optional and thus will be silently 708 ignored. 710 The result of having such nodes that do not implement the proposed 711 SRLG extensions is largely detailed in this memo. However, SRLG 712 constraint paths can still be calculated using the SRLG sub-TLVs as 713 proposed in [GMPLS-OSPF] (referred here as Type 1). It is assumed 714 that nodes supporting SRLG encoding and processing as proposed in 715 this document (referred here as Type 2) do also support the [GMPLS- 716 OSPF] one. Therefore, if the nodes simultaneously adjacent to Type 1 717 and Type 2 only encoding supports both, no interoperability issues 718 should arise from running both types in the same routing area. 720 The present document also mandates that these sub-TLVs are mutually 721 exclusive i.e. they MUST never appear simultaneously as sub-TLV of 722 the same top level Link TLV [OSPF-TE]. 724 7.2 IS-IS Compatibility Considerations 726 TBD. 728 8. Security Considerations 730 Security considerations related to SRLG and related applications are 731 left for further study. 733 9. References 735 [CROCH] O.Crochat, J.-Y. Le Boudec and O. Gerstel, "Protection 736 Interoperability for WDM Optical Networks," IEEE/ACM 737 Transactions on Networking, Vol. 8, No. 3, June 2000, 738 pp. 384-395. 740 [IEEE-ORL] J.Strand et al., "Issues for Routing in the Optical 741 Layer," IEEE Communication Magazine, Volume 39, Number 742 2, Feb�01. 744 [GMPLS-ISIS] K.Kompella et al., "ISIS Extensions in Support of 745 Generalized MPLS," Internet Draft, Work in Progress, 746 draft-ietf-isis-gmpls-extensions-16.txt. 748 [GMPLS-OSPF] K.Kompella et al., "OSPF Extensions in Support of 749 Generalized MPLS," Internet Draft, Work in Progress, 750 draft-ietf-ccamp-ospf-gmpls-extensions-08.txt. 752 [GMPLS-RTG] K.Kompella et al., "Routing Extensions in Support of 753 Generalized MPLS," Internet Draft, Work in Progress, 754 draft-ietf-ccamp-gmpls-routing-05.txt. 756 D.Papadimitriou et al. - Expires December 2003 14 758 [IPO-FRM] J.Luciani et al., "IP over Optical Networks A 759 Framework," Internet Draft, Work in progress, draft- 760 ietf-ipo-framework-04.txt. 762 [IPO-IMP] J.Strand et al., "Impairments And Other Constraints On 763 Optical Layer Routing," Internet Draft, Work in 764 progress, draft-ietf-ipo-impairments-05.txt. 766 [MPLS-BDL] K.Kompella et al., "Link Bundling in MPLS Traffic 767 Engineering", Internet Draft, Work in progress, draft- 768 ietf-mpls-bundle-04.txt. 770 [OSPF-TE] D.Katz, D.Yeung and K.Kompella, "Traffic Engineering 771 Extensions to OSPF," draft-katz-yeung-ospf-traffic- 772 10.txt, Internet Draft, Work in Progress. 774 [RFC-2328] J.Moy, RFC 2328, "OSPF Version 2," STD 54, IETF 775 Standard Track, April 1998. 777 [RFC-2370] R.Coltun, RFC 2370, Standard Track, "The OSPF Opaque 778 LSA Option," July 1998. 780 10. Acknowledgments 782 The authors would like to thank Bernard Sales, Emmanuel Desmet and 783 Gert Grammel for their constructive comments, David Griffith for its 784 active contribution and Bart Rousseau for its revision efforts. 786 11. Author's Addresses 788 Dimitri Papadimitriou (Editor) 789 Francis Wellesplein, 1 790 B-2018 Antwerpen, Belgium 791 Phone: +32 3 240-8491 792 Email: dimitri.papadimitriou@alcatel.be 794 Fabrice Poppe (EPO) 795 Email: fpoppe@epo.org 797 Jim Jones (Alcatel) 798 3400 W. Plano Parkway, 799 Plano, TX 75075, USA 800 Phone: +1 972 519-2744 801 Email: jim.d.jones@alcatel.com 803 Senthil Venkatachalam (OPNet) 804 Email: svenkatachalam@opnet.com 806 Sudheer Dharanikota (Consulting) 807 Email: sudheer@ieee.org 809 Raj Jain (Nayna Networks) 810 157 Topaz St., 812 D.Papadimitriou et al. - Expires December 2003 15 813 Milpitas, CA 95035, USA 814 Phone: +1 408 956-8000X309 815 Email: raj@nayna.com 817 Riad Hartani (Caspian Networks) 818 170 Baytech Drive, 819 San Jose, CA 95134, USA 820 Phone: +1 408 382-5216 821 Email: riad@caspiannetworks.com 823 Yong Xue (WorldCom) 824 Ashburn, VA, USA 825 Phone: +1 703 886-5358 826 Email: yong.xue@wcom.com 828 D.Papadimitriou et al. - Expires December 2003 16 829 Appendix A: SRLG Computational Model 831 A.1 SRLG Concept and Example 833 The present model is intended to be used to automate the discovery 834 of the Shared Risk Link Groups (SRLGs) at a given layer for a given 835 physical resource type. 837 Note that a typical resource type can be a fiber, a fiber segment, 838 or a fiber trunk. SRLG definition and properties were described in 839 Section 3. 841 Example: 843 The following example referring to Figure 5 (for the physical 844 network topology) offers some clarification. Let assume that 845 - N1, N2, N3, and N4 represent locations that are linked by the 846 fiber segments, 847 - A, B, C, D and E be fiber segments, 848 - and F1 (ACD), F2 (AB), F3 (BCD) and F4 (DE) are fiber links routed 849 over the fiber segment topology. 851 N1 N2 852 | | 853 | | F1 854 |A |D N1 ------------ N2 855 | | | | 856 | | | | 857 | C | | | 858 x-------------x |F2 |F4 859 | | | | 860 | | | | 861 | | | F3 | 862 |B |E N3 ------------ N4 863 | | 864 | | 865 N3 N4 867 Figure 4. Correlation between Fiber segment and Fiber link topology 869 In such a physical topology the obvious SRLGs are the following: 870 - {F1, F2} both going down when segment A breaks 871 - {F1, F3} both going down when segment C breaks 872 - {F1, F4} both going down when segment D breaks 873 - {F2, F3} both going down when segment B breaks 874 - {F3, F4} both going down when segment E breaks 876 These five SRLGs can be replaced by two SRLGs, S1 = {F1, F2, F3} and 877 S2 = {F1, F3, F4}, where S1 and S2 constitute the minimum edge 878 covering with cliques of the Shared Risk Relationship (SRR) graph 879 that can be drawn between F1, F2, F3, F4 (see Figure 5). A clique of 880 a graph G is a sub-graph of G in which every two nodes are connected 882 D.Papadimitriou et al. - Expires December 2003 17 883 by an edge. This decomposition is unique. If there was an additional 884 dependency between F2 and F4, there would be a unique SRLG, S = {F1, 885 F2, F3, F4}. 887 F1 ------- F4 888 | \ | 889 | \ | 890 | \ | 891 | \ | 892 | \ | 893 | \ | 894 | \ | 895 F2 ------- F3 897 Figure 5. SRR Graph between fiber link and segment 899 Although R1 = F1-F2-F3 and R2 = F4 are diverse path between 900 locations N2 and N4 in the fiber topology (link and node 901 disjointness), they are not diverse with respect to SRLGs. This is 902 because both R1 and R2 cover SRLG S2, which contains F1, F3 (part of 903 R1) and F4 (part of R2). SRLGs are thus a way of formalizing the 904 propagation of (link-based) risk dependencies from server to client 905 layers. 907 The rules guiding the definition of minimum set of SRLGs for more 908 complex physical network topologies will be addressed in a future 909 version of this document. 911 A.2 Risk Type 913 As specified up to now, the current approach considers that each of 914 the network resource may experience one or more failure type(s). The 915 same applies to geographical locations: a given location might 916 experience one or more failure types. Moreover, by applying the SRLG 917 properties, a network resource failure can potentially cover more 918 than one geographical location. Consequently, some heuristics must 919 be introduced to keep the SRLG computational complexity limited. 921 In order to limit the computational complexity, we define the 922 following heuristics when considering the SRLG computation with 923 respect to the type of risk: 925 1. The set of risk types associated to network resources corresponds 926 exactly to the set of resource type failure. 927 - So, for instance, the risk type associated to a fiber segment 928 is a fiber segment failure. The same principle applies for 929 other network resources such as fiber link, fiber segment and 930 fiber trunk. Consequently, the current approach does not 931 consider a finest granularity for the network resource failure 932 than the one referred by their type. 934 2. A risk type associated to a geographical structure covers exactly 935 the region where it is defined. Moreover, a geographical failure 937 D.Papadimitriou et al. - Expires December 2003 18 938 is limited to a given location and does not contaminate the 939 neighboring locations or generate another failure 940 - For instance, we consider that an earthquake covers exactly 941 one region or one area and that such a failure does not 942 generate a hurricane impacting the neighboring locations. So, 943 there is no correlation between geographical failures. 945 3. Each of the network resources covers exactly one geographical 946 logical structure. 947 - Consequently, when a geographical failure occurs, it 948 generates a failure impacting the entire network resources 949 included within the corresponding location. Hence, there is 950 an ON/OFF relationship between geographical and network 951 resource failures. 953 Consequently, when considering network resources, the risk type 954 associated to an SRLG is defined as the potential failure of one (or 955 more than one) instance belonging to a given resource type or the 956 potential failure of any of its hierarchical resource dependence. 958 Thus, we define the concept of SRLG with respect to a given resource 959 type and subsequently to the Risk Type (RT) to which this resource 960 type refers. Moreover, for a given resource type (or class), each of 961 the resources are identified by a Resource Identifier (RID). Since 962 each of these resource classes corresponds to an SRLG class, we can 963 assign an identifier to each of the SRLG classes members and define 964 their value as the SRLG identifier. 966 Moreover, by applying the defined heuristics above, the SRLG 967 identifiers can be grouped together by taking into account their 968 geographical location. The latter is encoded by identifying the 969 region identifier (region ID) including the resource identifiers to 970 which the SRLG refers. 972 A.3 Calculation of Shared Risk Link Groups 974 In the calculation method, shared-risk(RID i, RID j, RT) is TRUE 975 only if the resource identifiers RID i and RID j belong to the same 976 SRLG with respect to the risk type RT. The risk types considered 977 here are related the fiber segment, and the fiber link risk failure. 979 A recursive calculation of shared-risk proceeds as follows: 981 shared-risk(RID i, RID j, RT) = 982 at-risk(RID i, RT) 983 and at-risk(RID j, RT) 984 and (RID i = RID j 985 or (exists RID k, RID l 986 such that 987 depends-on(RID i, RID k) 988 and depends-on(RID j, RID l) 989 and shared-risk(RID k, RID l, RT))) 991 D.Papadimitriou et al. - Expires December 2003 19 992 In this calculation: 993 - at-risk(RID i, RT) is TRUE only if RID is susceptible to a risk of 994 type RT, either directly, or indirectly, through the failure of 995 one of the resources it depends on. 996 - depends-on(RID i, RID j) is TRUE only if RID i fails as soon as 997 RID j fails. 999 If we refer to the example detailed in section 1.1, then shared- 1000 risk(F1, F2, [fiber segment failure]) = TRUE because depends-on(F1, 1001 A) = TRUE, depends-on(F2, A) = TRUE and at-risk(A, [fiber segment 1002 failure]) = TRUE, the latter simply because A is a fiber segment. 1004 A.4 Practical Method for SRLG Calculation 1006 The recursive formula presented in the previous section does not 1007 directly lead to an efficient algorithm. It�s top-down nature 1008 illustrates nicely the recursive nature of the SRLG concept, but the 1009 calculation of the SRLGs in a top-down fashion would be totally 1010 inefficient, entailing the calculation of the same SRLGs in lower 1011 network layers over and over again. 1013 A more efficient algorithm can be obtained from a bottom-up 1014 calculation. Figure 6 illustrates this by using the example we 1015 introduced in the Section A.1 and in by introducing the concept of 1016 Shared Risk Relationship Graph (SRR) which defines the membership of 1017 a resource belonging to the same SRLG. 1019 F1 ---------- F4 1020 | \ ^ | 1021 | \ | | 1022 | \ | | Fiber SRR Graph 1023 --->| \ | |<--- 1024 | | \ | | | where F1=ACD, F2=AB, F3=BCE, F4=DE 1025 | | ^\ | | | 1026 | | | \| | | 1027 | | | | | | 1028 | | | |\ | | 1029 | | | | \ | | 1030 | F2 ----|--|-- F3 | 1031 | ^ | | | 1032 | | | | | 1033 +++++++++++++++++++++++++++++ 1034 | | | | | 1035 | | | | | 1036 --- A | | -- D | 1037 | | | 1038 | | | 1039 | C | Fiber Segment SRR Graph 1040 | | 1041 | | 1042 B -- E --- 1044 D.Papadimitriou et al. - Expires December 2003 20 1045 Figure 6. Bottom-up calculation of Shared Risk Relationships 1047 For the calculation of a set of SRLGs, we need to calculate a Shared 1048 Risk Relationship (SRR) graph. The bottom-up calculation of the 1049 fiber SRR graph proceeds as follows: 1051 - Step 1. For each fiber segment, there is an SRR between every two 1052 fibers contained in that segment (vertical arrows in Figure 6.) 1054 - Step 2. For every SRR between two fiber segments, there is an SRR 1055 between every two fibers contained in either of the two fiber 1056 segments. 1058 In the previous example, there are no SRRs between fiber segments, 1059 and the calculation stops after Step 1. 1061 A.5 Application of the Model 1063 The model is intended to be used to automate the discovery of the 1064 SRLGs at a given layer for a given risk type (RT). 1066 The dependencies may be confined to one layer, e.g. the dependency 1067 of an optical link on a node (for instance, a DWDM system) to which 1068 it is connected, when the RT = [Node failure]. Dependencies may also 1069 extend over layer boundaries, e.g. the dependency of a TDM circuit 1070 (or sub-channel) in an SDH network established by using an optical 1071 channel (or wavelength) through the optical network that is the 1072 server layer of the SDH network, when RT = [fiber failure]. 1074 Let two optical network resources RID i and RID j within the same 1075 layer share a common risk of type RT. Let this risk type be tied to 1076 a lower layer, referred to as the risk layer. To enable this layer 1077 to infer shared-risk(RID i, RID j, RT), its server layer should 1078 advertise the following information: 1080 shared-risk(component_1, component_2, RT) 1082 where component_1 are services of the server layer on which RID i 1083 relies and component_2 are services of the serving layer on which 1084 RID j relies, respectively. 1086 If the server layer is not the risk layer, the latter has to infer 1087 this knowledge from what its server layer is advertising. If shared 1088 risk relationships are not advertised, client layers should at least 1089 be able to query from their server layer the shared risk 1090 relationships between the services they receive. 1092 Some dependencies do not lend themselves easily to automatic 1093 discovery. For instance, it is hardly imaginable that the process of 1094 finding out through which fiber segments a fiber goes can be 1095 automated. This means that part of the image of depends-on (RID i, 1097 D.Papadimitriou et al. - Expires December 2003 21 1098 RID j) will have to be provided �manually� by the operator or be at 1099 least statically configured into a centralized repository. 1101 More formally, an efficient calculation of shared risk link 1102 relationships relies on two things: 1104 - In the lowest network layer with elements susceptible to the risk 1105 type RT that is considered, every network element RID j 1106 susceptible to the risk RT constitutes an SRR on its own, that is, 1107 (RID j, RID j) satisfies the recursive formula; 1109 - Every SRR that has been discovered in one network layer leads to 1110 SRRs in the next higher network layer. In particular, two next 1111 higher layer network elements (RID i, RID j) depending on lower 1112 layer network elements that have an SRR satisfy the recursive 1113 formula. In order to allow an efficient calculation of the shared 1114 risk relationships in the next higher layer (e.g. the fiber 1115 layer), the shared risk relationships that were discovered in 1116 lower layers (e.g. the fiber segment layer) are stored in SRR 1117 graphs. This way, the recalculation of lower layer shared risk 1118 relationships can be avoided. 1120 D.Papadimitriou et al. - Expires December 2003 22 1121 Full Copyright Statement 1123 "Copyright (C) The Internet Society (date). All Rights Reserved. 1124 This document and translations of it may be copied and furnished to 1125 others, and derivative works that comment on or otherwise explain it 1126 or assist in its implementation may be prepared, copied, published 1127 and distributed, in whole or in part, without restriction of any 1128 kind, provided that the above copyright notice and this paragraph 1129 are included on all such copies and derivative works. However, this 1130 document itself may not be modified in any way, such as by removing 1131 the copyright notice or references to the Internet Society or other 1132 Internet organizations, except as needed for the purpose of 1133 developing Internet standards in which case the procedures for 1134 copyrights defined in the Internet Standards process must be 1135 followed, or as required to translate it into languages other than 1136 English. 1138 The limited permissions granted above are perpetual and will not be 1139 revoked by the Internet Society or its successors or assigns. 1141 This document and the information contained herein is provided on an 1142 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1143 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 1144 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 1145 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1146 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." 1148 D.Papadimitriou et al. - Expires December 2003 23