Subject: [manet] Flooding via MPRs

From: Richard <[email-masked]>
Date: Tue, 03 Sep 2002 08:43:20 -0700

All,

I would like to suggest some ideas for possible inclusion
in the MPRF (Flooding via Multipoint Relays) draft that
Charlie Perkins presented at the Japan meeting, and hopefully
to stimulate some discussion.
For reference, here is a link to the MPRF presentation:
http://www.ietf.org/proceedings/02jul/slides/manet-1/sld001.htm

I have exchanged some emails with Charlie regarding these ideas,
and he agreed with me that it would be a good idea to post my
suggestions to the manet list.

First, I want to point out that Charlie and I are using a more
general definition for MPR than the one given in the OLSR draft.
In particular, the OLSR draft defines an MPR as "a node which is 
selected by its one-hop neighbor...", whereas the more general
definition allows an MPR to select itself, either with respect 
to one or more neighbors called "MPR sources" (instead of 
"MPR selectors") or independent of the source (in which case the 
decision to forward a flooded packet is independent of the neighbor 
from which the packet was received).  

Under this more general definition, the "parents" of TBRPF 
(which select themselves) can now be called MPRs.
Thus, OLSR and TBRPF both select MPRs, but in different ways.
I think this simplifies the discussion (instead of saying
that "parents" are analogous to MPRs).

The rule for forwarding a flooded packet based on MPRs is as follows: 
a non-duplicate flooded packet with nonzero TTL is forwarded if the 
router is an MPR w.r.t. the neighbor from which the packet was received 
(previous hop), or (when the previous hop is not known) if the router 
is a source-independent MPR.  
The previous hop can be known if layer-2 addresses are accessible, 
or if the packet is tunneled/encapsulated at each hop.  

Knowing the previous hop is likely to make the flooding more efficient
(since fewer nodes will forward each packet), which might justify
the additional overhead of tunneling.

To provide some more background, I will quote some excerpts from
Charlie's emails to me (with his permission):

Charles Perkins wrote:

> Right. The decision _could_ be based on options depending on
> accessibility of layer-2 addresses, and _should_ be smoothly
> selectable so that the same algorithm works whether or not the
> decision is source dependent.

...

> I guess that the point of doing an MPR draft is that
> there needs to be a way of finding MPRs.  It does not
> mean that every ad-hoc networking protocol has to be
> able to follow that particular algorithm/protocol, but
> I think that the MPR draft should be ABLE to be
> applied to the four protocols of current interest.

> It looks like a sure bet that MPRF won't resemble
> very closely what's in OLSR, for a variety of reasons
> mainly centering around my demand for maximal simplicity.
> Whether the result is "closer" to OLSR or TBRPF depends
> on the typical array of considerations, including your
> own suggestions, whatever ideas we can come up with,
> working group consensus, and pure luck.

> I'm still puzzling over whether a node should tell its
> neighbors whether it wants them to be MPRs, or instead
> whether every node should decide for itself whether it
> wants to be an MPR.  The latter, of course, immediately
> solves the tunneling problem.  I like it.  When I get
> past my current backlog of things to do yesterday, I'll
> try to figure it out the rest of the way.

The TBRPF method in which nodes select themselves as MPRs
is one possible solution to this problem.  Although the method
is source-dependent, it is easily modified to be source-independent
(see below). 

We are not claiming any IPR for this technique: we have not submitted
a patent application and do not plan to.  (In fact, due to recent
developments, IPR is not likely to be an issue for TBRPF in general,
but this is another topic.)

The TBRPF method is as follows: Based on 2-hop information, each
node computes the min-hop path (up to 2 hops) from each neighbor
to each other neighbor, using min node ID as a tie breaker.
If the 2nd node of any such path is the node itself, then the node 
selects itself as MPR for the neighbor that is the 3rd (last) node 
of the 2-hop path.  A node selects itself as a *source-independent*
MPR if it has selected itself as an MPR for *any* neighbor.

Note that using min node ID reduces the number of MPRs.
Of course, hysteresis can be used so that only high quality
neighbors are considered.

This method has the following advantages:

  - Avoids overhead for sending messages to update MPRs.
  - Faster response to failures since MPRs select themselves
    without having to wait for neighbors to select them.
  - Both source-dependent and source-independent MPRs are selected,
    and using node ID is a good way to reduce the number of
    source-independent MPRs.

That's all for now.

Regards,
Richard

P.S. The source-independent version of the method described above
is similar (but not equivalent) to the distributed algorithm
in the following paper for finding a connected dominating set:

Jie Wu, Hailan Li: A Dominating-Set-Based Routing Scheme in Ad Hoc 
Wireless Networks. Telecommunication Systems 18(1-3): 13-36 (2001)

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Tao Lin" <[email-masked]>
Date: Tue, 3 Sep 2002 15:02:41 -0400

The ideas in our paper include but are not limited to the one in your email.
We also did the simulations similar to what you mentioned (OLSR vs. TBRPF),
the results of which will appear in the next paper currently in preparation.
We will send you a copy when we are able to disseminate itb.

Thanks for your interest,

 Tao

----- Original Message -----
From: <[email-masked]>
To: "Tao Lin" <[email-masked]>
Cc: "Richard" <[email-masked]>; <[email-masked]>; <[email-masked]>;
<[email-masked]>
Sent: Tuesday, September 03, 2002 1:49 PM
Subject: Re: [manet] Flooding via MPRs

>
> > Richard,
> >
> > Our research group already worked on this topic. A paper regarding this
idea
> > is submitted recently. Once it is accepted I will give a reference link
to
> > it. Hope it can bring more ideas to MANET group.
> >
> > Thanks,
> >
> >  Tao
> >
>
> Tao,
>
> Are you computing MPRs similarly to the method I described
> (similar to TBRPF)?  Except for the extension involving
> source-independent MPRs, the idea has already appeared
> in the TBRPF drafts for some time (via the selection of
> "parents" and the use of this information for flooding), so I
> don't see how it can be published as a new idea, unless you have
> some variation not included in the TBRPF draft.
> If you have simulation results (e.g., comparing the performance
> of TBRPF flooding to OLSR flooding) then I would be very interested
> to see them, since I was planning to conduct my own simulations.
>
> Regards,
> Richard
>
>
> >
> > ----- Original Message -----
> > From: "Richard" <[email-masked]>
> > To: <[email-masked]>
> > Cc: <[email-masked]>; <[email-masked]>
> > Sent: Tuesday, September 03, 2002 11:43 AM
> > Subject: [manet] Flooding via MPRs
> >
> >
> > >
> > > All,
> > >