idnits 2.17.1 draft-kini-restoration-shared-backup-00.txt: 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 seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard 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. ** There are 35 instances of too long lines in the document, the longest one being 8 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' Summary: 5 errors (**), 0 flaws (~~), 2 warnings (==), 12 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft Sriganesh Kini 2 Expires : April, 2001 Murali Kodialam 3 T.V.Lakshman 4 - Bell Labs 6 Curtis Villamizar 7 - Avici Systems 9 Shared backup Label Switched Path restoration 11 draft-kini-restoration-shared-backup-00.txt 13 Status of this Memo 15 This document is an Internet-Draft and is in full conformance with 16 all provisions of Section 10 of RFC2026. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet- Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 Abstract 36 Traffic engineering using MPLS involves the setting up of label 37 switched paths (LSP) possibly with explicit routing and with 38 bandwidth guarantees (for label switched paths). The reliability of 39 these LSPs can be increased by providing a backup LSP onto which 40 traffic can be switched upon failure of an element in the path of the 41 active LSP. Backup LSPs can be routed in a way that bandwidth can be 42 shared between backup links of more than one active path while still 43 guaranteeing recoverability for a set of failures. This sharing greatly 44 increases the network efficiency, thereby increasing the number of LSPs 45 that can be carried while maintaining guarantees. Algorithms which can 46 route such recoverable LSPs while using only aggregate network usage 47 information are being developed. 49 This informational draft illustrates the concept of sharing links along 50 backup paths and examines the requirements from link state 51 information and the signaling functions. 53 1. Introduction 55 The Multi Protocol Label Switching (MPLS) working group has developed a 56 framework and standards which enable traffic engineering of networks. 57 The framework is described in [8] and the architecture is described in 58 [7]. The MPLS framework is becoming increasing popular to traffic 59 engineer IP networks. 61 MPLS uses the label swapping paradigm to switch data over an LSP. The 62 functional capabilities required for operations in an MPLS domain are 63 described in [9]. The network layer routing determines the route of an 64 LSP from the topology of the network and the current demands of the 65 applications utilizing the network. Link state routing protocols like 66 OSPF (as described in [1]) and IS-IS (as described in [2]) can provide 67 the topology information to network layer routing that engineers 68 traffic. Signaling protocols like RSVP (as described in [9] and [10]) 69 and LDP (as described in [11] and [12]) are then used to setup the LSP. 71 Since a LSP traverses a fixed path in the network, its reliability 72 depends on the links and nodes along the path. Traditionally IP 73 networks have carried only best-effort traffic. However new applications 74 are using the IP network infrastructure in ways that make it highly 75 desirable to incorporate faster repair. 77 MPLS based recovery provides a faster restoration mechanism 78 than layer 3 routing. Several methods have been proposed for MPLS 79 based recovery. A framework and terminology for MPLS based recovery 80 is described in [3]. 82 Setting up a backup LSP for an active LSP (e.g. [6]) is one way to 83 achieve reliability. A straightforward solution to this problem is to 84 find two disjoint paths. However this requires at least twice the amount 85 of network resources. For a restoration objective like single link 86 failure recovery, links on the backup path can be shared between 87 different active paths in a way that single link failure restoration 88 is guaranteed. This must be done without requiring per-LSP routing 89 information for all LSPs currently carried by the network, since keeping 90 track of per-LSP routing information for the whole network is not 91 feasible. It is more desirable to efficiently route recoverable LSPs 92 with shared backups using only aggregate network usage information. 93 Aggregate information useful for setting up shared backup paths is 94 obtainable by adding a few new information elements to the link state 95 advertisement of a link state routing protocol like OSPF or ISIS. 96 Algorithms which can operate using aggregate information are being 97 developed. An example of one such algorithm is described later. 98 Other examples of such algorithms are in [4],[5]. These algorithms 99 achieve a very high degree of sharing by using aggregate information 100 that can be conveyed by a link state routing protocol. 102 The key concept of sharing backup paths is described in section 2. 103 The requirements from link state protocols and signaling protocols 104 is briefly examined in section 3. 106 2. Concept of sharing backup paths 108 A brief description of the concept of sharing is described in this 109 section. 111 The model under which these principle of sharing is expected to be 112 deployed is very general. Requests for LSPs should be routed as they 113 arrive (online). A new type of LSP can be computed where given 114 a source and destination, an active path and a backup path (possibly 115 shared) is calculated. Links on the backup path are possibly shared 116 between backup paths of other active paths in a way that single 117 link/node failure restoration is guaranteed. As requests for setup and 118 teardown of such LSPs arrive and link failures occur the total link 119 bandwidth allocated for active paths and backup paths vary accordingly. 121 Section 2.1 through 2.3 illustrate the sharing concept through some 122 examples and section 2.4 outlines one simple algorithm that achieves 123 sharing and guarantees single link failure recovery. This algorithm 124 needs only aggregate information. [4] and [5] are other instances of 125 similar algorithms. They achieve a very high degree of sharing using 126 only aggregate information. 128 2.1 Sharing backup : single link failure recovery 130 Figure 1 illustrates a simple case of sharing of backup paths in a way 131 that single link failure can be recovered. A and B are label switch 132 routers. Say each link is of unit bandwidth and each LSP request 133 is also of unit bandwidth. L1 and L2 are two active paths. L1b is the 134 backup for L1 and L2b is the backup for L2. L1b and L2b can be 135 accomodated on the same link by sharing the bandwidth. Clearly, if 136 either one of L1 or L2 fail the system can recover. 138 L1 139 ____________________ 140 / \ 141 | | 142 ---- L1b L2b ---- 143 | A |----------------| B | 144 ---- ---- 145 | | 146 \____________________/ 147 L2 149 Figure 1 : Sharing backup links with link failure recovery 151 2.2 Sharing backup : single node failure recovery 153 Figure 2 illustrates a simple case of sharing of backup paths in a way 154 that single node failure can be recovered. 156 ---- L2 ---- 157 | A |--------------------------| B | 158 ---- ---- 159 | | 160 |L2b |L2b 161 | | 162 | | 163 ---- L1b L2b ---- 164 | C |--------------------------| D | 165 ---- ---- 166 | | 167 |L1b |L1b 168 | | 169 | | 170 ---- L1 ---- L1 ---- 171 | E |---------| F |-----------| G | 172 ---- ---- ---- 174 Figure 2 : Sharing backup links with node failure recovery 176 A,B, ... G are label switch routers. L1 is an active path along E-F-G. 177 The corresponding backup L1b is along the path E-C-D-G. Similarly 178 L2 is an active path along A-B. L2b is the corresponding backup path 179 along A-C-D-B. Clearly, if max-bandwidth(L1,L2) is allocated on link 180 C-D for L1b and L2b together, the system can ensure single node failure 181 recovery. 183 2.3 Local restoration : single link/node recovery 185 Local restoration (SONET like recovery constraints), can be achieved 186 by providing intermediate nodes with a backup path. The intermediate 187 nodes can switchover to the backup path immediately on getting a failure 188 indication. 190 Figure 3 illustrates an example of local restoration for single link 191 failure recovery. 193 ---- ---- 194 ____| D |____ _____| E |____ 195 L1b/ ---- \L1b /L1b ---- \L1b 196 / \ / \ 197 ---- L1 ---- L1 ---- 198 | A |--------------| B |---------------| C | 199 ---- ---- ---- 201 Figure 3 : Local restoration of link failure 203 Clearly from section 2.1 sharing of backup paths can be done in this 204 case to achieve single link/node failure recovery. In fact a further 205 degree of sharing can be achieved by sharing of links between segments 206 of the backup paths A-D-B and B-E-C (intra demand sharing). 208 Similarly Figure 4 illustrates an example of local restoration for single 209 node failure recovery. 211 ---- ---- 212 ________________| E |_____________ _____| F |____ 213 L1b/ ---- \L1b /L1b ---- \L1b 214 / \ / \ 215 ---- L1 ---- L1 ---- L1 ---- 216 | A |--------------| B |---------------| C |--------------| D | 217 ---- ---- ---- ---- 218 \ / 219 \L1b ---- /L1b 220 \_______________| G |_____________/ 221 ---- 223 Figure 4 : Local restoration of single node/link failure 225 Clearly from section 2.1 and 2.2, Figure 3, and Figure 4 backup sharing 226 (intra and inter demand sharing) can be done in this case as well. 228 2.4 A simple algorithm for calculated shared backup path 230 Terminology : Say for link (i,j) 231 i) the cumulative bandwidth allocated for active paths is F(i,j) 232 ii) the cumulative bandwidth allocated for backup paths is G(i,j) 233 iii) the residual bandwidth free for allocation is R(i,j) 235 For a request of bandwidth b the active path is calculated as the 236 shortest path on the topology of links that have R(i,j) > b. 237 Let M be the max of the F values along the active path. The backup 238 path is calculated as follows. The cost of a link (u,v) is now taken as 239 i) 0 if { M+b < G(u,v) } else 240 ii) b if { G(u,v) <= M and b <= R(u,v) } else 241 iii) M+b - G(u,v) if { M <= G(u,v) and M+b <= G(u,v)+R(u,v) } else 242 iv) infinity in all other cases 244 The backup path is calculated as the shortest path on the topology with 245 the cost of links calculated as above. 247 The lack of an active path or a backup path with finite cost represent 248 failure conditions. 250 3. Requirements for shared backup lsp restoration 252 Requirements from link state routing protocols and signaling protocols 253 is briefly described in this section. 255 Aggregate information about a link that has to be conveyed by a link 256 state routing protocol should consist of 257 i) The total bandwidth used on the link for active LSPs 258 ii) Total bandwidth used on the link for backup LSPs 259 iii) Total available bandwidth on the link 261 The signaling protocol information elements should consist of 262 i) The setup information and procedures for a backup LSP 263 ii) The association between the active and backup LSP 265 4. Security Considerations 267 This document raises no new security issues. 269 5. Acknowledgements 271 The authors would like to thank Vishal Sharma and Roch Guerin for their 272 comments on this work. 274 6. References 276 [1] Moy, J,, "OSPF Version 2" RFC 2328, April 1998. 278 [2] "Intermediate System to Intermediate System Intra-Domain Routeing 279 Exchange Protocol for use in Conjunction with the Protocol for 280 Providing the Connectionless mode Network Service (ISO 8473)", ISO 281 DP 10589, February 1990. 283 [3] Makam, V., Sharma, V., Huang, C., Owens, K., Mack-Crane, B., et 284 al, "A Framework for MPLS-based Recovery," Work in Progress, 285 Internet Draft , 286 February 2000. 288 [4] Lakshman, T.V., Kodialam, M., "Dynamic Routing of Bandwidth 289 Guaranteed Tunnels with Restoration", Proceedings of INFOCOM 2000, 290 April 2000. 292 [5] Lakshman, T.V., Kodialam, M., "Dynamic Routing of Bandwidth 293 Guaranteed Tunnels Using Aggregated Link Usage Information", 294 To be published in Proceedings of INFOCOM 2001. 296 [6] Haskin, D., Krishnan, R., "A Method for Setting an Alternative Label 297 Switched Paths to Handle Fast Reroute", Work in Progress, Internet Draft 298 , May 2000. 300 [7] Rosen, E., Viswanathan, A., and Callon, R., "Multiprotocol Label 301 Switching Architecture", Work in Progress, Internet Draft , August 1999. 304 [8] Callon, R., Doolan, P., Feldman, N., Fredette, A., Swallow, G., 305 Viswanathan, A., "A Framework for Multiprotocol Label Switching", 306 Work in Progress, Internet Draft , 307 September 1999. 309 [9] Braden, R., Zhang, L., Berson, S., Herzog, S., "Resource 310 ReSerVation Protocol (RSVP) -- Version 1 Functional 311 Specification", RFC 2205, September 1997. 313 [10] Awduche, D. et al "RSVP-TE: Extensions to RSVP for LSP Tunnels", Work in 314 Progress, Internet Draft , September 1999. 321 [12] Jamoussi, B. "Constraint-Based LSP Setup using LDP", Work in 322 Progress, Internet Draft , 323 September 1999. 325 7. Author's Addresses 327 Sriganesh Kini 328 Lucent Technologies, Bell Labs 329 Room 4C-526, 101 Crawfords Corner Road 330 Holmdel, NJ 07733-3030 331 Phone : 732 949 6418 332 Email : kini@dnrc.bell-labs.com 334 Murali Kodialam 335 Lucent Technologies, Bell Labs 336 Room 4D-525, 101 Crawfords Corner Road 337 Holmdel, NJ 07733-3030 338 Phone : 732 949 6296 339 Email : muralik@dnrc.bell-labs.com 341 T.V.Lakshman 342 Lucent Technologies, Bell Labs 343 Room 4D-531, 101 Crawfords Corner Road 344 Holmdel, NJ 07733-3030 345 Phone : 732 949 4778 346 Email : lakshman@dnrc.bell-labs.com 348 Curtis Villamizar 349 Avici Systems 350 Email : curtis@avici.com 352 Full Copyright Statement 354 Copyright (C) The Internet Society (2000). All Rights Reserved. 356 This document and translations of it may be copied and furnished to 357 others, and derivative works that comment on or otherwise explain it 358 or assist in its implementation may be prepared, copied, published 359 and distributed, in whole or in part, without restriction of any 360 kind, provided that the above copyright notice and this paragraph 361 are included on all such copies and derivative works. However, this 362 document itself may not be modified in any way, such as by removing 363 the copyright notice or references to the Internet Society or other 364 Internet organizations, except as needed for the purpose of 365 developing Internet standards in which case the procedures for 366 copyrights defined in the Internet Standards process must be 367 followed, or as required to translate it into languages other than 368 English. 370 The limited permissions granted above are perpetual and will not be 371 revoked by the Internet Society or its successors or assigns. 373 This document and the information contained herein is provided on an 374 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 375 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 376 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 377 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 378 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."