Network Working Group P. Francois Internet Draft O. Bonaventure Expiration Date: July 2006 M. Shand S. Previdi S. Bryant March 2006 Loop-free convergence using ordered FIB updates draft-francois-ordered-fib-01.txt Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This draft proposes a mechanism to prevent transient loops during non-urgent topology changes by ordering the FIB updates on routers, in networks which use link state routing protocols. This mechanism can be used in case of graceful link shutdowns, metric changes and when a link is enabled. The mechanism can also be used in the case of link-state change of a set of links attached to one common node, e.g. a linecard removal. The solution can also be used in conjunction with a FRR mechanism which turns a sudden link failure into a non-urgent change, by ensuring a local protection of the link, if protection is ensured for all the prefixes that are reached via this link. After a non-urgent topology change, each router computes a rank that defines Francois et al. Expires July 2006 [Page 1] Internet Draft Ordered FIB Updates March 2006 the time at which it can safely update its FIB. A completion message mechanism is also proposed in order to speed up the convergence process. 1. Introduction With link-state protocols [ISIS,OSPF], each time the network topology changes, some routers need to modify their Forwarding Information Base (FIB) to take into account the new topology. Each topology change causes a convergence phase. During this phase, routers may transiently have inconsistent FIBs, which leads to packet loops and losses, even if the reachability of the destinations is not compromised after the topology change. Packet losses and transient loops can also occur in the case of a link down event implied by a maintenance operation, even if this operation is predictable and not urgent. When the link state change is a metric update and when a new link is brought up in the network, there is no direct loss of connectivity, but transient packet loops and loss can still occur. For example, in Figure 1, we can see that if the link between X and Y is shut down by an operator, packets destined to X can loop between R and Y when Y has updated its FIB while R has not updated its FIB yet, and packets destined to Y can loop between X and S if X updates its FIB before S. According to the current behaviour of ISIS and OSPF, this scenario will happen most of the time because X and Y are the first routers to be aware of the failure, so that they will update their FIB at first. 1 X-------------/-------------Y | | | | | | | | 1 | | 1 | | | | | | | | S---------------------------R 2 Figure 1 : A simple topology The goal of this draft is to define a mechanism aimed at ordering the updates of the FIB among the routers of the network to ensure the Francois et al. Expires July 2006 [Page 2] Internet Draft Ordered FIB Updates March 2006 transient consistency of the FIBs, so that no forwarding and packet losses can occur, in the case of predictable link-state changes, i.e. link metric update, manual link down/up, manual router down/up, and predictable state changes of a set of links attached to one router (e.g a linecard). If a link is protected [IPFRR,MPLSFRR], a loop free convergence mechanism can also be used in place of the usual fast, best effort approach, to avoid forwarding loops in the upstream routers. The mechanisms that are used are exactly the same, so that we will only talk about predictable changes in the remainder of the paper. This document is organised as follows. We first show in section 2 that there is an ordering for the FIB updates that allows to avoid all transient loops when a single link fails, is activated or when an IGP metric changes. We also present an essentially similar ordering for the events affecting a set of links with one common node, e.g. a linecard removal. In section 3, we present an implementation of the ordering schemes. In section 4, a mechanism aimed at speeding up the loop-free convergence process is presented. We extend the mechanism to support general SRLG down and SRLG up events, in Appendix B. 2. Ordering of the FIB updates In this section, we briefly present an ordering of the FIB updates that allows to avoid transient forwarding loops in the network in the case of topology changes. A more detailed analysis of the rerouting dynamics and correctness proofs of the mechanism can be found in [PFOB05]. 2.1 Single Link events 2.1.1 Link down / metric increase We first consider the non-urgent failure of a link or the increase of the metric associated with one directed link. In this case, to ensure the transient consistency of the forwarding tables of the routers, a router R should update its FIB AFTER all the routers that used R BEFORE the event to reach the affected link. Let us show that this rule ensures the transient consistency of all the routers. We assume that the link X->Y is manually shut down or that its metric is increased. We define an outdated FIB for a destination as being a FIB that still reflects the shortest paths that were used before the change in the topology to reach the destination. Firstly, once a packet reaches a Francois et al. Expires July 2006 [Page 3] Internet Draft Ordered FIB Updates March 2006 router R with an outdated FIB for its destination, it will only traverse routers with an outdated FIB, when the ordering is respected The packet thus reaches X and it will be forwarded along X->Y and reach its destination. Y cannot use the link X<->Y to reach the destination, as it would mean that there was a forwarding loop before the event. The paths between Y and the destination are still valid and will not change, so that the packet arriving in Y will reach its destination. Secondly, a packet cannot loop while being exclusively forwarded by routers with an updated FIB. Otherwise, there would be a permanent loop after the convergence, so that any packet is proved to never enter a loop. In other words, when the ordering is respected, a packet enters the network and follows a path composed of updated or unaffected routers. If it reaches an outdated router, it cannot reach an updated router anymore, so that it will not loop as it is forwarded on the consistent path that was used before the event. If it does not reach an outdated router, it will be forwarded on the loop free path that will be used after the convergence. According to the proposed ordering, X and Y will be the last routers to update their FIB. Once both routers have updated their FIB, the link can actually be shut down. 2.1.2 Link up / metric decrease In the case of link up events or metric decreases, to ensure the transient consistency of the forwarding tables of the routers, a router R should update its FIB BEFORE all the routers that WILL use R to reach the affected link. Let us show that this rule ensures the transient consistency of the routers. We assume that the link X->Y goes up or that its metric is decreased. Firstly, when a packet reaches a router R that has already updated its FIB, all the routers on the path from R to X have also updated their FIB, so that the packet will reach X and be forwarded along X->Y, to finally reach its destination. Secondly, a packet cannot loop between routers that have not yet updated their FIB, so that any packet is proved to never enter a loop. 2.2 SRLG events with one node in common. Francois et al. Expires July 2006 [Page 4] Internet Draft Ordered FIB Updates March 2006 Topological events can affect the state of a set of links. Some of those events are sometimes caused by maintenance operations. For example, a router shutdown or a linecard removal is a predictable operation that should not cause packet losses or transient loops. Quite similarly, when a router is brought up in the network or a linecard is set up, no transient forwarding loops should be possible. When a set of links is affected by a non-urgent event, it is possible that a few LSPs are required to fully describe the topological change. For example, in the case of a router up event, the LSPs of the router coming up and the LSP of its neighbours are required to consider the links as being up. Another example is the case where a router is shut down and has not the opportunity to send a LSP to describe the failure of all its links. To solve that issue, a router that receives a LSP describing a non-urgent event SHOULD wait a period of time to be able to detect the whole description of the event and find out that this is an event concerning links that have one node in common. 2.2.1 Router down events An ordering of the FIB updates can also avoid transient loops in the case of a router down event. There are multiple implementation choices to advertise the failure of a node. Firstly, a router being shut down can send a new link-state packet that describes the failure of all its links, by setting the cost of each link to MAX_COST. Secondly, the router can purge its own link-state packet. Finally, and only in IS-IS, the router can send its link-state packet by setting the overload-bit. All those solutions will let the other routers of the network know about the failure by receiving one single message. The other routers of the network can avoid transient loops while adapting to the node failure by respecting a rule that is very similar to the one mentioned in the case of a link down event : A router R should update its FIB AFTER all the routers that use R to reach the router that is shutdown. Let us show that this ordering ensures the transient consistency of the forwarding. We assume that the router X is being shut down. Router X will be effectively shut down once all its neighbours have updated their FIB, which implies that it will be shutdown once all the routers of the network have updated their FIB. Francois et al. Expires July 2006 [Page 5] Internet Draft Ordered FIB Updates March 2006 Firstly, if a packet to a destination D reaches a router that has not updated its FIB and that used X to reach D, it will only traverse routers that have not updated their FIB, to finally reach X. X will then forward the packet to its nexthop for D, and the packet will reach its destination. This nexthop could not have X in its path(s) to D before the event, as the contrary would mean that there was a loop before the event. Secondly, a packet that does not reach a router with an outdated FIB cannot loop. Otherwise, there would be a permanent loop after the convergence. 2.2.2 Router up events The ordering of the FIB updates follows a rule that is very similar to the rule mentioned in the case of a link up event. A router R should update its FIB BEFORE all the routers that WILL use R to reach the router that is brought up. Let us show that this ordering ensures the transient consistency of the forwarding. We assume that the router X comes in the network. Firstly, when a packet with destination D reaches a router R that has already updated its FIB, and that uses X to reach D, the packet will reach X as it will traverse routers that have already updated their FIB. X will then forward the packet to its nexthop for destination D. The path from this nexthop to D cannot contain X, so that the packet is proved to be consistently forwarded to D. Secondly, a packet that exclusively traverses routers with an outdated FIB cannot loop. Otherwise, there was a permanent loop before the event. 2.2.3 Sets of links with one common node. Those kinds of events also have the particularity that they can be described with one single link-state update packet, i.e. the link- state packet of the node that is adjacent to all the links whose state is changing. When those links are going down or their metric is increased, the ordering that is applied for router down events can also be used. When those links are going up or their metric is decreased, the ordering that is applied for router up events can also be used. 3. Implementation of the ordering Francois et al. Expires July 2006 [Page 6] Internet Draft Ordered FIB Updates March 2006 In this section, we show how the proposed ordering can be applied by routers that have to adapt to a topology change. 3.1 Single link events 3.1.1 Link down / metric increase To respect the proposed ordering, routers can compute a rank that will be used to determine the time at which they can perform their FIB update. In the case of the failure of link X->Y or an increase of the metric of link X->Y, router R will compute the reverse Shortest Path Tree (rSPT) of Y. This rSPT gives the shortest paths to reach Y. The branch of the reverse SPT that is below R corresponds to the set of shortest paths to R that are used by the routers that reach X->Y via R. We define the rank of router R as the depth (in number of hops) of this branch. In the case of ECM paths, we use the maximum depth. Router R will update its FIB at time : T0 + rank * MAX_FIB where T0 is the arrival time of the link-state packet containing the topology change and MAX_FIB a network-wide constant that reflects the maximum time required to update a FIB. The value of MAX_FIB is implementation specific and is out of the scope of this document. This value must be agreed by all the routers of the network. This agreement can be done by using a capability TLV as defined in [SLFTV]. All the routers that use R to reach X->Y will compute a lower rank than R, so that the order will be respected. It should be noted that only the routers that used X->Y before the event have to compute their rank. 3.1.2 Link up / metric decrease In the case of a link up or a link metric decrease affecting link X->Y, a router R must have a rank that is higher than the rank of the routers that it will use to reach X->Y, according to the rule mentioned in section 2.1.2. The rank of R is thus equal to the number of hops between R and X in its Shortest Path Tree. When R has multiple equal cost paths to X, the rank is the length of the longest path in hops to X. Router R will update its FIB at time : T0 + rank * MAX_FIB where T0 is the arrival time of the link-state packet containing the topology change and MAX_FIB a network-wide constant that reflects the maximum time required to update a FIB. Francois et al. Expires July 2006 [Page 7] Internet Draft Ordered FIB Updates March 2006 It should be noted that only the routers that use X->Y after the event have to compute a rank, i.e. only the routers that have X->Y in their SPT after the link-state change. 3.2 SRLG events with one node in common 3.2.1 Router down events When a router X is shut down, the rank that has to be applied by a router R is equal to the depth of the branch under R in rSPT(X). In the case of ECM paths to R, the maximum of the length must be taken into account. Note that X will only be actually shut down once all the routers have updated their FIB. The rank that is computed by X thus gives the time at which X can be effectively shut down. 3.2.2 Router up events When a router X comes in the network, the rank that has to be applied by a router R is equal to the maximum length of its ECM paths to X, in its updated Shortest Path Tree. Note that X will be the first to update its FIB, as it will have a rank equal to 0. This translates the fact that X must have updated its FIB before any router can use it to forward packets. 3.2.3 Sets of links with one common node. When a set of links attached to a given node is shut down, the algorithm that has to be applied to respect the ordering is the same as if the common node was shut down. When a set of links attached to a given node is brought up, the algorithm that has to be applied to respect the ordering is the same as if the node was brought up in the network. 4. Completion messages 4.1 General Idea As noted in the previous sections, only the routers that are currently using a link affected by a topology change need to update their FIB. The FIB of all the other routers does not need to be updated at all. Furthermore, the routers that need to update their FIB do not necessarily need MAX_FIB seconds to perform their FIB update [CCRJULY]. Francois et al. Expires July 2006 [Page 8] Internet Draft Ordered FIB Updates March 2006 In this section, we show how completion messages can be used to speed up the convergence after a non-urgent topology change by shortcutting the computed rank while respecting the transient consistency of the routers. To do this, we adapt the mechanism proposed in [PFOB05]. Routers maintain a waiting list, that lists the neighbours from which they have to wait for a completion message before being allowed to update their own FIB. Upon reception of a completion message from a neighbour, a router removes this neighbour from its waiting list. Once its waiting list becomes empty, the router is allowed to update its FIB. Once this is done, the router is allowed to send a completion message to the neighbours that have to wait for it. Those routers are listed in a list called Notification List. Completion messages contain an identification of the event it refers to, by specifying the change in the state of the concerned link. The next sections explain how the waiting list W must be built for each type of event, and when completion messages are sent by the routers. We also describe how the Notification list N must be built. Note that the solution works if each router considers the set of its neighbours as its notification list. However, this is not optimal as completion messages could be sent to neighbours that do not need them. 4.2 Format of completion messages The format of completion is protocol dependent. The information that has to be encoded in the completion messages is an identification of the link to which the messages refers. For the cases where a set of links attached to the same routers is shut down or brought up, the message can either contain the identifications of the concerned links or simply the identification of the node that is common to this set of links. 4.3 Construction of the waiting list and notification lists 4.3.1 Single link events 4.3.1.1 Link down / metric increase Let us assume that the link X->Y goes down, or its metric is increased. A router R that currently has X->Y in its SPT computes rSPT(Y) to determine its rank. By doing this, it computes the set of routers (and thus implicitly the set of its neighbours) that use it to reach link X->Y. The waiting list of R is equal to the set of Francois et al. Expires July 2006 [Page 9] Internet Draft Ordered FIB Updates March 2006 neighbours that use it to reach X->Y. These are the neighbours below R in rSPT(Y). The current SPT of R gives the set of neighbours that R uses to reach X->Y. These neighbours have to wait for R, and R is thus present in their waiting list. The notification list of R contains contains those neigbours. 4.3.1.2 Link up / metric decrease Let us assume that the link X->Y goes up, or its metric is updated. A router R will compute its new SPT (SPT_new(R)). If X->Y is present in SPT_new(R), R will use link X->Y and thus needs to compute its rank. For this, R computes the set of routers (and implicitly its set of neighbours) that it uses to reach X->Y. The nexthops for X in SPT_new(R). R must reroute after those routers to respect the ordering. Its waiting list is thus equal to those nexthops. When R has updated its FIB, it can send a completion message to its neighbours, so that a neighbour that has R in its waiting list will be allowed to remove R from it. The notification list of R thus contains all the neighbours of R. Note that R is not forced to send a completion message to the initial members of its Waiting List, as these neighbours will not wait for a completion message from R. 4.3.2 SRLG Events with one node in common 4.3.2.1 Router down Let us assume that a router X goes down. A router R will compute rSPT(X) to determine its rank. When doing this, it also computes the set of its neighbours that use R to reach X. The waiting list of R is equal to this set. The current SPT of R gives the set of neighbours that will have R in their waiting list. Once R has updated its FIB, it will send its completion messages to those neighbours. Note that R could send a completion message to all its neighbours, this has no impact on the correctness of the protocol. 4.3.2.2 Router up Let us assume that a router X comes in the network. A router R will compute its new SPT. It thus also computes its nexthops for X. This set of nexthops (more than one in the case of equal cost paths to X) is the waiting list that R will use. Once R has updated its FIB, it sends a completion message to its Francois et al. Expires July 2006 [Page 10] Internet Draft Ordered FIB Updates March 2006 neighbours, so that a neighbour that has R in its waiting list will be allowed to remove R from it. 4.3.2.3 Sets of links with one common node When a set of links attached to one given router X goes down, the same ordering as for the failure of node X has to be respected. Thus, the construction of the waiting list is exactly the same. The waiting list of a router R is the set of neighbours of R that use R to reach X. This set is obtained by computing rSPT(X). When a set of links attached to one given router X goes up, the same ordering as for a router X up event has to be respected. Thus the construction of the waiting list is exactly the same. The waiting list of a router R is the set of neighbours of R that R will use to reach X in the new topology. These are the nexthops for X in the updated SPT of R. Security Considerations No security issues are introduced by this draft, as it only proposes algorithms. Potential security issues should be discussed in the documents that apply the proposed mechanism to IS-IS and OSPF. Acknowledgements We would like to thank Clarence Filsfils and Jean Philippe Vasseur for their contribution to the ideas presented in this draft. IANA Considerations This draft requires no IANA actions. References [OSPF] J. Moy, OSPF Version 2. RFC 2328. Apr. 1998. [IS-IS] "Intermediate system to Intermediate system routeing information exchange protocol for use in conjunction with the Protocol for providing the Connectionless -mode Network Service (ISO 8473)",ISO/IEC 10589:2002, Second Edition. Francois et al. Expires July 2006 [Page 11] Internet Draft Ordered FIB Updates March 2006 [IPFRR] M. Shand, S. Bryant, IP Fast Reroute Framework, draft-ietf-rtgwg-ipfrr-framework-03.txt, June 2005 [MPLSFRR] Pan, P. et al, "Fast Reroute Extensions to RSVP-TE for LSP Tunnels", RFC 4090 [PFOB05] P. Francois, O. Bonaventure. Avoiding transient loops during IGP convergence. IEEE INFOCOM 2005, March 2005, Miami, Fl., USA www.info.ucl.ac.be/people/OBO/papers/pfr-infocom05.pdf [CCRJULY] P. Francois, C. Filsfils, J. Evans, O. Bonaventure. Achieving sub-second IGP convergence in large IP networks, ACM SIGCOMM Computer Communication Review, July 2005 http://portal.acm.org/citation.cfm?id=1070873.1070877 [SLFTV] A. Atlas, S. Bryant, M. Shand, Synchronization of Loop Free Timer Values, draft-atlas-bryant-shand-lf-timers-00.txt Appendix A : Pseudo-codes Figure 2 shows the pseudocode for the router reaction in case of non- urgent link failure or metric increase. Pseudo-code for link (X->Y) down/metric increase in router R : If(X->Y in SPT(R)){ //R is affected by the event //Compute rspt(Y) rspt = rSPT(Y); //compute the rank from rspt (can also be done directly //during rspt computation) worst_case_update_delay = depth(R,rspt) * MAX_FIB //Build the waiting list : these are the neighbours below R in rspt // WaitingList = getNeighboursUpstream(R,rspt); //Build the list of neighbours to which R will send a //completion message : //these are the nexthops for X in the current SPT of R completionMessageSendingList = nexthops(X,SPT(R)); Francois et al. Expires July 2006 [Page 12] Internet Draft Ordered FIB Updates March 2006 //Wait for the waiting list to be empty or the rank time //to elapse. while(not (WaitingList.empty()) || worst_case_update_delay.elapsed()){ if(completionMessageReceived()){ //New completion message received WaitingList.remove(completionMessage.sender); } } //Rank time has elapsed or waiting list is empty UpdateFIB(); //FIB has been updated, send completion messages ForEach(N in completionMessageSendingList){ send(N,"FIB Updated for X->Y"); } } else{ //R is not affected by the event, nothing to do } Figure 2 : Pseudocode for link down/metric increase Figure 3 provides the pseudocode for the reaction of a router to a non-urgent link up or metric decrease event. Pseudo-code for link (X->Y) up/metric decrease in router R : //Compute the new SPT. newSPT = computeSPT(R) If(X->Y in newSPT){ //R is affected by the event //compute the rank of the router. This is the length (in hops) //from R to X in the new spt. (note that it is equal to the //length from R to X in the old spt. worst_case_update_delay = PathLength(R,X,newSPT) * MAX_FIB //Build the waiting list : the nexthops for X in the new SPT. WaitingList = nexthops(R,X,newSPT); //Wait for the waiting list to be empty or the rank time to elapse. while(not(WaitingList.empty())||worst_case_update_delay.elapsed()){ if(completionMessageReceived()){ //New completion message received WaitingList.remove(completionMessage.sender); } } //Rank time has elapsed or waiting list is empty Francois et al. Expires July 2006 [Page 13] Internet Draft Ordered FIB Updates March 2006 UpdateFIB(); //Fib updated, send completion messages to the neighbours. ForEach(N in Neighbours(R)) Send(N,"Fib Updated X->Y"); } else{ //R is not affected by the event, nothing to do } Figure 3 : Pseudocode for link up/metric decrease Appendix B : General SRLG case B.1 Orderings B.1.1 SRLG down When a set of links is shut down, routers must update their FIB by respecting an ordering such that, when a packet destined to p reaches a rerouting router R (for the destination D), that has not updated its FIB for D yet, the packet will follow the path from R to D that was followed before the event. This means that a router R can only update its FIB for a destination D after the routers that used R to reach D. B.1.2 SRLG up When a set of links is brought up in the network, routers must update their FIB by respecting an ordering such that, when a packet destined to D reaches a rerouting router R (for the destination D), that has already updated its FIB for D, the packet will follow the post- convergence path from R to D. This means that a router R can only update its FIB for a destination D after the routers that R will use to reach D. B.2 Implementation B.2.1 SRLG down When a router has to reroute by considering that a set of links is shut down, it will compute the ranks associated with each of the links being shut down. It does this by applying the same algorithm as for single link down events. The rank at which a router R must update its FIB for a destination D is equal to the minimum rank among the Francois et al. Expires July 2006 [Page 14] Internet Draft Ordered FIB Updates March 2006 ranks of the links that R uses to reach the destination D. In the worst-case, a router R will have to split the set of destinations to be updated in as many groups as there are links being shut down. B.2.2 SRLG up When a router has to reroute by considering that a set of links is brought up, it will compute the ranks associated with each of the links being brought up. It does this by applying the same algorithm as for single link up events. The rank at which a router R must update its FIB for a destination D is equal to the maximum rank among the ranks of the links that R will use to reach the destination D. In the worst-case, a router R will have to split the set of destinations to be updated in as many groups as there are links being brought up. B.3 Completion messages B.3.1 SRLG down A router R implicitely computes the waiting lists associated with the links being shut down when it determines the ranks that have to be applied. The waiting list associated with a link X-->Y contains the neigbours of R that were using R to reach Y via X-->Y. These are the routers that are below R in rSPT(Y) When R has received a completion message from all the members of the waiting list associated with one link, it is allowed to update its FIB for all the destinations that it was previously reaching via this link. This is true even if it has not received the necessary completion messages for the other links being shut down that it also uses to reach the destinations. A router will send a completion message to its neighbours for a given link being shutdown once it has updated its FIB for all the prefixes that it reached via the link. B.3.2 SRLG up A router R implicitely computes the waiting lists associated with the links being brought up when it determines the ranks that have to be Francois et al. Expires July 2006 [Page 15] Internet Draft Ordered FIB Updates March 2006 applied. The waiting list associated with a link X-->Y contains the neighbours of R that R will use the reach Y via X-->Y in the new topology. A router R is allowed to update its FIB for a destination D once it has received a completion message from all the members of the waiting lists associated with the links being brouth up that R will use to reach D. A router R is allowed to send a completion message for a link X-->Y when it has updated its FIB for the destinations that it will reach via X-->Y. The semantics of the completion message is exclusive, which means that if R will use two links being brought up to reach a destination D, and R has sent a completion message for only one of the links, R may have not updated its FIB for the destination D. Authors' Addresses Pierre Francois Universite catholique de Louvain Place Sainte Barbe, 2 B-1348, Louvain-La-Neuve Belgium Email: pfr@info.ucl.ac.be Olivier Bonaventure Universite catholique de Louvain Place Ste Barbe, 2 B-1348, Louvain-La-Neuve Belgium Email: Bonaventure@info.ucl.ac.be Mike Shand Cisco Systems, 250, Longwater Avenue, Green Park, Reading, RG2 6GB, United Kingdom Email: mshand@cisco.com Stefano Previdi Cisco Systems Via Del Serafico 200 00142 Roma - Italy Email : sprevidi@cisco.com Francois et al. Expires July 2006 [Page 16] Internet Draft Ordered FIB Updates March 2006 Stewart Bryant Cisco Systems, 250, Longwater Avenue, Green Park, Reading, RG2 6GB, United Kingdom Email: stbryant@cisco.com Intellectual Property Considerations The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf- ipr@ietf.org. Full Copyright Statement Copyright (C) The Internet Society (2006). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Francois et al. Expires July 2006 [Page 17]