Subject: LFAs and OSPF with multiple intra-area AS-external or summary-routes

From: Alia Atlas <[email-masked]>
Date: Mon, 07 Feb 2005 20:56:20 -0500

The behavior of loop-free alternates within a single area seems pretty 
clear.  Things get a bit more interesting when considering multiple areas 
for OSPF.  For instance, consider the following topology where the --- 
lines indicate area 1 and the **** lines indicate area 2.

                                   5
                     [ A2 ] ************** [ Z ]
                       *                     *
                       *                     *
                    10 *                     *
              10       *    1                *
   [ A1 ] ---------- [ S ]*****[ N2 ]        *
     |                 |         *           *
   5 |               5 |       1 *           *
     |       5         |    1    *    13     *
   [ X ] ----------- [ N1 ]----[ Y ] **** [ ASBR2]
     |                                       *
   5 |                                       * 10
     |        10                             *
   [ ASBR 1] ---- P                          P

In the above topology, S learns two routes to the prefix P.  From area 1, S 
learns an intra-area route to ASBR1 with a cost of 15 (25 to P); similarly 
from area 2, S learns an intra-area route to ASBR2 with a cost of 15 (25 to P).

Assuming that S is doing ECMP, S would normally select both N1 and N2 as 
primary next-hops.  The question is what should S select for alternates. S 
could assume that N1 and N2 can be alternates for each other & provide both 
link and node protection.  However, Y is also an ABR & sees a shorter path 
to the prefix P via N1 in area 1.  Thus, although the primary path computed 
by S for area 2 didn't use N1, traffic forwarded to N2 will go to Y and 
thus to N1.

Therefore, the two primary next-hops can't be guaranteed to provide 
node-protection.  Similarly, there could be a broadcast interface between 
S, N1 and Y in the above topology - and then link protection wouldn't be 
provided.

In a more absurd topology, S could not even have the topology information 
available to in any way determine this.  This would be the case when 2 ABRs 
were crossed.

This seems to me to indicate that a primary next-hop SHOULD be protected by 
an alternate next-hop from the same area; this implies the need to store an 
alternate per (non-backbone) area primary next-hop to gain protection.

Also, the ability of an alternate path to exit the area and (potentially) 
return via the "protected" primary neighbor or a link to that neighbor may 
need to be considered.  This could happen by crossing 2 ABRs, one of which 
had a shorter intra-area route in the second area & the other which had a 
shorter intra-area route in the first area - that was back through the 
"protected" primary neighbor.

I believe that both of the above are potentially of concern for inter-area 
routes and AS-external routes.

The first seems like it could be solved by requiring a primary next-hop be 
protected by an alternate from the same area - even if there is an 
equal-cost path via a different area.  The second seems more theoretically 
problematic - though less realistic.  These issues appear to only exist for 
the ABRs.

Thoughts?  Have I missed anything?  Any suggestions on reasonable 
compromise approaches?

Thanks,
Alia

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

---

From: Alex Zinin <[email-masked]>
Date: Tue, 8 Feb 2005 11:52:49 -0800

Alia,

  Couple of things here.

  The OSPF spec says that when an ASBR is reachable with the same cost through
  more than one area, the paths through a single area (with the highest area ID)
  must be picked. However, I do know certain implementations would load-balance
  in such situation.

  I agree with your suggestion to require the protecting neighbor to be in the
  same area. I'd like us to keep the mechanism as simple as practically
  feasible. As we gain experience and feel more comfortable going further, we'll
  be able to extend this.

  Regarding the cases, where traffic will still get diverted to another area--
  this is what the applicability statement is for. In other words, we provide
  a tool that (as always) has its own limitations. As long as the tool is
  practically useful, and limitations are carefully described in the AS, we're
  fine.

  Thanks for looking at this!

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

---

From: Alia Atlas <[email-masked]>
Date: Tue, 08 Feb 2005 16:26:34 -0500

Alex,
>   must be picked. However, I do know certain implementations would 

Despite hunting the OSPF spec, I missed that bit; thanks for point it 
out.  Certain implementations, as you say, would load-balance in that 
situation.

I guess the question is whether this is preferable behavior or becomes bad 
when doing IP FRR.

I believe that the same problem can exist with an inter-area route if a 
router is in two non-backbone areas and isn't in the backbone area.  I'm 
still thinking about whether the problem might exist if it is in the 
backbone area and connected by multiple virtual links in different transit 
areas.

>   feasible. As we gain experience and feel more comfortable going 

The problem is that this isn't a completely simple solution - from an 
implementation perspective.  There are two issues.  First, say that we've 
got two primary next-hops P1 and P2 (in areas 1 and 2 respectively) with 
their associated alternates A1 and A2 (again in areas 1 and 2 
respectively).  Now, if the link to P1 fails, does all traffic suddenly get 
routed to A1 in preference to the equal-cost P2?  Do I put the traffic that 
was going to P1 onto A1 and leave the other traffic on P2?  Arguably, if 
there are alternates on the path from P2, then those could be used (if 
there's a corresponding failure on that path).  Say the failure is of P1 
and the path from P2 reenters the area via node Y.    Then it is possible 
that Y's LFA in that area is S itself.

This latter is really just another case of the alternate next-hop not going 
via the intra-area path computed but into a different area.  If we can 
solve that one (I like applicability statements if we can frame it clearly 
:-), then perhaps this becomes a non-issue.

Second, there's a practical limitation of how many next-hops (primary or 
alternate) one may store with a particular route.  This could limit the 
number of areas that a router can take a shortest-path from.  Granted, a 
router may only support ECMP up to some number - but previously only 1 or 
2  (worst-case with ECMP to two neighbors across the same interface) extra 
next-hops were ever needed to store alternates.  Now it could be one for 
every area - or even 2 (in the worst-case).

The second is "just" an implementability concern - it's certainly possible 
but just more complex.  For the first, I think we may wish to define 
rules/recommendations.  Of course, we've not defined the rules for ECMP in 
a single area; maybe its an implementation-specific decision but I think it 
bears a bit of discussion.

>   practically useful, and limitations are carefully described in the AS, 

I'd be happy to see it solved with an applicability statement - but I'm not 
certain of how to specify it.

>   Thanks for looking at this!

The joys of implementation :-)  Thanks actually go to Srinivas and Namrata 
for pointing out the lack of specification :-(

Alia

---

From: Alex Zinin <[email-masked]>
Date: Tue, 8 Feb 2005 23:48:11 -0800

Alia,

> backbone area and connected by multiple virtual links in different transit 

Yes, we need to consider the transit area case, since it makes it possible for
routing entries to have next-hops in more than one area. This is standard
behavior. Once this is solved, non-standard things like ECMP to ASEs and
multiple non-bb area (as in e.g. RFC3509) would most probably benefit from a
similar solution.

> respectively).

ok

> Now, if the link to P1 fails, does all traffic suddenly get

Do you have an example for this scenario? A diagram would make it easier to
analyze. Also, I think one implicit thing here that's worth made explicit is
what we mean by a single failure in the FRR fundamentals. Case 1: it is a single
failure per complete set of areas. Case 2: single failure per area. It seems
that reducing to case 1 may make things simpler.

> every area - or even 2 (in the worst-case).

How about we look at it this way: what we're interested in is protection,
whether this is ECMP or LFA. Removing increased memory consumption from
consideration as something we'll have to deal with anyways: if an implementation
is constrained to support N next-hops only, and all of the slots for a route are
taken, well then one option is to not install LFAs at all--the route is
protected with ECMP after all. Should the topology change such that some slots
become available--one can add LFAs there.

> bears a bit of discussion.

Yes, let's discuss this a bit and see if anything needs to be recommended or
some explanatory text added to the document.

Regards,

Alex

---

From: Alia Atlas <[email-masked]>
Date: Wed, 09 Feb 2005 11:31:58 -0500

Alex,

>multiple non-bb area (as in e.g. RFC3509) would most probably benefit from a

Agreed.

>that reducing to case 1 may make things simpler.

I hadn't gotten to considering case 2; I'm still on case 1.

Here's an example.  In this case --- are area 1 and **** are area 2.  S is 
connected via a virtual link to ABR1 in area 1 and by a virtual link to 
ABR2 in area 2.  Y isn't connected to the backbone; it could also have 
virtual links in the two areas to ABR1 and ABR2 if needed.

               10        1
       [ A1 ]-----[ S ]*****[ P2 ]
         |          |          *
         |        5 |          * 1
         |          |     1    *
      10 |        [ P1 ]-----[ Y ]
         |          |          *
         |        5 |          * 13
         |     5    |          *
        [ABR1]----[ B ]     [ ABR2 ]
          |                    |
       10 |                    | 10
          |                    |
       Summary Prefix 1   Summary Prefix 1

>become available--one can add LFAs there.

True - but the ECMP may not give protection in the multi-area paths.

>some explanatory text added to the document.

OK.  I'll start a separate thread on ECMP considerations (with examples).

Thanks!
Alia

---

From: Alex Zinin <[email-masked]>
Date: Wed, 9 Feb 2005 12:17:05 -0800

Alia,

>>what we mean by a single failure in the FRR fundamentals. Case 1: it is a
>>single failure per complete set of areas. Case 2: single failure per area. It
>>seems that reducing to case 1 may make things simpler.

>        [ A1 ]-----[ S ]*****[ P2 ]

Thanks.
In this scenario, assuming the failure is that of P1 node, Y would lose its
connectivity in area 1 completely, wouldn't it?

> True - but the ECMP may not give protection in the multi-area paths.

I'm sorry, I'm not sure I understand correctly what you mean here. Could you
explain, please?

Alex

---

From: Alia Atlas <[email-masked]>
Date: Wed, 09 Feb 2005 15:40:28 -0500

>connectivity in area 1 completely, wouldn't it?

True.  One could easily add a link between Y and another node in area 1 so 
that doesn't happen.  There could be a link between S and Y of greater cost 
- so that Y tries to use S as a loop-free link-protecting alternate.

>I'm sorry, I'm not sure I understand correctly what you mean here. Could you

Because the path in area 2 might cross back to area 1, the path in area 2 
may not be link or node protecting with regard to the path in area 1.  In 
the above example, P2 offers node-protection, but not link-protection to 
the path via P1.  If a broadcast link (with the different costs) connected 
S, P1 and Y, then P2 wouldn't be link-protecting either.

Does that clear things up or shall I do more ascii art? ;-)

Alia

---

From: Alex Zinin <[email-masked]>
Date: Wed, 9 Feb 2005 17:25:39 -0800

Alia,

> - so that Y tries to use S as a loop-free link-protecting alternate.

Understood.

I thought about this today. It seems that in the above situation, for a loop to
form, S doesn't even have to be a direct neighbor of Y, just belong to the path
rooted at Y's LFA. In fact, it also appears that S doesn't even have to do
ECMP...

I need to think more about this, but it seems that the LFA condition for ABRs
cannot be simply based on a single area topology. I'll provide more details when
I'm done going through different scenarios.

Of course, the last resort is to say that transit areas are not supported yet,
but I want to make sure we understand how hard it would be to get them to work
first.

Alex

---

From: Alia Atlas <[email-masked]>
Date: Wed, 09 Feb 2005 20:45:41 -0500

Alex,

>rooted at Y's LFA. In fact, it also appears that S doesn't even have to do

Yes... Basically, the loop-free check doesn't have enough information.

>I'm done going through different scenarios.

Looking forward to it :-)  I'm trying to do the same.

>but I want to make sure we understand how hard it would be to get them to 
>work first.

I think there is still a problem with the AS-external as well.  For 
instance, say S has two equal-cost paths in area 1 to E1 and E2.  On the 
path from E2 to the prefix advertised by ASBR1, let it cross an ABR whose 
shorter path is through area 2 to ASBR2.  Then, let that path cross another 
ABR whose shorter path is through area 1 via E1 (or the link to E1 even).

Maybe there's a restriction about LFAs passing through ABRs :-(

Alia

---

From: Alia Atlas <[email-masked]>
Date: Wed, 09 Feb 2005 20:53:44 -0500

Alex,

One thing to note is that the problem can't occur if D_opt(N, D) < D_opt(E, 
D).  I.e., if the alternate next-hop is a downstream path with regard to 
the primary next-hop.  Not that this helps with coverage :-(

Similarly, if no other ABR in the area is announcing a shorter path than 
D_opt(E,D), then it couldn't happen.  Or even if the combo of the distance 
from the other ABR to E plus the path announced is shorter than 
D_opt(E,D).   If S is an ABR, then S could hear all the other ABR's summary 
routes and be able to determine this, I think.  Not that it's pretty...

Alia

---

From: Alex Zinin <[email-masked]>
Date: Wed, 9 Feb 2005 18:14:45 -0800

Yes, I've gone through these too.

The direction I'm going in now is to look at it from the perspective
of intersecting SPTs--each SPT being in it's own area and intersection
points being ABRs. What we need is to make sure that when we move traffic
to an alternate, we don't end up moving it up the tree in another area
and receiving it back to us down that tree.