Subject: Re: [manet] MPRF and "reliability" considerations

From: "Pete Sholander" <[email-masked]>
Date: Thu, 26 Feb 2004 09:50:21 -0500

Justin,

Good point in general.  Large amounts of user traffic can crowd out routing protocol messages.  

However, can't this be solved in deployed MANETs via network-layer and link-layer techniques that give routing-control traffic some level of priority?  Examples are DiffServ and IEEE 802.11p.  (Note: in my old age, I forget which letter was per-frame prioritization.  So, "p" may be wrong!?)  Did you try those techniques in GloMoSim?

--Pete Sholander
Atlanta, GA

>>> Justin Lipman <[email-masked]> 02/25/04 10:11PM >>>

Hi all,

I wonder if there has been some consideration as to the performance of 
optimised flooding mechanisms in the presence of background traffic. 

>From my own simulations results in Glomosim... MPR and other optimised 
flooding mechanisms performed very badly as increasing CBR background traffic 
was introduced, especially compared to Blind flooding. This makes their use 
very limited. 

The following is a paper on reliable optimised flooding that shows some 
results for MPR, LMST, Blind flooding vs a more reliable version of LMST that 
uses unicast packet transmission instead of broadcast packet transmission.

http://www.cse.unsw.edu.au/~justinl/rmst.pdf 

Kind regards,
Justin

-- 
Research Associate
Smart Internet Technology Cooperative Research Centre
http://www.titr.uow.edu.au/~justin 

On Thu, 26 Feb 2004 10:09 am, Richard Ogier wrote:
> Charlie,
>
> Suppose that each MPR is a guaranteed relay as you say:
> > Suppose that an MPR is taken as a "guaranteed"
> > relay for a flooded message.  By that, I mean the
> > node _will_ transmit a flooded message if that
> > flooded message is sent by its MPR selector.
>
> Then the nodes that relay the packet are the MPRs of the originator,
> the MPRs of the MPRs of the originator, etc.
>
> However, I don't think this set of nodes includes every node that
> is an MPR of some neighboring MPR (as in your
> modified step 5.2).   The difference is that there has to be
> a sequence of nodes u_1,..., u_n where u_n is the originator
> and each node is an MPR of the next node in the sequence.
> The difference is that the sequence must lead to the originator,
> and it might not.
>
> I will have additional suggestions soon.
>
> Regards,
> Richard
>
>
> ----- Original Message -----
> From: "Charles E. Perkins" <[email-masked]>
> To: "Richard Ogier" <[email-masked]>
> Cc: "Mobile Ad Hoc IETF working group" <[email-masked]>
> Sent: Wednesday, February 25, 2004 1:36 PM
> Subject: Re: [manet] MPRF [flooding protocol] document initial revision
>
> > Hello Richard,
> >
> > I did go back and look over the discussion that
> > you cited.  It was very interesting work.  I have
> > some further comments.
> >
> > I suppose I have been assuming that the MPRs
> > themselves form a connected dominating set.
> > This provides assurance that a message
> > transmitted by all MPRs goes everywhere.
> > I believe this assumption is justified by
> > the selection algorithm.
> >
> > Suppose that an MPR is taken as a "guaranteed"
> > relay for a flooded message.  By that, I mean the
> > node _will_ transmit a flooded message if that
> > flooded message is sent by its MPR selector.
> >
> > My suggested change amounts to a "premature"
> > scheduling of this guaranteed relay operation.
> > In other words, I _claim_ that it "cannot" produce
> > _more_ transmissions, if the MPR selector itself
> > is an MPR.
> >
> > If my _claim_ is correct, then I can't see how
> > Cedric's simulations would show that more packets
> > were sent.  Perhaps the aforementioned step 5.2
> > needs one further refinement:
> >
> >           5.2  If this node is MPR for any neighboring MPR, and if the
> >                time to live of the message is greater than '1', the mes-
> >                sage MUST be forwarded according to the following by
> >                broadcasting it on all interfaces that have symmetric
> >                neighbors other than the sender, with the TTL of the mes-
> >                sage reduced by one.
> >
> > If my claim is incorrect, it would be very
> > helpful for me if you might explain why.
> >
> > Regards,
> > Charlie P.
> >
> > Richard Ogier wrote:
> > > Yes, I recall that this method was discussed on the list about
> > > a year ago, and Cedric ran some simulations showing that
> > > it resulted in a large number of transmissions (in one case
> > > about 50% of the nodes transmitted a given flooded packet).
> > > So let's not forget about efficiency.
> > >
> > > There are several other methods that avoid having to know
> > > the previous hop, including one suggested by Thomas Clausen
> > > or Philippe Jacquet about a year ago in which a node relays a flooded
> > > packet if and only if the minimum ID neighbor is an MPR selector,
> > > or the node has smaller ID than all neighbors.  I am comparing
> > > several of these via simulations and will announce the results
> > > in a few weeks.
> > >
> > > Richard
> > >
> > > ----- Original Message -----
> > > From: "Joe Macker" <[email-masked]>
> > > To: "Charles E. Perkins" <[email-masked]>; "Richard Ogier"
> > > <[email-masked]>
> > > Cc: "Mobile Ad Hoc IETF working group" <[email-masked]>
> > > Sent: Wednesday, February 25, 2004 10:43 AM
> > > Subject: Re: [manet] MPRF [flooding protocol] document initial revision
> > >
> > > > At 12:37 PM 2/25/2004, Charles E. Perkins wrote:
> > > > >Hello Richard,
> > > > >
> > > > >Taking your suggestions out of order, I'd first agree
> > > > >with your proposed terminology.  I have noticed many
> > > > >times that the terminology surrounding the flooding
> > > > >discussion can be very confusing.  I will try to go
> > > > >through the MPRF draft to make the indicated revisions
> > > > >to our terminology.
> > > > >
> > > > >The example you give is, I think, applicable to other
> > > > >situations where an MPR node receives a flooded
> > > > >packet from other neighbors first.  It seems to me
> > > > >that a very simple fix would work, though.
> > > > >
> > > > >If a MPR node receives a flooded packet from ANY
> > > > >neighbor, it should go ahead and transmit the
> > > > >packet again to its neighbors, and mark the
> > > > >packet as already processed.
> > > >
> > > > Charlie:
> > > >
> > > > Several of us have been talking about and actually implementing
> > > > that for quite awhile. The previous hop state is also not required.
> > > > The election heuristics can also be tweaked in simple ways
> > > > to have more common or less common MPR sets.
> > > >
> > > > We have this MPR-F option functional in a
> > > > working implementation (providing generic multicast MANET
> > > > forwarding). We are presently examining its robustness and
> > > > performance in a few scenarios against other more stateful
> > > > approaches.
> > > >
> > > > I must confess I haven't read the ID in detail yet, we're just busy
> > > > implementing things.
> > > >
> > > > -Joe
> > > >
> > > >
> > > >
> > > > _______________________________________________
> > > > manet mailing list
> > > > [email-masked] 
> > > > https://www1.ietf.org/mailman/listinfo/manet 
>
> _______________________________________________
> manet mailing list
> [email-masked] 
> https://www1.ietf.org/mailman/listinfo/manet 

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

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

---

From: Justin Lipman <[email-masked]>
Date: Fri, 27 Feb 2004 09:55:30 +1100

> However, can't this be solved in deployed MANETs via network-layer and
> link-layer techniques that give routing-control traffic some level of
> priority?  Examples are DiffServ and IEEE 802.11p.  (Note: in my old age, I
> forget which letter was per-frame prioritization.  So, "p" may be wrong!?) 
> Did you try those techniques in GloMoSim?

Hi Pete,

No I didnt. Ill take a look at what you are refering to as Im not aware of it.
However, I dont think assigning priorities to packets will help given hidden 
node problems etc... 

However, I think the problem with using optimised flooding algorithms is that 
specific nodes are required to rebroadcast the message being flooded. Yet, if 
they do not receive the message, then the floods progression in a direction 
is limited. Secondly, by reducing the redundancy we limit the number of paths 
the message can successfully be delivered.

kind regards,
Justin

> flooding mechanisms performed very badly as increasing CBR background
> traffic was introduced, especially compared to Blind flooding. This makes
> their use very limited.
>
> results for MPR, LMST, Blind flooding vs a more reliable version of LMST
> that uses unicast packet transmission instead of broadcast packet
> transmission.
>