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

From: Tony Przygienda <[email-masked]>
Date: Fri, 6 Aug 2004 23:26:40 +0200

Richard Ogier wrote:

> Gary,
>
> Please see my comments below.

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 ;-)
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.
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

---

From: Richard Ogier <[email-masked]>
Date: Sun, 15 Aug 2004 09:27:38 -0700

Tony and all,

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

> 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.)

> around to generate the spanning tree and am surprised nobody picked up

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

---

From: "Madhavi W. Chandra" <[email-masked]>
Date: Mon, 16 Aug 2004 10:24:04 -0400

> to minimize the size of Hellos in such networks.)

Actually, our mechanism is flexible.  We have the ability to send
all data in a Hello for k consecutive Hellos (persistently)...or only
partial data in k consecutive Hellos (for example, neighbors that are
being dropped)...or send data only in one Hello.  This coupled
with the reply/request mechanism provides flexibility.

Although we haven't been able to run simulations yet, its seems that
sending data in k consecutive Hellos in a low-rate-of-change network is
excessive.  So, it may not be the case that a flat 'send in k
consecutive Hellos' is an optimum approach.

In any case, this is work that should be considered in the design
team....and provided as an outcome of the DT.

-Madhavi

---

From: Richard Ogier <[email-masked]>
Date: Mon, 16 Aug 2004 21:50:55 -0700

> consecutive Hellos' is an optimum approach.

My first thought is that in a low-rate-of-change network, there
won't be many changes to report! So, reporting each (infrequent)
change in 3 consecutive Hellos would add very little overhead.
Even if there is one neighbor change per Hello, reporting
each change 3 times adds only about 8 bytes (2 router IDs) per Hello
(compared to reporting each change only once). However, we also have
to consider the probability that (in your Hello protocol) some
neighbors will not hear the Hello reporting the change and will
thus unicast a Hello request, which also results in a reply to
the request. Even if there are only 20 neighbors, and even if
only 10% of Hellos are missed, then on average 2 neighbors will
send a Hello request, which, being a separate unicast packet, would
result in much more overhead than 2 router IDs. Please correct me
if I am missing something.

[I should clarify that TBRPF does not report every neighbor change
3 (or k) times, but AT MOST 3 (or k) times. A node stops reporting
a neighbor change if it is clear the the neighbor already knows
about the change.]

I agree that your protocol can report each change
k times (persistently, with the N bit set), but you still
require the initial Hello (with the N bit NOT set) to be
received, so that doesn't help in terms of avoiding Hello
replies. Maybe you are now saying that your protocol can
report each change k times with the N bit NOT set, but your
draft does not mention that possibility. Perhaps a MAY or SHOULD
should be added to make the reader aware of this possibility.

The nice thing about the TBRPF Hello protocol is that it shows
that Hello replies are not needed. Unless simulations show
that using Hello replies results in a significant overhead
reduction, then it might be best to simplify the protocol
and omit Hello replies.

Richard

---

From: "Madhavi W. Chandra" <[email-masked]>
Date: Tue, 17 Aug 2004 11:40:52 -0400

> should be added to make the reader aware of this possibility.

The N bit is set to indicate that "the TLVs included in this
Hellos are being sent persistently...and there is more state
associated with this Hello that is not being sent persistently".  This
would be used to send partial-state persistently.  If you are sending
full state persistently (as in TBRPF), then you simply send the same
SCS number WITHOUT the N bit set for k number of times.  So, it's the
same behavior as TBRPF.  It DOES NOT depend on receiving the first
Hello with a certain SCS number.  I guess I thought it was implicit in
the draft, but I can surely clearly state it.

The Request/Reply mechanism gives you flexibility.  A Hello reply is
nothing more than a Full Hello.

-Madhavi

P.S.  By the way, isn't this a discussion that we should be having on
the Design Team?  I'm fine either way, but I thought that's why the
design team was formed.

---

From: Erblichs <[email-masked]>
Date: Mon, 23 Aug 2004 15:30:40 -0700

Design Considerations Wireless Interface   April 04

Group,

        I am sure that I am late to these wireless discussions..
        I will try to keep my comments short.. My two cents..

        FYI: Their is always a number of hosts that
        though they are "mobile" tend to be stationary for
        periods of time. It is almost imperative to scale the
        kbps requirements downwards during these times while
        being able to verify that the LSDBs are synchronized.

        First, is this paper assuming the the LSF packet
        type without acks? I am not.

        3.1 Neighbor Discovery

        Their are actually two bps values being generated here.
        The first is a 1-way discovery within the avg 1/2 of
        hello interval. The second is increased reliabliity
        tradeoff in the event that multiple hellos are lost.

        The true required hello overhead are the extra hellos being
        sent that are duplicates within the dead router interval.

        If we see no loss, then the minimum required hello pkt
        overhead calcs should use dead router interval. The diff
        between that value and your value should the resultant
        overhead needed to assure a level of relaibility given
        a certain loss of pkts.

        3.2 Adj Forming

        Their is a implied assumption that when a "partioned
        network comes together" that their will be only one
        router between the partition. If most of the new
        full adjs are between the new partitions, and
        they are formed first, then the "avg-LSAsOutSync" will
        initially start at 100% * the number of number of
        routers.

        EX: the area is partitioned between A and B. All of
        the routers within A are sync with each other and the
        same goes for B. Now we have 5 routers on the side of
        A and 5 routers on the B side. A time "1" adjs will
        form between A1/B1, A2/B2 ... A5/B5. All LSAs at this
        time are different. It is only at a later time does
        the avg-..OutSync drop to significantly lower values.

        Secondly, the lifetime of a LSA needs to be considered.
        WRT, DNA (Do NOT AGE) LSAs the lifetime is infinite
        and should not be part of the flooding overhead.

        Thirdly, if a nbr leaves and returns within the
        LSA lifetime (and the router dead interval), then
        the nbr movement cancels and should not effect the
        equation (or be counted twice??).

        3.3 LS Flooding

        A)

        "... Link State Flooding overhead to be the amount of
        overhead generated without any packet loss."

        Shouldn't this be added..

        and that a ack is recieved within the timeframe as
        to prevent a control packet rexmit.

        Reason, is that pkt processing delays also cause
        rexmits...

        B) neighborchangerate

        This is bounded by the router dead interval, it takes
        us dead router interval to see that a router has gone
        away.

        It is also bounded by 1/2 the value of the hello interval
        to detect that a router has gone 2-way.

        To effect this value, one concievably could generate
        a hello when,
                * an interface comes up,
                * first time we see a nbr listed in the hello,

        instead of jsut periodicly xmiting hellos..

        3.4 Reliability

        I am not sure that you are seeking reliability as to
        be seeking an implicit way to verify that two or more
        LSDBs have converged.

        Within a wireless environment, the only method that I
        can CONCIEVABLY come up with is with a new OSPF control
        packets that contains a sum of the LSA checksums in a
        LSDB. If the values matched, then I could assume that
        the LSDBs probably match, given a LSA count, and THEN stop
        rexmiting LSAs. To belablor the point, as a router
        enters a new region of an area, he or she could xmit
        this new control packet with 0. This could inform all
        recvrs to xmit their LSAs.. Thus, the area goes into
        a quiesent mode where just minimal summary information
        is xmited when the mobile environment is temporalily in
        stasis.

        This above concept assumes that the total number of
        LSAs that need to be freq xmited is great, that
        the overhead to process them is significant, and that
        LSDB convergence is intended.

        --- I think this is enough to add at this time...

        Mitchell Erblich
        Sr. Software Engineer
        Currently consulting..