Internet Draft Alia Atlas, Ed (Avici Systems)
Expires: November 2004
U-turn Alternates for IP/LDP Local Protection
draft-atlas-ip-local-protect-uturn-00.txt
Status of this Memo
By submitting this Internet-Draft, I certify that any applicable
patent or other IPR claims of which I am aware have been disclosed,
or will be disclosed, and any of which I 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/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
This document extends the architecture and selection process for
providing local protection for IP unicast and/or LDP traffic in the
event of a single link or node failures until the router has
converged. When computing the primary next-hop for a prefix, a
router S also determines an alternate next-hop which can be used if
the primary next-hop fails. The alternate can be either a loop-free
alternate, as described elsewhere, or a U-turn alternate, which goes
to a neighbor whose primary next-hop to the prefix is the router S,
but that neighbor has a loop-free node-protecting alternate, which
thus does not go through router S to reach the destination prefix.
A router may indicate the capability to break U-turns on its links;
only such links can be used as U-turn alternate next-hops. To signal
Atlas et al. [Page 1]
Internet Draft November 2004
this capability, a router must be capable of detecting when it
receives traffic for a given destination from a primary neighbor for
that destination and the router must forward that traffic to the
selected alternate next-hop.
To support U-Turn alternates and node-protection, a router must know
what links its neighbor can consider for alternates, how a neighbor
will select an alternate, and upon which interfaces a neighbor can
break U-turns. This document defines a common selection criteria
which MUST be followed. In addition, it is necessary to signal two
capabilities per link. First is whether U-turns can be broken on the
link and second is whether the link should be used as an alternate,
as determined administratively.
Atlas et al. [Page 2]
Internet Draft November 2004
Contents
1 Introduction ................................................. 3
2 Terminology .................................................. 5
3 Finding an Alternate ......................................... 6
3.1 U-Turn Alternates .......................................... 7
3.1.1 ECMP U-Turn Neighbors ..................................... 11
3.1.2 U-Turn Neighbor's Alternate ............................... 12
3.1.2.1 Computing Alternate So Primary Next-Hop Can Use
Computing Router for U-Turn Alternate .................. 14
3.2 Selection of an Alternate .................................. 15
3.2.1 IP Local Protection Alternate Capability ................. 15
3.2.2 U-Turn Breaking Capability ............................... 16
3.2.3 Characterization of Neighbors ............................ 16
3.2.4 Selection Procedure ...................................... 17
3.2.4.1 Alternate Selection with One Primary Neighbor .......... 17
3.2.4.2 Alternate Selection with Multiple Potential
Primary Neighbors ...................................... 18
4 Using an Alternate ........................................... 19
4.1 Breaking U-Turns ........................................... 19
4.1.1 Broadcast and NBMA Interfaces ............................ 21
4.2 Responding to a Local Failure .............................. 22
5 Requirements on LDP Mode ..................................... 22
6 Routing Aspects .............................................. 22
7 U-Turn Alternates Interactions with Tunnels .................. 24
8 Security Considerations ...................................... 24
9 Intellectual Property Considerations ......................... 24
10 Full Copyright Statement ..................................... 24
11 References ................................................... 25
12 Authors Information .......................................... 26
13 Editor's Information ......................................... 27
Appendix A U-turn Alternate Proofs ............................. 27
1. Introduction
Applications such as VoIP and pseudo-wires can be very sensitive to
traffic loss, such as occurs when a link or router in the network
fails. A router's convergence time is generally on the order of
seconds; the application traffic may be sensitive to losses greater
than 10s of milliseconds.
This document extends the architecture defined in [LOOP-FREE], which
allows a router whose local link has failed to forward traffic to a
pre-computed alternate until the router installs the new primary
next-hops based upon the changed network topology.
The existence of suitable loop-free alternate next-hops is topology
Atlas et al. [Page 3]
Internet Draft November 2004
dependent. This document defines a second type of alternate next-
hop, known as a u-turn alternate, and provides the common behavior
and selection method necessary to allow u-turn alternates to
function.
The topology in Figure 1 is an example where there is no loop-free
alternate from S to D, but there is a u-turn alternate.
\
@@@ /__
/ \ +--+--+
+----------| N_1 |
| 5 +-----+
| |
+---+-+ |
| S | @ |10
+-----+ @ |
| \@/ |
| |5 |
\|/ | |
| |
+-----+ |
| P | +-----+
+-----+ | R_1 |
| +-----+
| |5 |
\|/ | | |10
| \|/ |
+-----+ |
| D |---------+
+-----+
Figure 1: Topology with U-turn Alternate
In Figure 1, there is no loop-free alternate for S to use to reach D.
This is because the costs are such that N_1 uses S as its primary
neighbor; therefore if S were to send the traffic to N_1, it would
loop back to S. If both S and N_1 support the mechanisms defined in
this document, then S could use N_1 as a u-turn alternate. Traffic
destined to D which was sent by S to N_1 would be forwarded by N_1 to
R_1, N_1's loop-free node-protecting alternate.
As with loop-free alternates, the existence of suitable u-turn
alternates is topology dependent; it extends the coverage on topology
above that seen with just loop-free alternates.
2. Terminology
Atlas et al. [Page 4]
Internet Draft November 2004
SPT --- Shortest Path Tree
D --- The destination router under discussion.
S --- The source router under discussion. It is the viewpoint from
which IP/LDP Local Protection is described.
P --- The router which is the primary next-hop neighbor to get from S
to D. Where there is an ECMP set for the shortest path from S
to D, these will be referred to as P_1, P_2, etc.
N_i --- The ith neighbor of S
R_i_j --- The jth neighbor of N_i, the ith neighbor of S.
Distance_!S(N_i, D) --- The distance of the shortest path from N_i to
D which does not go through router S.
Distance_opt(A, B) or D_opt(A,B) --- The distance of a shortest path
from A to B.
Reverse Distance of a node X --- This is the Distance_opt(X, S).
Loop-Free Alternate --- This is a next-hop that is not a primary
next-hop whose shortest path to the destination from the
alternate neighbor does not go back through the router S.
U-Turn Alternate --- This is an alternate next-hop of S that goes to
a neighbor N_i, whose primary next-hop is S, and whose
alternate neighbor does not go back trough the router S, which
may therefore use the link to N_i as an alternate.
Link(A->B) --- A link connecting router A to router B.
____\ This is an arrow indicating the primary next-hop towards D.
/
@@@@\ This is an arrow indicating the alternate next-hop towards D
/
Primary Neighbor --- One or more of the primary next-hops for S to
reach the destination D goes directly to this neighbor.
Loop-Free Neighbor --- A Neighbor N_i which is not the primary
neighbor and whose shortest path to D does not go through S.
U-Turn Neighbor --- A neighbor N_i is a U-Turn neighbor of router S
with respect to a given destination D if and only if S is a
Atlas et al. [Page 5]
Internet Draft November 2004
primary neighbor of N_i to reach the destination D for all
primary paths which go through S to reach D.
ECMP U-Turn Neighbor --- A neighbor N_i which is a U-Turn neighbor
and which has at least one equal cost path to reach D that does
not go through S as well as the path(s) which do go through S to
reach D.
Looping Neighbor --- A neighbor N_i is a looping neighbor of router S
with respect to a given destination D if and only if S is not
the primary next-hop of N_i on at least one optimal path from S
to D which also goes through S.
Loop-Free Node-Protecting Alternate --- This is a path via a Loop-
Free Neighbor N_i which does not go through the particular
primary neighbor of S which is being protected to reach the
destination D.
Loop-Free Link-Protecting Alternate --- This is a path via a Loop-
Free Neighbor N_i which does go through the particular primary
neighbor of S which is being protected to reach the destination
D.
U-Turn Node-Protecting Alternate --- This is a path via a U-Turn
Neighbor N_i which does not go through S or any of S's primary
neighbors to reach the destination D.
U-Turn Link-Protecting Alternate --- This is a path via a U-Turn
Neighbor N_i which does not go through S but does go through one
or more of S's primary neighbors to reach the destination D.
3. Finding an Alternate
As with primary next-hops, an alternate next-hop is discussed in
relation to a particular destination router D. For this discussion,
the following terminology, illustrated in Figure 2, will be used.
The router on which the search for an alternate is proceeding is S.
The primary next-hop neighbor to get from S to D is P. Additionally,
S has various neighbors which will be labeled N_1, N_2, etc. Where
an arbitrary neighbor of S is intended, N_i will be used. Routers
which are neighbors of neighbors will be labeled R_1, R_2, etc.
Where an arbitrary neighbor of a neighbor N_i is intended, it will be
referred to as R_i_j.
+-----+
\ / _| R_2 |
Atlas et al. [Page 6]
Internet Draft November 2004
+-----+__ \| |/ / +-----+
| N_3 | \ -+ +- __/ \
+-----+ \____ / \
\ \ / \
\ +-----+ \
\ _| N_2 | \
| __/ +-----+ \
\ / \ |
\ / / \_ |
+-----+ |/ \ |
| S | +- \ +-----+ |
+-----+ \_| R_1 | |
/ / \ +-----+ |
|/ / \ / |
+- / \ / |
/ +-----+ / / |
+-----+/ | N_1 | / |/ |
| P | +-----+ / +- |
+-----+ \ / /
\ \ \__ / /
\ \ \| \ / /
\| \ -+ +-----+ /
-+ \_________________| D |---------/
+-----+
Figure 2: Topology for Terminology
As described in [LOOP-FREE], a neighbor can provide a loop-free
alternate if Equation 1 is true.
Distance_!S(N_i, D) < Distance_opt(N_i, S) + Distance_opt(S, D)
Equation 1: Criteria for a Loop-Free Alternate
3.1 U-Turn Alternates
In examining realistic networks, it was seen that loop-free
alternates did not provide adequate coverage for the traffic between
all the source-destination pairs. This means that it is not
sufficient to expand the set of points where S can cause its traffic
to join the SPT to be only S's neighbors.
The next possibility is to see whether S could expand its SPT join
points to include router S's neighbors' neighbors. This is only of
interest if S had no loop-free node-protecting alternate available
for the given destination D. If there are no loop-free alternates,
that implies that all of S's non-primary neighbors will send traffic
Atlas et al. [Page 7]
Internet Draft November 2004
for D back to S.
+-----+ \
| N_4 |\ \| / +-----+
+-----+ \ -+ |/ /| R_3 |
/ \ +- / +-----+
/ 15 | _/ |
| | 5 / |
| 50 \ / |
+-----+ | +-----+ |
| N_2 | / ______/| N_3 | |
+-----+ \ / / +-----+ 70 |
| \ \| / / 30 / |
10| \ -+ / / |/ |
| 15 \ +-----+ +- |
@ | \-----| S | |
@ | / +-----+ |
\@/ | @@@@ | |
| \ | |10 /
| | | /
+-----+ \_/ | /
| R_2 | +-----+ /
+-----+ | P | /
\ +-----+ /
\ \ 40 / /
\| \ 10 / / /
-+ \ / |/ /
+-----+ / +- /
| R_1 |---/ /
+-----+ /
\ 10 +-----+
\ \------------------| D |
\| +-----+
-+
P is primary next-hop of S
N_2 and N_3 are U-Turn Neighbors of S
N_4 is a Looping Neighbor of S
Figure 3: Terminology of Looping Neighbors and Example U-Turn Alternate
The topology shown in Figure 3 gives an example where router S has no
loop-free alternate to reach D. Router S uses P as its primary
next-hop (distance of 30). S has three other neighbors, but all of
them will send traffic for D back through S.
In order for S to be able to use a neighbor's neighbor as a point
where S's traffic can rejoin the SPT, S must be able to direct
Atlas et al. [Page 8]
Internet Draft November 2004
traffic to a neighbor N_i and that neighbor N_i must be able to
direct traffic to one of its appropriate neighbors R_i_j instead of
along the SPT. In deciding to use its alternate, S has the ability
to force traffic destined to D to go through the selected alternate
neighbor N_i. However, for S to reach the appropriate neighbor's
neighbor R_i_j, the selected neighbor N_i must be able to detect
that the traffic should not be sent along its shortest path to D,
which would lead back to S, and should instead be sent to its
appropriate neighbor R_i_j.
This detection and forwarding contrary to the SPT by N_i must occur
without any communication from S upon the failure which would cause S
to redirect the traffic to N_i. There is already communication from
S to N_i indicating when a link has failed, but such communication
would cause the fail-over of traffic to take longer than the desired
10s of milliseconds if N_i depended upon it to decide that it should
forward contrary to the SPT. In essence, the assumption being made
is that the time budget to recover traffic in the event of a failure
is being consumed by router S's detection of the failure and switch-
over to its pre-computed alternate.
With that assumption, it is clear that N_i's behavior to forward
traffic contrary to the SPT on receiving traffic from S must be a
default behavior. This default behavior must not change how traffic
is forwarded unless a forwarding loop is detected; basic IP
forwarding must be preserved in the absence of a failure. Router N_i
can detect if it is receiving traffic from a neighbor to whom it
would forward that traffic; this detection is done via a reverse
forwarding check. Such a reverse forwarding check should consider
not only if traffic is received on the same interface as it would be
forwarded out, but whether it was received from the same neighbor to
whom it would be forwarded. Normally, if traffic fails a reverse
forwarding check (i.e. would be forwarded out to the same neighbor as
received from), then that traffic is either discarded or forwarded
into a loop. In IP/LDP Local Protection, however, traffic that fails
a reverse forwarding check is forwarded to the appropriate R_i_j, if
available, rather than being discarded.
First, this detection can be used by N_i to determine not to forward
the traffic according to the SPT (or discard it), but to instead send
the traffic to N_i's appropriate neighbor R_i_j. N_i can only detect
the traffic to be redirected if S sends it directly to N_i, which is
under S's control, and if N_i would send that traffic back to S,
according to the SPT. This motivates the definition of a Looping
Neighbor and a U-turn Neighbor.
Looping Neighbor --- A neighbor N_i is a looping neighbor of
router S with respect to a given
Atlas et al. [Page 9]
Internet Draft November 2004
destination D if any of N_i's shortest
paths to D goes through S but S is not the
primary next-hop of N_i for all those
paths through S.
U-Turn Neighbor --- A neighbor N_i is a U-Turn Neighbor of
router S with respect to a given destination
D if and only if S is a primary next-hop of
N_i to reach the destination D for all
primary paths which go through S to reach D.
A Looping Neighbor cannot provide any type of alternate. A U-Turn
neighbor may be able to provide an alternate. In Figure 3, S has two
U-Turn Neighbors N_2 and N_3 and one looping neighbor N_4. For
neighbor N_4, the path to D is N_3 to S to N_1 to R_1 to D; because
there is a node between N4 and S on the path, N_4 is a looping
neighbor.
Mathematically, for a neighbor N_i to be a U-Turn neighbor, it is
necessary that Equation 2, which is the exact opposite of Equation 1,
be true. If the equality is true, that means that there are multiple
optimal paths, at least one of which goes through S and one does not.
Such a neighbor may be an ECMP U-Turn neighbor or may be a looping
neighbor.
Distance_!S(N_i, D) >= Distance_opt(N_i, S) + Distance_opt(S, D)
Equation 2: U-Turn or Looping Neighbor
Additionally, all optimal paths to reach D that go via S must be via
a direct link between N_i and S. If a neighbor N_i satisfies
Equation 2 and all optimal paths to reach D that go via S are via a
direct link between N_i and S, then it is a U-turn neighbor.
The above clarifies what a U-Turn neighbor is and how such a neighbor
can detect traffic from router S and redirect it. It is still
necessary to describe where the U-Turn neighbor N_i redirects the
traffic.
It is also necessary to describe on what interfaces a router N_i must
consider that it could be a U-Turn neighbor. A router N_i must
detect traffic coming from its primary neighbor and redirect that
traffic to the appropriate alternate. This is termed breaking a U-
turn because it redirects traffic to the alternate and avoids
forwarding the traffic back into the U-turn loop. If a router
advertises that an interface is U-turn capable, meaning that the
router can break U-turns on traffic entering that interface, then the
Atlas et al. [Page 10]
Internet Draft November 2004
router must break U-turns for all traffic coming from a primary
neighbor. The router is not responsible for breaking U-turns for
traffic from potential primary neighbors which were not selected.
3.1.1. ECMP U-Turn Neighbors
The above definition for U-Turn Neighbor allows a neighbor, which has
equal cost paths (an ECMP set) where one of those paths goes directly
to S and others may not, to be a U-Turn Neighbor. Consider the
topology shown in Figure 4. In this figure, N_1 has three equal-cost
paths to reach D which are N_1 - S - P - D, N_1 - R_1 - D, and N_1 -
R_2 - D. Because the only path that goes through S goes directly
through S, N_1 is a U-Turn neighbor of S.
+-----+------\
/--| N_1 | 5 \
/ / +-----+\ \ +-----+
|/ / 10 \ \ 15 \------| R_3 |
+- / 10 \ \ +-----+
/ | \ \ |
+-----+ | | \ \| |
| S | \|/ | \ -+ | |
+-----+ | \ | \|/
/ +-----+ \ |
/ / 10 | R_1 | \ 15|
|/ / +-----+ \ |
+- / / / +-----+ |
/ |/ / 20 | R_2 | |
+-----+ +- / +-----+ |
| P | | /__ 15 / |
+-----+ | \ / |
\ | /-------/ +-----+
\ \ 10 | / | X |
\| \ | / /__ +-----+
-+ \ +-----+ \ / 15
\------| D |-------------------/
+-----+
Figure 4: ECMP U-Turn Neighbor
Distance_!S(N_i, D) = Distance_opt(N_i, S) + Distance_opt(S, D)
Equation 3: ECMP Neighbor
A neighbor is an ECMP neighbor if Equation 3 is true. S does not
know whether a neighbor N_i supports ECMP or how that neighbor
selects among the equal cost paths. Recall that a node will only
break U-Turns on the interfaces connected to that node's primary
Atlas et al. [Page 11]
Internet Draft November 2004
neighbors.
Consider the topology in Figure 5, where N_2 has three equal cost
primary neighbors which are S, N_1 and R_1. If N_2 were to select
only N_1 as its primary neighbor, then N_2 would break U-Turns only
on traffic received from N_1 and not on traffic received from S.
Therefore, S cannot consider N_2 as an ECMP U-Turn neighbor because S
cannot rely upon N_2 to break U-turns for traffic destined to D which
is received from S.
If N_2 has multiple paths to reach D which go through S and not all
such paths have a first hop which is a direct link between N_2 and S,
then S cannot use N_2 as a U-Turn neighbor.
10 +-----+
/ /--------------| N_2 |\ \
|/ / +-----+ \ \|
+- / /----/ 5 \ -+
/ / / \
/ 5 +-----+ |/ |
/ /----| N_1 | +- | 5
+-----+ / +-----+ |
| S |/ / +-----+
+-----+ |/ | R_1 |
/ / +- +-----+
|/ / 5 /
+- / / 15
+-----+ /--------/
| P | /
+-----+ / /
\ / |/
\ \ 5 +-----+ / +-
\| \-------------| D |/
-+ +-----+
Figure 5: ECMP Neighbor Which is Not an ECMP U-Turn Neighbor
If all paths from an ECMP neighbor N_i to destination D which go via
S have S as the primary neighbor, then S can use N_2 as a ECMP U-Turn
neighbor.
3.1.2. U-Turn Neighbor's Alternate
The requirement for the neighbor's neighbor R_i_j to which a U-Turn
Neighbor N_i will redirect traffic from S destined to D is that the
traffic not come back to S. Equation 4 gives this requirement that
R_i_j must have a path to D that does not go through S which is
shorter than the path to D going via S. This can be expressed as
Atlas et al. [Page 12]
Internet Draft November 2004
follows.
Distance_!S(R_i_j, D) < Distance_opt(R_i_j, S) + Distance_opt(S, D)
Equation 4: Loop-Free Neighbor's Neighbor
Equation 4 means that a U-Turn neighbor's alternate cannot be an ECMP
set which contains that U-Turn neighbor.
If N_i is a U-Turn neighbor, then the optimal path to D from N_i is
via S; the path is N_i - S - ... - D. Therefore, if the optimal path
from R_i_j goes through N_i, it must also go through S. Thus, if
Equation 4 holds for a R_i_j, that implies that the path from R_i_j
does not go through N_i. This may be made clearer by considering
Figure 6 below. If the shortest path from R_1 to D went through N_1,
then it would go through S as well, because the shortest path from
N_1 to D is through S. Therefore, if the shortest path from R_1 does
not go through S, it cannot have gone through N_1.
5 +-----+ @
/ /--------------| N_2 |\ @
|/ / +-----+ \ \@/
+- / /@\ \
/ @ \
/ @ |
/ | 15
+-----+ |
| S | +-----+
+-----+ | R_1 |
/ / +-----+
|/ / 5 /
+- / / 5
+-----+ /--------/
| P | /
+-----+ / /
\ / |/
\ \ 5 +-----+ / +-
\| \-------------| D |/
-+ +-----+
Figure 6: U-Turn Alternate Example
This is a proof by contradiction showing that if a neighbor's
neighbor Ri,j is loop-free with respect to S, then it is also
loop-free with respect to Ni.
If the optimal path from Ri,j to D goes through Ni, then
Atlas et al. [Page 13]
Internet Draft November 2004
D_!S,N_i(R_i,j , D) = D_opt(R_i,j, N_i) + D_opt(Ni, D)
Because N_i is a U-Turn neighbor, the shortest path to D is via
S so:
D_opt(N_i, D) = D_opt(N_i, S) + D_opt(S, D)
The previous two equations can be combined to form the
following:
D_!S,N_i(R_i,j , D) = D_opt(R_i,j, N_i) + D_opt(N_i, S) + D_opt(S, D)
The following observation can be made because Distanceopt(Ri,j,
S) is the minimum distance of a path to get from Ri,j to S, so
the path to do so via Ni cannot have a lower distance.
D_opt(R_i,j, S) = D_opt(R_i,j, N_i) + D_opt(N_i, S)
This can be combined with the previous equation to yield
D_!S,Ni(R_i,j , D) = D_opt(R_i,j, S) + D_opt(S, D)
This equation is the opposite of Equation 4. Thus, if Equation
4 is true, then the optimal path from Ri,j to D does not go
through Ni.
Proof 1: Proof that a Loop-Free R_i_j (Neighbor's Neighbor)
Implies R_i_j Doesn't Loop to Neighbor N_i
The proof given in Proof 1 means that if a U-Turn Neighbor N_i has
itself a neighbor R_i_j that satisfies Equation 4, then that router
R_i_j is itself a loop-free alternate with respect to N_i.
Regrettably, the converse does not apply; just because R_i_j is
loop-free with respect to N_i and D does not mean that R_i_j is
loop-free with respect to S and D.
3.1.2.1. Computing Alternate So Primary Next-Hop Can Use Computing
Router for U-Turn Alternate
Each router independently computes the alternate that it will select.
It is necessary to consider what alternate S could select so that S's
primary next-hop P could use S as a U-Turn alternate. In other
words, consider the computation when S is in the role of a neighbor
to the router doing the computation.
To describe this using router S as the computing router, S would need
to verify that both Equation 1 is true and that S's selected
alternate N_i does not have a path that goes through P.
This can be described as if N_i were doing the computation as
follows. The criteria described in Equation 4 requires that if a U-
Turn neighbor N_i is to be used as a U-Turn alternate then N_i must
Atlas et al. [Page 14]
Internet Draft November 2004
have a loop-free alternate which avoids N_i's primary neighbor S.
Such an alternate will be referred to as a loop-free node-protecting
alternate. N_i can identify loop-free alternates by checking the
validity of Equation 5. Additionally, N_i will need to tell whether
the path from a loop-free R_i_j to D goes through N_i's primary
next-hop neighbor, S.
D_!S(R_i_j, D) < D_opt(R_i_j, N_i) + D_opt(N_i, D)
Equation 5: Neighbor's Loop-Free Alternate
3.2 Selection of an Alternate
A router S may have multiple alternates that it must decide between.
A common selection method is necessary to support U-Turn Alternates.
This is because it is not sufficient for router S to know that its
U-Turn neighbor N_i has itself a neighbor R_i,j that is loop-free
with respect to S and D if S does not also know that N_i will select
that R_i,j or another with the same properties.
The same set of failure scenarios that can be protected against with
a loop-free alternate is of interest with a u-turn alternate.
Similarly, there is the same interaction with maximum costed links
and broadcast interfaces as described in [LOOP-FREE]. In addition,
if all links from a neighbor N_i to a neighbor's neighbor R_i_j have
a reverse cost of LSInfinity, then router S cannot consider that N_i
could provide a U-turn alternate via R_i_j.
3.2.1. IP Local Protection Alternate Capability
There are a number of different reasons why an operator may not wish
for a particular interface to be used as an alternate. For instance,
the interface may go to an edge router or the interface may not have
sufficient bandwidth to contain the traffic which would be put on it
in the event of failure.
Because a router's neighbors may desire to use that router to provide
a U-turn alternate, a router must flood to its neighbors which
interfaces are not capable of providing alternates. This information
allows a router's neighbors to accurately determine whether or not
the router has a loop-free node-protecting alternate.
The extensions to signal this local-protection alternate capability
are described in [OSPF-LOCAL-PROTECT] and [ISIS-LOCAL-PROTECT].
3.2.2. U-Turn Breaking Capability
Atlas et al. [Page 15]
Internet Draft November 2004
A router S may only use its neighbor N_u as a U-Turn alternate if N_u
indicates that it is capable of breaking U-Turns on a link between S
and N_u. The capability to break U-Turns must be signaled for a link
in order for S to determine that it can use N_u as a U-Turn
alternate. By default, S MUST assume that a neighbor cannot provide
a U-Turn alternate unless that neighbor indicates the U-Turn breaking
capability on a link between S and N_u. This U-Turn breaking
capability need only be flooded to a node's neighbors.
The extensions to signal the U-turn breaking capability are also
described in [OSPF-LOCAL-PROTECT] and [ISIS-LOCAL-PROTECT].
3.2.3 Characterization of Neighbors
Each neighbor N_i can be categorized as to the type of path it can
provide to a particular destination D. Once the primary paths have
been determined and removed from consideration, each neighbor can be
characterized as providing a path in one of the following categories
for a particular destination D. It is possible for a neighbor to
provide both the primary path and a loop-free link-protecting
alternate. The path through the neighbor N_i is either a:
(A) Loop-Free Node-Protecting Alternate --- not a primary path
and the path avoids both S, the interfaces connecting S to its
primary neighbors, and its primary neighbors on the path to D.
(B) Loop-Free Link-Protecting Alternate --- not a primary path
and the path avoids S and the interfaces connecting S to its
primary neighbors, but goes through a primary neighbor on the
path to D.
(C) U-Turn Node-Protecting Alternate --- the neighbor is a U-
Turn neighbor or a ECMP U-Turn neighbor and the alternate that
the neighbor has selected does not go through a primary neighbor
of S to reach D.
(D) U-Turn Link-Protecting Alternate --- the neighbor is a U-
Turn neighbor or a ECMP U-Turn neighbor and the alternate that
the neighbor has selected goes through a primary neighbor of S
to reach D.
(E) Unavailable --- because the neighbor is looping or a U-Turn
neighbor which didn't itself have a loop-free node-protecting
path, or a U-Turn neighbor which couldn't break U-Turns or the
links to the neighbor are configured to not be used as
alternates. The neighbor may also be disqualified because it is
Atlas et al. [Page 16]
Internet Draft November 2004
connected to S solely via broadcast interfaces which also have
primary next-hops.
3.2.4. Selection Procedure
Once the neighbors have been categorized, a selection can be made.
The selection should maximize the failures which can be protected
against. A node S can only be used to break U-turns by its primary
neighbors if S has a loop-free node-protecting alternate.
The selection procedure depends on whether S has a single potential
primary neighbor or multiple potential primary neighbors. A router S
is defined to have a single potential primary neighbor only if there
are no equal cost paths that go through any other neighbor; i.e., a
router S cannot be considered to have a single potential primary
neighbor just because S does not support ECMP or just because S
selects as primary next-hops links to only one potential primary
neighbor.
3.2.4.1. Alternate Selection with One Primary Neighbor
Because a router S can only be used to break U-Turns by its primary
neighbor if S selects a loop-free node-protecting alternate, the
following rules MUST be followed when selecting an alternate. This
describes a policy which reduces the computational complexity
associated with identifying the u-turn alternates.
then S MUST select one of those alternates. Let M be the set of
neighbors which provide loop-free node-protecting alternates.
If S has multiple loop-free node protecting alternates, then S
MUST select the best alternate through a N_k such that:
D_!S(N_k, D) - D_opt(N_k, P) = min_forall m in M
(D_!S(m, D) - D_opt(m, P))
Equation 6: Selection Among Multiple Loop-Free
Node-Protecting Alternates
where P is the primary neighbor of S.
To rephrase the above to consider the S is the node looking for
a U-Turn alternate, the way of selecting among loop-free node-
protecting alternates above, ensures that N_i's primary neighbor
S can determine which alternate was picked by N_i. For S to
know that S's U-Turn neighbor N_i can provide a loop-free node-
protecting alternate, S must know if
Atlas et al. [Page 17]
Internet Draft November 2004
min_forall j in J ( D_!S(R_i_j, D) - D_opt(R_i_j, S) )
< D_opt(S, D)
Equation 7: Determination if a U-Turn Neighbor
can provide a U-Turn Alternate
If a router obeys Equation 6 when selecting among multiple
loop-free node-protecting alternates, as it MUST for IP/LDP
Local Protection, this allows S to determine exactly which
alternate was selected by N_i without needing to know the each
D_!S(R_i_j). Equation 7 allows S to determine that N_i has a
loop-free node-protecting alternate. Equation 6 allows S to
know exactly which alternate will be selected so that S can
determine whether that alternate protects against S's primary
neighbor as well. If there are multiple neighbors which provide
the minimum as expressed in Equation 6, then a router can select
among them arbitrarily.
2. If a router S has no loop-free node-protecting alternates,
then S's alternate selection has no consequences for its
neighbors because S cannot provide a U-Turn alternate.
Therefore, S can select freely among the loop-free link-
protecting alternates, u-turn node-protecting alternates and u-
turn link protecting alternates which S has available. Clearly
selecting a u-turn node-protecting alternate, if one is
available, will provide node-protection, while the other options
will not. Selection among these categories is a router-local
decision.
3. If S has neither loop-free node-protecting alternates,
loop-free link-protecting alternates, u-turn node-protecting
alternates, nor u-turn link-protecting alternates, then S has no
alternate available for traffic to the destination D from the
source S.
3.2.4.2. Alternate Selection with Multiple Potential Primary Neighbors
The selection among multiple equal cost paths is a router-local
decision. Therefore, a router N_i cannot know which of the potential
primary neighbors that S will choose to use.
As described in Section 3.1.2.1, N_i can only select S for its U-Turn
alternate if any potential primary neighbor which S might select,
except for N_i itself, will not go via N_i to reach the destination
D.
Since a router S has multiple potential primary neighbors, router S
MUST select one or more alternates for breaking U-Turns from among
Atlas et al. [Page 18]
Internet Draft November 2004
next-hops to its potential primary neighbors. If router S does not
have a potential primary neighbor that is node-protecting for a
particular primary next-hop, that indicates that the particular
primary neighbor will not use S as a U-turn alternate.
Router S need not use the same alternate(s) for breaking U-Turns on
traffic received from a primary next-hop as for when the primary
next-hop fails. The alternate(s) used when a primary next-hop fails
are a router-local decision.
4. Using an Alternate
If an alternate is available, it is used in two circumstances. In
the first circumstance, it is used to redirect traffic received from
a primary next-hop neighbor. In the second circumstance, it is used
to redirect traffic when the primary next-hop has failed. As
mentioned in Section 3.2.4.2, for destinations with multiple
potential primary neighbors, the alternates used for each purpose
need not be the same.
4.1. Breaking U-Turns
If one ignores potential security redirection, IP forwarding is a
purely destination based algorithm. Traffic is forwarded based upon
the destination IP address, regardless of the incoming interface.
As previously described in Section 3.1.2, IP/LDP Local Protection
requires that a U-Turn neighbor be capable of detecting traffic
coming from the primary next-hop neighbor and redirecting it to the
alternate, if an alternate which is node-protecting is available.
This becomes the new default behavior. This behavior is described
below. A router which indicates that it is capable of breaking U-
Turns on an interface MUST obey the following behavior on that
interface.
For an IP destination
If packet received on interface connected to a primary neighbor {
if the interface is U-Turn Breaking Capable {
if primary next-hop has a loop-free
node-protecting alternate
forward the packet to that alternate
else forward to a primary next-hop
} else forward to a primary next-hop
} else forward to a primary next-hop
New Forwarding Rule
Atlas et al. [Page 19]
Internet Draft November 2004
+--------------------------+
| N_1 |
| |
| primary alternate | Router
| D: S R_1 | Forwarding
| C: R_1 R_2 | Table
| |
|--------+--------+--------|
| D: R_1 | D: S | D: S | Interfaces'
| C: R_1 | C: R_1 | C: R_2 | Forwarding
+--------------------------+
/ | \
/ L_1 | L_2 \ L_3
/ | \
/ +-----+ \
+-----+ | R_2 | \
| S | +-----+ +-----+
+-----+ / | R_1 |
/ / +-----+
/ / /
/ / /
+-----+ / /--------/
| P | / /
+-----+ __ / __ /
\ / \ / \ /
\ / \/ \ /
\------ | |
\ CLOUD /
_/ |
/ |
\_ ___ /
/\_/ \_/
/ \
/ \
/ +-----+
+-----+ | D |
| C | +-----+
+-----+
Figure 7: Example Forwarding Table
If an interface is U-Turn capable and has a node-protecting
alternate, traffic received on its primary next-hop will be forwarded
to its alternate next-hop. Otherwise, the current behavior will be
preserved, which is forwarding traffic received to its primary next-
hop.
If a broadcast interface is U-turn capable, then it is acceptable to
Atlas et al. [Page 20]
Internet Draft November 2004
forward traffic from all nodes on that interface via the alternate
path. This will work if all nodes on that interface have a common
topology because they are in the same OSPF area or ISIS level.
To clarify the above behavior, consider the example below in Figure
7. In this case, router N_1 has a primary and an alternate for two
destinations D and C. The primary next-hop for destination D is
router S and the alternate next-hop is R_1. Similarly, the primary
next-hop for destination C is router R_1 and the alternate next-hop
is R_2. The three interfaces L_1, L_2, and L_3 shown on router N_1
have different forwarding tables as shown in Figure 7; additional
interfaces would have the same forwarding table as for interface L_2,
which is not a primary next-hop for either destination.
4.1.1. Broadcast and NBMA Interfaces
NBMA and broadcast interfaces can be treated identically for IP/LDP
Local Protection; both involve the case of possibly receiving traffic
from multiple neighbors. With broadcast interfaces (i.e. Gigabit
Ethernet), there can be multiple neighbors connected to the same
interface. If all the neighbors are not in the same area, then it is
not desirable to treat the traffic received identically, because
traffic may be incorrectly sent to the alternate. It is extremely
desirable to have at most one forwarding table per interface.
Therefore, it must be considered whether all traffic received on an
interface can be treated identically, regardless of the neighbor
sourcing the traffic on that interface, as long as all the neighbors
on the interface are in the same area.
The cost for any node on the broadcast interface to reach S or P will
be identical. Because all link costs are positive, no neighbor on
the broadcast interface will ever send traffic to S along that
interface in order to reach P. Therefore, S can assume that any
traffic received on the broadcast interface which goes to a
destination via a primary next-hop neighbor that is also on the
broadcast interface is in fact sent by that primary next-hop neighbor
and should be redirected to break the U-Turn.
Thus, if router S has a primary next-hop neighbor for a given prefix
on the broadcast interface, S should redirect all traffic received
destined to that prefix on the broadcast interface to S's alternate
next-hop.
An interface can be either a primary next-hop or the alternate next-
hop, but not both because there would be no protection if the
interface failed.
Atlas et al. [Page 21]
Internet Draft November 2004
+-----------+-----------+------------+----------+
| | | | |
| | /P\ | /P\ | /P\ | /P\
| 2 3| | 3| | 4| | 5| |
| | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
| P | | S | | N_1 | | N_2 | | N_3 |
+-----+ +-----+ +-----+ +-----+ +-----+
\ \ 10
\ \ 10 @ \________
\| \ @| \
-+ \ -+ +-----+
\ ________| N_4 |
\ / 10 +-----+
+-----+ /
| D |/
+-----+
Figure 8: Topology With Broadcast Interface
4.2. Responding to a Local Failure
When a local interface failure is detected, traffic that was destined
to go out the failed interface must be redirected to the appropriate
alternate next-hops. The alternate next-hop is pre-computed to be
reliable in the event of the failure scenario being protected against
(i.e. link or node failure).
Convergence on the part of the U-turn neighbor N_i will not
invalidate the U-turn alternate. The loop-free node-protecting
alternate of N_i which goes via R_i,j will not be affected by the
failure, because it was independent of the affected elements. If
N_i's new primary neighbor remains S, then the traffic will continue
to be directed towards the appropriate R_i,j. If N_i converges to a
path which does not include S to reach D, then traffic received from
S for D will be sent along the new path and no forwarding loop will
ensue.
5. Requirements on LDP Mode
U-turn alternates do not impose any additional sessions or signaling
on LDP. LDP can use the u-turn alternates to protect LDP traffic if
the requirements specified in [LOOP-FREE] are met.
6. Routing Aspects
As described in [LOOP-FREE], the additional complexity for inheriting
alternate next-hops is for inter-region routes where there are ECMP
Atlas et al. [Page 22]
Internet Draft November 2004
through different area border routers and yet a single primary
neighbor. This scenario is illustrated in Figure 9.
............... +--+--+ 15
......+----------------| ABRt|----------------+
... | 15 +-----+ |
.. | ... |
.. 5 +-----+ 15 +--+--+ .. |
. +------| A2 +---------| R1 |-----+ . |
.. | +-----+ +-----+ 20 | . |
. | +-----+ 10 |
. | +--------------| ABR2|---------+ |
. | | 15 +-----+ | |
. +-----+ 5 +---+-+ . | |
. | S |-----------| P |------------+ . +-----+
. +-----+ +-----+ 5 | . | D |
. | | . +-----+
. | | . |
.. | +-----+ +-----+ 20 |
. +-----| A1 |------------------| ABR1|------------+
. 10 +-----+ 15 +-----+
... ...
... ...
...... .....
..............
Figure 9: Inter-Region Destination via
Multiple Border Routers but One Primary Neighbor
The main question when deciding whether an alternate can be
inherited is whether or not that alternate will continue to
provide the necessary protection. I.e., will the alternate
continue to be usable as an alternate and provide the same link
or node protection with respect to the destination that was
provided with respect to the border router. The relationships
shown in Figure 6 will be used for illustrative purposes,
although the topology connecting them may be more general than
that shown. The proofs and explanations are provided in [LOOP-
FREE] and below, but the answer is that the alternate will be
usable as an alternate and provide at least the same link or
node protection that was provided with respect to the border
router. The alternate next-hop inheritance procedure SHOULD
select a loop-free node-protecting alternate, if one is
available.
[LOOP-FREE] proved this when only loop-free alternates were
considered. It is necessary to prove the same thing when U-turn
alternates are considered.
Atlas et al. [Page 23]
Internet Draft November 2004
The use of this for alternate next-hop inheritance applies to
OSPF, ISIS and BGP as described in [LOOP-FREE].
7. U-Turn Alternates Interactions with Tunnels
IP/LDP Local Protection treats IGP tunnels the same as any other
link. If router S is not the endpoint of the tunnel, then the
alternate path is computed as normal. If router S is the ingress
into the tunnel, then all destinations which have the tunnel as a
primary next-hop may be protected via a protection scheme associated
with the tunnel.
One issue with MPLS RSVP-TE tunnels is that an LSP may be created
where the router uses penultimate-hop popping (PHP). Traffic
received via that tunnel is undistinguishable from traffic received
over the interface. If some of the traffic received via the LSP is
destined back to the penultimate hop, then the egress router would
consider that the traffic required U-Turn breaking and would redirect
that traffic to its alternate, if available. To avoid such a
scenario, a router can simply not request PHP for those LSPs which
are entering via an interface upon which the router has advertised
that it can break U-Turns. If a router must do PHP, then it can stop
advertising the ability to break U-Turns upon the interface.
For IP traffic, it is not possible to resolve the PHP issue. For LDP
traffic, it would be possible to advertise a different label for a
FEC on targeted sessions from the label advertised for non-targeted
sessions. In this case, only traffic received with the label for
non-targeted sessions would be subject to U-Turn breaking.
8. Security Considerations
This document does not introduce any new security issues. The
mechanisms described in this document depend upon the network
topology distributed via an IGP, such as OSPF or ISIS. It is
dependent upon the security associated with those protocols.
9. Intellectual Property Considerations
Avici Systems has intellectual property rights claimed in regard to
the specification contained in this document.
10. 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."
Atlas et al. [Page 24]
Internet Draft November 2004
"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.
11. References
[LOOP-FREE] A. Atlas, R. Torvi, G. Choudhury, B. Imhoff, C. Martin,
D. Fedyk, "Loop-Free Alternates for IP/LDP Local Protection", draft-
atlas-ip-local-protect-loopfree-00.txt, June 2004, work-in-progress
[OSPF-LOCAL-PROTECT] A. Atlas, R. Torvi, G. Choudhury, B. Imhoff, C.
Martin, D. Fedyk, "OSPFv2 Extensions for Link Capabilities and IP/LDP
Local Protection", draft-atlas-ospf-local-protect-cap-00.txt,
February 2004, work-in-progress
[ISIS-LOCAL-PROTECT] A. Atlas, R. Torvi, C. Martin, "ISIS Extensions
for Signaling Local Protection Capabilities", draft-martin-isis-
local-protect-cap-00.txt, February 2004, work-in-progress
[LDP] L. Anderson, P. Doolan, N. Feldman, A. Fredette, B. Thomas,
"LDP Specification", RFC 3036, January 2001
[RSVP-TE] D. Awduche, L. Berger, D. Gan, T. Li, V Srinivasan, G.
Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209,
December 2001
[RSVP-TE FRR] P. Pan, D. Gan, G. Swallow, JP Vasseur, D. Cooper, A.
Atlas, and M. Jork, "Fast Reroute Extensions to RSVP-TE for LSP
Tunnels", work-in-progress draft-ietf-mpls-rsvp-lsp-fastreroute-
06.txt, June 2004
[RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and
McPherson, D., "OSPF Stub Router Advertisement", RFC 3137, June 2001
[RFC3277] D. McPherson, "Intermediate System to Intermediate System
(IS-IS) Transient Blackhole Avoidance", RFC 3277, April 2002
[ISIS] R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual
Environments", RFC 1195, December 1990
[RFC2966] T. Li, T. Przygienda, H. Smit, "Domain-wide Prefix
Distribution with Two-Level IS-IS", RFC 2966, October 2000
[OSPF] J. Moy, "OSPF Version 2", RFC 2328, April 1998
Atlas et al. [Page 25]
Internet Draft November 2004
[RFC2370] R. Coltun, "The OSPF Opaque LSA Option", RFC 2370, July
1998
12. Authors Information
Raveendra Torvi
Avici Systems
101 Billerica Avenue
N. Billerica, MA 01862
USA
email: rtorvi@avici.com
phone: +1 978 964 2026
Gagan Choudhury
AT&T
Room D5-3C21
200 Laurel Avenue
Middletown, NJ 07748
USA
email: gchoudhury@att.com
phone: +1 732 420-3721
Christian Martin
Verizon
1880 Campus Commons Drive
Reston, VA 20191
email: cmartin@verizon.com
Brent Imhoff
WilTel Communications
3180 Rider Trail South
Bridgeton, MO 63045
USA
email: brent.imhoff@wcg.com
phone: +1 314 595 6853
Don Fedyk
Nortel Networks
600 Technology Park
Billerica, MA 01821
email: dwfedyk@nortelnetworks.com
phone: +1 978 288 3041
12. Editor's Information
Alia Atlas
Avici Systems
101 Billerica Avenue
Atlas et al. [Page 26]
Internet Draft November 2004
N. Billerica, MA 01862
USA
email: aatlas@avici.com
phone: +1 978 964 2070
Appendix A: U-turn Alternate Proofs
............... +--+--+ 15
......+----------------| ABRt|----------------+
... | 15 +-----+ |
.. | ... |
.. 5 +-----+ 15 +--+--+ .. |
. +------| A2 +---------| R1 |-----+ . |
.. | +-----+ +-----+ 20 | . |
. | +-----+ 10 |
. | +--------------| ABR2|---------+ |
. | | 15 +-----+ | |
. +-----+ 5 +---+-+ . | |
. | S |-----------| P |------------+ . +-----+
. +-----+ +-----+ 5 | . | D |
. | | . +-----+
. | | . |
.. | +-----+ +-----+ 20 |
. +-----| A1 |------------------| ABR1|------------+
. 10 +-----+ 15 +-----+
... ...
... ...
...... .....
..............
Figure 10: Inter-Region Destination via
Multiple Border Routers but One Primary Neighbor
Consider where A2 is a U-turn alternate for ABR2. This case
matters only if A2 is not a loop-free alternate for any ABR
offering an optimal equal-cost path from S to D.
There are two possibilities for the path from A2 to D. First,
A2's optimal path to D is via one of the set of ABRs giving
optimal equal-cost paths from S to D. Therefore, A2 is still a
U-turn neighbor of S with respect to D. Consider that R1 is the
neighbor of A2 which provides the loop-free node-protecting
alternate for ABR2. In that case, either R1's optimal path to D
is via one of the ABRs in the set, in which case that it is
loop-free and avoids S be can be shown or R1 will go via a
different ABR, ABRt, in which case it will also remain loop-free
and avoid P (same proofs as in [LOOP-FREE] with R1 replacing
Atlas et al. [Page 27]
Internet Draft November 2004
A2).
The other possibility is that A2's optimal path to D is via a
different ABR, ABRt.
Step i: D_opt(A2, ABRt) + D_opt(ABRt, D) <=
D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D)
Step ii: D_opt(S, ABR2) + D_opt(ABR2, D) <
D_opt(S, ABRt) + D_opt(ABRt, D)
Step iii: D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D) <
D_opt(A2, S) + D_opt(S, ABRt) + D_opt(ABRt, D)
Step iv: D_opt(A2, ABRt) + D_opt(ABRt, D) <
D_opt(A2, S) + D_opt(S, ABRt) + D_opt(ABRt, D)
Therefore, if Dopt(A2, D) is via ABRt, it does not go through S.
The same proof can be done to show that the path would be loop-free
with respect to P and D, simply by substituting P for S in the above
proof.
Thus, if A2 offered a U-Turn alternate for one of the ABRs offering
an optimal equal-cost path from S to D, A2 will, at the worst, offer
a U-turn alternate for D.
If a U-Turn neighbor offered a node-protecting alternate to one of
the ABRs offering an optimal equal-cost path from S to D, then the
U-Turn neighbor will still offer a node-protecting alternate because
it will fall into one of the following 3 categories:
1) The U-turn neighbor is still a U-turn neighbor. Its neighbor Ri,
which
provides the loop-free node-protecting alternate, has the
shortest path to D
via one of the ABRs, in which case, if it was protecting against
P before, it
still will be.
2) The U-turn neighbor is still a U-turn neighbor. Its neighbor Ri
has the
shortest path to D via a different ABR, in which case it doesn't
go through
P.
Atlas et al. [Page 28]
Internet Draft November 2004
3) The U-turn neighbor offers a loop-free alternate to reach D, in
which case it
must go through a different ABR and therefore doesn't go through
P.
Atlas et al. [Page 29]