Subject: Re: [Ospf-wireless-design] Another example for self-selected MPRs

From: "Madhavi W. Chandra" <[email-masked]>
Date: Tue, 5 Apr 2005 15:51:15 -0400

On Tue, Mar 29, 2005 at 06:14:16PM -0800, Richard Ogier wrote:
> 
> To help understand how my proposed solution uses Hellos to learn
> 2-hop neighbor information and to update self-selected MPRs (or MDRs),
> I would like to present another example.
> 
> Let's assume that (differential) Hellos must be used to learn
> 2-hop neighbor information, e.g., so that partial-topology
> LSAs can be generated.  Also, assume that Hellos are sent
> every 2 seconds, and that no early Hellos are sent.
> 
> First, I want to point out that, for self-selected MPRs/MDRs, only
> DRs and BDRs need to advertise their full neighborhood (periodically)
> in Hellos. This is an additional benefit of using self-selected MPRs,
> because they are in the "middle of the action", i.e., they can directly
> see both the upstream neighbors and the downstream neighbors.
> However, for this example, I will assume that all nodes periodically
> advertise their full neighborhood in Hellos.
> 
>       1
>      / \
>     /   \
>    2 --- 3
>     \   /
>      \ /
>       4
> 
> 
> Assume that initially node 3 is an MPR, either self-selected, or
> neighbor-selected by node 1.
> 
> Now assume that node 4 detects the failure of its link to node 3 at
> time 0, either from a link-layer failure notification, or from
> not hearing Hellos from node 3 for RouterDeadInterval.
> 
> Then node 4 will send a Hello at time 2 (worst case) that indicates
> node 3 is no longer a neighbor. Assume that node 3 can still hear
> Hellos from node 4, so both nodes 2 and 3 will receive the Hello.

Actually, the backup Overlapping Relays (node 2) will go into action 
since it wouldn't have received node 4's ACK.  This will happen at 
(Pushbacktimer + jitter), which is latest by 
(RxmtInterval/2 - propagatation delays).  Even taking
the default RxmtInterval of 5 seconds, puts this time on par, if not
sooner, with the 2second Hello time example.  So, the rest of the example 
of Node 2 knowing it is an Active Overlapping Relay at time 6 is moot.  
Jitter is used for backups to avoid multiple backups firing at the same 
time.  

Please keep in mind that the backup mechanism in Overlapping Relays is 
a powerful yet simple feature and integral to the operation, and should 
not be overlooked.

Thanks,
Madhavi
 
> If MPRs are self-selected, then node 2 will select itself as an MPR
> at time 2, when it receives the Hello from node 4.
> 
> If MPRs are neighbor-selected, then node 3 will send a Hello at
> time 4 (worst case) indicating that node 4 is no longer a neighbor.
> When node 1 receives this Hello, it will select node 2 as an MPR,
> and will send a Hello at time 6 including the updated MPR.
> Node 2 will then know it is an MPR at time 6, compared to time 2
> for self-selected MPRs.
> 
> (I know that non-active overlapping relays will forward MPRs
> during this recovery period, but with an added delay of
> PushbackInterval, and possibly additional overhead if
> mutiple non-active relays flood the LSA at nearly the same time,
> a real possibility if the number of non-active relays is large.)
> 
> Richard
> 
> 
> 
> 
> _______________________________________________
> Ospf-wireless-design mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

_______________________________________________
Ospf-wireless-design mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

---

From: Richard Ogier <[email-masked]>
Date: Tue, 05 Apr 2005 15:39:29 -0700

>Jitter is used for backups to avoid multiple backups firing at the same 

There are still some differences. For example, for the 6 seconds it
may take to select another MPR, *every* LSA will suffer the
PushbackInterval + jitter delay, whereas once a self-selected MPR
selects itself, it will forward new LSAs immediately. Also, the use
of PushbackInterval imposes a more strict constraint on AckInterval
(the maximum time to send a delayed ACK), i.e., AckInterval must be
less than (RxmtInterval/2 - propagation delays). What concerns me
most is scalability. In a very dense network, there could be a large
number of backup Overlapping Relays, and even with jitter the
probability of multiple backups forwarding the LSA becomes
significant. (Of course, backup MPRs are not as desirable as active
MPRs - otherwise there would be no need to select active MPRs.)

But I consider the above to be minor compared to the other advantages
of self-selected MDRs, which have been discussed.
I think simulations will be most useful in comparing the
two approaches.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Tue, 12 Apr 2005 09:43:28 -0700

I want to mention another design goal of of the MDR/BMDR flooding
procedure.  I wanted it to be useful for other MANET applications
that do not require reliable flooding and therefore do not use ACKs.
Thus, I designed the flooding procedure so that it provides redundancy
(via the BMDRs) to improve the delivery ratio even if ACKs are not used.
Thus, a BMDR forwards an LSA not based on ACKs, but based on
whether the neighboring relays that transmitted the LSA cover
all neighbors.  Thus, the flooding procedure is separate from
the reliability procedure (ACKs and retransmissions).

Non-active overlapping relays (NAORs) require that ACKs be
used, since all NAORs will eventually forward each LSA if it
is never ACKed.  (If we disable the NAORs in applications that
do not use ACKs, so that only active MPRs forward LSAs, then
reliability will be poor, especially if it can take 6 seconds
to select a new MPR following a link failure.)

Also, the use of Hellos instead of router LSAs to learn 2-hop neighbor
information makes the flooding protocol more modular (since it
does not depend on LSAs), allowing it to be used for other
MANET applications.

Another design goal is scalability. I wanted the overhead to increase
linearly with the number of nodes for a fixed network diameter,
i.e., to increase linearly with the density (average node degree).
This is true for MDR flooding whether we consider 100 nodes, 1000 nodes,
or 10,000 nodes. MPRs are also scalable, since the average number of
MPRs per node is roughly constant as the node degree increases.
But this is not true for non-active overlapping relays (NAORs).
There must be a time interval DELTA such that if two NAORs
decide to forward the same LSA within time DELTA of each other,
then both will forward the LSA. Therefore, if the node degree
is large enough, so that the number of NAORs is large enough,
then the number of NAORs that decide to forward a given LSA
will increase linearly with the node degree. This will cause
the total number of LSA transmissions to increase quadratically
with the network density, which is something I wanted to avoid.

(Even though the NAORs are triggered only when MPRs are temporarily
unavailable following topology changes, this will be some percentage
of time depending on the degree of mobility, and in any case
the resulting quadratic term will dominate the total overhead
for a sufficently dense network.)

Richard