INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
Network Working Group S. Bryant
Internet Draft M. Shand
Expiration Date: Sep 2005 Cisco Systems
Mar 2005
IP Fast Reroute Using Notvia Addresses
<draft-bryant-shand-ipfrr-notvia-addresses-00.txt>
Status of this Memo
By submitting this Internet-Draft, we certify that any applicable
patent or other IPR claims of which we are aware have been
disclosed, or will be disclosed, and any of which we become aware
will be disclosed, in accordance with RFC 3668.
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/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
Abstract
This draft describes a mechanism that provides fast reroute in an
IP network through encapsulation to "notvia" addresses. A single
level of encapsulation is used. The mechanism protects unicast,
multicast and LDP traffic against link, router and shared risk
group failure, regardless of network topology and metrics.
Conventions used in this document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in
this document are to be interpreted as described in RFC 2119
[RFC2119].
Bryant, Shand Expires Sep 2005 [Page 1]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
Table of Contents
1. Introduction........................................................3
2. Overview of Notvia Repairs..........................................3
3. Repair Computation..................................................4
4. How a repairing node repairs........................................5
4.1 Node Failure.....................................................5
4.2 Link Failure.....................................................5
4.3 Multi-homed Prefix...............................................6
4.4 Shared Risk Groups...............................................7
4.5 Multicast........................................................7
4.6 Fast Reroute in an MPLS LDP Network..............................7
5. Local Area Networks.................................................8
6. Loop Free Alternatives.............................................10
7. Equal Cost Multi-Path..............................................10
8. Encapsulation......................................................10
9. Routing Extensions.................................................11
10. Incremental Deployment............................................11
11. IANA considerations...............................................11
12. Security Considerations...........................................11
Bryant, Shand Expires Sep 2005 [Page 2]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
1. Introduction
When a link or a router fails, only the neighbors of the failure
are initially aware that the failure has occurred. In a network
operating IP fast reroute (IPFRR), the routers that are the
neighbors of the failure repair the failure. These repairing
routers have to steer packets to their destinations despite the
fact that most other routers in the network are unaware of the
nature and location of the failure.
A common limitation in most IPFRR mechanisms is an inability to
steer the repaired packet round an identified failure. The extent
to which this limitation affects the repair coverage is topology
dependent. The mechanism proposed here is to encapsulate the packet
to an address that explicitly identifies the network component that
the repair must avoid. This produces a repair mechanism, which,
provided the network in not partitioned by the failure, will always
achieve a repair.
2. Overview of Notvia Repairs
The purpose of a repair is to deliver packets to their destination
without traversing a known failure in the network, i.e. to deliver
the packet not via the failure. In its simplest form, this repair
mechanism works by assigning an additional address to each
interface in the network. This additional address is called the
notvia address. The semantics of a notvia address are that a packet
addressed to a notvia address must be delivered to the router with
that address, not via the neighboring router on the interface to
which that address is assigned.
To repair a failure, the repairing router encapsulates the packet
to the notvia address of the router interface on the far side of
the failure. The routers on the repair path then know to which
router they must deliver the packet, and which network component
they must avoid. The network fragment shown in Figure 1 illustrates
this.
A
|Ap Bp is the address to use to get
| a packet to B notvia P
Sp Pa|Pb
S----------P----------B
Ps|Pc Bp
|
Cp|
C
Figure 1: Notvia Addresses
Bryant, Shand Expires Sep 2005 [Page 3]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
Assume that S has a packet for some destination D that it would
normally send via P and B, and that S suspects that P has failed. S
encapsulates the packet to Bp. The path from S to Bp is the
shortest path from S to B not going via P. If the network contains
a path from S to B that does not transit router P, then the packet
will be successfully delivered to B. When the packet addressed to
Bp arrives at B, B removes the encapsulation and forwards the
repaired packet towards its final destination.
Note that a packet may back track after the encapsulation is
removed. However, because the decapsulating router is always closer
to the packet destination than the encapsulating router, the packet
will not loop.
3. Repair Computation
The notvia repair mechanism requires that all routers on the path
from S to B (Figure 1) have a route to Bp. They can calculate this
by failing node P, running an SPF, and finding the shortest route
to B.
A router has no simple way of knowing whether it is on the shortest
path for any particular repair. It is therefore necessary for every
router to calculate the path it would use in the event of any
possible router failure. Each router therefore fails every router
in the network, one at a time, and calculates it own best route to
each of the neighbors of that router. In other words, again with
reference to Figure 1, some router X will consider each router in
turn to be P, fail P, and then calculate its own route to each of
the notvia P addresses advertised by the neighbors of P. i.e. X
calculates its route to Sp, Ap, Bp, and Cp, in each case, not via
P.
To calculate the repair paths a router has to calculate n-1 SPFs
where n is the number of routers in the network. This is expensive
to compute. However the problem is amenable to a solution in which
each router (X) proceeds as follows. X first calculates the base
topology with all routers functional and determines its normal path
to all notvia addresses. X then fails some router P and performs an
incremental SPF. This incremental calculation is terminated when
all of the notvia P addresses are attached to the SPT. X then
reverts to the base topology and repeats the process failing each
router P in turn.
This algorithm is significantly less expensive than a set of full
SPFs. Thus, although a router has to calculate the repair paths for
n-1 failures, the computational effort is much less than n-1 SPFs.
Experiments on a selection of real world network topologies with
between 40 and 400 nodes suggest that the worst case computational
complexity using the above optimizations is equivalent to
performing between 5 and 13 full SPFs.
Bryant, Shand Expires Sep 2005 [Page 4]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
4. How a repairing node repairs
This section explains the operation of each type of repair
necessary in the network.
4.1 Node Failure
When router P fails (Figure 1) S encapsulates any packet that it
would send to B via P to Bp, and then sends the encapsulated packet
on the shortest path to Bp. S follows the same procedure for
routers A, and C in Figure 1. The packet is decapsulated at the
repair target (A, B or C) and then forwarded normally to its
destination.
Notice that with this technique only one level of encapsulation is
needed, and that it is possible to repair ANY failure regardless of
link metrics and any asymmetry that may be present in the network.
The only exception to this is where the failure was a single point
of failure that partitioned the network, in which case ANY repair
is clearly impossible.
4.2 Link Failure
The normal mode of operation of the network would be to assume
router failure. However, where some destinations are only reachable
through the failed router, it is desirable that an attempt be made
to repair to those destinations by assuming that only a link
failure has occurred.
To perform a link repair, S encapsulates to Ps (i.e. it instructs
the network to deliver the packet to P notvia S). All of the
neighbors of S will have calculated a path to Ps in case S itself
had failed. S could therefore give the packet to any of its
neighbors (except, of course, P). However, S should preferably send
the encapsulated packet on the shortest available path to P. This
path is calculated by running an SPF with the link SP failed. Note
that this may again be an incremental calculation which can
terminate when address Ps has been reattached.
It is necessary to consider the behavior of IPFRR solutions when a
link repair is attempted in the presence of node failure. The
notvia IPFRR solution prevents the formation of loops forming as a
result of mutual repair, by never providing a repair path for a
notvia address. Referring to Figure 1, if A was the neighbor of P
that was on the link repair path from S to P, and P itself had
failed, the repaired packet from S would arrive at A encapsulated
to Ps. A would have detected that the AP link had failed and would
normally attempt to repair the packet. However, no repair path is
provided for any notvia address, and so A would be forced to drop
the packet, thus preventing the formation of loop.
Bryant, Shand Expires Sep 2005 [Page 5]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
4.3 Multi-homed Prefix
A multi-homed Prefix (MHP) is reachable via more than one router in
the network. When IPFRR router S (Figure 2) discovers that P has
failed, it needs to send MHP packets addressed to X, which are
normally reachable through P, to an alternate router, which is
still able to reach X.
X X X
| | |
| | |
| Sp |Pb |
Z...............S----------P----------B...............Y
Ps|Pc Bp
|
Cp|
C
Figure 2: Multi-home Prefixes
S should choose the closest router that can reach X during the
failure as the alternate router. S determines which router to use
as the alternate while running the SPF with P failed. This is
accomplished by continuing to run the incremental SPF with P failed
until all of P's notvia addresses and MHPs (X) are attached.
Assume that the alternate router is Z, which S can reach without
using the failed router P. S cannot just send the packet towards Z,
because the other routers in the network will not be aware of the
failure of P, and may loop the packet back to S. S therefore
encapsulates the packet to Z (using a normal address for Z). Z
removes the encapsulation and forwards the packet to X.
Now assume that the alternate router is Y, which S reaches via P
and B. To reach Y, S must first repair the packet to B using the
normal notvia repair mechanism. To do this S encapsulates the
packet for X to Bp. B removes the encapsulation and discovers that
the packet is intended for MHP X. B then follows the algorithm
above and B encapsulates the packet to Y (using a normal address
for Y). Y removes the encapsulation and forwards the packet to X.
It may be that the cost of reaching X using local delivery from the
alternate router is greater than the cost of reaching X via P.
Under those circumstances the alternate router would normally
forward to X via P, which would cause the IPFRR repair to loop. To
prevent the repair from looping the alternate router must locally
deliver a packet received via a repair encapsulation.
Notice that using the notvia approach, only one level of
encapsulation was needed to repair MHPs to the alternate router.
Bryant, Shand Expires Sep 2005 [Page 6]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
4.4 Shared Risk Groups
When the network contains a shared risk group (SRG), it must be
assumed that all members of the SRG fail simultaneously. When
undertaking SRG repair the scope of the notvia address therefore
changes from notvia a particular router to notvia the whole SRG.
All routers calculate a route to each of the notvia addresses of
the interfaces that connect the SRG to the rest of the network.
This calculation is made by simultaneously failing all members of
the SRG in the incremental SPF.
When a router that is adjacent to an SRG member makes a repair, it
encapsulates the packet to the notvia address of the router that
has the lowest cost from the SRG to the destination (i.e. the
egress point of the SRG prior to the failure).
Asrg Fsrg
S----------P------P'--------A----P''------F--------G
| | |
|Csrg |Dsrg |
C D E
| | |
| | |
H J K
Figure 3: Shared Risk Group
Thus in Figure 3, S would encapsulate to Csrg to reach H, to Dsrg
to reach J, to Asrg to reach K and to Fsrg to reach G.
4.5 Multicast
Multicast traffic is repaired in a similar way to unicast, however
the multicast forwarder is able to use the notvia address to which
the multicast packet was addressed as an indication of the expected
receive interface and hence to correctly run the required RPF
check.
A more complete description of multicast operation will be provided
in the next version of this draft.
4.6 Fast Reroute in an MPLS LDP Network.
Notvia addresses are IP addresses and LDP will distribute labels
for them in the usual way. The notvia repair mechanism may
therefore be used to provide fast re-route in an MPLS network by
first pushing the label which the repair endpoint uses to forward
the packet, and then pushing the label corresponding to the notvia
address needed to effect the repair. Referring once again to Figure
1, if S has a packet destined for D that it must reach via P and B,
S first pushes B's label for D. S then pushes the label that its
next hop to Bp needs to reach Bp.
Bryant, Shand Expires Sep 2005 [Page 7]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
Note that in an MPLS LDP network it is necessary for S to have the
repair endpoint's label for the destination. When S is effecting a
link repair it already has this. In the case of a node repair, S
either needs to set up a directed LDP session with each of its
neighbor's neighbors, or it needs to use the next-next hop label
distribution mechanism proposed in [NNHL]. Where an extended SRG is
being repaired, S must determine which routers its traffic would
traverse on egress form the SRG, and then establish directed LDP
sessions with each of those routers.
5. Local Area Networks
LANs are a special type of SRG and are solved using the SRG
mechanisms outlined above. With all SRGs there is a trade-off
between the sophistication of the fault detection and the size of
the SRG.
+--------------P'-------C
|
|
|
A--------S--------+
(N)
+--------------P--------B
|
|
|
+--------------P''------D
Figure 4 Local Area Networks
Consider the LAN shown in Figure 4. For connectivity purposes, we
consider that the LAN is represented by the pseudonode (N). To
provide IPFRR protection, S must run a connectivity check to each
of its protected LAN adjacencies P, P', and P'', using, for example
BFD [BFD].
When S discovers that it has lost connectivity to P, it is unsure
whether the failure is:
. its own interface to the LAN,
. the LAN itself,
. the LAN interface of P
. or the node P.
With no further diagnostics S must repair traffic sent through P
and B, to B notvia P,N (i.e. not via P and not via N), on the
Bryant, Shand Expires Sep 2005 [Page 8]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
conservative assumption that both the entire LAN and P have failed.
Destinations for which P is a single point of failure must as usual
be sent to P using an address which avoids the interface by which P
is reached from S, i.e. to P notvia N. Similarly for routers P' and
P''.
Notice that each router that is connected to a LAN must, as usual,
advertise one notvia address for each neighbor. In addition, each
router on the LAN must advertise an extra address not via the
pseudonode (N).
Notice also that each neighbor of a router connected to a LAN must
advertise two notvia addresses, the usual one not via the neighbor
and an additional one, not via either the neighbor or the
pseudonode. The required set of LAN address assignments is shown in
figure 5 below. Each router on the LAN, and each of its neighbors,
is advertising exactly one address more than it would otherwise
have advertised if this degree of connectivity had been achieved
through the use of point to point links.
P's P'p P'c Cp'n
+--------------P'-------C
| P'p''Pn Cp'
|
Asn Sa Pp Pp' |
A--------S--------+ Ps Pp' Pb Bpn
As P''Pn +--------------P--------B
| Pp''Pn Bp
|
| Ps Pp Pd Dp''n
+--------------P''------D
Pp' Pn Dp''
Figure 5 Local Area Networks
To explicitly diagnose the failed network component S correlates
the connectivity reports from P and one or more of the other
routers on the LAN, in this case, P' and P''. If it lost
connectivity to P alone, it could deduce that the LAN was still
functioning and that the fault lay with either P, or the interface
connecting P to the LAN. It would then repair to B not via P (and P
notvia N for destinations for which P is a signal point of failure)
in the usual way. If S lost connectivity to more than one router on
the LAN, it could conclude that the fault lay only with the LAN,
and could repair to P, P' and P'' notvia N, again in the usual way.
Now we need to consider what happens if S fails. Router A needs to
be able to repair to every router on the LAN notvia S which it does
in the usual way using the set of notvia S addresses.
An alternative approach that provides less post-failure
connectivity, but uses less addresses is to consider the LAN and
Bryant, Shand Expires Sep 2005 [Page 9]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
all of its connected routers as a single SRG. Thus the address P
not via the LAN (Pl) would require P to be reached notvia any
router connected to the LAN. This is shown in Figure 6.
P'l Cl
+--------------P'-------C
| P'c
|
As Sl |
A--------S--------+ Pl Bl
Sa +--------------P--------B
| Pb
|
| P''l Dl
+--------------P''------D
P''d
Figure 6 Local Area Networks - LAN SRG
In this case when S detected that P had failed it would send
traffic reached via P and B to B notvia the LAN or any router
attached to the LAN (i.e. to Bl). Any destination only reachable
through P would be addressed to P notvia the LAN or any router
attached to the LAN (except of course P).
6. Loop Free Alternatives
The use of loop free alternates (LFA) as a repair mechanism has
been studied [LFA]. Where an LFA exists, S may use this in place of
the notvia repair mechanism for unicast packets (including MHP
alternate routers). Multicast traffic requires the use of a repair
encapsulation so that the router at the repair endpoint can make
the necessary RPF check.
7. Equal Cost Multi-Path
A router can use an equal cost multi-path (ECMP) repair in place of
a notvia repair for unicast packets.
A router computing a notvia repair path MAY subject the repair to
ECMP.
8. Encapsulation
Any IETF specified IP in IP encapsulation may be used to carry a
notvia repair. IP in IP [IPIP], GRE [RFC1701] and L2TPv3 [L2TPv3],
all have the necessary and sufficient properties. The requirement
is that both the encapsulating router and the router to which the
encapsulated packet is addressed have a common ability to process
the chose encapsulation type.
Bryant, Shand Expires Sep 2005 [Page 10]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
9. Routing Extensions
IPFRR requires IGP extensions. Each IPFRR router that is directly
connected to a protected network component must advertise a notvia
address for that component. This must be advertised in such a way
that the association between the protected component (router or
SRG) and the notvia address can be determined by the other routers
in the network.
It is necessary that notvia capable routers advertise in the IGP
that they will calculate notvia routes.
It is necessary for routers to advertise the type of encapsulation
that they support (LDP, GRE [RFC1701], L2TPv3 etc). However the
deployment of mixed IP encapsulation types within a network is
deprecated.
10. Incremental Deployment
Incremental deployment is supported by excluding routers that are
not calculating notvia routes from the base topology. In that way
repairs may be steered around island of routers that are not IPFRR
capable.
Routers that are protecting a network component need to have the
capability to encapsulate and decapsulate packets. However, routers
that are on the repair path only need to be capable of calculating
notvia paths and including the notvia addresses in their FIB i.e.
these routers do not need any changes to their forwarding
mechanism.
11. IANA considerations
There are no IANA considerations that arise from this draft.
12. Security Considerations
The repair endpoints present vulnerability in that they might be
used as a method of disguising the delivery of a packet to a point
in the network. The primary method of protection should be through
the use of a private address space for the notvia addresses. These
addresses MUST NOT be advertised outside the area, and SHOULD be
filtered at the network entry points. In addition a mechanism might
be developed that allowed the use of the mild security available
through the use of a key [RFC1701] [L2TPv3]. With the deployment of
such mechanisms, the repair endpoints would not increase the
security risk beyond that of existing IP tunnel mechanisms.
An attacker may attempt to overload a router by addressing an
excessive traffic load to the decapsulation endpoint. Typically
routers take a 50% performance penalty in decapsulating a packet.
The attacker could not be certain that the router would be
impacted, and the extremely high volume of traffic needed, would
easily be detected as an anomaly.
Bryant, Shand Expires Sep 2005 [Page 11]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
If an attacker were able to influence the availability of a link,
they could cause the network to invoke the notvia repair mechanism.
A network protected by notvia IPFRR is less vulnerable to such an
attack than a network that undertook a full convergence in response
to a link up/down event.
Intellectual Property Statement
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 (2004). 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.
Normative References
There are no normative references.
Informative References
Internet-drafts are works in progress available from
<http://www.ietf.org/internet-drafts/>
Bryant, Shand Expires Sep 2005 [Page 12]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
[BFD] Katz, D., Ward, D., "Bidirectional Forwarding
Detection", < draft-katz-ward-bfd-02.txt>, May
2004, (work in progress).
RFC1701 RFC 1701, Generic Routing Encapsulation (GRE).
S. Hanks, T. Li, D. Farinacci, P. Traina.
October 1994.
[IPFRR] Shand, M., "IP Fast-reroute Framework", <draft-
ietf-rtgwg-ipfrr-framework-01.txt>, June 2004,
(work in progress).
[l2TPV3] J. Lau, Ed., et al., "Layer Two Tunneling
Protocol - Version 3 (L2TPv3)" <draft-ietf-
l2tpext-l2tp-base-15.txt>, December 2004,
(work in progress)
[LFA] A. Atlas, Ed, "Basic Specification for IP Fast-
Reroute: Loop-free Alternates", <draft-ietf-
rtgwg-ipfrr-spec-base-02.txt>, January 2005,
(work in progress).
[LDP] Andersson, L., Doolan, P., Feldman, N.,
Fredette, A. and B. Thomas, "LDP
Specification", RFC 3036,
January 2001.
[NNHL] Shen, N., et al "Discovering LDP Next-Nexthop
Labels", <draft-shen-mpls-ldp-nnhop-label-
01.txt>, July 2004, (work in progress)
[MPLS-TE] Ping Pan, et al, "Fast Reroute Extensions to
RSVP-TE for LSP Tunnels",
<draft-ietf-mpls-rsvp-lsp-fastreroute-07.txt>,
(work in progress).
[TUNNEL] Bryant, S., Shand, M., "IP Fast Reroute using
tunnels", <draft-bryant-ipfrr-tunnels-00.txt>,
May 2004 (work in progress).
Authors' Addresses
Stewart Bryant
Cisco Systems,
250, Longwater,
Green Park,
Reading, RG2 6GB,
United Kingdom. Email: stbryant@cisco.com
Mike Shand
Cisco Systems,
Bryant, Shand Expires Sep 2005 [Page 13]
INTERNET DRAFT IP Fast Reroute Using Notvia Addresses Mar 2005
250, Longwater,
Green Park,
Reading, RG2 6GB,
United Kingdom. Email: mshand@cisco.com
Bryant, Shand Expires Sep 2005 [Page 14]