Re: [manet] I-D Action: draft-ietf-manet-olsrv2-multipath-03.txt

[Philippe Jacquet <[e-mail]>]

Thanks Jiazi,

But it is one point that the existing pairs of disjoints paths do not fit someone expectations, and it is another point that the algorithm you propose does not fully achieve what it is claimed to do. I guess you should correct your default algorithm.  

Best,
Philippe
----- Mail original -----
De: "Jiazi YI" <[e-mail]>
À: "Philippe Jacquet" <[e-mail]>
Cc: "manet" <[e-mail]>
Envoyé: Mercredi 27 Mai 2015 23:05:02
Objet: Re: [manet] I-D Action: draft-ietf-manet-olsrv2-multipath-03.txt

Hi Philippe,

Thanks very much for the comments. Please check inline:


On Wed, May 27, 2015 at 5:11 PM, Philippe Jacquet <[e-mail]
> wrote:

> Hi Jiazi,
>
> I have looked at your multi path algorithm. It seems that you take as
> first path the shortest (default) path. I believe this may not work
> properly in some cases. For example in the scheme below
>          D
>         /|
>        H |
>        | C
>        G |\
>         \| F
>          B |
>          | E
>          |/
>          A
> The shortest path from A to D is the central path ABCD. If you remove it
> then your network is disconnected with A and D standing in different
> components, unreachable.
>

Based on the default multipath algorithm in the draft, with the given
topology, B and C won't not be "removed", but related links will be
punished. So the obtained path set would be something like (depending on
the cost function)

A-B-C-D  and A-E-F-C-D.

Of course, this is still not exactly the ideal pair ABGHD and AEFCD.
One of the reasons that we didn't require strict disjoint paths is (even
they can provide the shortest cost in total),  sometimes it is probably not
a good choice. For example, with the topology below:


  ---50 hops-------
   /                                     \
  /                                       \
S----B-------------D
      \           /
       \---C-----/

It's better to choose S-B-C-D and S-B-D, than S----50hops----D and S-B-D.
The latter would cause large delay variance between the paths, and make the
packet scheduling more complex.

So the general idea of the default algorithm is: if you can get disjoint
paths, do it. But if it's with too much cost, then you can make use of used
vertex. An extreme case is, it goes back to single path routing (for
example, if node C doesn't exist in the above example) --- but you didn't
loose anything (except additional overhead due to the source routing
header), compared to single path.



>
> The good pair of paths in the example above is ABGHD and AEFCD. The
> problem is finding the pair of disjoint paths with the shortest length sum
> and in most case it does not take the shortest path. There is the classic
> algorithm of Suurballe and Tarjan which is linear in the number of edges
> and it finds the shortest cycle to all remote destinations. If we look for
> the k-tuple of pairwise disjoint path with shortest path sum there are
> classic solutions based on easy linear programming.
>

Thanks for providing the pointer. As said in the draft, using different
algorithms won't impact interoperability, and the protocol doesn't prohibit
it. In fact, it's also an experimental point (illustrated in section 1.1,
experiments to be conducted).
I think we can provide a reference to the Suurballe's paper, as an example
of alternatives.


>
> Of course in order to have k disjoint paths we must have a network with a
> node connectivity degree larger than k, or at least we must have the source
> and destination in the same k-connected component. Another point, since
> OLSR is based on reduced topology information, one must care that the MPR
> set satisfies a k-coverage property (a two hope node which is covered by at
> least k neighbor, must be covered by k MPRs).
>

Yes, we are aware of the fact the OLSR uses reduced topology. But as I
said, the algorithm only tries its best to find the k *disjoint* paths. If
unfortunately, we have a topology like

A---B---C---D

Then we have k same paths -- but we didn't loose anything, and it won't
impact interoperability.


>
> I hope this helps.
>

Thanks again Philippe, it does help a lot !

best

Jiazi


>
> Philippe
> ----- Mail original -----
> De: "Jiazi YI" <[e-mail]>
> À: "manet" <[e-mail]>
> Envoyé: Mardi 26 Mai 2015 00:32:27
> Objet: Re: [manet] I-D Action: draft-ietf-manet-olsrv2-multipath-03.txt
>
> Dear all,
>
> As you might have seen, a new revision of olsrv2-multipath has been
> submitted. Sorry for the relatively delayed submission -- the birth of my
> new "boss" gave lots of extra work in the last two months.
>
> This revision mainly addresses previous comments from Justin (thanks very
> much!). Other than the editorial issues, the main changes include:
>
>    - Changing the MP_OLSRv2 TLV to SR_OLSRv2 TLV. Other than the name
> change, this also releases the requirement of joining the source-route
> header from MP-OLSR supported router, to source routing supported router.
>
>   - Making multi-path Dijkstra as a "default" algorithm for obtaining
> multiple paths. Other algorithms are allowed, as long as they fit the
> requirements defined in the document. It won't impact the interoperability.
>
>   - Providing references to RFC 6554 and RFC 5095, which describes the
> vulnerabilities of source routing.
>
> There is one thing that I'm not sure about for the moment: currently, we
> defined SR_OLSRv2 TLV as *Message-Type-specific Message TLV* for HELLO and
> TC messages separately, to identify the originators that supports source
> routing.
> I'm wondering, maybe it's better to define a *Message TLV* instead, as this
> feature (identifying source routing support) can be useful for other
> messages types also?
>
> regards
>
> Jiazi
>
>
>
> On Tue, May 26, 2015 at 12:09 AM, <[e-mail]> wrote:
>
> >
> > A New Internet-Draft is available from the on-line Internet-Drafts
> > directories.
> >  This draft is a work item of the Mobile Ad-hoc Networks Working Group of
> > the IETF.
> >
> >         Title           : Multi-path Extension for the Optimized Link
> > State Routing Protocol version 2 (OLSRv2)
> >         Authors         : Jiazi Yi
> >                           Benoit Parrein
> >         Filename        : draft-ietf-manet-olsrv2-multipath-03.txt
> >         Pages           : 19
> >         Date            : 2015-05-25
> >
> > Abstract:
> >    This document specifies a multi-path extension for the Optimized Link
> >    State Routing Protocol version 2 (OLSRv2) to discover multiple
> >    disjoint paths, so as to improve reliability of the OLSRv2 protocol.
> >    The interoperability with OLSRv2 is retained.
> >
> >
> > The IETF datatracker status page for this draft is:
> > https://datatracker.ietf.org/doc/draft-ietf-manet-olsrv2-multipath/
> >
> > There's also a htmlized version available at:
> > https://tools.ietf.org/html/draft-ietf-manet-olsrv2-multipath-03
> >
> > A diff from the previous version is available at:
> > https://www.ietf.org/rfcdiff?url2=draft-ietf-manet-olsrv2-multipath-03
> >
> >
> > Please note that it may take a couple of minutes from the time of
> > submission
> > until the htmlized version and diff are available at tools.ietf.org.
> >
> > Internet-Drafts are also available by anonymous FTP at:
> > ftp://ftp.ietf.org/internet-drafts/
> >
> > _______________________________________________
> > manet mailing list
> > [e-mail]
> > https://www.ietf.org/mailman/listinfo/manet
> >
>
> _______________________________________________
> manet mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/manet
>