Subject: Re: [Rift] Clarification on North/South bound SPF

From: "Nagendra Kumar Nainar (naikumar)" <[email-masked]>
Date: Thu, 3 May 2018 16:23:18 +0000

Hi Tony,

Thanks.  I think I get it now ☺

Just confirming my understanding – While computing Northbound SPF, a node will consider a) “locally” originated Node N-TIE, b) Node N-TIE from same level c) Node/Prefix S-TIE. But it does not consider any other N-TIE(ex: the one from downstream or lower level nodes). On the same line, while computing southbound SPF, it will consider a)Entire Prefix/Node N-TIE b) (obviously) locally originated Node S-TIE.

Is that a fair understanding?

Thanks,
Nagendra

From: Tony Przygienda <[email-masked]>
Date: Wednesday, April 25, 2018 at 12:34 AM
To: Nagendra Kumar Nainar <[email-masked]>
Cc: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [Rift] Clarification on North/South bound SPF

Hey Nagendra, good drilling, good observations, let me expound a bit ;-)
a. "SPF" per se is a lie in the draft to seem more familiar to existing stuff  than it is ;-), RIFT is loop free & with that RIFT CAN compute all feasible paths, i.e. you could use a "modified kind of SPF" if you will where you have a candidate list per level independent of distance (i.e. you get all paths with all distances & you can use all of those). Draft doesn't mention that, will probably do in the future but when you implement stuff it becomes blatantly obvious what I mean ;-}
b. Your point 1: It's a bit more complicated albeit you are right.
i) when you're a leaf you do not strictly speaking have a S node TIE (since it's not necessary) so you'd use your own (leaf's N node-tie & then use the upper level's S node-tie [as you say]) to double-check the bi-directionality.
c. as meta-point:
observe that N- and S-node-TIEs are fully symmetric right now (in terms of adjacencies) for many reasons so it really doesn't matter which one you use ;-)
d. as meta-meta-point:
N- and S-node-TIEs are NOT fully symmetric  (if you read the schema you see mysterious unexplained stuff in NodeTIEElement, this has to do with something we call "transitive disaggregation" and will be added to the draft. I'm discussing the math with Pascal and we try to find a simple representation of it but in terms of SPF it plays no role).
I hope I clarified more than I confused here, otherwise just keep poking ;-)
--- tony

On Tue, Apr 24, 2018 at 2:40 PM, Nagendra Kumar Nainar (naikumar) <[email-masked]<mailto:[email-masked]>> wrote:
Hi Authors,

While I am still reading, I thought of quickly clarifying a couple of points to better understand the remaining part of the draft ☺

  1.  In Section 4.2.5.1, N-SPF is defined as below

“N-SPF uses northbound and east-west adjacencies in North Node TIEs
   when progressing Dijkstra.”

Based on my reading so far, N-SPF is triggered to compute the path towards upper level (Level0 to Level1 and so on) and I believe this requires N-SPF to be run on Node S-TIE and not Node N-TIE right?. Should it not be “N-SPF uses northbound and east-west adjacencies in Node S-TIE when progressing Dijkstra”?.

  1.  Similar one in Section 4.2.5.2 – S-SPF should use soutbound adjacencies in node N-TIE right?.

Am I missing something?.

Thanks,
Nagendra

_______________________________________________
Rift mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/rift

---

From: Antoni Przygienda <[email-masked]>
Date: Thu, 3 May 2018 17:12:02 +0000

Inline …

<[email-masked]<mailto:[email-masked]>> spake:

Hi Tony,

Just confirming my understanding – While computing Northbound SPF, a node will consider a) “locally” originated Node N-TIE

Yes … You may not have southbound stuff & may not even generate a node S-TIE in your implementation

b) Node N-TIE from same level

you don’t see them l-)  Only Node S-TIEs in your level are reflected and if you’re a leaf you even don’t have that …

c) Node/Prefix S-TIE. But it does not consider any other N-TIE(ex: the one from downstream or lower level nodes). On the same line, while computing southbound SPF, it will consider a)Entire Prefix/Node N-TIE b) (obviously) locally originated Node S-TIE.

Observe the log from the interim, I comment in which should clarify what you use …

COMPUTATION_ID: 8456
     May 01 20:09:51.107 DEBG running North SPF graph closure on 6 nodes originating in 111

So, N-SPF for 111 starts.

     May 01 20:09:51.107 DEBG ++ Entering node 111 @ 0

We are on PENT with distance 0

     May 01 20:09:51.107 DEBG ++++ Entering node 111 dist 0 with 4 neighbors
     May 01 20:09:51.107 DEBG ++ Link to node 21 @ hndl 0 checking backlinks North

21 is north of 111 so it can be used

     May 01 20:09:51.107 DEBG ++++++ found backlink in North

Looking @ 21’s Node S-TIE we find ourselves

     May 01 20:09:51.107 DEBG ++++++ added 21 @ 1 nhops ComputationNextHopsType({NeighborNextHopType { distance: 1, interface: 4120, neighborid: 21 }})

So it goes on the TENT @ distance 1 from us

     May 01 20:09:51.107 DEBG ++ Link to node 22 @ hndl 1 checking backlinks North
     May 01 20:09:51.107 DEBG ++++++ found backlink in North
     May 01 20:09:51.107 DEBG ++++++ added 22 @ 1 nhops ComputationNextHopsType({NeighborNextHopType { distance: 1, interface: 4123, neighborid: 22 }})

Same for 22

     May 01 20:09:51.108 DEBG ---- node 1111 in level 22 is opposite DAG closure direction
     May 01 20:09:51.108 DEBG ---- node 1112 in level 22 is opposite DAG closure direction

Well, we have adjacencies to 1111 and 1112 but they’re south of us …

     May 01 20:09:51.108 DEBG ++ Entering node 21 @ 1
     May 01 20:09:51.108 DEBG ++++ Entering node 21 dist 1 with 4 neighbors
     May 01 20:09:51.108 DEBG ---- node 112 in level 23 is opposite DAG closure direction
     May 01 20:09:51.108 DEBG ---- node 121 in level 23 is opposite DAG closure direction
     May 01 20:09:51.108 DEBG ---- node 122 in level 23 is opposite DAG closure direction

Taking 21 from TENT we find that all its adjacencies point south, we’re using his node S-TIE, we have nothing else …

     May 01 20:09:51.108 DEBG ++ Entering node 22 @ 1
     May 01 20:09:51.108 DEBG ++++ Entering node 22 dist 1 with 4 neighbors
     May 01 20:09:51.108 DEBG ---- node 112 in level 23 is opposite DAG closure direction
     May 01 20:09:51.108 DEBG ---- node 121 in level 23 is opposite DAG closure direction
     May 01 20:09:51.108 DEBG ---- node 122 in level 23 is opposite DAG closure direction
subsystem: spf

same for 22

   May 01 20:09:51.109 DEBG 3 SPF reachable systems expanded to South 2 prefixes

OK, we have 3 systems reachable after N-SPF and we use their prefix S-TIES! to expand

   May 01 20:09:51.109 DEBG direction South 2 prefixes attached with diffsize 2
  subsystem: rib
   extensive: prefixes
    May 01 20:09:51.109 DEBG prefix changes:
DeltaCompareVec(
    {
        Ipv4prefix(
            IPv4PrefixType {
                address: 0.0.0.0,
                prefixlen: 0
            }
        ): DeltaCompareEntry {
            deltatype: ElementAdded,
            value: Some(
                CompositeNextHopsWithTotalMetrics(
                    {
                        2147484256: 2
                    }
                )
            )
        },

and voila, default routes are here