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]