Re: [Rift] AD Review draft-ietf-rift-rift-16 (§4.2.3 thru §4.2.3.2)

[[e-mail]]

I didn't have better resolution before I sent out that comment. 


I can live with the  definitions anyway.


Thank you very much for the explanations.












Best Regards,


Yuehua Wei

















Original



From: PascalThubert(pthubert) <[e-mail]>
To: Tony Przygienda <[e-mail]>;魏月华00019655;
Cc: jhead=[e-mail] <jhead=[e-mail]>;[e-mail] <[e-mail]>;[e-mail] <[e-mail]>;张征00007940;[e-mail] <[e-mail]>;[e-mail] <[e-mail]>;
Date: 2023年04月07日 13:19
Subject: RE: [Rift] AD Review draft-ietf-rift-rift-16 (§4.2.3 thru §4.2.3.2)


On the side, a routing that relies on a "metric" is in essence greedy, meaning that the packet must progress (reduce the cost at each hop) to avoid loops.
As breakages create valleys, this is doomed unless you create either a huge multipath capability like in RIFT, or alternate topologies that can be used to take the packet out of a valley a non-obstructed place in the graph. ARCs micro topologies inside the (extended) SPF as opposed to after the fact like most FRR solutions, and then uses a state in the packet to traverse the micro topology and inject the packet back.
 
Cool stuff...
 
Pascal
 
> -----Original Message-----
> From: Tony Przygienda <[e-mail]> 
> Sent: jeudi 6 avril 2023 18:39
> To: [e-mail]
> Cc: jhead=[e-mail]; [e-mail]; draft-ietf-
> [e-mail]; [e-mail]; [e-mail];
> [e-mail]
> Subject: Re: [Rift] AD Review draft-ietf-rift-rift-16 (§4.2.3 thru §4.2.3.2)
>  
> to correct myself, as side note: hop-by-hop forwarding works not only on
> shortest-path metrics, it's a more complex thing including e.g. valley-free
> routing as well where the metric is an interesting vector that either
> preconditions special construction of routing tables (and mostly leads into
> understanding of the directionality of the graph, i.e. a partial order of
> nodes as in rift or the GROW leaking work) or state on the packet (e.g.
> ROLL)
>  
> -- tony
>  
> On Thu, Apr 6, 2023 at 6:30 PM Tony Przygienda <[e-mail]> wrote:
>  
> > Yuehua, well, in a sense a good catch, in another sense not much we
> > can do about it without causing massive confusion
> > 
> > so, if you look at mathematical definition of simple metric space
> > [kind of special case of topology] (which we have to do here to really
> > explain the terms rather than the happily and sloppily used terms
> > around IP routing for last 3 decades)
> > 
> > 
> > Metric Space
> > ------------------------------
> > 
> > A metric space is a set <https://mathworld.wolfram.com/Set.html> [image:
> > S] with a global distance function
> > <https://mathworld.wolfram.com/Function.html> (the metric
> > <https://mathworld.wolfram.com/Metric.html> [image: g]) that, for
> > every two points [image: x,y] in [image: S], gives the distance
> > <https://mathworld.wolfram.com/Distance.html> between them as a
> > nonnegative <https://mathworld.wolfram.com/Nonnegative.html> real
> > number <https://mathworld.wolfram.com/RealNumber.html> [image:
> > g(x,y)]. A metric space must also satisfy
> > 
> > 1. [image: g(x,y)=0] iff <https://mathworld.wolfram.com/Iff.html> [image:
> > x=y],
> > 
> > 2. [image: g(x,y)=g(y,x)],
> > 
> > 3. The triangle inequality
> > <https://mathworld.wolfram.com/TriangleInequality.html> [image:
> > g(x,y)+g(y,z)>=g(x,z)].
> > 
> > 
> > However we have in the case of bidirected graphs really a topology
> > defined over a metric space which is more complex since g(x,y) is not
> > necessarily equal g(y,x) and triangle inequality only holds _if_ we
> > define the distance as 'shortest distance' (whatever _that_ is ;-) and
> > we do NOT have negative metrics on any edges (it's even more complex,
> > I glance only here over that stuff; I can give you Bell Labs paper
> > reference providing a very strict definition of that but that would
> > probably make you fall asleep unless you hard core mathematician
> > skilled in topological spaces ;-) Ultimately, the DAG formed by the
> > metric space on the bidirected graph is what we end up talking about
> > but it's another weird thing, first it is source specific so kind of
> > each source has a metric space on the graph it uses ;-) and why we
> > revert to DAGs is because extension of a DAG over a metric space is a
> > chain (welcome to tons math terms ;-) which is the precondition for hop-by-
> hop forwarding to even work.
> > so you see distance (function) and metric are the same thing really no
> > matter all those flourishes. cost is not really anything, it's really
> > distance between two members of the set (which should be symmetric in
> > metric space but as I said in bidirected graphs it isn't but I don't
> > remember of a strict mathematical definition of that, probably
> > somewhere bidirected (assymetric) graphs). So in a case of topological
> > graph theory if you can lay out the graph in the euclidian plane so
> > the cost of an edge is equivalent to geometrical distance (euclidian)
> > you have an equivalence _but_ since we're in generic bidirected graph
> > you cannot do that (I assume you followed the chain of definitions
> > here and it's evident why not ;-)
> > 
> > _but_ if we introduce the terms along the strict lines of metric
> > space/topology on bidirected graphs e'one in IP routing will simply
> > get confused, normally the terms distance and metric and cost are all
> > used interchangeably with metric (but sometimes cost as well) being
> > often used as one-hop-distance
> > 
> > so the best approach to not confuse anyone is really in my eyes to go
> > 
> > metric/cost = distance one hop  (so special case of a distance
> > function and in graph theory terms) distance/cost = sum of
> > metrics/cost [you see how the recursion creeps in given overlapping
> > semantic fields].
> > 
> > Generally, we had this sloppy language in IP routing for 30 years and
> > people in context kind of always decoded it so I chose to run with it ...
> > 
> > -- tony
> > 
> > 
> > 
> > 
> > On Thu, Apr 6, 2023 at 9:16 AM <[e-mail]> wrote:
> > 
> >> Hi Jordan,
> >> 
> >> One comment about definitions of “Metric” and “Cost”. It seems that
> >> circular definition still exist.
> >> 
> >> 
> >> 
> >> 
> >> There is clearly some type of circular definition between the cost
> >> 
> >> ("weighted distance") and the distance ("sum of costs").  ??
> >> 
> >> 
> >> 
> >> yeah, I don't want to go full tilt math definitions where topology
> >> defines those terms strictly but
> >> 
> >> we should unify the terms here
> >> 
> >> 
> >> 
> >> metric = how far is something in one hop
> >> 
> >> cost = sum of metrics = distance
> >> 
> >> 
> >> 
> >> 
> >> 
> >> Also, note that "weighted" is only used in this definition -- except
> >> 
> >> when referring to weighted ECMP or UCMP.
> >> 
> >> 
> >> 
> >>     jhead>> Per Tony's comments, I've added a definition for metric
> >> and unified the definitions.
> >> 
> >> 
> >> 
> >>         Metric: The cost between two neighbors exactly one layer 3
> >> hop away from each other.
> >> 
> >> 
> >> 
> >>         Cost: The sum of metrics between two nodes.
> >> 
> >> 
> >> 
> >>         Distance: The sum of costs (bound by infinite distance)
> >> between two nodes.
> >> 
> >> 
> >> 
> >> 
> >> Thanks,
> >> 
> >> *Yuehua Wei*
> >> 
> >> 
> >> Original
> >> *From: *JordanHead <jhead=[e-mail]> 
> >> *To: *Tony Przygienda <[e-mail]>;Alvaro Retana < 
> >> [e-mail]>;
> >> *Cc: *[e-mail] <[e-mail]>;
> >> 张征00007940;[e-mail] <[e-mail]>;[e-mail]
> >> < [e-mail]>;
> >> *Date: *2023年03月13日 22:28
> >> *Subject: **Re: [Rift] AD Review draft-ietf-rift-rift-16 (§4.2.3 thru
> >> §4.2.3.2)*
> >> _______________________________________________
> >> RIFT mailing list
> >> [e-mail]
> >> https://www.ietf.org/mailman/listinfo/rift
> >> 
> >> Alvaro,
> >> 
> >> 
> >> 
> >> Comments inline as jhead>> 
> >> 
> >> 
> >> Thanks
> >> 
> >> 
> >> 
> >> From: Tony Przygienda [e-mail]
> >> 
> >> Date: Wednesday, February 22, 2023 at 1:39 PM
> >> 
> >> To: Alvaro Retana [e-mail]
> >> 
> >> Cc: Jordan Head [e-mail], [e-mail]
> >> [e-mail], [e-mail]
> >> [e-mail], [e-mail] [e-mail],
> >> [e-mail] [e-mail]
> >> 
> >> Subject: Re: [Rift] AD Review draft-ietf-rift-rift-16 (§4.2.3 thru
> >> §4.2.3.2)
> >> 
> >> 
> >> 
> >> [External Email. Be cautious of content]
> >> 
> >> 
> >> 
> >> missed all reply
> >> 
> >> 
> >> 
> >> catching up on reviews today ...
> >> 
> >> 
> >> 
> >> 
> >> 
> >> On Mon, Feb 13, 2023 at 2:00 PM Alvaro Retana [e-mail]
> >> wrote:
> >> 
> >> Hi!
> >> 
> >> 
> >> 
> >> This message covers §4.2.3 to the end of §4.2.3.2.
> >> 
> >> 
> >> 
> >> Alvaro.
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 2207    4.2.3.  Topology Exchange (TIE Exchange)
> >> 
> >> 
> >> 
> >> 2209    4.2.3.1.  Topology Information Elements
> >> 
> >> ...
> >> 
> >> 2214       The TIE exchange mechanism uses the port indicated by each
> >> node in
> >> 
> >> 2215       the LIE exchange as `flood_port` in `LIEPacket` and the
> >> interface on
> >> 
> >> 2216       which the adjacency has been formed as destination.  TIEs MUST
> >> be
> >> 
> >> 2217       sent with an IPv4 Time to Live (TTL) or an IPv6 Hop Limit (HL)
> >> of
> >> 
> >> 2218       either 1 or 255 and also MUST be ignored if received with
> >> values
> >> 
> >> 2219       different than 1 or 255.  This prevents RIFT information from
> >> 
> >> 2220       reaching beyond a single L3 next-hop in the topology.  TIEs
> >> SHOULD be
> >> 
> >> 2221       sent with network control precedence unless an implementation
> >> is
> >> 
> >> 2222       prevented from doing so [RFC2474].
> >> 
> >> 
> >> 
> >> [major] "This prevents RIFT information from reaching beyond a single
> >> 
> >> L3 next-hop in the topology." 
> >> 
> >> 
> >> 
> >> This is not completely true for TTL = 1.  It is true that the TIE
> >> 
> >> cannot be forwarded beyond the local subnet.  But it is not true that
> >> 
> >> a TIE cannot be forwarded *into* the local subnet.  This is one of
> >> the
> >> 
> >> attack vectors that are left open -- these are the same concerns as
> >> 
> >> with the LIEs.
> >> 
> >> 
> >> 
> >> ? RIFT works on p2p links which are always an L3 next hop. Hence
> >> 
> >> the subnet is 2 routers only (be it v4, v6 or v6 LLC)
> >> 
> >> 
> >> 
> >>     jhead>> I had mentioned that we added references, but Tony
> >> pointed out the obvious in that this doesn't apply as links are P2P
> >> only. I pulled those back out.
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 2224       TIEs contain sequence numbers, lifetimes and a type.  Each
> >> type has
> >> 
> >> 2225       ample identifying number space and information is spread across
> >> 
> >> 2226       possibly many TIEs of a certain type by the means of a hash
> >> function
> >> 
> >> 2227       that an implementation can individually determine.  One extreme
> >> 
> >> 2228       design choice is a prefix per TIE which leads to more BGP-like
> >> 
> >> 2229       behavior where small increments are only advertised on route
> >> changes
> >> 
> >> 2230       vs. deploying with dense prefix packing into few TIEs leading
> >> to more
> >> 
> >> 2231       traditional IGP trade-off with fewer TIEs.  An implementation
> >> may
> >> 
> >> 2232       even rehash prefix to TIE mapping at any time at the cost of
> >> 
> >> 2233       significant amount of re-advertisements of TIEs.
> >> 
> >> 
> >> 
> >> [major] "TIEs contain sequence numbers, lifetimes and a type." 
> >> 
> >> 
> >> 
> >> There is one TIE, but multiple types of TIEElements, right?  And each
> >> 
> >> TIE carries only one TIEElement at a time, right?
> >> 
> >> 
> >> 
> >> If so, then "information is spread across possibly many TIEs of a
> >> 
> >> certain type" should say "across multiple TIEElements", or maybe
> >> 
> >> "across multiple TIEs with the same TIEElement type", or something
> >> 
> >> like that.
> >> 
> >> 
> >> 
> >> ok, I like your last suggestion
> >> 
> >> 
> >> 
> >>     jhead>> Fixed using your last suggestion.
> >> 
> >> 
> >> 
> >> 
> >> 
> >> [major] "...information is spread across possibly many TIEs of a
> >> 
> >> certain type by the means of a hash function that an implementation
> >> 
> >> can individually determine." 
> >> 
> >> 
> >> 
> >> Does the receiver need to know the hash function?  I'm hoping the
> >> answer is No.
> >> 
> >> 
> >> 
> >> answer is No. Each node is completely free to choose how it spreads
> >> the
> >> 
> >> info across TIEs of same type.
> >> 
> >> 
> >> 
> >> 
> >> 
> >> The rest of this paragraph only talks about prefixes.  Even if
> >> 
> >> possibly less common, I assume that the ability to spread information
> >> 
> >> applies to all TIEElement Types.  Is that true?  If so, please be
> >> 
> >> explicit -- and maybe keep the text about prefixes as an example.
> >> 
> >> 
> >> 
> >> RIFT being very symmetrical this applies to _all_ tie types. we can
> >> mention that, giving more examples
> >> 
> >> I think is counter productive.
> >> 
> >> 
> >> 
> >>     jhead>> Added that this applies to ALL TIEElement types, but we
> >> removed the prefix example.
> >> 
> >> 
> >> 
> >> 
> >> 
> >> [major] Please remove comparisons or references to other protocols:
> >> 
> >> "BGP-like behavior...traditional IGP".
> >> 
> >> 
> >> 
> >> ack
> >> 
> >> 
> >> 
> >>     jhead>> Already fixed as per previous comments.
> >> 
> >> 
> >> 
> >> 
> >> 
> >> ...
> >> 
> >> 2238    4.2.3.2.  Southbound and Northbound TIE Representation
> >> 
> >> ...
> >> 
> >> 2248       The North TIEs hold all of the node's adjacencies and local
> >> prefixes
> >> 
> >> 2249       while the South TIEs hold only all of the node's adjacencies,
> >> the
> >> 
> >> 2250       default prefix with necessary disaggregated prefixes and local
> >> 
> >> 2251       prefixes.  Section 4.2.5 explains further details.
> >> 
> >> 
> >> 
> >> [minor] I know I should go look at §4.2.5, but the description of
> >> 
> >> doesn't seem correct:
> >> 
> >> 
> >> 
> >> "North TIEs hold all of the node's adjacencies and local prefixes" 
> >> 
> >> 
> >> 
> >> "South TIEs hold only" -- "only" seems to indicate less information
> >> --
> >> 
> >> "all of the node's adjacencies, the default prefix with necessary
> >> 
> >> disaggregated prefixes and local prefixes".   So the South TIEs have
> >> 
> >> more information.
> >> 
> >> 
> >> 
> >> Maybe it's a matter of eliminating "only".
> >> 
> >> 
> >> 
> >> Yes, south ties hold less information. The text is correct. North
> >> TIEs are
> >> 
> >> really a full link state database of the node (since we have north
> >> flooding)
> >> 
> >> while south is a "compressed" view with mostly just default prefix
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 2253       The TIE types are mostly symmetric in both directions and
> >> Table 3
> >> 
> >> 2254       provides a quick reference to main TIE types including
> >> direction and
> >> 
> >> 2255       their function.  The direction itself is carried in
> >> `direction` of
> >> 
> >> 2256       `TIEID` schema element.
> >> 
> >> 
> >> 
> >> [major] The TIE types (the table says "TIE-Types", please be
> >> 
> >> consistent) in the table are not the same as the types defined in the
> >> 
> >> schema:
> >> 
> >> 
> >> 
> >> ok, let's remove the table and refer to schema only
> >> 
> >> 
> >> 
> >>     jhead>> The "TIE-Types" table has been removed and we now refer
> >> to the schema.
> >> 
> >> 
> >> 
> >> 
> >> 
> >> /** Type of TIE.
> >> 
> >> */
> >> 
> >> enum TIETypeType {
> >> 
> >>     Illegal                                     = 0,
> >> 
> >>     TIETypeMinValue                             = 1,
> >> 
> >>     /** first legal value */
> >> 
> >>     NodeTIEType                                 = 2,
> >> 
> >>     PrefixTIEType                               = 3,
> >> 
> >>     PositiveDisaggregationPrefixTIEType         = 4,
> >> 
> >>     NegativeDisaggregationPrefixTIEType         = 5,
> >> 
> >>     PGPrefixTIEType                             = 6,
> >> 
> >>     KeyValueTIEType                             = 7,
> >> 
> >>     ExternalPrefixTIEType                       = 8,
> >> 
> >>     PositiveExternalDisaggregationPrefixTIEType = 9,
> >> 
> >>     TIETypeMaxValue                             = 10,
> >> 
> >> }
> >> 
> >> 
> >> 
> >> See my comment above about differentiating between the types of TIEs
> >> 
> >> (shown in the table) and the types of TIEElements (defined in the
> >> 
> >> schema).  As is, the terminology is confusing because TIE types seem
> >> 
> >> to have two different meanings. (The last sentence in this section
> >> 
> >> also uses the same confusing terminology.)
> >> 
> >> 
> >> 
> >> A simplistic interpretation indicates that a TIE type is the same as
> >> 
> >> the corresponding TIEElement type, but with a direction.
> >> 
> >> 
> >> 
> >> yes, that's one way to see it, a TIE has a type and the type forces
> >> the according
> >> 
> >> schema element
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 2258
> >> +=========================+=================================+
> >> 
> >> 2259           | TIE-Type                |
> >> Content                         |
> >> 
> >> 2260
> >> +=========================+=================================+
> >> 
> >> 2261           | Node North TIE          | node properties and
> >> adjacencies |
> >> 
> >> 2262
> >>         +-------------------------+---------------------------------+
> >> 
> >> 2263           | Node South TIE          | same content as node North
> >> TIE  |
> >> 
> >> 2264
> >> +-------------------------+---------------------------------+
> >> 
> >> 2265           | Prefix North TIE        | contains nodes' 
> >> directly        |
> >> 
> >> 2266           |                         | reachable
> >> prefixes              |
> >> 
> >> 2267
> >> +-------------------------+---------------------------------+
> >> 
> >> 
> >> 
> >> [nit] s/nodes'/node's
> >> 
> >> 
> >> 
> >>     jhead>> Table removed.
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 2268           | Prefix South TIE        | contains originated
> >> defaults    |
> >> 
> >> 2269           |                         | and directly reachable
> >> prefixes |
> >> 
> >> 2270
> >> +-------------------------+---------------------------------+
> >> 
> >> 
> >> 
> >> [minor] "directly reachable prefixes" 
> >> 
> >> 
> >> 
> >> The text above, and a definition in the schema, use "local prefixes" 
> >> 
> >> instead.  Please be consistent.
> >> 
> >> 
> >> 
> >> ok, yes, let's align the terminology to the schema
> >> 
> >> 
> >> 
> >>     jhead>> Table removed.
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 2271           | Positive Disaggregation | contains disaggregated
> >> prefixes |
> >> 
> >> 2272           | South TIE
> >> |                                 |
> >> 
> >> 2273
> >> +-------------------------+---------------------------------+
> >> 
> >> 2274           | Negative Disaggregation | contains special,
> >> negatively    |
> >> 
> >> 2275           | South TIE               | disaggregated prefixes
> >> to       |
> >> 
> >> 2276           |                         | support multi-plane
> >> designs     |
> >> 
> >> 2277
> >> +-------------------------+---------------------------------+
> >> 
> >> 2278           | External Prefix North   | contains external
> >> prefixes      |
> >> 
> >> 2279           | TIE
> >> |                                 |
> >> 
> >> 2280
> >> +-------------------------+---------------------------------+
> >> 
> >> 2281           | Key-Value North TIE     | contains nodes northbound
> >> KVs   |
> >> 
> >> 2282
> >> +-------------------------+---------------------------------+
> >> 
> >> 2283           | Key-Value South TIE     | contains nodes southbound
> >> KVs   |
> >> 
> >> 2284
> >> +-------------------------+---------------------------------+
> >> 
> >> 
> >> 
> >> 2286                                 Table 3: TIE Types
> >> 
> >> 
> >> 
> >> [major] The table doesn't include all the TIEElement types + direction.
> >> 
> >> 
> >> 
> >> as I said, let's remove it and refer to schema only to prevent copies
> >> 
> >> 
> >> 
> >>     jhead>> Table removed.
> >> 
> >> 
> >> 
> >> 2288       As an example illustrating a databases holding both
> >> representations,
> >> 
> >> 2289       the topology in Figure 2 with the optional link between spine
> >> 111 and
> >> 
> >> 2290       spine 112 (so that the flooding on an East-West link can be
> >> shown) is
> >> 
> >> 2291       considered.  Unnumbered interfaces are implicitly assumed and
> >> for
> >> 
> >> 2292       simplicity, the key value elements which may be included in
> >> their
> >> 
> >> 2293       South TIEs or North TIEs are not shown.  First, in Figure 15
> >> are the
> >> 
> >> 2294       TIEs generated by some nodes.
> >> 
> >> 
> >> 
> >> 2296              ToF 21 South TIEs:
> >> 
> >> 2297              Node South TIE:
> >> 
> >> 2298                NodeElement(level=2, neighbors((Spine 111, level 1,
> >> cost 1),
> >> 
> >> 2299                (Spine 112, level 1, cost 1), (Spine 121, level 1,
> >> cost 1),
> >> 
> >> 2300                (Spine 122, level 1, cost 1)))
> >> 
> >> 2301              Prefix South TIE:
> >> 
> >> 2302                SouthPrefixesElement(prefixes(0/0, cost 1), (::/0,
> >> cost 1))
> >> 
> >> 
> >> 
> >> [major] s/NodeElement/NodeTIEElement/g
> >> 
> >> In order to match the schema.
> >> 
> >> 
> >> 
> >> ok
> >> 
> >> 
> >> 
> >>     jhead>> Fixed.
> >> 
> >> 
> >> 
> >> [major] s/SouthPrefixesElement/PrefixTIEElement/g
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> 
> >> [major] For the prefixes, "cost" is used.  However, the schema uses
> >> 
> >> "metric" in the PrefixAttributes structure:
> >> 
> >> 
> >> 
> >> ok, yeah, can do.
> >> 
> >> 
> >> 
> >>     jhead>> Fixed all instances of SouthPrefixesElement and
> >> NorthPrefixesElement.
> >> 
> >> 
> >> 
> >> 
> >> 
> >> /** Distance of the prefix. */
> >> 
> >> 2: required common.MetricType            metric
> >> 
> >>         = common.default_distance;
> >> 
> >> 
> >> 
> >> Note that NodeNeighborsTIEElement uses different language to refer to
> >> 
> >> the same thing:
> >> 
> >> 
> >> 
> >> /**  Cost to neighbor. Ignore anything larger than
> >> `infinite_distance`
> >> 
> >> and `invalid_distance` */
> >> 
> >> 3: optional common.MetricType               cost
> >> 
> >>             = common.default_distance;
> >> 
> >> 
> >> 
> >> 
> >> 
> >> The terminology section defines cost, but not metric.  Please be
> >> consistent.
> >> 
> >> 
> >> 
> >> The definitions are:
> >> 
> >> 
> >> 
> >>    Cost:  The term signifies the weighted distance between two
> >> neighbors