Subject: Re: [manet] Comments on "Problem Statement for OSPF Extensions ..." draft

From: "Madhavi W. Chandra" <[email-masked]>
Date: Wed, 7 Apr 2004 12:34:04 -0400

Tom and Charlie,

I agree with most of Tom's responses...see one comment at the end. 
Charlie, can you please forward the editorial comments that you had.

Thanks,
Madhavi

On Tue, Mar 30, 2004 at 08:09:17PM -0800, Henderson, Thomas R wrote:
> Charlie,
> thanks for your comments (responses inline)
> 
> > -----Original Message-----
> > From: Charles E.Perkins [mailto:[email-masked]]
> > Sent: Thursday, March 25, 2004 1:28 PM
> > To: Mobile Ad Hoc IETF working group
> > Subject: [manet] Comments on "Problem Statement for OSPF 
> > Extensions ..."
> > draft
> > 
> > 
> > 
> > Hello folks,
> > 
> > During the recent meeting, the abovementioned draft
> > was discussed.   The draft has been submitted for a
> > long time, but after finally reading the draft, and
> > motivated by the recent WG discussion, I have a few
> > comments.
> > 
> > - In section 2.1, it is stated that mobility makes
> >   the use of directional antennas into a pointless
> >   exercise.  There are numerous studies that conclude
> >   otherwise.  It seems likely that, given sufficient
> >   justification, a workable system can be built.
> >   Whether or not the additional cost is justified
> >   compared to other expenses is debatable.  Overall,
> >   however, I would say that "pointless" is far too
> >   strong an adjective in this sentence.
> 
> agreed-- maybe "difficult" instead
> 
> > 
> > - In section 2.3, the acronym "VC" is left undefined.
> 
> virtual circuit
> 
> > 
> > - In section 2.5, the misconception is promulgated
> >   that receiving takes less power than transmitting.
> >   While it is typically true per message, the fact is
> >   that receiving is often more power-consuming
> >   when the receiver has to be always powered up.
> >   In contrast, typically the transmitter can be
> >   powered down during most of the timm.
> 
> agreed, although the point that power management is a 
> concern is still applicable (but this should be reworded)
> 
> > 
> > - In section 2.7, if a node's ability to support new
> >   neighbors is exhausted, then one can truly say that
> >   the number of neighbors is numerically limited,
> >   so that the nodal degree is limited.  Said another
> >   way, geographic proximity may not result in network
> >   adjacency.
> 
> agreed (I don't think you are arguing the text?).
> Fred Baker's "outsider's view of MANET" draft explored
> the possibility of limiting the nodal degree.
> 
> > 
> > - In section 2.8, replace "should not thrash" by
> >   "should avoid thrashing"
> > 
> > - In section 2.9, last paragraph: the suggested
> >   strategy requires too much binding between a node's
> >   IPv4 addressability and its IPv6 addressability.
> >   This issue may not need solution in this document
> >   anyway.  In fact, I question the need for binding
> >   even separate network interfaces to the same nodal
> >   identifier, but again that is a separate issue.
> 
> This section alludes to a draft in the OSPF WG suggesting
> that multiple addressing families could be supported by
> a single protocol (OSPFv3).  The point is that, if we
> are doing ad hoc routing at layer 3, we should concern
> ourselves with handling both v4 and v6 efficiently.
> 
> > 
> > - Section 2.10 gets to the heart of a crucial
> >   problem.  I would suggest that it be taken as
> >   a requirement to outfit the OSPF implementations
> >   so that unreliable flooding is acceptable,
> >   otherwise I just don't believe the solution
> >   will be scalable.
> > 
> 
> I agree with you that this is a crucial problem, and the
> way that this is solved is going to affect the 
> scalability.  

Agreed.  And, as Tom pointed out on another email thread, the debate
over reliable vs. unreliable flooding will really depend on the
mobility scenario.  It seems intuitive that unreliable flooding will
'outperform' reliable flooding in a highly mobile environment...and
probably the opposite in a relatively low mobility environment where
periodic signaling seems excessive.  In any case, as we know
performance is not just the overhead.  It is a tradeoff that will be
governed by the network scenario.  We can change the wording to
indicate as such.

-Madhavi
 
> Our studies have indicated that flooding is by far the 
> dominant contributor to overhead.  We have looked at
> a number of the proposals for reliable but optimized
> flooding, and found that they can improve the situation,
> but a reduction in overhead by half seems to be a rough
> bound on the achievable improvement.  However, in some
> highly mobile environments, unreliable flooding does
> significantly better (order of magnitude) than reliable
> flooding.  
> 
> We'll put out a draft on this topic shortly, but suffice
> it to say that reliable flooding doesn't seem capable of
> approaching the overhead reduction offered by unreliable
> flooding, as mobility increases.  
> 
> But whether or not a reliable flooding protocol can be 
> scalable or not scalable is debatable.  "Doesn't scale"
> is frequently a dismissive term that is not qualified
> enough.  The working group may decide that, in the case
> of OSPF, it is willing to trade some scalability to 
> retain reliable (but optimized) flooding.  The design 
> decision that I believe is the true non-starter is to 
> decide a priori that OSPF flooding should not be optimized,
> period.  
> 
> Tom
> 
> _______________________________________________
> 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: "Charles E.Perkins" <[email-masked]>
Date: Wed, 07 Apr 2004 10:08:01 -0700

Hello Madhavi,

Long time, no see!

>>> == me,
>>  == Tom
>   == Madhavi

> I agree with most of Tom's responses...see one comment at the end.

Sounds like we are all three in basic agreement here...

> Charlie, can you please forward the editorial comments that you had.

I'll type them in separately, but if I forget to send them please
remind me because this is one of those weeks.

In my comments below, I also discuss some of Tom's points
a bit more.

>>>   exercise.           ...........
>>>            I would say that "pointless" is far too

Judging from later discussion, I would suggest that
"more expensive" is about the most pejorative term
one might truthfully use here.

>> concern is still applicable (but this should be reworded)

Certainly, power management is crucial, and for
the most part overlooked in [manet] development
up until now.  However, there are many interesting
results we could try to incorporate.  Moreover, this
has a strong interaction with flooding strategies.

>> ourselves with handling both v4 and v6 efficiently.

Agreed -- but it does not necessarily imply a close binding
of those addresses _as part of the routing protocol_

>    ...                                             the debate
> 'outperform' reliable flooding in a highly mobile environment...

Check.

>                                                               and
> periodic signaling seems excessive.

You seem to mean that (a) reliable flooding can outperform
unreliable flooding in a low- (or zero-!) mobility
environment, which is within the realm of imagination.  Then
the next clause would mean that in low-mobility environments
periodic advertisements are excessive, which also sounds
reasonable if you mean that they aren't needed since likely
nothing has changed.  But, in context it means that OSPF is
both more likely to succeed and yet burdened with excessive
signaling in a low mobility environment.  In fact, I could
even agree, after more investigation, with both parts, but
I was not sure it was what you meant.

Furthermore, while it is within the realm of imagination
that reliable flooding can outperform unreliable flooding
in low-mobility scenarios, it is by no means certain, and
probably depends a lot on other features of the algorithms
doing the flooding.

I thought that the _only_ reason for even considering
reliable flooding was because that was what OSPF already
did.

>                                        In any case, as we know

Do you think it's acceptable to equip OSPF with extensions
that presume reliable flooding even when that strategy is
likely to place stringent limits on the how fast the nodes
are "allowed" to move?

>> enough.

That's true, but I make a very intentional effort to
avoid such dismissive uses.  Even scalability isn't
important unless one's protocol is intended to be
applicable to large-scale deployments, according to
whatever parameter you want to make large (often
the number of nodes, but could also be the amount
of traffic or number of flows).

>>    The working group may decide that, in the case
>> retain reliable (but optimized) flooding.

"Reliable" does not equal "optimized", except unless
all the signaling overhead is counted and it is indeed
optimal.  Furthermore, "optimized" is subject to the
same abuse as "scalable", and both really need to be
put in good context in order to be truly understood.

>>                                        The design

I am sure I agree with this statement, but I also admit
I was wondering what motivated it.

Regards,
Charlie P.

---

From: Justin Lipman <[email-masked]>
Date: Thu, 8 Apr 2004 10:28:21 +1000

> reliable flooding was because that was what OSPF already

Charles,

What is your definition of "reliable" flooding?

Blind flooding can be seen as reliable and my own work shows it performs very 
well (if one ignores the broadcast storm). Sadly, MPR and other optimised 
flooding algorithms do not perform well at all!

Kind regards,
Justin

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

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 07 Apr 2004 19:06:54 -0700

Hello Justin,

Your observation is very important to understanding
how to improve MPR flooding.  We have, indeed,
measured a drop in packet delivery ratio when the
number of broadcasts is kept to the theoretical
minimum.  This occurs because broadcasts are not
reliable, and when some are lost during MPR flooding
their absence is more damaging than with blind flooding
(I assume not totally blind!).

More comments inline below...

>What is your definition of "reliable" flooding?
I thought it meant that a broadcast source gets an acknowledgement
from each of its neighbors that its broadcast was received.  This
acknowledgement can come in various forms, of course.  If I am
using the term in some way that is not compatible with the discussion
about OSPF extensions, I hope someone will tell me what the correct
meaning should be.

>Blind flooding can be seen as reliable and my own work shows it performs very well (if one ignores the broadcast storm).
>
Why is it legitimate to ignore the broadcast storm?  That's the
entire motivation anyway for trying to create a better broadcast
mechanism.  Congestion due to broadcast can significantly
degrade packet delivery ratios in many scenarios.

> Sadly, MPR and other optimised 
I thought it depended on the scenario!

Regards,
Charlie P.

---

From: Justin Lipman <[email-masked]>
Date: Thu, 8 Apr 2004 12:45:06 +1000

Hi Charles,

> (I assume not totally blind!).

Very true...

I have some results in the following paper which shows the performance of 
Blind flooding, MPR, LMST Flooding and a reliable variant of RMST that 
utilises unicast transmission instead of less reliable broadcast 
transmission.

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

This approach takes optimisation to the extreme using MST and is probably not 
acceptable for route discovery in reactive routing protocols. Also it places 
much emphasis on transmission power control. However, for a proactive routing 
protocol like OLSR where link state dissemination is the requirement, it may 
be most applicable.

We have a paper in preparation which looks at ways of improving MPR 
reliability for use in both reactive and proactive routing protocols.

Ill be happy to send that to you once its ready.

> about OSPF extensions, I hope someone will tell me what the correct

Im not sure either if its compatible with the OSPF extensions as I havent kept 
up with that. Im interested to know though.

However, my definition of "reliable flooding" is that the message being 
flooded is delivered to as many nodes as possible. This is irrespective of 
local acknowledgement of received packets. For example Wei Lou's work:
http://www.cse.fau.edu/~wlou/publications.htm

W. Lou and J. Wu, Double-Covered Broadcast (DCB): A Simple Reliable Broadcast 
Algorithm in MANETs, accepted to appear in Proc. of IEEE Conf. on Computer 
Communications (INFOCOM 2004), Hong Kong, China, April, 2004. 

W. Lou and J. Wu, A Reliable Broadcast Algorithm with Selected 
Acknowledgements in Mobile Ad Hoc Networks, Proc. of IEEE 2003 Global 
Communications Conference (GLOBECOM 2003), San Francisco, California, USA, 
December, 2003. 

> >Blind flooding can be seen as reliable and my own work shows it performs
> > very well (if one ignores the broadcast storm).
>

I "dont" think it is legitimate to ignore the broadcast storm.
I was just saying if one were to ignore the broadcast storm problem then Blind 
flooding does provide very reliable packet delivery as shown in my paper.

My approach, RMST, addresses the broadcast storm problem and has comparable 
reliability to blind flooding (in terms of packet delivery).

> I thought it depended on the scenario!

Hmmm... not sure what you mean?

In my paper I introduced increasing CBR traffic into the network from 3 source 
destination pairs. The optimised approaches performed very badly. Blind 
flooding performed very well as did RMST.

I can think of two scenarios:

- If there is heavy network load (traffic) the packet loss in the network 
increases, resulting in reduced packet delivery by the optimised flooding 
mechanism.

- If nodes are mobile and the neighbour information being used is outdated 
this may lead to bad rebroadcast decisions by the optimised flooding 
mechanism, possibly resulting in reduced packet delivery. Examples of this 
are nodes being selected as rebroadcasting node, or in self-selecting 
approaches nodes not selecting themselves to rebroadcast...

Gezzz ad hoc networks are a fascinating problem! :-)

Kind regards,
Justin

---

From: Einar Vollset <[email-masked]>
Date: Thu, 8 Apr 2004 13:32:58 +0100

> local acknowledgement of received packets

I disagree. I believe a  "reliable" protocol has to involve 
acknowledgments on some level.

A protocol which doesn't include some sort of acknowledgment from the 
receivers, cannot provide any guarantees of delivery: It can only 
increase the average packet delivery ratio. The difference is subtle, 
but important.
The work by Wei and Lou is a case in point: Their work is good at 
increasing the packet delivery ratio while keeping the transmission 
overhead low, but  can only provide delivery guarantees to those nodes 
included in the CDS and which are as a result required to send an 
acknowledgment (which may, of course, be a passive acknowledgment). The 
fact that each node which is not required to acknowledge is covered by 
2 nodes which are, only increases the likelihood that those nodes will 
receive the packet, it does not provide a guarantee that they do so. 
This is analogous to me attempting to tell my brother that his jacket 
is on fire; unless he acknowledges that he has heard me (by say, taking 
his jacket off), I cannot know if he has heard me, no matter how many 
times I tell him.

Of course, you might be satisfied with increasing the average packet 
delivery ratio to a certain level, given the nature of the MANET 
environment, but using a protocol which does not provide any delivery 
guarantees implies that the sending node cannot reason about which 
nodes have received it, so it might have to periodically broadcast an 
important message. This is the natural trade-off between unreliable and 
(possibly more costly) reliable broadcast/multicast/whatever protocols.

Cheers,

Einar

----------------------------------------
Einar Vollset
PhD Student
School of Computing Science
University of Newcastle, UK
http://vollset.org
-----------------------------------------

---

From: "Madhavi W. Chandra" <[email-masked]>
Date: Thu, 8 Apr 2004 12:33:06 -0400

Hi Charlie,

> Long time, no see!

I know!  I trust all is well.

> Sounds like we are all three in basic agreement here...

Yes, for the most part I think so.

> remind me because this is one of those weeks.

OK...thanks!

> I was not sure it was what you meant.

Sorry.  What I mean is that in low mobility environments, reliable 
event driven signaling seems more productive than periodic signaling
since likely nothing has changed.  The point is that the performance
of reliable vs. unreliable will depend on the dynamic nature of the
network.  And, for unreliable flooding...the flooding period.  

> reliable flooding was because that was what OSPF already

I wouldn't say that.  Reliable event-driven flooding has its merits in
performance as well.  

In high mobility, frequent period flooding would be needed to avoid
packet loss and low throughput...so the overhead may be justified.  But,
the same frequency will unnecessarily consume bandwidth in low
mobility scenarios.  Even with a dynamic flooding period, it is not
instantaneous, so I'm not clear on what happens while in flux.  I can
imagine that in low mobility, you have a 'large' flooding
period to reduce the unnecessary overhead.  If the network becomes
highly dynamic before the flooding period catches up, what happens to
network throughput?  I imagine that many packets will get dropped.

So, it comes down to 'performance' and network requirements.

> likely to place stringent limits on the how fast the nodes

Do you mean that reliable flooding will impose an 'upper' limit on the
dynamic nature of the network?  Clearly we cannot place such limits.
As I see it, this is work in progress and the solution may end up
being a hybrid approach, or some other optimizations that further
reduce the impact of ACKing.

I guess I'm just saying that we should not dismiss reliable flooding.
The solution phase is still in an early stage.

Regards,
Madhavi

---

From: "Madhavi W. Chandra" <[email-masked]>
Date: Thu, 8 Apr 2004 12:44:06 -0400

Hello Justin and Charlie,

> > about OSPF extensions, I hope someone will tell me what the correct

I've been operating on this understanding of reliable flooding as
well...that the recipient signals back in some form that it has indeed
received the transmission.  To me, the reliable flooding definition
below sounds more like best effort.  Justin, thanks for the pointers
below...I'll have to look into them.

Regards,
Madhavi

---

From: Justin Lipman <[email-masked]>
Date: Sat, 10 Apr 2004 14:34:26 +1000

Hi there Einar,

I recall you had a good paper on a reliable flooding approach.
Perhaps you can supply a pointer to it for those interested?

> acknowledgments on some level.

My own approach has hop by hop acknowledgement.
There are some approaches that require all nodes receiving a flooded message 
to send back an acknowledgement to the source of the flood. However, other 
than knowing n nodes received a flooded message, an ad hoc node generally has 
no idea about how many nodes there are in an ad hoc network. So I dont know 
how useful that is.

> increase the average packet delivery ratio. The difference is subtle,

Yep agreed. I guess it depends upon the application the "type" of reliability 
required.

> (possibly more costly) reliable broadcast/multicast/whatever protocols.

Again... if a node in an ad hoc network of n nodes performing a reliable flood 
receives m replies (where m<n) and has little knowledge of nodes beyond 1 or 
2 hops, then the usefulness of those acknowledgements is probably somewhat 
limited. On a hop-by-hop basis I think it makes sense though.

I recall your approach allowed for partitioning in the ad hoc network etc. 
Something mine and others do not.

Kind regards,
Justin