Subject: Re: Comments on Algorithm description in draft-ietf-rtgwg-ipfrr-spec-base-09

From: mike shand <[email-masked]>
Date: Fri, 09 Nov 2007 10:44:02 +0000

Alia,

I think the proposed more detailed definitions, and the one or two
fixes you propose below sort this out.

see inline for my responses, but it all looks good.

thanks.

Mike

Alia Atlas wrote:

Stewart,

Thanks for the careful read and good comments; sorry for taking so long
to respond - I've been traveling & sick.

On 10/3/07, Stewart Bryant
<[email-masked]>
wrote:

Alia

We have taken a look at the algorithm in section 3.6 of

draft-ietf-rtgwg-ipfrr-spec-base-09, and there are a

number of cases where some clarification is needed to aid

understanding.

The root problem is that you have an object oriented

description of the algorithm but have not always defined

the objects.

Please see below.

We will also provide comments on the draft itself in another email.

Mike & Stewart

======begin=====

S is the computing router and has candidate next-hops H_1 through

H_k.

SB> You need to define a candidate next hop before you can say a
router

SB> has them (i.e. move the definition earlier)

N_i and N_j are used to refer to neighbors of S. For a next-hop

to be a candidate, the next-hop must be associated with a bi-

directional link, as is determined by the IGP.

SB> I think you want to say:

SB> S is the computing router

SB> S has neighbours N_1 to N_j

SB> The candidate next hops H_1 to H_k are the subset of N that are

SB> bidirectionally connected to S.

This is almost correct - a next-hop includes not just the neighbor but
also

the outgoing interface.  There can be multiple candidate next-hops that
refer to

the same neighbor N_i.

Yes. I wonder if it would be clearer if you added something like

"S may may have multiple next hops over different interfaces to each
neighbor".

SB>
Why does H_i have to be bidirectionally connected?

Just because bidirectional connectivity is required in OSPF/ISIS for a
link

to be usable.   I think that is more a sanity-check that both ends of
the link

have the same database - and I see no reason to vary from it here.

Do you disagree?

No. It just wasn't clear WHY it had to be bidirectional. I think I was
searching for some more subtle reason :-)

For a particular

destination router D, let S have already computed D_opt(S, D), and

for each neighbor N_i, D_opt(N_i, D), D_opt(N_i, S), and D_opt(N_i,

SB> Why is this N_i and not H_i?

A next-hop is the (outgoing interface,  N_i) pair.  The distance
computed is to

the neighbor N_i and need not go through the outgoing interface
associated with

H_i.

Yes I think that the explanation (up front) that a next-hop is the
(outgoing interface,  N_i) pair would probably clarify this enough.

N_j), the distance from N_i to each other neighbor N_j, and the set

of SRLGs traversed by the path D_opt(N_i, D).  S should follow the

below procedure for every primary next-hop selected to reach D. This

set of primary next-hops is represented P_1 to P_p.  This procedure

finds the alternate next-hop(s) for P_i.

SB> In the text so far X_i refers  to the node  itself, i.e. what
you later

SB> appear to call X_i.neighbor. This is confusing

I'm not sure exactly what you mean here (since there aren't any X_i in
the text).

Is this the confusion between a neighbor N_i and a next-hop H_i that
contains

(outgoing interface, neighbor)?

X was used as a generic. We found the suffix ".neighbor" confusing and
it didn't seem to be consistently applied.

Does replacing the following paragraph

"S is the computing router and has candidate next-hops H_1 through

H_k.  N_i and N_j are used to refer to neighbors of S. For a next-hop

to be a candidate, the next-hop must be associated with a bi-

directional link, as is determined by the IGP."

with

"S is the computing router.  S has neighbors N_1 to N_j.  A

candidate next-hop is indicated by (outgoing link, neighbor) and

the outgoing link must be bidirectionally connected, as is

determined by the IGP.  The candidate next-hops of S are enumerated as

H_1 through H_k."

help?

Yes. That sounds perfect.

First, initialize the alternate information for P_i as follows:

P_i.alt_next_hops = {}

P_i.alt_type = NONE

P_i.alt_link-protect = FALSE

P_i.alt_node-protect = FALSE

P_i.alt_srlg-protect = {}

For each candidate next-hop H_h,

1.   Initialize variables as follows:

cand_type = NONE

cand_link-protect = FALSE

cand_node-protect = FALSE

cand_srlg-protect = {}

2.   If H_h is P_i, skip it and continue to the next candidate next-

hop.

3.   If H_h.link is administratively allowed to be used as an

alternate,

SB> You need to define H_h.link. Do you mean the link

SB> between S and H_h, and can their be multiple links

SB> between S and H?

Does explaining that a next-hop is a (outgoing link, neighbor) pair
earlier in the modified paragraph help?

Yes. Perhaps to really reinforce the point, you could add after that
paragraph that H_i.link refers to the link of that next hop and
H_i.neighbor refers to the neighbor.

and the cost of H_h.link is less than the maximum,

and the reverse cost of H_h is less than the maximum,

and H_h.neighbor is not overloaded (for ISIS),

and H_h.link is bi-directional,

SB> H_h is already defined to be bidirectional - why is this is test

SB> condition?

I want the algorithm to capture all the conditions; the other was just
the text

defining what are valid candidate next-hops.  I think it is clearer to
have all the conditions

in one place rather than scattered; I could remove this condition from
the earlier text if that

would be preferable.

I'm not sure it matters now that it is clear why the bidirectionbality
is in there in the first place. (i.e. the front para now refers to the
IGP).

Its kind of hard, now that you have explained it here , to go back to
thinking how someone would read the revised text without the benefit of
your explanation, but I THINK it is now clear.

then
H_h can be considered as an alternate.  Otherwise, skip it

and continue to the next candidate next-hop.

4.   If D_opt( H_h.neighbor, D) >= D_opt( H_h.neighbor, S) +
D_opt(S,

D), then H_h is not loop-free.  Skip it and continue to the next

candidate next-hop.

SB> You need to define H_h.neighbour. Does it just mean the node

SB> H_h? In which case, why is it different from H_h?

Again, H_h is a next-hop so (outgoing link, neighbor)

Yes I think the modified text up front makes this clear now.

5.   cand_type = LOOP-FREE.

6.   If H_h is a primary next-hop, set cand_type to PRIMARY.

7.   If H_h.link is not P_i.link, set cand_link-protect to TRUE.

8.   If D_opt(H_h.neighbor, D) < D_opt(H_h.neighbor,
P_i.neighbor) +

D_opt(P_i.neighbor, D), set cand_node-protect to TRUE.

SB> You need to define P_i.neighbour

P_i is a primary next-hop and next-hops are (outgoing link, neighbor).

Again, I think this is now clear from the upfront stuff, especially if
you add my suggestion about spelling out in detail the meaning of .link
and .neighbor. It was disconcerting reading this for the first time and
having to assume that is what you meant, but not being quite sure.

9.   If the router considers SRLGs, then set the cand_srlg-protect to

the set of SRLGs traversed on the path from S via P_i to

SB> Does this mean S via Pi.link to P_i.neighbour?

yes - fixed

good

P_i.neighbor.  Remove
the set of SRLGs to which H_h belongs from

cand_srlg-protect.  Remove from cand_srlg-protect the set of

SRLGs traversed on the path from H_h.neighbor to D. Now

cand_srlg-protect holds the set of SRLGs to which P_i belongs

and that are not traversed on the path from S via H_h to D.

10.  If cand_type is PRIMARY, the router prefers other primary next-

hops for use as the alternate, and the P_i.alt_type is not

PRIMARY, goto Step 19.

11.  If cand_node-protect is TRUE and P_i.alt_node-protect is FALSE,

goto Paragraph 19.

12.  If cand_link-protect is TRUE and P_i.alt_link-protect is FALSE,

goto Step 19.

13.  If cand_srlg-protect has a better set of SRLGs than

P_i.alt_srlg-protect, goto Step 19.

14.  If cand_srlg-protect is different from P_i.alt_srlg-protect,

then select between H_h and P_i.alt_next_hops based upon

distance, IP addresses, or any router-local tie-breaker.  If H_h

is preferred, then goto Step 19.  Otherwise, skip H_h and

continue to the next candidate next-hop.

SB> The nesting of the IF then ELSE statements in step 14 is not
clear.

I changed the "Otherwise," to "If P_i.alt_next_hops is preferred,"

That makes it clear.

15.  If D_opt(H_h.neighbor, D) < D_opt(P_i.neighbor, D) and

D_opt(P_i.alt_next_hops, D) >= D_opt(P_i.neighbor, D), then
H_h

is a downstream alternate and P_i.alt_next_hops is simply an

LFA.  Prefer H_h and goto Step 19.

16.  Based upon the alternate types, the alternate distances, IP

addresses, or other tie-breakers, decide if H_h is preferred to

P_i.alt_next_hops.  If so, goto Step 19.

17.  Decide if P_i.alt_next_hops is preferred to H_h.  If so, then

skip H_h and continue to the next candidate next-hop.

18.  Add H_h into P_i.alt_next_hops.  Set P_i.alt_type to the better

type of H_h.alt_type and P_i.alt_type.  Continue to the next

candidate next-hop.

19.  Replace the P_i alternate next-hop set with H_h as follows:

P_i.alt_next_hops = {H_h}

P_i.alt_type = cand_type

P_i.alt_link-protect = cand_link-protect

P_i.alt_node-protect = cand_node-protect

P_i.alt_srlg-protect = cand_srlg-protect

Continue to the next candidate next-hop.

========end======

Alia

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

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