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

[Jiazi YI <[e-mail]>]

Hi Philippe,

I'm not sure what "expectations" you meant here. In the assumption of the
default algorithm, the expectations are:
   - Get disjoint paths with reasonable costs
   - Less variance between different paths are expected. For example, if we
have topology like

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

Then we would rather having one path than two paths.

In fact, sometimes a *best* path is desired if we want to send the most
important information through the best path. For example, if we transfer
SVC (scalable video coding) streams, in which the video is encoded into a
set of bitstreams with different priorities. The bitstream with highest
priority is sent through the best path (for basic quality), and the ones
with low priority are sent through inferior paths (for enhanced quality).
Meanwhile, we don't want to see too much cost difference in the paths.

In fact, the default algorithm doesn't claim to explore strict disjoint
paths. Maybe we didn't say it clear enough in the draft -- will clarify it
in the next revision.

It's normal that different scenarios have different expectations in the
paths obtained, that's why we didn't prohibit the use of other algorithms.

best

Jiazi


On Thu, May 28, 2015 at 2:57 PM, Philippe Jacquet <[e-mail]
> wrote:

> 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
> >
>