Internet Draft Submitted to MPLS Working Group Siamack Ayandeh INTERNET DRAFT Nortel <draft-ayandeh-mpls-dynamics-00.txt> Yanhe Fan Nortel March 1998 Expires September 1998 MPLS Routing Dynamics Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-drafts as reference material or to cite them other than as "work in progress." To learn the current status of any Internet-Draft, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). Abstract This Internet draft outlines how transients in protocols such as OSPF [7] (intra-domain routing) and MPLS LDP [2] can lead to periods of time with loops and other undesirable routing phenomenon. It defines a set of metrics to quantify this dynamic behavior. Quantification of these metrics, using a simulation model, for various local vs. egress label allocation schemes is used as the basis of a comparative analysis. This includes quantifying any incremental impact that MPLS may have once it is introduced into an autonomous IP routing area. The resulting insights would help develop a better understanding of routing dynamics. This includes identifying key nodal and network variables which impact routing dynamics hence guiding MPLS feature selection and IP network design. Ayandeh and Fan [Page 1] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 Table of Content 1. Overview of the Issues of Network Routing Dynamics 2 2. What Impacts Network Routing Dynamics 3 3. Metrics to Quantify Network Routing Dynamics 4 4. A Description of the Model and Configurations 5 5. Label Allocation Schemes (Local vs. Egress Control) 9 6. Routing Dynamics: Results and Discussion 10 7. Conclusion 16 Appendix A The Sensitive Analysis of the Time of Label Allocating (in Allocating Task) 16 References 17 1. Overview of the Issue of Network Routing Dynamics The issue of network routing dynamics and stability has received attention in the literature recently where measurements of routing traffic for BGP backbones are used to quantify the stability of the routing information. Inter-domain routing information exchange often suffer from rapid fluctuation in network reachability information. This phenomenon also referred to as "route flaps" can contribute to poor end to end performance of networks while degrading overall efficiency. The focus of this investigation however is intra-domain routing, in particular OSPF, and how transients in such protocols can lead to periods of time with loops and other undesirable exchanged routing phenomenon. As such a cause and effect investigation technique is deployed where addition/deletion of networks or link up/down events trigger intra-domain routing protocol information exchange. Using a simulation model the behavior of these protocols is tracked and observed resulting in insights and metrics which can be used to quantify and develop a better understanding of routing dynamics. The simulation model mimics the behavior of both layer-3 routing protocols such as OSPF, as well as MPLS. As a whole the tool allows an investigation of the network behavior, with and without MPLS, generating metrics which quantify the following: - Impact of introducing protocols such as MPLS/LDP on network dynamics - Comparison of various MPLS proposals for network control and dealing with loops - Identifying key nodal and network variables which impact routing dynamics hence providing insights in MPLS feature selection and network design. Given the many technical proposals which have already been put forward or are in process of submission to IETF MPLS WG, the Ayandeh and Fan [Page 2] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 simulation capability allows for a first order assessment of various proposals. This provides the first step in assessment and in not intended to replace prototyping or implementation trials. 2. What Impacts Network Routing Dynamics Network routing dynamics entails transient behavior which results in undesirable circumstances such as routing loops, interface speed mismatch, and black holes. A number of network and nodal features impact the dynamic behavior of network routing and are briefly discussed below: a. The nature of the protocol in question and the control approach adapted. For example label distribution may be achieved through schemes referred to as "Local Controls" vs. "Egress Control". Different protocols exhibit different dynamic behavior. b. Duration of Shortest Path (SP) table computations which is a function of network size and CPU MIPS available for this purpose. c. Propagation time of events which is a function of speed of event detection, link speed, and CPU MIPS, as well as network topology. d. Volume of users traffic which may compete with communication of routing information. This occurs to a lessor extent on the links, through priority queuing, and can occur to a greater extent when competing for a shared CPU resource. e. Rate of BGP route injections which is an indicator of instability of inter-domain routing in a large network. Intranets may be immune to such effects. The impact of features listed above are captured through a series of events which act as stimuli for the network under simulation. These events may also reflect a change in network and nodal configuration. The list of events are: 1. Addition or deletion of networks 2. Link failure 3. Change in the capacity of Label Switch Routers (LSRs) and the network links 4. Influence of the nodal architecture of the LSR 5. External route updates (not currently in the model) need hierarchical label allocation 6. Change in topology under investigation i.e. a linear topology vs. a mesh These events result in routing events which trigger route calculation and label allocation. Ayandeh and Fan [Page 3] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 3. Metrics to Quantify Network Routing Dynamics Parameters which defined the metric for routing dynamics and stability are listed and discussed below. We try to capture the significance of each parameter with long term intention of developing metrics which would readily quantify network intra-domain routing dynamics. Note that the value of these parameters is impacted by the list of features "a" to "e" of section 2. 3.1. Routing Table Update Time (RTUT) The time interval between occurrence of an event, which results in routing table updates, and end of the routing table update for a given LSR. Such an update may be incremental or result of a shortest path calculation: - Incremental update result from BGP injections. - Shortest path calculation updates the routing table to reflect say a change in AS network topology. Significance: This parameter impacts all the other parameters listed below. As such it is a base metric. 3.2. Routing Table Convergence Time (RTCT) An event may result in a number of LSRs needing a routing table update. The RTCT is the longest of such routing table update times. Note that RTCT is not expected to be affected by the LDP for both local control and egress control provided the following guidelines are followed: - LSAs are transmitted at highest link priority; - LDP traffic is light and forwarded with priority; - Route checking functions and LDP protocols require small amount of processing compared to SP route calculations. Significance: This is a base metric and minimizing RTCT should be a network design goal. 3.3. Label Allocation Time (LAT) Labels may be allocated to a new route or may be re-allocated as a result of a change to a route. Once an event results in a new route, LAT is defined as the interval between such an event and an LSR being capable of doing L2 forwarding (having both incoming and outgoing labels for local control, or receiving Acknowledgment message(s) from upstream neighbor(s) for egress control) for the new or the changed route. This interval accounts for shortest path calculations, local label manipulations if any, and the time it Ayandeh and Fan [Page 4] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 takes to communicate this information to other LSRs. Note that the scope of such an advertisement may be the LSR's neighbors as with local allocation or more extensive as with egress controls. LAT is measured with respect to individual LSRs. Note that propagation time of events and label distribution impact the label allocation time with a linear multi-hop topology having a greater impact on egress controls vs. local controls. Significance: LAT allows for a comparison of different label distribution schemes such as local and egress controls. It is a measure of a network's response to any route change and the speed with which it becomes capable of doing label based forwarding. 3.4. Label Allocation Convergence Time (LACT) An event may result in a number of LSRs needing to allocate labels. The LACT is the longest of such label allocation times through out the network under investigation. 3.5. Loop Intensity (LI) Routing protocols such as OSPF may create transient routing loops, since each node learns the current link status of the network at a different time. The impact of loops may be packets which do not reach their destination. If prolonged, loops may lead to congestion on certain links. Beside L3 loops i.e. resulting from layer-3 forwarding, there may be L2 loops (which result from forwarding based on labels). The latter occurs when using label allocation methods which use local control. Let : A: be the number of paths with loops; N: be the total number of paths considered (see explanation below) L: be the sum of all loop durations. LI is then defined as: LI = (A*L)/(N*RTCT). In this draft, when L3 loops are considered, N is 225 i.e. all possible source and destination pairs of 15 LSRs. For L2 loops, N equals to 14 (the number of paths to a single destination N6). Significance: LI is a measure of the severity and potential impact of loops on payload and network traffic. 4. A Description of the Model and Configurations 4.1. The Simulation Environment Ayandeh and Fan [Page 5] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 The results in this draft are based on a simulation model of OSPF with only one single area. No BGP injections are currently assumed in the model. LDP [4] for local control and ARIS [6] protocol for the egress control are modeled. The simulation tool used is an extended library of C++ classes and functions which have been developed for the purpose of discrete event simulations and statistical data collection. 4.2 A Single Autonomous System Figure 1 shows the single autonomous system which was simulated. There are fifteen LSRs (LSR1 - LSR15) and fifteen networks (N1 - N15). All the LSRs and networks are connected via SONET links. OSPF is used as the IGP and the routing domain has only one area. +-----+ +-----+ +-----+ N6 |LSR6 | N10 |LSR10| |LSR9 | N9 +-----+ +-----+ +-----+ | \ / | \ / +-----+ +-----+ N7 |LSR7 |============|LSR8 | N8 +-----+ +-----+ // \\ N5 // \\ N11 +-----+ // \\+-----+ +-----+ |LSR5 |// \|LSR11|----|LSR12| N12 N1 +-----+ +-----+ +-----+ +-----+ || || | |LSR1 |\ || || | +-----+ \ +-----+ || +-----+ \|LSR4 | || |LSR13| N13 N2 /+-----+ || +-----+ +-----+ / || || |LSR2 |/ || N15 || +-----+ +-----+ +-----+ +-----+ N3 |LSR3 |===========================|LSR15|----|LSR14| N14 +-----+ +-----+ +-----+ Figure 1: A single Autonomous System Ayandeh and Fan [Page 6] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 4.3. Nodal Model Reflecting a Simple Generic LSR Architecture Figure 2 shows the nodal model of LSR from label allocation's perspective. +-----------------------------+ | Label Allocating | | | +-----------------------------+ | Route Computing | | | +--------------+--------------+ | RouteCheck | Flooding | | | | +-----------------------------+ | Forwarding | | | +-----------------------------+ Figure 2: Nodal Model We define the following simulation modules to capture each of the components of the nodal model in figure 2: a. Forwarding Module: copying packets from input to output buffers or internal buffers for route/allocation handling b. RouteCheck Module: upon receiving a link state advertisement, it checks against link state database record to determine which is more recent c. Flooding Module: copying packets on all interfaces to neighbors d. Computing Module: triggered by the new advertisement, calculating the routing table by either Dijkstra (IGP updates) or incremental (EGP) algorithm e. Allocating Module: allocating a label for the stream and propagates the binding information to neighbor(s) All these modules execute independently i.e. there is no processor competition among them. The only exceptions are Computing and Allocation Tasks. Both Tasks share the same processor and Computing Task has the priority. Figure 3 is the block diagram of an LSR. Ayandeh and Fan [Page 7] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 neighbor(s) / \ | binding/requiring binding +----------+ +-----------------------> |Allocating| | +----------+ | / \ | | route | | | change | | | | | binding | +----------+ new +---------+ | | |RouteCheck|-----> |Computing| | | +----------+\ +---------+ | | / \ | \ | | LSAs| | \ new | binding | | | \ \ / +----------+ | \ +--------+ LSAs ----> |Forwarding| | --------> |Flooding|--> all +----------+ | +--------+ neighbors user traffic | | \ / \ / user traffic old LSAs Figure 3 Model of an LSR 4.4. Work Times Used Within a Node Forwarding Task User packet arrival interval has the Weibull distribution: W(4.0, mean/24.0); User packet length has Weibull distribution: W(1.1, 1.143) RouteCheck Task Checking Time is 10.0 us Flooding Task Transmission time: packet length/link bandwidth Computing Task Computing time (100 mips): 57.5 us Allocation Task local/remote without attribute checking: 1.0 us; local/remote with attribute checking: 1.5 us; others: 0.2 us 4.5. Nodal and Link Capacities Used in The Network Model Default configuration for each LSR are Ayandeh and Fan [Page 8] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 a) CUP power available for Computing and Allocating is 100 mips b) Computing has priority to use the CPU power c) Maximum forwarding capacity is 836,000 pps The regular links are OC3 links and the bold links are 2xOC3 capacity. 5. Label Allocation Schemes (Local vs. Egress Controls) A fundamental concept in MPLS is the association of labels and network layer routing. The difference between the various contributions, lie in what the label assignment trigger is, at what degree of granularity the labels are assigned, and how the label/stream binding information is distributed. In this draft, we only consider the topology-driven allocation for fine granularity (i.e. per layer-3 route) and explicit label distribution. There are two types of topology-driven allocation: local control and egress control. Label allocation methods we investigate in this draft include: Local Control(and its three flavors): [3,4] a) downstream label allocation (DS) The label allocation is done by the downstream LSR, i.e. the incoming labels are allocated locally and the outgoing labels are allocated remotely(by downstream LSR). b) upstream label allocation (US) The label allocation is done by the upstream LSR, i.e. the incoming labels are allocated remotely (by the upstream LSR) and outgoing labels are allocated locally. c) downstream label allocation on demand (DSD) The label allocation is done by the downstream LSR upon receiving the request from the upstream LSR, i.e. the incoming labels are allocated locally after receiving the request from upstream LSR and the outgoing labels are allocated remotely(by the downstream LSR). Egress Control [2,5,6] a) basic egress label allocation (BEC) Only the egress node may initiate the transmission of label allocation information. Non-egress nodes wait until they get a label from downstream LSR, allocate a label and pass a corresponding label to upstream LSR(s). Ayandeh and Fan [Page 9] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 b) egress label allocation with diffusion (ECD) Works in the same way as basic egress label allocation except that it uses "diffusion computation" to prune the upstream tree before replacing the old LSP with a new LSP. This is done by removing all LSRs from the tree that would otherwise be on a looping path. 6. Routing Dynamics: Results and Discussion We use a what-if analysis approach. We create an event, observe the consequences, and measure the metrics defined in section 3. There are two type of events: a) Event 1(E1): A new network attaches to LSR2. b) Event 2(E2): The Link between LSR5 and LSR7 goes down. This link failure will affect multiple routes and we only consider the label allocation for the route of N6 at this time. Event 1 is the case that an LSP is initially set up and Event 2 is the case that the LSP in question is changed. The events are repeated a number of times in order to cope with the randomness of user traffic. Unless stated explicitly, the values we present are the average value over the runs. Each LSR is fed with user traffic. The LSR Utilization(LU) is the percentage of LSRs' maximum forwarding capacity which is used by user traffic. By default, all LSRs have the same LU. The time unit used in this draft is microseconds. 6.1. Label Allocation Convergence 6.1.1. Label Allocation Convergence Time (LACT) The Table 1 and Table 2 give the comparison of LACT among the five label allocation methods. Table 1 LACT Comparison (E1) ----------------------------------- LU | DS | US | DSD | BEC | ECD ----+-----+-----+-----+-----+------ 10 | 157 | 162 | 167 | 164 | 164 20 | 169 | 175 | 183 | 179 | 179 30 | 187 | 197 | 208 | 202 | 202 40 | 230 | 239 | 258 | 249 | 249 50 | 267 | 289 | 322 | 310 | 310 60 | 371 | 415 | 467 | 442 | 442 70 | 550 | 627 | 719 | 670 | 670 80 | 918 | 1050| 1276| 1139| 1139 ----------------------------------- Ayandeh and Fan [Page 10] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 Table 2 LACT Comparison (E2) ----------------------------------- LU | DS | US | DSD | BEC | ECD ----+-----+-----+-----+-----+------ 10 | 113 | 108 | 117 | 127 | 147 20 | 120 | 115 | 128 | 138 | 165 30 | 132 | 127 | 142 | 157 | 202 40 | 154 | 146 | 170 | 188 | 250 50 | 186 | 177 | 212 | 244 | 343 60 | 250 | 229 | 293 | 350 | 541 70 | 375 | 349 | 462 | 555 | 935 80 | 604 | 550 | 760 | 907 | 1633 ----------------------------------- For the initial setup of an LSP (E1), the LACT differences among the five allocation methods are small, especially for the light to medium LSR utilization. The downstream allocation has the best performance and downstream on demand allocation is the worst in term of the LACT. The two egress control allocation methods have the same performance since no diffusion computation is required. For the LSP change (E2), the egress control allocation has much longer LACT than local control(see Table 2). Comparing with DS (LU=80%), BEC and ECD will take 50% and 170% more time to converge. This means that local control's period of instability is shorter than egress control in the face of transients. Egress controls on the other hand avoid transient loops. Both schemes however are equally exposed to other forms of loops, which occur outside of the transient interval, i.e. the ones that are caused by other factors such as say software bugs. This latter category however are likely to occur with a much lower frequency. For the local control, the DS and US have the roughly same performance and DSD has the worst LACT. For the egress control, BCE and ECD have the same LACT if there is no diffusion computation involved, otherwise the difference may be noticeable. 6.1.2. Label Allocation Time (LAT) Tables 3 and 4 show the comparison of label allocation time (LAT) among the five allocation methods at 60% LSR utilization. Ayandeh and Fan [Page 11] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 Table 3 LAT Comparison (E1) -------------------------------------- LSR | DS | US | DSD | BEC | ECD -------+-----+-----+-----+-----+------ LSR01 | 189 | 183 | 241 | 193 | 193 LSR02 | 97 | 169 | 97 | 174 | 174 LSR03 | 186 | 242 | 229 | 257 | 257 LSR04 | 150 | 241 | 193 | 256 | 256 LSR05 | 189 | 249 | 238 | 267 | 267 LSR06 | 271 | 263 | 322 | 286 | 286 LSR07 | 229 | 302 | 278 | 327 | 327 LSR08 | 260 | 334 | 300 | 359 | 359 LSR09 | 299 | 293 | 358 | 320 | 320 LSR10 | 292 | 283 | 337 | 312 | 312 LSR11 | 266 | 308 | 306 | 334 | 334 LSR12 | 290 | 348 | 332 | 375 | 375 LSR13 | 327 | 322 | 373 | 348 | 348 LSR14 | 268 | 262 | 317 | 278 | 278 LSR15 | 228 | 310 | 269 | 330 | 330 -------------------------------------- Table 4 LAT Comparison (E2) -------------------------------------- LSR | DS | US | DSD | BEC | ECD -------+-----+-----+-----+-----+------ LSR01 | 182 | 177 | 233 | 287 | - LSR02 | 187 | 180 | 234 | 289 | - LSR03 | 208 | 177 | 230 | 276 | 407 LSR04 | 193 | 224 | 207 | 347 | 541 LSR05 | 166 | 97 | 173 | 285 | 497 -------------------------------------- For event 1, all LSRs will allocate a label for the route of the new attached network. The following is the label allocation LSR sequence, DS : LSR2, 4, 3, 5, 1, 15, 7, 8, 11, 14, 6, 12, 10, 9 and 13 US : LSR2, 1, 4, 3, 5, 14, 6, 10, 9, 7, 11, 15, 13, 8 and 12 DSD : LSR2, 4, 3, 5, 1, 15, 7, 8, 11, 14, 6, 12, 10, 9 and 13 BEC : LSR2, 1, 4, 3, 5, 14, 6, 10, 9, 7, 15, 11, 13, 8 and 12 ECD : LSR2, 1, 4, 3, 5, 14, 6, 10, 9, 7, 15, 11, 13, 8 and 12 For event 2, only LSR1 - LSR5's label for N6 will be affected by either re-allocation or re-sending/checking binding information. The LSR sequence is as follows, DS : LSR5, 1, 2, 4 and 3 US : LSR5, 3, 1, 2 and 4 DSD : LSR5, 4, 3, 1 and 2 BEC : LSR3, 5, 1, 2 and 4 ECD : LSR3, 5 and 4 Ayandeh and Fan [Page 12] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 From the LSR sequence we may see the differences among those allocation methods and get the sense of why one takes longer than the other. 6.2. Impact on the Routing Convergence Table 5 shows the impact on routing (OSPF) and the RTCT among the five allocation methods generically referred to as MPLS. Differences between label allocation schemes are negligible (within 0.17 %) since the work times assumed are similar and SP calculation has priority over label processing. Table 5 RTCT Comparison (E1&E2) -------------------------------- | E1 | E2 ------------------+------------- LU | OSPF | MPLS | OSPF | MPLS ----+------+------+------+------ 10 | 155 | 155 | 126 | 126 20 | 166 | 166 | 136 | 136 30 | 184 | 184 | 148 | 149 40 | 224 | 225 | 181 | 181 50 | 259 | 259 | 214 | 215 60 | 360 | 361 | 289 | 291 70 | 539 | 539 | 429 | 431 80 | 895 | 895 | 734 | 735 -------------------------------- The impact of running explicit label distribution protocols is very small on the routing convergence and the five methods have almost the same performance and impact. These simulation results very much depend on the assumption about work-time value of Allocating Task. In order to assess the sensitivity of the results with respect to this assumption, we enlarge these value by a factor of 10 and 25 times. This analysis shows that the simulation results are not sensitive to those values until label allocation will take roughly the same or more time than routing table computation. This is only likely to occur for a large number of route updates. For details see Appendix A. 6.3. Loops In order to capture the multiple hop loops, we add an asymmetric link to the network between LSR5 and LSR15. The bandwidth from LSR15 to LSR5 is 3xOC3 and the bandwidth from LSR5 to LSR15 is half an OC3. We consider Event 2 (E2 where link between LSR5 and LSR7 goes down) with no repetition. Our simulation results show that the same link Ayandeh and Fan [Page 13] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 failure event does not always create the L3 transient multiple-hop loop and the L3 transient loop does not always result in L2 loop. The occurrence of transient loops (L3, L2) very much depends on the sequence of (events leading to) routing table updates and label allocation. The following is the case that we capture both L3 and L2 multiple-hop transient loops. The LU is 80%. The next hops to N6 before and after the link failure are Table 6 Next Hop to N6 ---------------------------- LSR No. | Before | After ----------+--------+-------- 5 | LSR7 | LSR4 4 | LSR5 | LSR3 3 | LSR15 | LSR15 15 | LSR5 | LSR11 ---------------------------- 6.3.1. L3 Loop There is one four-hop transient loop. Taking the link failure as start of time, this loop starts at 113 and ends at 354, with the duration of 241 us. +--> LSR5 --> LSR4 --> LSR3 --> LSR15 --+ | | +---------------------------------------+ The loop intensity index (LI) is 0.019 ((14*241)/(225*773)). 6.3.2. L2 Loop a) Local Control There is one multiple L2 transient loop when using downstream allocation (DS) +--> LSR5 --> LSR4 --> LSR3 --> LSR15 --+ | | +---------------------------------------+ This loop is from 212 to 354 and its duration is 142 us. The L2 loop is completely covered by the L3 loop. The LI is 0.092 = ((7*142)/(14*773)). Ayandeh and Fan [Page 14] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 Note: Since the set of paths in L3 and L2 looping consideration is different, currently the LIs in two cases are not comparable. Table 7 below shows the routing table update time and the label allocation times which lead to the loops described above. Table 7 RTUT & LAT ---------------------- LSR No.| RTUT | LAT --------+------------- 5 | 100 | 212 4 | 113 | 212 3 | 208 | 209 15 | 354 | 355 ---------------------- b) Egress Control Egress control label allocation can avoid L2 loop setup. With the same L3 transient loop, egress control allocation allows L2 loop-free LSP setup. This is because egress control uses the LSR path vector, similar in function to the BGP AS_PATH attribute. 6.3.3. Discussion The L3 loop is the same for both local control and egress control. Local control may create the L2 loop. This is because an LSR can assign a label whenever it wants. This independence results in a short LACT (355 us). The shorter LACT is, the more stable the networks is. Egress control can avoid the L2 loops. The reason is that when routes are changing, the node R detects a change in the next hop for a given stream, it asks its new next hop for a label and the associated LSR ID list. It then makes sure that R's ID is not in the LSR ID list received from the new next hop. R either grows a new switched path upstream tree to replace the old LSP (BEC) or starts a "Diffusion Computation" to prune the tree upstream of R by removing all LSRs on that tree which would be on a looping path if R was to switch-over to the new path (ECD). Then R can replace the old LSP with the new LSP without causing any loops. Egress control introduces the dependence among the LSRs. This dependence results in a longer LACT, 872 for BEC and 1586 for ECD. LACT increases by 517 (146%, more) and 1231 (347% more), compared with DS. The benefits of using ECD is avoiding the unnecessary unsplicing/ resplicing (LSR1, 2, 3, 14 in this case). The disadvantage of ECD is the longer LACT. Comparing with BEC, ECD increases LACT by 714 Ayandeh and Fan [Page 15] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 (82% more). The comparison between BEC and ECD is shown in Table 8. Table 8 LAT ---------------------- LSR No.| BEC | ECD --------+-----+------- LSR01 | 855 | - LSR02 | 822 | - LSR03 | 872 | 1004 LSR04 | 858 | 1586 LSR05 | 862 | 1288 LSR14 | 734 | - LSR15 | 822 | 1117 ---------------------- 7. Conclusion Label allocation convergence time (LACT) is the important metric to indicate how fast the whole network is fully capable of doing label forwarding again after a route change. To design an LDP with short LACT is one major goal of network design. Simulations show that when topology changes, local control has much shorter LACT than egress control. The period of layer-2 instability is therefore shorter for local controls. However this period may be accompanied by layer-2 loops. The topology change may cause L3 transient loops and the L3 loops may result the L2 loops. Our simulation shows that the L2 loops are overlapped by the L3 loops completely and that their duration is shorter than the latter. The egress control can avoid the L2 loops and local control can not. However egress controls suffer from a longer period when forwarding based on labels may not be available. This period overlaps with the interval when layer-3 loops are present (i.e. layer-3 forwarding may not help). More simulations are currently underway to quantify the benefits of each scheme using a single metric. Egress control with diffusion can avoid the unnecessary unsplicing/ resplicing when using basic egress control, but again with a longer LACT. Route Computation should have the priority over the label allocation, since LIB is built on top of FIB. Our simulation results show that for single route updates, running LDP has a minor impact on routing convergence. The five label allocation methods have almost the same and minor impact on routing convergence(see Appendix A). Appendix A The sensitive analysis of the time of label allocating (in Allocating Task) Ayandeh and Fan [Page 16] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 The assumption we make on Allocating Task is as following handling local assignment is 1.0 us, remote assignment 1.0 us, local/remote assignment with LSR ID checking 1.5 us and all others 0.2 us To make thing worse, we enlarge those value by 10 and 25 times. There are three sets of values set 1: 1.0/1.0/1.5/0.2 set 2: 10.0/10.0/15.0/2.0 set 3: 25.0/25.0/37.5/5.0 Using set 2, the time for allocation is still smaller than computing time(57.5 us), and the time for allocation is almost the same at some LSRs and lager in most LSRs than computing time for set 3. The LU is Low(20), Median(50) and High(80) Table 9 LACT (E1) ---------------------------------------------- Set No. | DS | BEC +-----+-----+-----+-----+-----+------ | Low | Med | High| Low | Med | High ---------+------+-----+------+-----+------+--- No. 1 | 169 | 267 | 918 | 179 | 310 | 1139 No. 2 | 188 | 289 | 939 | 225 | 368 | 1212 No. 3 | 218 | 325 | 974 | 343 | 483 | 1324 ----------------------------------------------- Table 10 RTCT (E1) ---------------------------------------------- Set No. | DS | BEC +-----+-----+-----+-----+-----+------ | Low | Med | High| Low | Med | High ---------+-----+-----+-----+-----+-----+------ No. 1 | 166 | 259 | 895 | 166 | 259 | 895 No. 2 | 166 | 259 | 895 | 166 | 259 | 895 No. 3 | 166 | 260 | 898 | 166 | 259 | 895 ----------------------------------------------- References [1] "A Framework for Multiprotocol Label Switching", R. Callon, P. Doolan, etc., work in progress, draft-mpls-framework-01.txt, July 1997 [2] "A Proposed Architecture for MPLS", E. Rosen, A. Viswanathan, R. Callon, work in progress, draft-ietf-mpls-arch-00.txt, August 1997 Ayandeh and Fan [Page 17] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998 [3] "Cisco Systems' Tag Switching Architecture Overview", Y. Rekhter, B. Davie etc., RFC 2105, February 1997 [4] "Tag Distribution Protocol", P. Doolan, B. Davie etc., work in progress, draft-doolan-tdp-spec-01.txt, May 1997 [5] "ARIS: Aggregate Route-Based IP Switching", A. Viswanathan etc., work in progress, draft-viswanathan-aris-overview-00.txt, March, 1997 [6] "ARIS Specification", N. Feldman and A. Viswanathan, work in progress, draft-feldman-aris-spec-00.txt, March 1997 [7] "OSPF version 2", J. Moy, RFC 1583, March 1994 Authors' Address Siamack Ayandeh Northern Telecom P.O Box 3511, Station C Ottawa, Ontario Canada (613) 763-3645 ayandeh@nortel.ca Yanhe Fan Northern Telecom P.O Box 3511, Station C Ottawa, Ontario Canada (613) 765-2315 yanhe@nortel.ca Ayandeh and Fan [Page 18] Internet Draft draft-ayandeh-mpls-dynamics-00.txt March 1998