idnits 2.17.1 draft-ayandeh-mpls-dynamics-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-23) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** 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? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 2) being 59 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 18 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** 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 ([2], [7]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 196 has weird spacing: '...tion or more ...' == Line 352 has weird spacing: '...traffic old ...' -- 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 (September 1998) is 9352 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) == Unused Reference: '1' is defined on line 798, but no explicit reference was found in the text -- No information found for draft-mpls-framework - is the name correct? -- Possible downref: Normative reference to a draft: ref. '1' == Outdated reference: A later version (-07) exists of draft-ietf-mpls-arch-00 ** Downref: Normative reference to an Informational RFC: RFC 2105 (ref. '3') == Outdated reference: A later version (-04) exists of draft-doolan-tdp-spec-01 -- Possible downref: Normative reference to a draft: ref. '4' -- Possible downref: Normative reference to a draft: ref. '5' -- Possible downref: Normative reference to a draft: ref. '6' ** Obsolete normative reference: RFC 1583 (ref. '7') (Obsoleted by RFC 2178) Summary: 13 errors (**), 0 flaws (~~), 8 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Submitted to MPLS Working Group Siamack Ayandeh 3 INTERNET DRAFT Nortel 4 5 Yanhe Fan 6 Nortel 8 March 1998 9 Expires September 1998 11 MPLS Routing Dynamics 13 Status of this Memo 15 This document is an Internet-Draft. Internet-Drafts are working 16 documents of the Internet Engineering Task Force (IETF), its areas, 17 and its working groups. Note that other groups may also distribute 18 working documents as Internet-Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-drafts as reference 23 material or to cite them other than as "work in progress." 25 To learn the current status of any Internet-Draft, please check the 26 "1id-abstracts.txt" listing contained in the Internet-Drafts shadow 27 Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), 28 munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or 29 ftp.isi.edu (US West Coast). 31 Abstract 33 This Internet draft outlines how transients in protocols such as 34 OSPF [7] (intra-domain routing) and MPLS LDP [2] can lead to periods 35 of time with loops and other undesirable routing phenomenon. It 36 defines a set of metrics to quantify this dynamic behavior. 37 Quantification of these metrics, using a simulation model, for 38 various local vs. egress label allocation schemes is used as the 39 basis of a comparative analysis. This includes quantifying any 40 incremental impact that MPLS may have once it is introduced into an 41 autonomous IP routing area. The resulting insights would help 42 develop a better understanding of routing dynamics. This includes 43 identifying key nodal and network variables which impact routing 44 dynamics hence guiding MPLS feature selection and IP network design. 46 Table of Content 48 1. Overview of the Issues of Network Routing Dynamics 2 49 2. What Impacts Network Routing Dynamics 3 50 3. Metrics to Quantify Network Routing Dynamics 4 51 4. A Description of the Model and Configurations 5 52 5. Label Allocation Schemes (Local vs. Egress Control) 9 53 6. Routing Dynamics: Results and Discussion 10 54 7. Conclusion 16 55 Appendix A The Sensitive Analysis of the Time of Label 56 Allocating (in Allocating Task) 16 57 References 17 59 1. Overview of the Issue of Network Routing Dynamics 61 The issue of network routing dynamics and stability has received 62 attention in the literature recently where measurements of routing 63 traffic for BGP backbones are used to quantify the stability of the 64 routing information. Inter-domain routing information exchange often 65 suffer from rapid fluctuation in network reachability information. 66 This phenomenon also referred to as "route flaps" can contribute to 67 poor end to end performance of networks while degrading overall 68 efficiency. 70 The focus of this investigation however is intra-domain routing, in 71 particular OSPF, and how transients in such protocols can lead to 72 periods of time with loops and other undesirable exchanged routing 73 phenomenon. As such a cause and effect investigation technique is 74 deployed where addition/deletion of networks or link up/down events 75 trigger intra-domain routing protocol information exchange. Using a 76 simulation model the behavior of these protocols is tracked and 77 observed resulting in insights and metrics which can be used to 78 quantify and develop a better understanding of routing dynamics. 80 The simulation model mimics the behavior of both layer-3 routing 81 protocols such as OSPF, as well as MPLS. As a whole the tool allows 82 an investigation of the network behavior, with and without MPLS, 83 generating metrics which quantify the following: 85 - Impact of introducing protocols such as MPLS/LDP on network 86 dynamics 87 - Comparison of various MPLS proposals for network control and 88 dealing with loops 89 - Identifying key nodal and network variables which impact routing 90 dynamics hence providing insights in MPLS feature selection and 91 network design. 93 Given the many technical proposals which have already been put 94 forward or are in process of submission to IETF MPLS WG, the 95 simulation capability allows for a first order assessment of various 96 proposals. This provides the first step in assessment and in not 97 intended to replace prototyping or implementation trials. 99 2. What Impacts Network Routing Dynamics 101 Network routing dynamics entails transient behavior which results 102 in undesirable circumstances such as routing loops, interface speed 103 mismatch, and black holes. A number of network and nodal features 104 impact the dynamic behavior of network routing and are briefly 105 discussed below: 107 a. The nature of the protocol in question and the control approach 108 adapted. For example label distribution may be achieved through 109 schemes referred to as "Local Controls" vs. "Egress Control". 110 Different protocols exhibit different dynamic behavior. 112 b. Duration of Shortest Path (SP) table computations which is a 113 function of network size and CPU MIPS available for this purpose. 115 c. Propagation time of events which is a function of speed of event 116 detection, link speed, and CPU MIPS, as well as network topology. 118 d. Volume of users traffic which may compete with communication of 119 routing information. This occurs to a lessor extent on the links, 120 through priority queuing, and can occur to a greater extent when 121 competing for a shared CPU resource. 123 e. Rate of BGP route injections which is an indicator of instability 124 of inter-domain routing in a large network. Intranets may be immune 125 to such effects. 127 The impact of features listed above are captured through a series of 128 events which act as stimuli for the network under simulation. These 129 events may also reflect a change in network and nodal configuration. 130 The list of events are: 132 1. Addition or deletion of networks 133 2. Link failure 134 3. Change in the capacity of Label Switch Routers (LSRs) and the 135 network links 136 4. Influence of the nodal architecture of the LSR 137 5. External route updates (not currently in the model) need 138 hierarchical label allocation 139 6. Change in topology under investigation i.e. a linear topology 140 vs. a mesh 142 These events result in routing events which trigger route 143 calculation and label allocation. 145 3. Metrics to Quantify Network Routing Dynamics 147 Parameters which defined the metric for routing dynamics and 148 stability are listed and discussed below. We try to capture the 149 significance of each parameter with long term intention of 150 developing metrics which would readily quantify network intra-domain 151 routing dynamics. Note that the value of these parameters is 152 impacted by the list of features "a" to "e" of section 2. 154 3.1. Routing Table Update Time (RTUT) 156 The time interval between occurrence of an event, which results in 157 routing table updates, and end of the routing table update for a 158 given LSR. Such an update may be incremental or result of a shortest 159 path calculation: 161 - Incremental update result from BGP injections. 162 - Shortest path calculation updates the routing table to reflect say 163 a change in AS network topology. 165 Significance: This parameter impacts all the other parameters listed 166 below. As such it is a base metric. 168 3.2. Routing Table Convergence Time (RTCT) 170 An event may result in a number of LSRs needing a routing table 171 update. The RTCT is the longest of such routing table update times. 173 Note that RTCT is not expected to be affected by the LDP for both 174 local control and egress control provided the following guidelines 175 are followed: 176 - LSAs are transmitted at highest link priority; 177 - LDP traffic is light and forwarded with priority; 178 - Route checking functions and LDP protocols require small amount 179 of processing compared to SP route calculations. 181 Significance: This is a base metric and minimizing RTCT should be 182 a network design goal. 184 3.3. Label Allocation Time (LAT) 186 Labels may be allocated to a new route or may be re-allocated as a 187 result of a change to a route. Once an event results in a new 188 route, LAT is defined as the interval between such an event and an 189 LSR being capable of doing L2 forwarding (having both incoming and 190 outgoing labels for local control, or receiving Acknowledgment 191 message(s) from upstream neighbor(s) for egress control) for the new 192 or the changed route. This interval accounts for shortest path 193 calculations, local label manipulations if any, and the time it 194 takes to communicate this information to other LSRs. Note that the 195 scope of such an advertisement may be the LSR's neighbors as with 196 local allocation or more extensive as with egress controls. LAT is 197 measured with respect to individual LSRs. 199 Note that propagation time of events and label distribution impact 200 the label allocation time with a linear multi-hop topology having a 201 greater impact on egress controls vs. local controls. 203 Significance: LAT allows for a comparison of different label 204 distribution schemes such as local and egress controls. It is a 205 measure of a network's response to any route change and the speed 206 with which it becomes capable of doing label based forwarding. 208 3.4. Label Allocation Convergence Time (LACT) 210 An event may result in a number of LSRs needing to allocate labels. 211 The LACT is the longest of such label allocation times through out 212 the network under investigation. 214 3.5. Loop Intensity (LI) 216 Routing protocols such as OSPF may create transient routing loops, 217 since each node learns the current link status of the network at a 218 different time. The impact of loops may be packets which do not 219 reach their destination. If prolonged, loops may lead to congestion 220 on certain links. Beside L3 loops i.e. resulting from layer-3 221 forwarding, there may be L2 loops (which result from forwarding 222 based on labels). The latter occurs when using label allocation 223 methods which use local control. 225 Let : 226 A: be the number of paths with loops; 227 N: be the total number of paths considered (see explanation below) 228 L: be the sum of all loop durations. 230 LI is then defined as: 232 LI = (A*L)/(N*RTCT). 234 In this draft, when L3 loops are considered, N is 225 i.e. all 235 possible source and destination pairs of 15 LSRs. For L2 loops, N 236 equals to 14 (the number of paths to a single destination N6). 238 Significance: LI is a measure of the severity and potential impact 239 of loops on payload and network traffic. 241 4. A Description of the Model and Configurations 243 4.1. The Simulation Environment 244 The results in this draft are based on a simulation model of OSPF 245 with only one single area. No BGP injections are currently assumed 246 in the model. LDP [4] for local control and ARIS [6] protocol for 247 the egress control are modeled. The simulation tool used is an 248 extended library of C++ classes and functions which have been 249 developed for the purpose of discrete event simulations and 250 statistical data collection. 252 4.2 A Single Autonomous System 254 Figure 1 shows the single autonomous system which was simulated. 255 There are fifteen LSRs (LSR1 - LSR15) and fifteen networks (N1 - 256 N15). All the LSRs and networks are connected via SONET links. OSPF 257 is used as the IGP and the routing domain has only one area. 259 +-----+ +-----+ +-----+ 260 N6 |LSR6 | N10 |LSR10| |LSR9 | N9 261 +-----+ +-----+ +-----+ 262 | \ / 263 | \ / 264 +-----+ +-----+ 265 N7 |LSR7 |============|LSR8 | N8 266 +-----+ +-----+ 267 // \\ 268 N5 // \\ N11 269 +-----+ // \\+-----+ +-----+ 270 |LSR5 |// \|LSR11|----|LSR12| N12 271 N1 +-----+ +-----+ +-----+ 272 +-----+ || || | 273 |LSR1 |\ || || | 274 +-----+ \ +-----+ || +-----+ 275 \|LSR4 | || |LSR13| N13 276 N2 /+-----+ || +-----+ 277 +-----+ / || || 278 |LSR2 |/ || N15 || 279 +-----+ +-----+ +-----+ +-----+ 280 N3 |LSR3 |===========================|LSR15|----|LSR14| N14 281 +-----+ +-----+ +-----+ 283 Figure 1: A single Autonomous System 285 4.3. Nodal Model Reflecting a Simple Generic LSR Architecture 287 Figure 2 shows the nodal model of LSR from label allocation's 288 perspective. 290 +-----------------------------+ 291 | Label Allocating | 292 | | 293 +-----------------------------+ 294 | Route Computing | 295 | | 296 +--------------+--------------+ 297 | RouteCheck | Flooding | 298 | | | 299 +-----------------------------+ 300 | Forwarding | 301 | | 302 +-----------------------------+ 304 Figure 2: Nodal Model 306 We define the following simulation modules to capture each of the 307 components of the nodal model in figure 2: 309 a. Forwarding Module: copying packets from input to output 310 buffers or internal buffers for route/allocation handling 312 b. RouteCheck Module: upon receiving a link state advertisement, 313 it checks against link state database record to determine which 314 is more recent 316 c. Flooding Module: copying packets on all interfaces to neighbors 318 d. Computing Module: triggered by the new advertisement, 319 calculating the routing table by either Dijkstra (IGP updates) 320 or incremental (EGP) algorithm 322 e. Allocating Module: allocating a label for the stream and 323 propagates the binding information to neighbor(s) 325 All these modules execute independently i.e. there is no processor 326 competition among them. The only exceptions are Computing and 327 Allocation Tasks. Both Tasks share the same processor and Computing 328 Task has the priority. Figure 3 is the block diagram of an LSR. 330 neighbor(s) 332 / \ 333 | binding/requiring 334 binding +----------+ 335 +-----------------------> |Allocating| 336 | +----------+ 337 | / \ | 338 | route | | 339 | change | | 340 | | | binding 341 | +----------+ new +---------+ | 342 | |RouteCheck|-----> |Computing| | 343 | +----------+\ +---------+ | 344 | / \ | \ | 345 | LSAs| | \ new | 346 binding | | | \ \ / 347 +----------+ | \ +--------+ 348 LSAs ----> |Forwarding| | --------> |Flooding|--> all 349 +----------+ | +--------+ neighbors 350 user traffic | | 351 \ / \ / 352 user traffic old LSAs 354 Figure 3 Model of an LSR 356 4.4. Work Times Used Within a Node 358 Forwarding Task 359 User packet arrival interval has the Weibull distribution: 360 W(4.0, mean/24.0); 361 User packet length has Weibull distribution: W(1.1, 1.143) 362 RouteCheck Task 363 Checking Time is 10.0 us 364 Flooding Task 365 Transmission time: packet length/link bandwidth 366 Computing Task 367 Computing time (100 mips): 57.5 us 368 Allocation Task 369 local/remote without attribute checking: 1.0 us; 370 local/remote with attribute checking: 1.5 us; others: 0.2 us 372 4.5. Nodal and Link Capacities Used in The Network Model 374 Default configuration for each LSR are 375 a) CUP power available for Computing and Allocating is 376 100 mips 377 b) Computing has priority to use the CPU power 378 c) Maximum forwarding capacity is 836,000 pps 380 The regular links are OC3 links and the bold links are 2xOC3 381 capacity. 383 5. Label Allocation Schemes (Local vs. Egress Controls) 385 A fundamental concept in MPLS is the association of labels and 386 network layer routing. The difference between the various 387 contributions, lie in what the label assignment trigger is, at what 388 degree of granularity the labels are assigned, and how the 389 label/stream binding information is distributed. 391 In this draft, we only consider the topology-driven allocation for 392 fine granularity (i.e. per layer-3 route) and explicit label 393 distribution. There are two types of topology-driven allocation: 394 local control and egress control. 396 Label allocation methods we investigate in this draft include: 398 Local Control(and its three flavors): [3,4] 400 a) downstream label allocation (DS) 401 The label allocation is done by the downstream LSR, i.e. the 402 incoming labels are allocated locally and the outgoing labels 403 are allocated remotely(by downstream LSR). 405 b) upstream label allocation (US) 406 The label allocation is done by the upstream LSR, i.e. the 407 incoming labels are allocated remotely (by the upstream LSR) 408 and outgoing labels are allocated locally. 410 c) downstream label allocation on demand (DSD) 411 The label allocation is done by the downstream LSR upon 412 receiving the request from the upstream LSR, i.e. the incoming 413 labels are allocated locally after receiving the request from 414 upstream LSR and the outgoing labels are allocated remotely(by 415 the downstream LSR). 417 Egress Control [2,5,6] 419 a) basic egress label allocation (BEC) 420 Only the egress node may initiate the transmission of label 421 allocation information. Non-egress nodes wait until they get a 422 label from downstream LSR, allocate a label and pass a 423 corresponding label to upstream LSR(s). 425 b) egress label allocation with diffusion (ECD) 426 Works in the same way as basic egress label allocation except 427 that it uses "diffusion computation" to prune the upstream tree 428 before replacing the old LSP with a new LSP. This is done by 429 removing all LSRs from the tree that would otherwise be on a 430 looping path. 432 6. Routing Dynamics: Results and Discussion 434 We use a what-if analysis approach. We create an event, observe the 435 consequences, and measure the metrics defined in section 3. There 436 are two type of events: 437 a) Event 1(E1): A new network attaches to LSR2. 438 b) Event 2(E2): The Link between LSR5 and LSR7 goes down. This 439 link failure will affect multiple routes and we only consider 440 the label allocation for the route of N6 at this time. 442 Event 1 is the case that an LSP is initially set up and Event 2 is 443 the case that the LSP in question is changed. The events are 444 repeated a number of times in order to cope with the randomness of 445 user traffic. Unless stated explicitly, the values we present are 446 the average value over the runs. Each LSR is fed with user traffic. 447 The LSR Utilization(LU) is the percentage of LSRs' maximum 448 forwarding capacity which is used by user traffic. By default, all 449 LSRs have the same LU. The time unit used in this draft is 450 microseconds. 452 6.1. Label Allocation Convergence 454 6.1.1. Label Allocation Convergence Time (LACT) 456 The Table 1 and Table 2 give the comparison of LACT among the five 457 label allocation methods. 459 Table 1 LACT Comparison (E1) 460 ----------------------------------- 461 LU | DS | US | DSD | BEC | ECD 462 ----+-----+-----+-----+-----+------ 463 10 | 157 | 162 | 167 | 164 | 164 464 20 | 169 | 175 | 183 | 179 | 179 465 30 | 187 | 197 | 208 | 202 | 202 466 40 | 230 | 239 | 258 | 249 | 249 467 50 | 267 | 289 | 322 | 310 | 310 468 60 | 371 | 415 | 467 | 442 | 442 469 70 | 550 | 627 | 719 | 670 | 670 470 80 | 918 | 1050| 1276| 1139| 1139 471 ----------------------------------- 472 Table 2 LACT Comparison (E2) 473 ----------------------------------- 474 LU | DS | US | DSD | BEC | ECD 475 ----+-----+-----+-----+-----+------ 476 10 | 113 | 108 | 117 | 127 | 147 477 20 | 120 | 115 | 128 | 138 | 165 478 30 | 132 | 127 | 142 | 157 | 202 479 40 | 154 | 146 | 170 | 188 | 250 480 50 | 186 | 177 | 212 | 244 | 343 481 60 | 250 | 229 | 293 | 350 | 541 482 70 | 375 | 349 | 462 | 555 | 935 483 80 | 604 | 550 | 760 | 907 | 1633 484 ----------------------------------- 486 For the initial setup of an LSP (E1), the LACT differences among 487 the five allocation methods are small, especially for the light to 488 medium LSR utilization. The downstream allocation has the best 489 performance and downstream on demand allocation is the worst in term 490 of the LACT. The two egress control allocation methods have the same 491 performance since no diffusion computation is required. 493 For the LSP change (E2), the egress control allocation has much 494 longer LACT than local control(see Table 2). Comparing with DS 495 (LU=80%), BEC and ECD will take 50% and 170% more time to converge. 496 This means that local control's period of instability is shorter than 497 egress control in the face of transients. Egress controls on the 498 other hand avoid transient loops. Both schemes however are equally 499 exposed to other forms of loops, which occur outside of the transient 500 interval, i.e. the ones that are caused by other factors such as say 501 software bugs. This latter category however are likely to occur with 502 a much lower frequency. 504 For the local control, the DS and US have the roughly same 505 performance and DSD has the worst LACT. For the egress control, BCE 506 and ECD have the same LACT if there is no diffusion computation 507 involved, otherwise the difference may be noticeable. 509 6.1.2. Label Allocation Time (LAT) 511 Tables 3 and 4 show the comparison of label allocation time 512 (LAT) among the five allocation methods at 60% LSR utilization. 514 Table 3 LAT Comparison (E1) 515 -------------------------------------- 516 LSR | DS | US | DSD | BEC | ECD 517 -------+-----+-----+-----+-----+------ 518 LSR01 | 189 | 183 | 241 | 193 | 193 519 LSR02 | 97 | 169 | 97 | 174 | 174 520 LSR03 | 186 | 242 | 229 | 257 | 257 521 LSR04 | 150 | 241 | 193 | 256 | 256 522 LSR05 | 189 | 249 | 238 | 267 | 267 523 LSR06 | 271 | 263 | 322 | 286 | 286 524 LSR07 | 229 | 302 | 278 | 327 | 327 525 LSR08 | 260 | 334 | 300 | 359 | 359 526 LSR09 | 299 | 293 | 358 | 320 | 320 527 LSR10 | 292 | 283 | 337 | 312 | 312 528 LSR11 | 266 | 308 | 306 | 334 | 334 529 LSR12 | 290 | 348 | 332 | 375 | 375 530 LSR13 | 327 | 322 | 373 | 348 | 348 531 LSR14 | 268 | 262 | 317 | 278 | 278 532 LSR15 | 228 | 310 | 269 | 330 | 330 533 -------------------------------------- 535 Table 4 LAT Comparison (E2) 536 -------------------------------------- 537 LSR | DS | US | DSD | BEC | ECD 538 -------+-----+-----+-----+-----+------ 539 LSR01 | 182 | 177 | 233 | 287 | - 540 LSR02 | 187 | 180 | 234 | 289 | - 541 LSR03 | 208 | 177 | 230 | 276 | 407 542 LSR04 | 193 | 224 | 207 | 347 | 541 543 LSR05 | 166 | 97 | 173 | 285 | 497 544 -------------------------------------- 546 For event 1, all LSRs will allocate a label for the route of the new 547 attached network. The following is the label allocation LSR sequence, 549 DS : LSR2, 4, 3, 5, 1, 15, 7, 8, 11, 14, 6, 12, 10, 9 and 13 550 US : LSR2, 1, 4, 3, 5, 14, 6, 10, 9, 7, 11, 15, 13, 8 and 12 551 DSD : LSR2, 4, 3, 5, 1, 15, 7, 8, 11, 14, 6, 12, 10, 9 and 13 552 BEC : LSR2, 1, 4, 3, 5, 14, 6, 10, 9, 7, 15, 11, 13, 8 and 12 553 ECD : LSR2, 1, 4, 3, 5, 14, 6, 10, 9, 7, 15, 11, 13, 8 and 12 555 For event 2, only LSR1 - LSR5's label for N6 will be affected by 556 either re-allocation or re-sending/checking binding information. The 557 LSR sequence is as follows, 559 DS : LSR5, 1, 2, 4 and 3 560 US : LSR5, 3, 1, 2 and 4 561 DSD : LSR5, 4, 3, 1 and 2 562 BEC : LSR3, 5, 1, 2 and 4 563 ECD : LSR3, 5 and 4 565 From the LSR sequence we may see the differences among those 566 allocation methods and get the sense of why one takes longer than 567 the other. 569 6.2. Impact on the Routing Convergence 571 Table 5 shows the impact on routing (OSPF) and the RTCT among the 572 five allocation methods generically referred to as MPLS. Differences 573 between label allocation schemes are negligible (within 0.17 %) 574 since the work times assumed are similar and SP calculation has 575 priority over label processing. 577 Table 5 RTCT Comparison (E1&E2) 578 -------------------------------- 579 | E1 | E2 580 ------------------+------------- 581 LU | OSPF | MPLS | OSPF | MPLS 582 ----+------+------+------+------ 583 10 | 155 | 155 | 126 | 126 584 20 | 166 | 166 | 136 | 136 585 30 | 184 | 184 | 148 | 149 586 40 | 224 | 225 | 181 | 181 587 50 | 259 | 259 | 214 | 215 588 60 | 360 | 361 | 289 | 291 589 70 | 539 | 539 | 429 | 431 590 80 | 895 | 895 | 734 | 735 591 -------------------------------- 593 The impact of running explicit label distribution protocols is very 594 small on the routing convergence and the five methods have almost 595 the same performance and impact. 597 These simulation results very much depend on the assumption about 598 work-time value of Allocating Task. In order to assess the 599 sensitivity of the results with respect to this assumption, we 600 enlarge these value by a factor of 10 and 25 times. This analysis 601 shows that the simulation results are not sensitive to those values 602 until label allocation will take roughly the same or more time than 603 routing table computation. This is only likely to occur for a large 604 number of route updates. For details see Appendix A. 606 6.3. Loops 608 In order to capture the multiple hop loops, we add an asymmetric 609 link to the network between LSR5 and LSR15. The bandwidth from LSR15 610 to LSR5 is 3xOC3 and the bandwidth from LSR5 to LSR15 is half an OC3. 612 We consider Event 2 (E2 where link between LSR5 and LSR7 goes down) 613 with no repetition. Our simulation results show that the same link 614 failure event does not always create the L3 transient multiple-hop 615 loop and the L3 transient loop does not always result in L2 loop. 616 The occurrence of transient loops (L3, L2) very much depends on the 617 sequence of (events leading to) routing table updates and label 618 allocation. 620 The following is the case that we capture both L3 and L2 multiple-hop 621 transient loops. The LU is 80%. The next hops to N6 before and after 622 the link failure are 624 Table 6 Next Hop to N6 625 ---------------------------- 626 LSR No. | Before | After 627 ----------+--------+-------- 628 5 | LSR7 | LSR4 629 4 | LSR5 | LSR3 630 3 | LSR15 | LSR15 631 15 | LSR5 | LSR11 632 ---------------------------- 634 6.3.1. L3 Loop 636 There is one four-hop transient loop. Taking the link failure as 637 start of time, this loop starts at 113 and ends at 354, with the 638 duration of 241 us. 640 +--> LSR5 --> LSR4 --> LSR3 --> LSR15 --+ 641 | | 642 +---------------------------------------+ 644 The loop intensity index (LI) is 0.019 ((14*241)/(225*773)). 646 6.3.2. L2 Loop 648 a) Local Control 649 There is one multiple L2 transient loop when using downstream 650 allocation (DS) 652 +--> LSR5 --> LSR4 --> LSR3 --> LSR15 --+ 653 | | 654 +---------------------------------------+ 656 This loop is from 212 to 354 and its duration is 142 us. The L2 657 loop is completely covered by the L3 loop. 659 The LI is 0.092 = ((7*142)/(14*773)). 661 Note: Since the set of paths in L3 and L2 looping consideration is 662 different, currently the LIs in two cases are not comparable. 664 Table 7 below shows the routing table update time and the label 665 allocation times which lead to the loops described above. 667 Table 7 RTUT & LAT 668 ---------------------- 669 LSR No.| RTUT | LAT 670 --------+------------- 671 5 | 100 | 212 672 4 | 113 | 212 673 3 | 208 | 209 674 15 | 354 | 355 675 ---------------------- 677 b) Egress Control 678 Egress control label allocation can avoid L2 loop setup. With the 679 same L3 transient loop, egress control allocation allows L2 680 loop-free LSP setup. This is because egress control uses the LSR 681 path vector, similar in function to the BGP AS_PATH attribute. 683 6.3.3. Discussion 685 The L3 loop is the same for both local control and egress control. 686 Local control may create the L2 loop. This is because an LSR can 687 assign a label whenever it wants. This independence results in a 688 short LACT (355 us). The shorter LACT is, the more stable the 689 networks is. 691 Egress control can avoid the L2 loops. The reason is that when 692 routes are changing, the node R detects a change in the next hop 693 for a given stream, it asks its new next hop for a label and the 694 associated LSR ID list. It then makes sure that R's ID is not in 695 the LSR ID list received from the new next hop. R either grows a new 696 switched path upstream tree to replace the old LSP (BEC) or starts 697 a "Diffusion Computation" to prune the tree upstream of R by 698 removing all LSRs on that tree which would be on a looping path if R 699 was to switch-over to the new path (ECD). Then R can replace the old 700 LSP with the new LSP without causing any loops. 702 Egress control introduces the dependence among the LSRs. This 703 dependence results in a longer LACT, 872 for BEC and 1586 for ECD. 704 LACT increases by 517 (146%, more) and 1231 (347% more), compared 705 with DS. 707 The benefits of using ECD is avoiding the unnecessary unsplicing/ 708 resplicing (LSR1, 2, 3, 14 in this case). The disadvantage of ECD 709 is the longer LACT. Comparing with BEC, ECD increases LACT by 714 710 (82% more). The comparison between BEC and ECD is shown in Table 8. 712 Table 8 LAT 713 ---------------------- 714 LSR No.| BEC | ECD 715 --------+-----+------- 716 LSR01 | 855 | - 717 LSR02 | 822 | - 718 LSR03 | 872 | 1004 719 LSR04 | 858 | 1586 720 LSR05 | 862 | 1288 721 LSR14 | 734 | - 722 LSR15 | 822 | 1117 723 ---------------------- 725 7. Conclusion 727 Label allocation convergence time (LACT) is the important metric to 728 indicate how fast the whole network is fully capable of doing label 729 forwarding again after a route change. To design an LDP with short 730 LACT is one major goal of network design. Simulations show that when 731 topology changes, local control has much shorter LACT than egress 732 control. The period of layer-2 instability is therefore shorter for 733 local controls. However this period may be accompanied by layer-2 734 loops. 736 The topology change may cause L3 transient loops and the L3 loops 737 may result the L2 loops. Our simulation shows that the L2 loops are 738 overlapped by the L3 loops completely and that their duration is 739 shorter than the latter. The egress control can avoid the L2 loops 740 and local control can not. However egress controls suffer from a 741 longer period when forwarding based on labels may not be available. 742 This period overlaps with the interval when layer-3 loops are 743 present (i.e. layer-3 forwarding may not help). More simulations are 744 currently underway to quantify the benefits of each scheme using a 745 single metric. 747 Egress control with diffusion can avoid the unnecessary unsplicing/ 748 resplicing when using basic egress control, but again with a longer 749 LACT. 751 Route Computation should have the priority over the label allocation, 752 since LIB is built on top of FIB. Our simulation results show that 753 for single route updates, running LDP has a minor impact on routing 754 convergence. The five label allocation methods have almost the same 755 and minor impact on routing convergence(see Appendix A). 757 Appendix A The sensitive analysis of the time of label allocating 758 (in Allocating Task) 760 The assumption we make on Allocating Task is as following 761 handling local assignment is 1.0 us, remote assignment 1.0 us, 762 local/remote assignment with LSR ID checking 1.5 us and all 763 others 0.2 us 764 To make thing worse, we enlarge those value by 10 and 25 times. 765 There are three sets of values 766 set 1: 1.0/1.0/1.5/0.2 767 set 2: 10.0/10.0/15.0/2.0 768 set 3: 25.0/25.0/37.5/5.0 769 Using set 2, the time for allocation is still smaller than computing 770 time(57.5 us), and the time for allocation is almost the same at 771 some LSRs and lager in most LSRs than computing time for set 3. The 772 LU is Low(20), Median(50) and High(80) 774 Table 9 LACT (E1) 775 ---------------------------------------------- 776 Set No. | DS | BEC 777 +-----+-----+-----+-----+-----+------ 778 | Low | Med | High| Low | Med | High 779 ---------+------+-----+------+-----+------+--- 780 No. 1 | 169 | 267 | 918 | 179 | 310 | 1139 781 No. 2 | 188 | 289 | 939 | 225 | 368 | 1212 782 No. 3 | 218 | 325 | 974 | 343 | 483 | 1324 783 ----------------------------------------------- 785 Table 10 RTCT (E1) 786 ---------------------------------------------- 787 Set No. | DS | BEC 788 +-----+-----+-----+-----+-----+------ 789 | Low | Med | High| Low | Med | High 790 ---------+-----+-----+-----+-----+-----+------ 791 No. 1 | 166 | 259 | 895 | 166 | 259 | 895 792 No. 2 | 166 | 259 | 895 | 166 | 259 | 895 793 No. 3 | 166 | 260 | 898 | 166 | 259 | 895 794 ----------------------------------------------- 796 References 798 [1] "A Framework for Multiprotocol Label Switching", R. Callon, P. 799 Doolan, etc., work in progress, draft-mpls-framework-01.txt, July 800 1997 801 [2] "A Proposed Architecture for MPLS", E. Rosen, A. Viswanathan, 802 R. Callon, work in progress, draft-ietf-mpls-arch-00.txt, August 1997 803 [3] "Cisco Systems' Tag Switching Architecture Overview", Y. Rekhter, 804 B. Davie etc., RFC 2105, February 1997 805 [4] "Tag Distribution Protocol", P. Doolan, B. Davie etc., work in 806 progress, draft-doolan-tdp-spec-01.txt, May 1997 807 [5] "ARIS: Aggregate Route-Based IP Switching", A. Viswanathan etc., 808 work in progress, draft-viswanathan-aris-overview-00.txt, March, 1997 809 [6] "ARIS Specification", N. Feldman and A. Viswanathan, work in 810 progress, draft-feldman-aris-spec-00.txt, March 1997 811 [7] "OSPF version 2", J. Moy, RFC 1583, March 1994 813 Authors' Address 815 Siamack Ayandeh 816 Northern Telecom 817 P.O Box 3511, Station C 818 Ottawa, Ontario 819 Canada 820 (613) 763-3645 821 ayandeh@nortel.ca 823 Yanhe Fan 824 Northern Telecom 825 P.O Box 3511, Station C 826 Ottawa, Ontario 827 Canada 828 (613) 765-2315 829 yanhe@nortel.ca