Re: Comments on draft-spagnolo-manet-ospf-design-00.txt

[Richard Ogier <[e-mail]>]

Tony and all,

Thanks for your comments.  Please see my response to
two of your comments below.


Tony Przygienda wrote:

>
>
> Richard, Gary, Russ,
>
> chewed my way through the recent threads and simulation results and here
> are my 'meta'-comments.
> From simple to hard:
>
> a) The simulation is considering relatively-low-rate-of-neighbor-change
> scenarios to jump to
> the conclusion that incremental-hellos are of little value (as has been
> observed by other people).
> On one hand, I agree obviously with the argument that with higher
> density of nodes can cause
> much higher rates of neighbor change as well as neighbor numbers, on the
> other hand, the
> complexity of the proposals is low enough to make the incremental-hellos
> a belts-and-suspenders
> optimization kind of thing, even if the link bandwidth overhead will not
> be staggering.
> Finally, I didn't drill through the proof of TBRPF to have an opinion as
> to the merits
> of either proposal but Russ's stuff looks simple enough ;-)


Actually, the main problem with Cisco's Hello protocol is the
additional overhead due to the unicast Hello requests, and the unicast
replies to those requests. In dense, highly mobile networks, this can
generate a lot of additional packets (as I discussed in a previous
message) and can actually generate more overhead than full Hellos.
(In highly mobile networks, it is desirable to use a smaller Hello
Interval for faster response to topology changes, so it is important
to minimize the size of Hellos in such networks.)

The incremental Hello protocol of TBRPF does not generate any packets
in addition to the one Hello per Hello Interval, but reports each
neighbor change in at most 3 (or k) consecutive Hellos.

To see how much overhead can be reduced by using incremental
Hellos versus full Hellos, I ran some ns-2 simulations.
I compared the incremental Hello protocol of TBRPF (RFC 3684)
to a modification of this protocol which uses full Hellos
similar to OSPF (each seen neighbor is included in each Hello).
Both protocols were run over IP over IEEE 802.11 with rate 2 Mbps.

The simulation model used 100 and 200 nodes in a 670x670 meter square,
with a transmission radius of 250 meters. Nodes moved according to the
the random waypoint model with maximum node speeds from 5 ms to 30 m/s
and a pause time of 0. The Hello Interval was 1 second (reasonable
for high mobility). The simulation was run for 500 seconds for
100 nodes and 200 seconds for 200 nodes. The results below show the
overhead in kbps for Hello packets:

            Max speed  Full Hellos   Incremental Hellos  % reduction
            ---------  -----------   ------------------  -----------
100 nodes      5 m/s    201.9 kbps       70.0 kbps          65.3%
100 nodes     10 m/s    220.1 kbps       73.8 kbps          66.5%
100 nodes     20 m/s    206.4 kbps       79.2 kbps          61.6%
100 nodes     30 m/s    215.2 kbps       85.0 kbps          60.5%

200 nodes     20 m/s    708 kbps         198 kbps           72%

The results show that incremental Hellos reduced the overhead by about
72% for 200 nodes, and 60% to 65% for 100 nodes (depending on the node
speed). The additional overhead for LS updates was 58.7 kbps for
100 nodes and 20 m/s. (TBRPF uses an efficient method for disseminating
partial topology information which uses incremental LS updates that
share the same packets as Hellos.)

>
> b) Obviously flooding is a more interesting topic and I liked to read
> all the interesting tossing of ideas.
> i) As first observation, the predicting of transitions between
> acknowledgable and non-to-be-acked LSAs
> will be hard (more in c) or rather prohibitive in terms of computing
> power if done well.
> ii) As second, having two different flooding mechanisms flipping will
> make something that is very fragile doubly so
> so it should be probably kept as a life-saving mechanism only.
> iii) Third, from my experience with OSPF & ISIS flooding implementation
> and deployment I observed that ISIS
> flooding tended to be somehow simpler to implement and debug and keep
> stable in the field. BDR did not buy much
> in practical deployment and the initial-TDBX was somehow faster but
> insignificantly so. My point is probably
> that if you find that unreliable flooding is in most cases a good or
> better solution, it may not be worth to
> build a hybrid or tweak reliable flooding much (albeit the protocol
> definitely very much deviates from OSPF then ;-)
> The cost is however that you have to shape the flooding on the link (the
> famous 33msec timer that can
> be deadly for a large-scale implementatoin if done naively) but that can
> be implemented using proper
> leaky-bucket techniques fairly cheaply.
> The argument about mobile-non-moving networks is strange to me (I mean
> the sensors network thing) since
> it seems to go into the direction of an orthogonal, low link quality-low
> bandwith routing rather than mobile routing (kind like ALSR).
> iv) Fourth, prunning of the flooding tree (MBR work, flooding spanning
> tree and such) is hard to get right
> and I don't know which of the ideas have most merit. I have to read and
> think more here.
> The MBR looks reasonable to me (albeit the algorithms
> to be run are a tad convoluted), I also always liked the
> flooding-spanning-tree idea with a token passed
> around to generate the spanning tree and am surprised nobody picked up
> on that.

This is similar to the CDS approach, since the non-leaf
nodes of a spanning tree form a CDS.  Instead of constructing
a tree (which may depend on the global topology), in a mobile
network it may be better to select the CDS nodes based on
local topology. I.e., each node decides whether it is in the
CDS based on 2-hop neighbor information.

However, I agree with you that a source-independent approach
is simpler than the source-dependent MPR approach.
Whether to use a (source-independent) CDS or (source-dependent)
MPRs is an issue that needs to discussed.

Richard

>
> c) Finally, I personally think from having seen it in another context
> that the 'predicting future' to know when to ACK
> and when not is
> bound to either fail or end up in some pretty heavy math that cannot be
> run real-time. Either we're dealing
> with something that is unpredictable (in terms of self-similarity
> beta=0.5), kind like exponential distribution or
> otherwise we can think about stuff in terms of self-similar pattern
> (since I do not believe that a single correlation
> over a well-known time-scale can be observed). If we know the beta (or
> measure it, which is
> a tad expensive computationally), there are methods to detect the
> time-scale of trends that we encounter (and therefore
> predict the future but only in terms of absolute beta, you know that the
> trend will persist with some probability
> but you cannot know which direction it is heading) and based on that an
> educated guess could be taken. But this
> again takes some serious computing power which I cannot believe will pay
> in mobile nodes just to optimize flooding. And
> in case you can do all that, yes, the at-source-squelching approach
> works much better that receiver based for
> couple of reasons I won't dwell further into.
>
> As a 'meta'-'meta' in connection to the group's meeting (sorry for this
> time, I try to be in D.C.) I think even more
> than before that the wireless extensions should be kept in a special
> OSPF area. The ideas passed around are radical enough
> to almost certainly make a general-interface-type-solution overburdened
> and the mix of different interfaces in same
> area very fragile deployment-wise.
>
> thanks
>
> -- tony
>