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

From: [email-masked]
Date: Mon, 25 May 2015 15:09:00 -0700

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/

---

From: Jiazi YI <[email-masked]>
Date: Tue, 26 May 2015 00:32:27 +0200

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, <[email-masked]> wrote:

>         Title           : Multi-path Extension for the Optimized Link
> State Routing Protocol version 2 (OLSRv2)
>         Authors         : Jiazi Yi
>                           Benoit Parrein
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet
>

---

From: Philippe Jacquet <[email-masked]>
Date: Wed, 27 May 2015 17:11:08 +0200 (CEST)

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. 

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. 

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

I hope this helps.

Philippe
----- Mail original -----
De: "Jiazi YI" <[email-masked]>
À: "manet" <[email-masked]>
Envoyé: Mardi 26 Mai 2015 00:32:27
Objet: Re: [manet] I-D Action: draft-ietf-manet-olsrv2-multipath-03.txt

Dear all,

regards

Jiazi

---

From: Jiazi YI <[email-masked]>
Date: Wed, 27 May 2015 23:05:02 +0200

Hi Philippe,

Thanks very much for the comments. Please check inline:

On Wed, May 27, 2015 at 5:11 PM, Philippe Jacquet <[email-masked]
> 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

---

From: Philippe Jacquet <[email-masked]>
Date: Thu, 28 May 2015 14:57:43 +0200 (CEST)

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" <[email-masked]>
À: "Philippe Jacquet" <[email-masked]>
Cc: "manet" <[email-masked]>
Envoyé: Mercredi 27 Mai 2015 23:05:02
Objet: Re: [manet] I-D Action: draft-ietf-manet-olsrv2-multipath-03.txt

Hi Philippe,

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

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

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

best

Jiazi

---

From: Jiazi YI <[email-masked]>
Date: Thu, 28 May 2015 16:35:55 +0200

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 <[email-masked]

> 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
> > >  This draft is a work item of the Mobile Ad-hoc Networks Working Group
> of
> > > the IETF.
> > >