[email protected]
[Top] [All Lists]

Re: node disjoint and SRLG

Subject: Re: node disjoint and SRLG
From: Stewart Bryant
Date: Fri, 26 Nov 2004 10:10:34 +0000

Alia Atlas wrote:

At 05:35 PM 11/22/2004, Curtis Villamizar wrote:

My point was that the node disjoint problem is a subset of the SRLG
problem.  It is a subset because you can define a SRLG to be all links
adjacent to a given node and therefore define the node disjoint case
as an SRLG case.  The local SRLG problem is also a subset of the SRLG

Local SRLGs and node disjoint are easier cases to handle than general SRLGs. Certainly, if one solves the general case, those can come for free.
One issue that I see for the non-source-routed tunnel based approach is
that it uses the original next-next-hop as a proxy for a set of
This was to reduce the number of SPFs that we ran. If we relax that
constaint we that look at alternatives.
It is possible that the path from the next-next-hop to a particular destination will not be available because it traverses a link in the same SRLG.
Strictly because there is no G such that the path from S to G and the
path from G to Si does not contain an SRLG member, even via a
secondary repair.
I think that this may make the destination assignment a bit trickier.

So far only MPLS/TE fully addresses SRLG and it does so very cleanly.

In a full overlay, MPLS/TE requires a CSPF per IGP node.

If we were willing to accept an SPF per node in the topology, then looking at SRLGs would be a lot simpler!
Agreed. Indeed I suspect a number of new approaches then become feasible.

If I were even willing to accept an SPF per neighbors' neighbor, it
would be completely clear how to do SRLGs for U-turn alternates.
I can see how with one SPF per node you can increase the reach of
U-turn, but surely to do SRLG you need to carry some vector in the
packet to steer it at critical places?

The computational complexity for MPLS/TE can be quite large, depending
on the number of tunnels to be considered. Sure, one can use techniques
to minimize the impact, but it is there.
I'd say it's clear that for IP FRR, there's a desire to have
substantially fewer SPFs than 1 per node.
That is a desire, although I have some personal doubts at the validity
of that constraint. Remember that when we designed link state
protocols we were using CPUs that were three orders of magnitude
slower than those that we use today.
There is the basic fact that without source-based routing, it might not
be possible to find an alternate.
If the general SRLG problem is not addressed, the failure to address
the problem should at least be acknowledged in the documents.
We can certainly do much better than the current document implies and
any description should include some sort of applicability statement that describes the constraints.
is not a requirement for IP FRR, that should at least be stated in the
framework document, but the limitations should also be acknowledged.

Normally it would be sufficient to list something as future work in
the framework but that should be done where algorithms are known and
only the protocol bits need to be defined later (and if needed).  In
this case there is question about whether feasible algorithms exists
so the limitation should be acknowledged and not just dismissed.

I guess it depends on the particular technique considered, but there are feasible algorithms for some of them.
For loop-free alternates, one can track the SRLGs traversed by each
neighbor, and decide whether to use a loop-free neighbor based on
whether the SRLGs of concern are passed.
We can do the same for tunnels, and you can do the same for U-turn.
The general approach is that you must check that you do not go over
an SRLG member during the period that you control the packet, and
then make sure that it does not go over one after it is released. The
issue is what to you do if it does.

- Stewart

Rtgwg mailing list
[email protected]

<Prev in Thread] Current Thread [Next in Thread>