Subject: [manet] Multipath routing

From: Carlos Calafate <[email-masked]>
Date: Thu, 27 Mar 2003 10:37:37 +0100 (CET)

Hi,

Can anyone tell me where I can find implementations of multipath routing
protocols for NS-2?

Regards,

_________________________________________________
Carlos Miguel Tavares de Araújo Cesariny Calafate
Universidad Politécnica de Valencia
e-mail: [email-masked]
http://reptar.grc.upv.es/~calafate/
_________________________________________________
\"In an open world without walls and fences who 
needs Windows and Gates?\"
_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: Joe Macker <[email-masked]>
Date: Thu, 27 Mar 2003 11:03:06 -0500

>Can anyone tell me where I can find implementations of multipath routing

We have an NRL version of an OLSR derivative (CVS repository) with lots of experimental options at http://pf.itd.nrl.navy.mil.  If compiled for ns2 this code has disjoint path routing/load balancing and other purely EXPERIMENTAL capabilities. While this code also compiles for Linux, the multipath routing option will only work within the simulator code.

-joe

---

From: [email-masked]
Date: Thu, 27 Mar 2003 09:16:54 -0800

One caution in using multipath routing with OLSR.
If you want two node-disjoint paths, for example, 
then the MPR Redundancy parameter needs to be 2,
since using non-redundant MPRs does not ensure that
disjoint paths will be found even if they exist.

>From the OLSR draft: "Redundancy of the MPR set affects the overhead 
through affecting the amount of links being advertised, the amount of 
nodes advertising links to the MPR selector and the efficiency of the 
MPR flooding mechanism."

The result is that increasing the MPR redundancy to 2 will
roughly increase the TC overhead by a factor of 4.
This is unnecessary - a factor of 2 is quite possible.

Some may argue that the factor of 4 buys more robustness,
but I have not seen any simulation results showing this,
and I doubt that it improves robustness sufficiently to
justify the large overhead.

Richard

> We have an NRL version of an OLSR derivative (CVS repository) with lots of ex
perimental options at http://pf.itd.nrl.navy.mil.  If compiled for ns2 this cod
e has disjoint path routing/load balancing and other purely EXPERIMENTAL capabi
lities. While this code also compiles for Linux, the multipath routing option w
ill only work within the simulator code.

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 27 Mar 2003 19:49:51 +0100

Hello,

I think multipath routing is a priori a problem of routing table: one must
have two entries in the routing table for the same destination. This is not
easy to handle in hop by hop routing. Maybe source routing option  in IP
stack would help. In order to have load balancing the routes should probably
be two hops or three hops away in order to avoid co-interference.

Regarding OLSR I don't think MPR coverage is an issue here since MPR
coverage addresses only flooding reliability. In OLSR one can advertize more
links than the MPR links. In fact nodes can advertize their whole link set
and simulations don't show tremendous more overhead (TC still benefit from
MPR forwarding). With knowledge of the whole link state in the network, one
can compute all possible redundant routes if one wishes so.

Philippe

---

From: Joe Macker <[email-masked]>
Date: Thu, 27 Mar 2003 14:57:35 -0500

>disjoint paths will be found even if they exist.

I should have added, this was ONLY done with a full link state advertisement option, but with minimal MPR control flooding. Many of these experimental features are also not related to the OLSR specification or the MPR robustness factor (it was just done to support more generic work by Justin Dean and myself). It borrows OLSR packet formats..

So MPR election has nothing to do with routing path selection,etc...in our non-spec case...
Also, I should have mentioned the load balancing results using full link state we obtained under congestion tests showed improvements, but not significant (somewhat scenario dependent).  We wouldn't recommend necessarily doing this function because the complexity did not seem to be worth it.. The full link state option, however, did improve route repair performance when a link layer detection mechanism was used..yes, there are more TCs generated and results are likely scenario dependent to some degree.  Just answering the question if there was an implementation and I wouldn't want that to be misinterpreted as a general recommendation.

---

From: [email-masked]
Date: Thu, 27 Mar 2003 14:24:14 -0800

Yes, advertising more links than the MPR links is more efficient
than using redundant MPRs.  But instead of advertising the 
full topology, it would be nice to allow advertising less 
than the full topology, e.g., a biconnected topology,
that would still allow computation of 2 disjoint paths to
each destination.  This could result in significantly less
overhead in very dense networks and in implementations that 
use smaller packet headers (so that the size of the TC message
becomes more significant).
I wonder why OLSR does not provide such an option.

Also, I wonder if there may be a problem with forwarding a packet
to a neighbor that is not an MPR of the following hop, i.e.,
such that the second link of the path is not an MPR link.
The potential problem is that the non-MPR neighbor might not even
know that the path exists (yet), since the neighbor would not
report the path. And if a link on the path fails, the non-MPR 
neighbor would not report the failure.  

Richard

---

From: Thomas Heide Clausen <[email-masked]>
Date: Fri, 28 Mar 2003 00:49:17 +0100

> I wonder why OLSR does not provide such an option.

The OLSR draft specifies, in the very beginning, that:

" Indeed, the only
  requirement for OLSR to provide routes to all destinations is that
  MPR nodes declare link-state information for links between them
  self and their MPR selectors. Additional available link-state
  information may be utilized, e.g. for redundancy."

I.e. the specifications gives a minimum requirement for correct
operation. Additional information may, under specific conditions, be
of advantage and is indeed permitted. Doesn't this address exactly
what you mention?

--thomas

---

From: [email-masked]
Date: Thu, 27 Mar 2003 16:10:59 -0800

> of advantage and is indeed permitted. Doesn't this address exactly

Not really. That informal statement from the Introduction only says that
additional link-state information may be "utilized".
But Section 11.1 (quoted below) is very specific about what redundant 
information may be included in TC messages.  Maybe you would like to
change "the amount of information that is included in the TC messages" to 
"the minimum information that must be included in the TC messages."

Richard

11.1.  TC_REDUNDANCY Parameter

   The parameter TC_REDUNDANCY specifies, for the local node, the amount
   of information that is included in the TC messages. The parameter is
   interpreted as follows:

   -  if the TC_REDUNDANCY parameter of the node is 0, then its
      advertised link set is limited to the MPR selector set (as
      described in section 4

   -  if the TC_REDUNDANCY parameter of the node is 1, then its
      advertised set is the union of its MPR set and its MPR selec-
      tor set,

   -  if the TC_REDUNDANCY parameter of the node is 2, then its
      advertised set is neighbor set (full link-state information is
      diffused).

   A node with willingness equal to zero SHOULD have TC_REDUNDANCY also
   equal to zero.

---

From: Thomas Heide Clausen <[email-masked]>
Date: Fri, 28 Mar 2003 01:37:13 +0100

On Thu, 27 Mar 2003 16:10:59 -0800
[email-masked] wrote:

> > > Yes, advertising more links than the MPR links is more
> > > efficient than using redundant MPRs.  But instead of
> > > advertising the full topology, it would be nice to allow
> > > advertising less than the full topology, e.g., a biconnected
> > > topology, that would still allow computation of 2 disjoint
> > > paths to each destination.  This could result in significantly
> > > less overhead in very dense networks and in implementations
> > > that use smaller packet headers (so that the size of the TC
> > > message becomes more significant).
> >   requirement for OLSR to provide routes to all destinations is
> >   that MPR nodes declare link-state information for links between
> >   them self and their MPR selectors. Additional available
> >   link-state information may be utilized, e.g. for redundancy."
> > 
> > operation. Additional information may, under specific conditions,
> > be of advantage and is indeed permitted. Doesn't this address
> > exactly what you mention?
> 
> Not really. That informal statement from the Introduction only says
> that additional link-state information may be "utilized".
> But Section 11.1 (quoted below) is very specific about what
> redundant information may be included in TC messages.  Maybe you
> would like to change "the amount of information that is included in
> the TC messages" to "the minimum information that must be included
> in the TC messages."

Not well that section 5 (Topology Discovery) states that:

"Routes are constructed through advertised links and links with
 neighbors. A node must at least disseminate links between itself and
 the nodes in its MPR-selector set, in order to provide sufficient
 information to enable routing."

This is not an informal statement, rather a firm requirement. Also,
later in 5.3:

"A TC message is sent by a node in the network to declare a set of
 links, called advertised link set which MUST include at least the
 links to all nodes of its MPR Selector set, i.e., the neighbors
 which have selected the sender node as a MPR. If, for some reason,
 it is required to distribute redundant TC information, refer to
 section 11."

I.e. section 11 is a proposed way of diffusing additional/redundant
TC-information. However any way you can concieve of, which satisfies
section 5 (that a node at least disseminates links between itself and
the MPR selector set), is permitted. I.e. section 5 specifies the
"musts" which are required for interoperability.

Notice that one of the options proposed in section 11 is, exactly,
what Joe implemented: diffusing full link-state, but profiting from
the MPR optimized flooding. Notice also, that you may come up with a
different set of links to diffuse, as long as you at least diffuse
the MPR selector set of each node.

--thomas

---

From: [email-masked]
Date: Thu, 27 Mar 2003 17:18:29 -0800

> This is not an informal statement, rather a firm requirement. Also,

The statement "A node must at least disseminate.." does not 
describe or imply how much *additional* information can be disseminated.
That is the purpose of Section 11.

You would have to say something like "any additional information may
be included".  But even if you did, Section 11 is very specific
about what additional information can be included, and would 
contradict such a statement.

>  it is required to distribute redundant TC information, refer to

I interpret this to mean that if you want to send redundant TC information, 
you must do so as specified in Section 11.  And as I said, Section 11 is 
very specific about what redundant information can be included in TC messages,
and allows only three options:

-   if the TC_REDUNDANCY parameter of the node is 0, then its
    advertised link set is limited to the MPR selector set (as
    described in section 4.6.2),

The first option actually says that the advertised link set is *limited*
to the MPR selector set. 

What value for TC_REDUNDANCY should I use if I want to report 
more than the MPR selector set, but less than the full topology
(e.g., a biconnected subgraph)? 
According to Section 11, it can't be 0, 1, or 2.

Richard

---

From: Thomas Heide Clausen <[email-masked]>
Date: Fri, 28 Mar 2003 03:02:54 +0100

On Thu, 27 Mar 2003 17:18:29 -0800
[email-masked] wrote:

> > > > > advertising less than the full topology, e.g., a
> > > > > biconnected topology, that would still allow computation of
> > > > > 2 disjoint paths to each destination.  This could result in
> > > > > significantly less overhead in very dense networks and in
> > > > > implementations that use smaller packet headers (so that
> > > > > the size of the TC message becomes more significant).
> > > >   requirement for OLSR to provide routes to all destinations
> > > >   is that MPR nodes declare link-state information for links
> > > >   between them self and their MPR selectors. Additional
> > > >   available link-state information may be utilized, e.g. for
> > > >   redundancy."
> > > > 
> > > > I.e. the specifications gives a minimum requirement for
> > > > correct operation. Additional information may, under specific
> > > > conditions, be of advantage and is indeed permitted. Doesn't
> > > > this address exactly what you mention?
> > > 
> > > Not really. That informal statement from the Introduction only
> > > says that additional link-state information may be "utilized".
> > > redundant information may be included in TC messages.  Maybe
> > > you would like to change "the amount of information that is
> > > included in the TC messages" to "the minimum information that
> > > must be included in the TC messages."
> > 
> >  neighbors. A node must at least disseminate links between itself
> >  and the nodes in its MPR-selector set, in order to provide
> >  sufficient information to enable routing."
> > 
> describe or imply how much *additional* information can be
> disseminated. That is the purpose of Section 11.

Actually, section 11 describes only the interpretation of the
TC_REDUNDANCY parameter. It does *not* modify the basic requirement
from section 5, namely that "A node must at least disseminate links
between itself and the nodes in its MPR-selector set, in order to
provide sufficient information to enable routing."

It is very much the intention of the spec. to give the minimal
required for interoperability (which is exactly that the MPR selector
set by dissiminated) while allowing for flexibility where needed.

> 
> You would have to say something like "any additional information
> may be included".  But even if you did, Section 11 is very specific

No. Section 11 specifies the interpretation of the TC_REDUNDANCY
parameter. Including additional information (again, respecting the
requirements of section 5) does not yield a contradiction.

> >  links, called advertised link set which MUST include at least
> >  the links to all nodes of its MPR Selector set, i.e., the
> >  neighbors which have selected the sender node as a MPR. If, for
> >  some reason, it is required to distribute redundant TC
> >  information, refer to section 11."
> 
> I interpret this to mean that if you want to send redundant TC
> information, you must do so as specified in Section 11.  And as I
> said, Section 11 is very specific about what redundant information
> can be included in TC messages, and allows only three options:

Section 11 is specific about the interpretation of the TC_REDUNDANCY
parameter only, supplementing section 5. It does not place any
further restrictions on section 5 which, to repeat myself, states
that "A node must at least disseminate links between itself and the
nodes in its MPR-selector set, in order to provide sufficient
information to enable routing."

> The first option actually says that the advertised link set is
> *limited* to the MPR selector set. 

Yes, *IF* the TC_REDUNDANCY parameter is employed.

> According to Section 11, it can't be 0, 1, or 2.

Well, if you want to advertise additional topological information,
then as long as you respect the requirements from section 5, namely
that "A node must at least disseminate links between itself and the
nodes in its MPR-selector set, in order to provide sufficient
information to enable routing", you are not conflicting the spec
atall. 

You will, basically, not need to be concerned with section 11, unless
you specifically need/want the features provided herein. This was
precisely the idea of seperating those issues (section 8-12): to only
engage these sections when the features they provide are explicitly
needed/wanted.

Anyways, I think that your issue basically is, that you read section
11 as "overriding" section 5, not "supplementing" section 5, correct?
Notice that section 11 does not include any "must", rather it uses
"can".  I'd be happy to change the "can" to a "may", if you think
that will be clearer? In either case, the interpretation is the same.

--thomas

> Richard
> 
> 
> > I.e. section 11 is a proposed way of diffusing
> > additional/redundant TC-information. However any way you can
> > concieve of, which satisfies section 5 (that a node at least
> > disseminates links between itself and the MPR selector set), is
> > permitted. I.e. section 5 specifies the"musts" which are required
> > for interoperability.
> > 
> > Notice that one of the options proposed in section 11 is,
> > exactly, what Joe implemented: diffusing full link-state, but
> > profiting from the MPR optimized flooding. Notice also, that you
> > may come up with a different set of links to diffuse, as long as
> > you at least diffuse the MPR selector set of each node.
> > 
> > --thomas
> 

-- 

-------------------------------------------
  Thomas Heide Clausen
  Civilingeniør i Datateknik (cand.polyt)
  M.Sc in Computer Engineering

  E-Mail: [email-masked]
  WWW:    http://www.cs.auc.dk/~voop
-------------------------------------------
_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: [email-masked]
Date: Thu, 27 Mar 2003 23:15:20 -0800

> Yes, *IF* the TC_REDUNDANCY parameter is employed.

Where does it say that the TC_REDUNDANCY parameter is optional?
A parameter is a parameter and must have a value.

> that will be clearer? In either case, the interpretation is the same.

No, that won't help.  First of all, it is not clear that the
TC_REDUNDANCY parameter is optional.

Section 5 specifies the minimum information that must be included 
in TC messages.  That leads me to ask "what else can be included?".
Section 11 says what else can (or may) be included.
I don't want to assume that I can include anything
in TC messages unless it says what else MAY be included.
For example, MAY I include garbage or non-adjacent links?
Also, it is natural to assume that if you want to 
advertise redundant infomation, then Section 11 applies,
since it is entitled "Distributing Redundant Topology
Information". 

That's all I have to say.  I'll leave it to you and others
to decide whether any changes should be made.

Richard