idnits 2.17.1 draft-papadimitriou-ccamp-srlg-processing-01.txt: -(1102): 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: ---------------------------------------------------------------------------- ** Missing document type: Expected "INTERNET-DRAFT" in the upper left hand corner of the first page ** The document is more than 15 pages and seems to lack a Table of Contents. == There are 23 instances of lines with non-ascii characters in the document. == The page length should not exceed 58 lines per page, but there was 21 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 == Unrecognized Status in 'Category: Internet Draft', assuming Proposed Standard (Expected one of 'Standards Track', 'Full Standard', 'Draft Standard', 'Proposed Standard', 'Best Current Practice', 'Informational', 'Experimental', 'Informational', 'Historic'.) -- 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 (November 2002) is 7833 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 515 -- Looks like a reference, but probably isn't: '3' on line 202 -- Looks like a reference, but probably isn't: '2' on line 515 -- Looks like a reference, but probably isn't: '4' on line 240 == Missing Reference: 'N' is mentioned on line 515, but not defined == Missing Reference: 'OSPF' is mentioned on line 724, but not defined == Unused Reference: 'IEEE-ORL' is defined on line 742, but no explicit reference was found in the text == Unused Reference: 'MPLS-BDL' is defined on line 768, but no explicit reference was found in the text == Unused Reference: 'RFC-2370' is defined on line 779, 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-14 ** 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-03 ** Downref: Normative reference to an Informational draft: draft-ietf-ipo-framework (ref. 'IPO-FRM') == Outdated reference: A later version (-05) exists of draft-ietf-ipo-impairments-02 ** 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 == Outdated reference: A later version (-10) exists of draft-katz-yeung-ospf-traffic-08 ** Obsolete normative reference: RFC 2370 (Obsoleted by RFC 5250) Summary: 10 errors (**), 0 flaws (~~), 17 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 Category: Internet Draft Fabrice Poppe (Alcatel) 4 Expires: May 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 November 2002 13 Shared Risk Link Groups Encoding and Processing 15 draft-papadimitriou-ccamp-srlg-processing-01.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 May 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 April 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 April 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 Sub-segment: a group of fiber links, any fiber link of a 183 sub-segment start and terminates at the same location 185 - Fiber Segment: a group of fiber sub-segments, any fiber sub- 186 segment of segment start and terminates at the same location 188 Moreover, one can consider sequences of fiber (sub-)segment starting 189 and terminating at the same node and defined them as fiber trunks 190 (also referred to as cable or fiber duct). 192 Thus, the approach developed here extends the definition and 193 concepts given in [IPO-FRM] and [IPO-IMP] by enabling fiber 194 topologies not strictly limited to point-to-point physical inter- 195 connections between nodes. 197 As represented in Figure 1, the fiber trunk going from location N[1] 198 to location N[3] is composed by the fiber segments A and B and the 199 fiber trunk from location N[1] to location N[2] includes the fiber 200 segments A, C and D. 202 Location N[1] Location N[3] 204 Sub-Segment A[1] Sub-Segment B[1] 205 --------------------------------------------------------------- 206 === . . . ====== Fiber Fiber ====== . . . ==== 207 === . . . ====== Fiber Fiber ====== . . . ==== 208 -------------------------------------------------------------- 209 Segment A Segment B 210 ------------------------------ ----------------------------- 211 === . . . ====== Fiber | | Fiber ====== . . . ==== 212 === . . . ====== Fiber | | Fiber ====== . . . ==== 213 ------------------------- | | ------------------------- 215 D.Papadimitriou et al. - Expires April 2003 4 216 Sub-Segment A[n] | | | | Sub-Segment B[n] 217 | | | | 218 | | | | Segment C 219 | | | | 220 Sub-Segment D[1] | | | | Sub-Segment E[1] 221 ------------------------- | | ------------------------- 222 === . . . ====== Fiber | | Fiber ====== . . . ==== 223 === . . . ====== Fiber | | Fiber ====== . . . ==== 224 ------------------------------ ------------------------------ 225 Segment D Segment E 226 --------------------------------------------------------------- 227 === . . . ====== Fiber Fiber ====== . . . ==== 228 === . . . ====== Fiber Fiber ====== . . . ==== 229 --------------------------------------------------------------- 230 Sub-Segment D[n] Sub-Segment E[n] 232 Location N[2] Location N[4] 234 Figure 1. Example of Physical Topology 236 In this figure, the Segment A is composed by the fiber sub-segments 237 A[1], A[2], ..., A[i], ..., A[n]. The same terminology applies for 238 the segments B, C, D and E. 240 Consequently, the fiber trunk from location N[2] to location N[4] 241 includes the sub-segments D[2] to D[n] and their corresponding sub- 242 segments within the segment E: E[2] to E[n]. The fiber trunk from 243 location N[1] to location N[2] includes the fiber sub-segments A[n], 244 C[1] and D[1]. 246 3.3 SRLG Definition and Properties 248 A SRLG is defined as the set of links (or optical lines) sharing a 249 common physical resource (including fiber links, sub-segment and 250 segment) i.e. sharing a common risk. For instance, a set of links L 251 belongs to the same SRLG s, if established over the same fiber link 252 l. 254 3.3.1 SRLG Properties 256 The SRLG properties can be summarized as follows: 258 1) A link belongs to more than one SRLG if and only if it crosses 259 (at least) one of the resources covered by each of these SRLGs 261 For instance: fiber link l belongs to the SRLG s1 and s2, if and 262 only if it crosses the fiber sub-segment A[1] and B[1] 264 2) Two links belonging to the same SRLG can belong individually to 265 other (one or more) SRLGs 267 D.Papadimitriou et al. - Expires April 2003 5 268 For instance: fiber links l1 and l2 belong to SRLG s3 (segment A) 269 while l1 belongs to SRLG s1 (since it covers sub-segment A[1]) and 270 l2 to SRLG s4 (since it covers sub-segment D[1]) 272 3.4.2 SRLG Disjointness 274 To define the LSP SRLG disjointness notion, we first introduce the 275 following definition: an LSP (i.e. sequence of links) covers an SRLG 276 if and only if it crosses one of the links belonging to that SRLG. 277 For instance: LSP p1 covers SRLG s1 (since it crosses link l1) 279 LSP SRLG disjointness can then be defined as follows. 281 1) Two LSPs are disjoint with respect to an SRLG s1 if and only if 282 at most one of them covers this SRLG. 284 For instance: LSPs p1 and p2 are disjoint with respect to SRLG s1 285 since only p1 covers SRLG s1. 287 2) Two LSPs are disjoint with respect to a set of SRLG S if and only 288 if the sets of SRLGs they individually cover are completely disjoint 290 For instance: LSP p1 and p3 are disjoint with respect to set of SRLG 291 S = {s1, s2, s3} since only p1 covers SRLG set S. 293 3.5 Computational Model Capabilities 295 This section briefly describes guidelines for an SRLG computational 296 model described in appendix A and based on the above definitions. 297 The main features of this model are: 299 - Support Constraint-based Shortest Path First (CSPF) algorithm for 300 explicit route (or path) computation by considering SRLG 301 disjointness with respect to one or more risk types 303 - Encompass hierarchical dependencies between physical resources 304 (inference of SRLG sets using bottom-up computation) 306 - CSPF computation including the relationship between physical 307 resources and topological structures. For instance: 308 . a fiber link can be part of given fiber trunk 309 . a fiber cable passing through an earthquake region 311 - Provide risk assessment during path computation implying 312 allocation of conditional failure probabilities with SRLGs 314 - SRLG information flooding well-scoped to reduce the amount of 315 link-state advertisements by using summarization 317 Consequently, the above features suggest an SRLG encoding mechanism 318 that enables: 319 - Accommodation of the physical and topological hierarchies 320 - Reduction of the path (i.e. explicit route) optimality 322 D.Papadimitriou et al. - Expires April 2003 6 323 3.6 SRLG Encoding 325 Using the above definitions and properties, the objective of the 326 hierarchical encoding is to achieve aggregation of the SRLG 327 Identifiers on top of the (passive) optical network topology. For 328 this purpose, we propose a linear encoding scheme including a type 329 field. This provides abstraction of the physical layer structure and 330 should facilitate the management of the SRLG Identifiers. 332 The proposed SRLG sub-TLV of the TE Link top level TLV includes the 333 following SRLG Identifier (64-bit field): 335 0 1 2 3 336 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 337 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 338 | Type | Weight | 339 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 340 | Identifier | 341 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 343 Within the SRLG Identifier field (64 bits), the Type field (8 bits) 344 defines the resource type (also generically referred to as the link 345 type) to which the Identifier (32 bits) integer value refers. The 346 weight field (24 bits) assigned on a per-SRLG basis along with the 347 Identifier is defined in Section 4. 349 The following Type field values are currently defined for physical 350 resources, any other value being reserved: 352 Type Value 353 -------------------- ------ 354 Reserved 0x00 355 Fiber Trunk 0x10 356 Fiber Segment 0x20 357 Fiber Sub-segment 0x30 358 Fiber Link 0x40 359 Node(*) 0xFF 361 (*) represents a non-GMPLS capable switching elements 363 Logical resources such as optical channels and TDM circuits (or 364 optical sub-channels) can take one of the following values: 366 Type Value 367 ------------------- ------ 368 Optical Channel 0x50 369 Optical Sub-Channel 0x60 371 Since a given physical or logical resource (for instance a fiber 372 link) can belong to more than one SRLG, the SRLG Identifier 373 structure is defined in the general case as a list of SRLG 374 Identifier (n x 64-bit): 376 D.Papadimitriou et al. - Expires April 2003 7 377 0 1 2 3 378 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 379 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 380 | Type | Weight | 381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 382 | Identifier | 383 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 384 | Type | Weight | 385 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 386 | Identifier | 387 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 388 | | 389 // ... // 390 | | 391 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 392 | Type | Weight | 393 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 394 | Identifier | 395 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 397 Therefore, though we propose a linear encoding, the aggregation of 398 the SRLG is still possible. This encoding also enables to perform 399 summarization (which is not equivalent to aggregation) at the 400 boundaries of structures defining the spatial coverage of an SRLG 401 Identifier list while overcoming the drawbacks of full hierarchical 402 encoding schemes. In this context, the weight value follows the 403 rules defined in the Section 4. 405 4. Risk Assessment 407 Risk assessment is defined as the quantification process of the 408 potential risk associated to the inclusion of a given resource 409 (belonging to a given resource type) located within a given logical 410 structure such as a geographical location for a given logical 411 network resource such as an optical channel. 413 4.1 Rationale for Risk Assessment 415 Consider the following example, where the client device makes the 416 following connection requests to the optical network: 418 - Request for a persistent connection with 99.999 % percent of 419 availability or equivalently a downtime less than X minutes per 420 year. 422 - Request for protection for a portion of the traffic (at the 423 expense of more charging) compared to other portion of the 424 traffic left unprotected and considered as extra traffic by the 425 server. 427 D.Papadimitriou et al. - Expires April 2003 8 428 Such requirements will be translated into path specific requests. 429 Such path specific requests can be grouped into path selection 430 requirements and path characterization requirements. 432 1. Path selection requirements 434 These typically dictate which physical path should be taken to 435 achieve the availability requirements of the client request. These 436 requirements are typically related to the logical and physical 437 diversity as mentioned in Section 3. 439 2. Path characterization requirements 441 Path characterization requirements typically dictate the recovery 442 mechanisms as specified by the client connection request. This can 443 be achieved in the form of section and/or path recovery but also 444 depending on the ring or meshed topology of the optical network. 445 However, these considerations are out of the scope of this document. 447 The components that need formalization in this example are: 448 - Step 1. Specification of the client requirements (service level). 449 - Step 2. Configuration of the network that helps in assessing the 450 service specifics such as the availability. 451 - Step 3. Propagation of the above-configured information. 452 - Step 4. Processing of the above-propagated information. 454 Step 1 of specifying the requirements is not in the scope of this 455 document. Steps 2 to 4 are discussed in the following sections where 456 we elaborate on the risk assessment during path selection. 458 4.2 Risk Assessment 460 Risk (the complementary of availability) assessment is defined as 461 the evaluation of the potential risk associated to the inclusion for 462 a given path of a specific network resource (i.e. belonging to a 463 given resource type). Given that an SRLG Identifier list is used to 464 encode the group of logical and physical resources, if a mechanism 465 is devised to assign the risk of failure associated with the 466 corresponding resource, the availability of the path using these 467 resources can be computed. This, in order to meet the connection 468 availability as requested by the client request. 470 A simple approach is to assign the conditional failure probability 471 to each of the SRLG Identifiers. This information is encoded in the 472 weight (24 bits) field along with the SRLG information as defined in 473 Section 3.3. The associated weights can be used to either increase 474 or decrease the potential usage of the resource (i.e. inclusion into 475 the selected route). The Weight field is defined as a 24-bit length 476 encoded integer number (maximum value 2^24 - 1) to be divided by 477 (2^24 � 1) and multiplied by 100 to get the corresponding value in 478 percents. For instance a conditional failure probability of 0.99999 479 corresponds to a weight of 16.777.047 and 0.00005 to 839. 481 D.Papadimitriou et al. - Expires April 2003 9 482 For instance, we can associate a conditional failure probability of 483 25% (weight = 4.194.304) to any fiber sub-segment. It means that by 484 selecting two (or more than two) different optical channel paths 485 including the same SRLG identifier with respect to fiber sub-segment 486 failure, if one of these connections fails, then the probability 487 that the other connection fails is 25%. 489 The failure probability of a fiber can also depend on the length of 490 the fiber. In addition, a fiber can pass across different regions 491 with different failure probabilities. In this case, we need to 492 consider an aggregated failure probability per fiber taking into 493 account each of the failure probabilities of its sub-components. 495 For instance, if we refer to our previous example and by considering 496 1. a conditional failure probability of 5% is associated to any 497 fiber link 498 2. a conditional failure probability of 1% is associated to any 499 fiber segment 501 Then by selecting two different optical channels included within the 502 same SRLG with respect to fiber segment failure, we obtain a 503 simultaneous connection failure probability of 1%. Consequently, 504 when a protected connection service is requested, by choosing fiber 505 segment path disjointness, the simultaneous connection failure 506 probability is also of 1%. However, if two optical channels flowing 507 through the same fiber link are selected, then we have a probability 508 of 5% that both optical channels fail simultaneously. 510 More generically, if one assigns a conditional failure probability 511 c[i] to each SRLG Identifier i, the resulting conditional failure 512 probability C for a logical resource (a connection, for instance) 513 using these N resources is given by: 515 C = 1 - (1 � c[1]) x (1 � c[2]) x . . . x (1 � c[N]) 517 When all the conditional failure probabilities c[i] are small (i.e. 518 c[i] << 1) C can be approximated by (1 - Sum[i]c[i]). 520 4.3 Risk Assessment Application 522 The relationship between the availability of the service requested 523 by the client (i.e. a working and a protection connection) and the 524 conditional failure probabilities of the physical resource elements 525 included within the corresponding paths can be described as follows. 527 If we consider for instance 1) a conditional failure probability of 528 1% if fiber links are selected within the same fiber trunk 2) a 529 conditional failure probability of 1% if fiber links are selected 530 within the same fiber segment and 3) the corresponding failure are 531 independent events. 533 Then the availability of a connection whose backup is established 534 over fiber links (in same fiber segment) and within the same fiber 536 D.Papadimitriou et al. - Expires April 2003 10 537 trunks as the primary connection itself is approximately 98% (by 538 using the above formula). 540 Note that the initial value of the conditional failure probability 541 needs to be statically encoded; however, based on the history of the 542 failures these values could be dynamically re-evaluated. The 543 corresponding mechanism needs to be specified and is left for 544 further study. 546 5. Applications 548 The SRLG method developed here results in applications related to 549 the CSPF explicit route computation and the SRLG identifier sets 550 summarization. The latter enables in turn, intra- and inter-area 551 diverse path computation. For that purpose we first extend the SRLG 552 concept for logical resources such as optical channels and optical 553 sub-channels (i.e. TDM connections). 555 5.1 Extension to the Logical Resources 557 The SRLG concept can be extended to logical structures and resources 558 by taking into account the following: 560 1. Given the physical decomposition of the optical network 561 topology, the SRLG encoding can be hierarchically structured. 562 The hierarchical encoding helps in constructing the logical 563 topology abstraction, which in turn can be used in SRLG 564 summarization and loose-path computation. The link semantic may 565 also be extended to accommodate virtual links. 567 2. Propagate the SRLG information related to these logical 568 (structures and resources) links, for instance (a set of) 569 optical channels using IGP flooding for intra- and inter-area 570 routing purposes. 572 3. Reduce the amount of the flooded information and hence explicit 573 route computation optimality and extend the flooding scope of 574 the propagated information to accommodate logical resources 575 (i.e. optical channels and TDM circuits). 577 5.2 SRLG Information Flooding and Summarization 579 The SRLG set of each link (i.e. physical and logical resources) is 580 encoded as described in Section 3.3. This information is propagated 581 once at initial configuration between the various nodes using the 582 GMPLS Traffic Engineering extensions to IGPs (see [GMPLS-OSPF] and 583 IS-IS [GMPLS-ISIS]). After this initial SRLG identifier exchange, 584 corresponding values do not change over time. 586 Nevertheless, the propagation of SRLG information will be necessary 587 whenever a new link is added or an existing link is removed. 588 Initially, it is assumed that the failure probabilities of the 589 various resources are (statically) configured. However, it is 591 D.Papadimitriou et al. - Expires April 2003 11 592 envisioned that after a certain running period, the failure 593 probability associated to the SRLG and propagated along with the 594 SRLG sub-TLV itself (as described in Section 3.3) will change over 595 time and thus give rise to a dynamic metric. 597 5.3 Bottom-Up Computation of SRLG Relationships 599 Once the traffic engineering (topology-related) link information is 600 received by the node, the corresponding SRLG relationships can be 601 computed on a regular basis. 603 The fiber trunk SRLG relationships are used to compute the fiber 604 segment SRLG relationships, which in turn are used to compute the 605 fiber sub-segment SRLG relationships and finally the fiber SRLG 606 relationships. To each SRLG relationship (at each level), which 607 defines the membership of a resource to a particular SRLG, we 608 associate the conditional failure probability between two resources 609 belonging to this level (for instance, between two fibers that have 610 a common fiber sub-segment). 612 5.4 Topology Summarization and Route Computation 614 A direct application of this model is the Constraint-based Shortest 615 Path First (CSPF) algorithm used for explicit route computation 616 (i.e. traffic-engineered LSP creation) to maximize the connection 617 disjointness and so decrease their common failure probability. Given 618 an existing set of connections across the network, the objective is 619 to compute, for a newly requested connection, an explicit route 620 across the optical network topology such that this connection is 621 diversely routed from an existing given set of connections. 623 The diversity requirement is a routing constraint, that can be 624 expressed in terms of a conditional failure probability with respect 625 to an existing (set of) connections and more generally any kind of 626 resources. Hence, in addition to the other traffic-engineering 627 constraints, the diversity constraint requires that the conditional 628 failure probability does not exceed a given threshold. The CSPF 629 algorithm needs to be updated to take the routing diversity 630 constraint into account. 632 The SRLG concept generates another dimension to the existing 633 constraint-based path computation methods traditionally used in 634 hierarchical networks. The SRLG constraints comes in addition to the 635 common traffic-engineering constraints such as bandwidth 636 availability, link metrics and TE attributes (see [OSPF-TE]). The 637 specificity of the routing diversity constraint requires the use of 638 a path computation algorithm that provides not only complete multi- 639 path disjointness but also partial multi-path disjointness with 640 respect to various risk factors. In a similar way, appropriate 641 mechanisms should also be used in order to perform path re- 642 optimization following various recovery strategies. 644 D.Papadimitriou et al. - Expires April 2003 12 645 The specific aspect of complete and partial multi-path disjointness 646 is related to the fact that a path may with respect to SRLG be fully 647 or partially disjoint from a given set of path. In brief, one speaks 648 about SRLG partial or full multi-path disjointness. This means that 649 a connection may be disjoint from another but only to some extent 650 with respect to some risk factors. Thus when referring to path 651 disjointness with respect to SRLG one may also include the ratio of 652 disjointness with respect to various risk type assigned to their 653 component resources. Consider for instance the LSPs p1 and p2 using 654 j1 and j2 resources respectively, m of these resources having an 655 SRLG in common, with m =< j1 and m =< j2, then [(j1-m) + (j2- 656 m)]/(j1+j2) provides the disjointness ratio. For instance, if j1=13, 657 j2=7 and m=1, this ratio equals 0.90, thus corresponding path p1 and 658 p2 are SRLG disjoint at 90%. 660 As such, this feature differentiates path disjointness constraint 661 from any other constraint commonly considered in path computation. 663 6. Scalability Considerations 665 6.1 OSPF Scalability Considerations 667 A node SHOULD minimize the amount of routing information it floods. 668 Each time a SRLG sub-TLV is configured or removed that information 669 shall be flooded (not necessarily immediately) to all nodes in the 670 routing domain. This results in updating an existing LSA or flushing 671 an existing LSA. Removing an LSA from the (TE) Link State DataBase 672 (TE LSDB) can be accomplished in OSPF by prematurely aging the LSA. 673 The LSA is re-flooded with an LSA age equal to MaxAge. Each node 674 receiving an existing LSA with MaxAge removes it from its link state 675 database. 677 Also, the usage of OSPF implies each LSA must be refreshed 678 periodically (when the LSA age field reaches the LSRefreshTime, see 679 [RFC-2328]) to avoid age timeout and removal from the link state 680 database. This periodical LSA flooding and processing applies 681 particularly to the TE link capability sub-TLVs defined in this 682 document since their variation period is expected to be much larger 683 than the LSRefreshTime. 685 An Opaque LSA has a length field of 16 bits indicating the length of 686 the LSA, including the header. Thus, the length of OSPF packets can 687 be up to 65535 octets (including the IP header). Moreover, an OSPF 688 packet can contain several (Opaque) LSAs. OSPF relies if necessary 689 on the IP fragmentation to transmit large packets without any loss 690 of functionality. However this is not recommended and it is 691 suggested to split packets that are too large into several smaller 692 packets. 694 Therefore, the proposed SRLG sub-TLVs defined in this document (and 695 included in the top level TE Link TLV) MUST not exceed the maximum 696 OSPF packet size. This limits the number of SRLG identifiers that a 697 sub-TLV can include to approximately 125 (also this number largely 699 D.Papadimitriou et al. - Expires April 2003 13 700 depends on the other sub-TLVs included in the corresponding TE LSA 701 constraining to take for the sake of this application a conservative 702 approach). 704 6.2 IS-IS Scalability Considerations 706 TBD. 708 7. Compatibility Considerations 710 7.1 OSPF Compatibility Considerations 712 There should be no interoperability issues with GMPLS-capable nodes 713 that do not implement the proposed SRLG extensions since the sub- 714 TLVs proposed in this document is optional and thus will be silently 715 ignored. 717 The result of having such nodes that do not implement the proposed 718 SRLG extensions is largely detailed in this memo. However, SRLG 719 constraint paths can still be calculated using the SRLG sub-TLVs as 720 proposed in [GMPLS-OSPF]. 722 The present memo mandates these sub-TLVs to be mutually exclusive 723 i.e. they MUST never appear simultaneously as sub-TLV of the same 724 top level Link TLV [OSPF]. 726 7.2 IS-IS Compatibility Considerations 728 TBD. 730 8. Security Considerations 732 Security considerations related to SRLG and related applications are 733 left for further study. 735 9. References 737 [CROCH] O.Crochat, J.-Y. Le Boudec and O. Gerstel, "Protection 738 Interoperability for WDM Optical Networks", IEEE/ACM 739 Transactions on Networking, Vol. 8, No. 3, June 2000, 740 pp. 384-395. 742 [IEEE-ORL] J.Strand et al., �Issues for Routing in the Optical 743 Layer�, IEEE Communication Magazine, Volume 39, Number 744 2, Feb�01. 746 [GMPLS-ISIS] K.Kompella et al., �ISIS Extensions in Support of 747 Generalized MPLS�, Internet Draft, Work in Progress, 748 draft-ietf-isis-gmpls-extensions-14.txt. 750 [GMPLS-OSPF] K.Kompella et al., �OSPF Extensions in Support of 751 Generalized MPLS�, Internet Draft, Work in Progress, 752 draft-ietf-ccamp-ospf-gmpls-extensions-08.txt. 754 D.Papadimitriou et al. - Expires April 2003 14 756 [GMPLS-RTG] K.Kompella et al., �Routing Extensions in Support of 757 Generalized MPLS,� Internet Draft, Work in Progress, 758 draft-ietf-ccamp-gmpls-routing-05.txt. 760 [IPO-FRM] J.Luciani et al., �IP over Optical Networks A 761 Framework�, Internet Draft, Work in progress, draft- 762 ietf-ipo-framework-03.txt. 764 [IPO-IMP] J.Strand et al., �Impairments And Other Constraints On 765 Optical Layer Routing�, Internet Draft, Work in 766 progress, draft-ietf-ipo-impairments-02.txt. 768 [MPLS-BDL] K.Kompella et al., �Link Bundling in MPLS Traffic 769 Engineering�, Internet Draft, Work in progress, draft- 770 ietf-mpls-bundle-04.txt. 772 [OSPF-TE] D.Katz, D.Yeung and K.Kompella, �Traffic Engineering 773 Extensions to OSPF�, draft-katz-yeung-ospf-traffic- 774 08.txt, Internet Draft, Work in Progress. 776 [RFC-2328] J.Moy, RFC 2328, �OSPF Version 2�, STD 54, IETF 777 Standard Track, April 1998. 779 [RFC-2370] R.Coltun, RFC 2370, Standard Track, "The OSPF Opaque 780 LSA Option", July 1998. 782 10. Acknowledgments 784 The authors would like to thank Bernard Sales, Emmanuel Desmet and 785 Gert Grammel for their constructive comments, David Griffith for its 786 active contribution and Bart Rousseau for its revision efforts. 788 11. Author's Addresses 790 Dimitri Papadimitriou (Editor) 791 Francis Wellesplein, 1 792 B-2018 Antwerpen, Belgium 793 Phone: +32 3 240-8491 794 Email: dimitri.papadimitriou@alcatel.be 796 Fabrice Poppe (Alcatel) 797 Francis Wellesplein, 1 798 B-2018 Antwerpen, Belgium 799 Phone: +32 3 240-8006 800 Email: fabrice.poppe@alcatel.be 802 Jim Jones (Alcatel) 803 3400 W. Plano Parkway, 804 Plano, TX 75075, USA 805 Phone: +1 972 519-2744 806 Email: jim.d.jones@alcatel.com 808 D.Papadimitriou et al. - Expires April 2003 15 809 Senthil Venkatachalam (OPNet) 810 Email: svenkatachalam@opnet.com 812 Sudheer Dharanikota (Consulting) 813 Email: sudheer@ieee.org 815 Raj Jain (Nayna Networks) 816 157 Topaz St., 817 Milpitas, CA 95035, USA 818 Phone: +1 408 956-8000X309 819 Email: raj@nayna.com 821 Riad Hartani (Caspian Networks) 822 170 Baytech Drive, 823 San Jose, CA 95134, USA 824 Phone: +1 408 382-5216 825 Email: riad@caspiannetworks.com 827 Yong Xue (WorldCom) 828 Ashburn, VA, USA 829 Phone: +1 703 886-5358 830 Email: yong.xue@wcom.com 832 Appendix A: SRLG Computational Model 834 A.1 SRLG Concept and Example 836 The present model is intended to be used to automate the discovery 837 of the Shared Risk Link Groups (SRLGs) at a given layer for a given 838 physical resource type. 840 Note that a typical resource type can be a fiber, a fiber sub- 841 segment, a fiber segment or a fiber trunk. SRLG definition and 842 properties were described in Section 3. 844 Example: 846 The following example referring to Figure 5 (for the physical 847 network topology) offers some clarification. Let assume that 848 - N1, N2, N3, and N4 represent locations that are linked by the 849 fiber sub-segments, 850 - A, B, C, D and E be fiber segments, 851 - and F1 (ACD), F2 (AB), F3 (BCD) and F4 (DE) are fiber links routed 852 over the fiber segment topology. 854 N1 N2 855 | | 856 | | F1 857 |A |D N1 ------------ N2 858 | | | | 859 | | | | 860 | C | | | 862 D.Papadimitriou et al. - Expires April 2003 16 863 x-------------x |F2 |F4 864 | | | | 865 | | | | 866 | | | F3 | 867 |B |E N3 ------------ N4 868 | | 869 | | 870 N3 N4 872 Figure 4. Correlation between Fiber segment and Fiber link topology 874 In such a physical topology the obvious SRLGs are the following: 875 - {F1, F2} both going down when segment A breaks 876 - {F1, F3} both going down when segment C breaks 877 - {F1, F4} both going down when segment D breaks 878 - {F2, F3} both going down when segment B breaks 879 - {F3, F4} both going down when segment E breaks 881 These five SRLGs can be replaced by two SRLGs, S1 = {F1, F2, F3} and 882 S2 = {F1, F3, F4}, where S1 and S2 constitute the minimum edge 883 covering with cliques of the Shared Risk Relationship (SRR) graph 884 that can be drawn between F1, F2, F3, F4 (see Figure 5). A clique of 885 a graph G is a sub-graph of G in which every two nodes are connected 886 by an edge. This decomposition is unique. If there was an additional 887 dependency between F2 and F4, there would be a unique SRLG, S = {F1, 888 F2, F3, F4}. 890 F1 ------- F4 891 | \ | 892 | \ | 893 | \ | 894 | \ | 895 | \ | 896 | \ | 897 | \ | 898 F2 ------- F3 900 Figure 5. SRR Graph between fiber link and segment 902 Although R1 = F1-F2-F3 and R2 = F4 are diverse path between 903 locations N2 and N4 in the fiber topology (link and node 904 disjointness), they are not diverse with respect to SRLGs. This is 905 because both R1 and R2 cover SRLG S2, which contains F1, F3 (part of 906 R1) and F4 (part of R2). SRLGs are thus a way of formalizing the 907 propagation of (link-based) risk dependencies from server to client 908 layers. 910 The rules guiding the definition of minimum set of SRLGs for more 911 complex physical network topologies will be addressed in a future 912 version of this document. 914 A.2 Risk Type 916 D.Papadimitriou et al. - Expires April 2003 17 917 As specified up to now, the current approach considers that each of 918 the network resource may experience one or more failure type(s). The 919 same applies to geographical locations: a given location might 920 experience one or more failure types. Moreover, by applying the SRLG 921 properties, a network resource failure can potentially cover more 922 than one geographical location. Consequently, some heuristics must 923 be introduced to keep the SRLG computational complexity limited. 925 In order to limit the computational complexity, we define the 926 following heuristics when considering the SRLG computation with 927 respect to the type of risk: 929 1. The set of risk types associated to network resources corresponds 930 exactly to the set of resource type failure. 931 - So, for instance, the risk type associated to a fiber segment 932 is a fiber segment failure. The same principle applies for 933 other network resources such as fiber link, fiber sub-segment 934 and fiber trunk. Consequently, the current approach does not 935 consider a finest granularity for the network resource failure 936 than the one referred by their type. 938 2. A risk type associated to a geographical structure covers exactly 939 the region where it is defined. Moreover, a geographical failure 940 is limited to a given location and does not contaminate the 941 neighboring locations or generate another failure 942 - For instance, we consider that an earthquake covers exactly 943 one region or one area and that such a failure does not 944 generate a hurricane impacting the neighboring locations. So, 945 there is no correlation between geographical failures. 947 3. Each of the network resources covers exactly one geographical 948 logical structure. 949 - Consequently, when a geographical failure occurs, it 950 generates a failure impacting the entire network resources 951 included within the corresponding location. Hence, there is 952 an ON/OFF relationship between geographical and network 953 resource failures. 955 Consequently, when considering network resources, the risk type 956 associated to an SRLG is defined as the potential failure of one (or 957 more than one) instance belonging to a given resource type or the 958 potential failure of any of its hierarchical resource dependence. 960 Thus, we define the concept of SRLG with respect to a given resource 961 type and subsequently to the Risk Type (RT) to which this resource 962 type refers. Moreover, for a given resource type (or class), each of 963 the resources are identified by a Resource Identifier (RID). Since 964 each of these resource classes corresponds to an SRLG class, we can 965 assign an identifier to each of the SRLG classes members and define 966 their value as the SRLG identifier. 968 Moreover, by applying the defined heuristics above, the SRLG 969 identifiers can be grouped together by taking into account their 971 D.Papadimitriou et al. - Expires April 2003 18 972 geographical location. The latter is encoded by identifying the 973 region identifier (region ID) including the resource identifiers to 974 which the SRLG refers. 976 A.3 Calculation of Shared Risk Link Groups 978 In the calculation method, shared-risk(RID i, RID j, RT) is TRUE 979 only if the resource identifiers RID i and RID j belong to the same 980 SRLG with respect to the risk type RT. The risk types considered 981 here are related the fiber segment, the fiber sub-segment and the 982 fiber link risk failure. 984 A recursive calculation of shared-risk proceeds as follows: 986 shared-risk(RID i, RID j, RT) = 987 at-risk(RID i, RT) 988 and at-risk(RID j, RT) 989 and (RID i = RID j 990 or (exists RID k, RID l 991 such that 992 depends-on(RID i, RID k) 993 and depends-on(RID j, RID l) 994 and shared-risk(RID k, RID l, RT))) 996 In this calculation: 997 - at-risk(RID i, RT) is TRUE only if RID is susceptible to a risk of 998 type RT, either directly, or indirectly, through the failure of 999 one of the resources it depends on. 1000 - depends-on(RID i, RID j) is TRUE only if RID i fails as soon as 1001 RID j fails. 1003 If we refer to the example detailed in section 1.1, then shared- 1004 risk(F1, F2, [fiber segment failure]) = TRUE because depends-on(F1, 1005 A) = TRUE, depends-on(F2, A) = TRUE and at-risk(A, [fiber segment 1006 failure]) = TRUE, the latter simply because A is a fiber segment. 1008 A.4 Practical Method for SRLG Calculation 1010 The recursive formula presented in the previous section does not 1011 directly lead to an efficient algorithm. It�s top-down nature 1012 illustrates nicely the recursive nature of the SRLG concept, but the 1013 calculation of the SRLGs in a top-down fashion would be totally 1014 inefficient, entailing the calculation of the same SRLGs in lower 1015 network layers over and over again. 1017 A more efficient algorithm can be obtained from a bottom-up 1018 calculation. Figure 6 illustrates this by using the example we 1019 introduced in the Section A.1 and in by introducing the concept of 1020 Shared Risk Relationship Graph (SRR) which defines the membership of 1021 a resource belonging to the same SRLG. 1023 F1 ---------- F4 1025 D.Papadimitriou et al. - Expires April 2003 19 1026 | \ ^ | 1027 | \ | | 1028 | \ | | Fiber SRR Graph 1029 --->| \ | |<--- 1030 | | \ | | | where F1=ACD, F2=AB, F3=BCE, F4=DE 1031 | | ^\ | | | 1032 | | | \| | | 1033 | | | | | | 1034 | | | |\ | | 1035 | | | | \ | | 1036 | F2 ----|--|-- F3 | 1037 | ^ | | | 1038 | | | | | 1039 +++++++++++++++++++++++++++++ 1040 | | | | | 1041 | | | | | 1042 --- A | | -- D | 1043 | | | 1044 | | | 1045 | C | Fiber Segment SRR Graph 1046 | | 1047 | | 1048 B -- E --- 1050 Figure 6. Bottom-up calculation of Shared Risk Relationships 1052 For the calculation of a set of SRLGs, we need to calculate a Shared 1053 Risk Relationship (SRR) graph. The bottom-up calculation of the 1054 fiber SRR graph proceeds as follows: 1056 - Step 1. For each fiber segment, there is an SRR between every two 1057 fibers contained in that segment (vertical arrows in Figure 6.) 1059 - Step 2. For every SRR between two fiber segments, there is an SRR 1060 between every two fibers contained in either of the two fiber 1061 segments. 1063 In the previous example, there are no SRRs between fiber segments, 1064 and the calculation stops after Step 1. 1066 A.5 Application of the Model 1068 The model is intended to be used to automate the discovery of the 1069 SRLGs at a given layer for a given risk type (RT). 1071 The dependencies may be confined to one layer, e.g. the dependency 1072 of an optical link on a node (for instance, a DWDM system) to which 1073 it is connected, when the RT = [Node failure]. Dependencies may also 1074 extend over layer boundaries, e.g. the dependency of a TDM circuit 1075 (or sub-channel) in an SDH network established by using an optical 1076 channel (or wavelength) through the optical network that is the 1077 server layer of the SDH network, when RT = [fiber failure]. 1079 D.Papadimitriou et al. - Expires April 2003 20 1080 Let two optical network resources RID i and RID j within the same 1081 layer share a common risk of type RT. Let this risk type be tied to 1082 a lower layer, referred to as the risk layer. To enable this layer 1083 to infer shared-risk(RID i, RID j, RT), its server layer should 1084 advertise the following information: 1086 shared-risk(component_1, component_2, RT) 1088 where component_1 are services of the server layer on which RID i 1089 relies and component_2 are services of the serving layer on which 1090 RID j relies, respectively. 1092 If the server layer is not the risk layer, the latter has to infer 1093 this knowledge from what its server layer is advertising. If shared 1094 risk relationships are not advertised, client layers should at least 1095 be able to query from their server layer the shared risk 1096 relationships between the services they receive. 1098 Some dependencies do not lend themselves easily to automatic 1099 discovery. For instance, it is hardly imaginable that the process of 1100 finding out through which fiber segments a fiber goes can be 1101 automated. This means that part of the image of depends-on (RID i, 1102 RID j) will have to be provided �manually� by the operator or be at 1103 least statically configured into a centralized repository. 1105 More formally, an efficient calculation of shared risk link 1106 relationships relies on two things: 1108 - In the lowest network layer with elements susceptible to the risk 1109 type RT that is considered, every network element RID j 1110 susceptible to the risk RT constitutes an SRR on its own, that is, 1111 (RID j, RID j) satisfies the recursive formula; 1113 - Every SRR that has been discovered in one network layer leads to 1114 SRRs in the next higher network layer. In particular, two next 1115 higher layer network elements (RID i, RID j) depending on lower 1116 layer network elements that have an SRR satisfy the recursive 1117 formula. In order to allow an efficient calculation of the shared 1118 risk relationships in the next higher layer (e.g. the fiber 1119 layer), the shared risk relationships that were discovered in 1120 lower layers (e.g. the fiber segment layer) are stored in SRR 1121 graphs. This way, the recalculation of lower layer shared risk 1122 relationships can be avoided. 1124 D.Papadimitriou et al. - Expires April 2003 21 1125 Full Copyright Statement 1127 "Copyright (C) The Internet Society (date). All Rights Reserved. 1128 This document and translations of it may be copied and furnished to 1129 others, and derivative works that comment on or otherwise explain it 1130 or assist in its implementation may be prepared, copied, published 1131 and distributed, in whole or in part, without restriction of any 1132 kind, provided that the above copyright notice and this paragraph 1133 are included on all such copies and derivative works. However, this 1134 document itself may not be modified in any way, such as by removing 1135 the copyright notice or references to the Internet Society or other 1136 Internet organizations, except as needed for the purpose of 1137 developing Internet standards in which case the procedures for 1138 copyrights defined in the Internet Standards process must be 1139 followed, or as required to translate it into languages other than 1140 English. 1142 The limited permissions granted above are perpetual and will not be 1143 revoked by the Internet Society or its successors or assigns. 1145 This document and the information contained herein is provided on an 1146 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1147 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 1148 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 1149 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1150 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." 1152 D.Papadimitriou et al. - Expires April 2003 22