Subject: Multi-area loop-free condition

From: Alex Zinin <[email-masked]>
Date: Thu, 10 Feb 2005 14:11:00 -0800

Folks-

I decided to start by analyzing when the loops may form in a multi-area
scenario.

You will need to refer to the following diagram:
http://www.psg.com/~zinin/ietf/rtgwg/ma-lfa.jpg
Sorry for not providing ASCII art, it's easier to follow using the colored
graphical form.

Solid red and blue arrow form the all-src-one-dst SPTs in area 0 and 1
correspondingly (*). Links not in the SPTs are not shown, except for the blue
dashed arrow, marked LFA, that shows the LFA link chosen by S. Nodes A and B are
ABRs. D is a multihomed destination we're interested in.

Costs from nodes to D are noted as Cna, where 'n' is the name of the node and
'a' is the area. So, Cb1 is the cost from B to D in area 1.

In a single-area situation (i.e. blue tree only), when P fails, S can safely use
E as its LFA. In essence, we're moving traffic to another branch, that is not
affected by the failure.

When the second area comes to play, moving traffic to a different blue branch
may also result in it going up an SPT in another area, e.g. node A. Hitting an
ABR on the way from an LFA by itself is not sufficient for loop formation.
It is necessary that A picks the red-tree route over the blue one, i.e.:

    Ca0 <= Ca1         (1)

However, this condition is still not sufficient for loop formation. If diverted
traffic stays on the red SPT, we're fine. The loop will form if B injects
traffic back to area 1:

    Cb1 <= Cb0         (2)

and, of course, S has to be indeed on B's SPT:

    Ce1 = C(e-a)1 + Ca1  (3)

E has to be on A's SPT:

    Cb1 = C(b-s)1 + Cs1  (4)

and B has to be on A's SPT:

    Ca0 = C(a-b)0 + Cb0   (5)

Note that S doesn't have to be an ABR, and hence only sees the topology within
the area and summary-LSAs. Note, however, that S is not guaranteed to know costs
to the destination from all ABRs in other area, since OSPF reannounces
inter-area destinations only from the backbone. So if we swap area 0 and 1 in
the example, blue routers are not going to see A's and B's costs to D in the red
area.

Checking conditions (3) and (4) is trivial--only intra-area topological
knowledge is required. Checking other conditions requires information from ABRs
that is not available in OSPF now--costs to all other ABRs, and costs to all
destinations (unrestricted by the normal OSPF route distribution mechanisms).

Comments are welcome.

-- 
Alex
http://www.psg.com/~zinin

(*) An all-src-one-dst SPT is simply a collection of one-src-all-dst SPTs
    pruned to contain only links needed to reach a particular destination.
    In this example, it is the trajectory that traffic to D will take from
    all other locations.

_______________________________________________
Rtgwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rtgwg

---

From: Alia Atlas <[email-masked]>
Date: Thu, 10 Feb 2005 18:39:15 -0500

>destinations (unrestricted by the normal OSPF route distribution mechanisms).

Costs to all destinations doesn't seem feasible/desirable to really pass 
around.  What if we make the worst-case assumption that B is always on the 
path from A to D?  It may be pessimistic, but at least we won't claim to 
have protection that causes loops.

Alia

---

From: Alia Atlas <[email-masked]>
Date: Thu, 10 Feb 2005 19:41:37 -0500

Alex,

The other case (for protection concerns & not looping) would be if B's path 
went through E or the link between S and E.

For the concern about B, one could also check if all ABRs were loop-free 
with respect to S, E & any pseudo-node in between.  Of course, that's 
rather worst-case.

Alia

---

From: Alex Zinin <[email-masked]>
Date: Thu, 10 Feb 2005 18:30:18 -0800

Folks-

 Just a small clarification: described below is a very _generic_ case of
 multi-area routing, in particular, requiring VLs configured in OSPF to allow
 transit non-backbone areas. The point of the exercise was to understand the
 general behavior. In reality, OSPF rules for ASE path preference and intra-
 area route calculations without transit areas will limit the scope of problem
 substantially. I simply didn't want to put everything in one thread.

---

From: Alex Zinin <[email-masked]>
Date: Fri, 11 Feb 2005 15:00:56 -0800

Alia,

> went through E or the link between S and E.

If you mean that B's SPT goes through E, and then through A, then this is not
possible. It's easily provable that as long as both tress as shortest-path, and
ABRs choose the path with the best metric, moving traffic down one tree won't
move it up the other. It's the LFA's property of possibly moving traffic to a
node with a greater cost that can create the looping effect.

> with respect to S, E & any pseudo-node in between.  Of course, that's 

this loop-free check would have to account other areas as well, wouldn't it?

Alex

---

From: Alia Atlas <[email-masked]>
Date: Fri, 11 Feb 2005 18:39:40 -0500

Alex,

>node with a greater cost that can create the looping effect.

I meant the following.   S's primary is E.  S's LFA goes to A in area 
1.   In area 2, A has a shorter path and its path goes to B.  In area 1, B 
has a shorter path and that goes through E.

It's just the same picture as you drew, except causing a lack of protection 
(b/c of going via E) instead of looping b/c of going via S.

>this loop-free check would have to account other areas as well, wouldn't it?

I don't think so.  The question is whether any other ABR's path to the 
destination goes through S in that specific area.  This check is kind of 
like pretending that all ABRs are connected via a 0-cost link & seeing what 
it does.

Alia

---

From: Alex Zinin <[email-masked]>
Date: Fri, 11 Feb 2005 16:04:20 -0800

Here's the outline of different situations relevant for IPFRR with multi-area
routing. This should help identify cases we need to care about:

 1. Intra-area destinations
    no issue here

 2. Inter-area:

    2.1 Standard behavior with no virtual links (no transit areas)
        - ABRs have to be backbone-connected, or they end up with no inter-area
          routes
        - ABRs consider summaries only from area 0, and hence
          have all next-hops for inter-area routes in one area.
          no issue here.

    2.2 Standard behavior with VLs configured (transit areas)
        - ABRs consider summaries from the backbone and the transit
          areas, some inter-area routes may have next-hops in more
          than one area. potential issue here.

    2.3 Alternative ABRs (e.g. rfc3509), considering summaries from
        more than 1 area. potential issue here.

 3. AS-external:
    3.1 Standard behavior with no VLs
    
        We are concerned with two possible cases:
          o Same ASBR visible to S (calculating ABR) via multiple areas
          o Different ASBRs announcing the same prefix that end up being
             visible to S via multiple areas with the same type & cost.

        In the former case, step (3) in section 16.4 of 2328 ensures that
        next-hops always belong to one area, so no issue here.

        In latter case, step (6) bullet (c) in 16.4 is engaged.
        
        a) if the ASBRs are not in the same area as S, the std ABR will only
          see inter-area paths through the backbone. no issue here.
          
        b) if the ASBRs are connected to one area that S is in, ABR S will
           always use the intra-area path. no issue here
          
        c) if the ASBRs are visible to S as intra-area in more than one area,
           i.e., ASBR1 in area 1 and ASBR2 in area 2. potential issue here

        I'm sure I've missed some scenario here :)
           
    3.2 Standard behavior with VLs

        Transit areas make it possible for S to see more than 1 inter-area
        route to an ASBR or inter-area routes to different ASBRs through
        non-backbone areas.

        The single ASBR case is taken care of by step (3) in 16.4, where
        a single area is picked.

        Multiple ASBRs visible through different areas (backbone and transit) is
        possible.

    3.3 Non-standard ECMP

 Given that virtual links are an extremely rare case in real-life networks, I'd
 like to suggest that we move it out of the consideration. At least at this
 point. I also suggest that we remove 3.3 from considerations, since it's really
 hard to discuss something we don't have documented; hopefully the discussion
 about other scenarios will give people enough clue to address those.

 This leaves us with:

  2.3 Alternative ABRs

 and

  3.1 c) ASBRs visible as inter-area in different areas.

 We could even drop 2.3 for now and concentrate on 3.1 c. I suspect that due to
 similarity, by solving the second, we'll solve the first.

 Comments, please.

---

From: Alia Atlas <[email-masked]>
Date: Sun, 13 Feb 2005 21:32:33 -0500

>         next-hops always belong to one area, so no issue here.

How does this solve the issue?   Say that A, B and C are all ABRs in areas 
1 and 2.  C is also an ASBR.  Now, A's shortest path to C may be in area 2 
- but goes via B.  B's shortest path to C may be in area 1.  I think this 
gets us back to the loop possibility in your earlier figure.

>  about other scenarios will give people enough clue to address those.

I completely agree as far as virtual links.  As far as the non-standard 
ECMP case,
if we can come up with a solution that isn't "don't do that - it hurts", 
then I agree.  Otherwise,  it may bear a bit of thought.

>  similarity, by solving the second, we'll solve the first.

I agree that if we solve one then it will probably generalize well to the 
others.

Alia

---

From: Alex Zinin <[email-masked]>
Date: Mon, 14 Feb 2005 14:38:08 -0800

Alia,

> gets us back to the loop possibility in your earlier figure.

You're right, I think. I got carried away by the ECMP case in the beginning
of this discussion, which is where the area-id tie breaker comes in.

> I completely agree as far as virtual links. As far as the non-standard ECMP
> case, if we can come up with a solution that isn't "don't do that - it hurts",

Sure. The FRR spec is not the right place to go after all possible creative
things people can do with OSPF. I was thinking about a general problem
description, rule to make sure FRR is guaranteed to work with the standard
behavior, plus some clues for the rest.

Alex

---

From: Alex Zinin <[email-masked]>
Date: Mon, 14 Feb 2005 22:47:41 -0800

Thinking about solutions for this...

As I think Alia mentioned earlier, if the LFAs to the potentially multi-homed
destinations are calculated using the downstream condition (i.e. the LFA's cost
to the destination is less than S's cost to it), then it can be proved that
using such LFAs will never results in traffic looping even in the case of
counter-directed SPTs in different areas.

This comes at the price of reduced coverage, but we can consider this as our
last-resort strategy in case the detailed analysis shows that other mechanisms
are too expensive.

Alex

---

From: Alia Atlas <[email-masked]>
Date: Tue, 15 Feb 2005 10:30:58 -0500

Alex,

>of this discussion, which is where the area-id tie breaker comes in.

The ECMP case was the first that came to mind - but clearly the 
generalizations happen :-(

>behavior, plus some clues for the rest.

So a brief description of the problem sounds like it should go in for now - 
with a description that the looping can, worst-case, be solved by the 
restriction to downstream paths.  Protection can also be guaranteed, but 
the alternate must have a shorter distance than the primary neighbor.

Alia