Subject: Re: [Ospf-manet] Mistake to avoid when simulating OSPF-MDR

From: Philippe Jacquet <[email-masked]>
Date: Tue, 12 Sep 2006 16:03:02 +0200

Dear Richard,

Thanks to broadcast, in wireless OSPF, LSA retransmission should need 
O(1) operations instead of O(n) as in regular OSPF. This greatly reduce 
the number of retransmissions which is the main goal, and also reduce 
the amount of processing overhead since wireless OSPF would be likely 
used for small portable device with low autonomy and processing power.

Indeed for each LSA you know the number N_waitack of adjacent neighbors 
from which you expect acknowledgement, number which is decremented 
everytime an ACK or an LSA is received from those adjacencies. The LSA 
would need to be rebroadcasted if the number N_waitack is not zero after 
the ack interval. This is an O(1) check.

With your new version of MDR you introduce an overhead complication that 
to my sense is not necessary, and lead to O(n) cost. Possible 
improvement in performance may happen because of some corner effect you 
have detected in the 2x2 you have intensively simulated but I am not 
sure it will really be significant in most scenarios. I don't know how 
you can proceed to an off line computations since some of the parameters 
(ACK and LSA transmissions) are clearly on-line.

Parts of the network that are highly mobile will generate more update 
and locally more processing but in your case you will create more burden 
in the other parts of the network (ie more LSA retransmissions at O(n) 
processing each).

In most cases MPR will be more performant with less processing overhead 
because the optimization is more efficient and less scenario dependent.

Best regards,
Philippe

Richard Ogier wrote:

> Philippe Jacquet wrote:
>
>> Richard Ogier wrote:
>>
>>> Philippe Jacquet wrote:
>>>
>>>> 1.  You were the one who raised first the complexity issue and that 
>>>> there could be problems to implement this feature in real time.  I 
>>>> could not have raised it myself because I was precisely asking you 
>>>> to explain me this feature. I didn't think about it in details, but 
>>>> I assume that in making MDR last hop dependent in such a more 
>>>> complex way than MPR are done, and knowing your opinion about MPR 
>>>> complexity, yes I understand that you have realized that there is a 
>>>> complexity issue about last hop dependent MDR flooding. MPRs are 
>>>> much more simple to utilize and more efficient and to my opinion 
>>>> your effort to make MDR comparable in performance would probably 
>>>> lead to a very heavy protocol.
>>>
>>>
>>>
>>>
>>>
>>> Not at all.  The change I suggested (below) is quite simple.
>>>
>>>> Finally, even if O(n) time is too large for deciding whether
>>>> to forward a new LSA, the router can easily compute in
>>>> advance (e.g., whenever the 2-hop neighbor information is
>>>> updated) a bit for each MDR/BMDR neighbor that indicates
>>>> whether the neighbor covers all other neighbors.
>>>
>>>
>>>
>>>
>>>
>>> But I don't think this simple change is necessary, since as I 
>>> mentioned,
>>> the LSA forwarding procedure of OSPF-MDR is not more complex than
>>> that of OSPF.  Both require O(n) time.
>>
>>
>>
>> But you agree that you raised this complexity issue the first time in 
>> the answer you sent to me.
>
>
>
> I don't think so. In your private email of 7/12/2006 you said "BTW 
> this seems
> to be a complication for real networks". Maybe you meant something else.
> But I don't see why it is important who raised the issue first.
>
>> Anyhow the O(n) complexity may be acceptable for an OSPF network that 
>> update its LSA every 20 minutes but maybe not when updates occurs for 
>> every 10 secondes.  Also the rule you described to me was also taking 
>> into account the neighbors who already sent  the LSA and the ACK and 
>> this cannot be computed off line and would make MDR flooding even 
>> more complicated. Do you plan to change your rules? 
>
>
>
> Not at this point.  As I said, OSPF already does O(n) processing
> when deciding to forward an LSA.  One of our objectives is to
> minimize the changes to OSPF, so changing this would be a major
> change to OSPF.  (As Aniket pointed out in his last email,
> in OSPF the DR is adjacent to all n of its bidirectional neighbors,
> so it should be acceptable for an MDR to also scan all of its
> neighbors when deciding whether to forward a new LSA.)
>
> Also, I don't think that O(n) is too much processing for
> each received new LSA, and avoiding this would be difficult,
> since one must at least look up the neighbor in the list of
> neighbors.  (For example, the GTNetS code does this for all of
> the implemented protocols, and it would be difficult to change
> the code to avoid this.)
>
> Note that MPRs or MDRs must be updated when the 2-hop neighbor 
> information
> changes, which requires O(n^2) processing every 5 seconds or so in
> a highly mobile network.
> If n = 100, then n^2 is 100 times n, so O(n^2) every 5 seconds
> is like O(n) every .05 sec.
> Anyway, as I mentioned above, if O(n) processing for each received
> new LSA is unacceptable, then more substantial changes to OSPF are
> needed.  But if we decide to go this way, OSPF-MDR can easily be
> changed as I mentioned.
>
> There is some confusion about the online rule I described and
> the "offline" rule that can be done instead, so I will provide
> details now to clarify this.
>
> The "online" method must determine which neighbors are covered
> when the new LSA is received.  An MDR immediately forwards
> the new LSA unless all neighbors that did not Ack the LSA
> are covered.
> It makes no sense to consider neighbors that already sent
> the same LSA, since we are talking about a *new* LSA, so this
> is the first time the LSA has been received!
> The use of Acks (in deciding whether to flood an LSA) is not very
> important, since MDRs forward LSAs immediately and Acks are delayed.
> (So, performance will not be affected much if we ignore Acks when
> deciding whether to forward an LSA.)
> Also, Acks are processed only when received from *adjacent* neighbors.
> The procedure for BMDRs is different, but you did not simulate
> BMDRs and did not ask about them.
>
> The "offline" method computes a bit for each neighbor
> (whenever the 2-hop neighbor info changes) that indicates whether
> the neighbor covers all of the other neighbors.
> If the offline method is used, then an MDR immediately forwards
> a received new LSA unless the neighbor from which the LSA was
> received covers all neighbors (or all neighbors that did not
> Ack the LSA).  As mentioned above, using Acks does not affect
> performance much, and Acks are processed only when received
> from adjacent neighbors.
>
> Richard
>
>
>
>

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

---

From: Richard Ogier <[email-masked]>
Date: Thu, 14 Sep 2006 12:42:40 -0700

Philippe,

Philippe Jacquet wrote:

> O(1) operations instead of O(n) as in regular OSPF. This greatly 
> reduce the number of retransmissions which is the main goal, and also 
> reduce the amount of processing overhead since wireless OSPF would be 
> likely used for small portable device with low autonomy and processing 
> power.

When you say this "greatly reduces the number of retransmissions",
I don't see how the number of operations per transmission by itself
reduces the number of transmissions.  Maybe you are talking about
the fact that OSPF always retransmits LSAs as unicasts, as does
the MDR extension, so there could potentially be a larger number
of LSA transmissions, including unicast retransmissions.

I originally thought about allowing retransmitted LSAs to be multicast.
(Note that the initial flood is always multicast.)
However, in OSPF-MDR, on average a router has only about 1 or 2
adjacent neighbors (depending on whether AdjConn = 1 or 2), so this
would not reduce overhead much.  Also, allowing multicast retransmissions
would require more changes to OSPF, so I think it is best to minimize
changes and keep OSPF's rule that retransmitted LSAs are always unicast.
Anyway, simulations can be done to see if it helps to multicast
retransmitted LSAs, and if it does help, OSPF-MDR could be modified
to allow this.

>
>
> Indeed for each LSA you know the number N_waitack of adjacent 
> neighbors from which you expect acknowledgement, number which is 
> decremented everytime an ACK or an LSA is received from those 
> adjacencies. The LSA would need to be rebroadcasted if the number 
> N_waitack is not zero after the ack interval. This is an O(1) check.

So you are talking about multicasting retransmitted LSAs, as I discussed 
above.

>
>
> With your new version of MDR you introduce an overhead complication 
> that to my sense is not necessary, and lead to O(n) cost.

As has been discussed, OSPF already requires O(n) cost when deciding
whether to forward an LSA, so OSPF-MDR does not introduce any additional
overhead or cost compared to OSPF. One of the goals is to minimize
changes to OSPF.

> Possible improvement in performance may happen because of some corner 
> effect you have detected in the 2x2 you have intensively simulated but 
> I am not sure it will really be significant in most scenarios.

As I mentioned in another email I posted on 7/26/06, you are correct
that this optimization (in which an LSA is not forwarded if all neighbors
are covered by the neighbor from which the LSA was received) helps
the most in networks with a small diameter, but such networks are
important.

> I don't know how you can proceed to an off line computations since 
> some of the parameters (ACK and LSA transmissions) are clearly on-line.

Then you didn't carefully read my email that you are replying to.
The "offline" version does not consider Acks, and an MDR forwards an
LSA only the first time it is received (so there are no previous LSA
transmissions to consider).  As I mentioned, ignoring Acks does
not affect performance significantly, since Acks are delayed.
The offline rule simply says that a new LSA is not forwarded if the
neighbor from which the LSA was received covers all other neighbors.
Note that MPRs also follow this rule, since a router will not be
selected as an MPR of a neighbor that covers all other neighbors.
So, if you simulate the "offline" version of OSPF-MDR, please
incorporate this simple rule.

> and locally more processing but in your case you will create more 
> burden in the other parts of the network (ie more LSA retransmissions 
> at O(n) processing each).

Detailed simulations will show whether OSPF-MDR generates more LSA
transmissions and retransmissions.  But if you are talking about
unicast versus multicast retransmitted LSAs, then for fairness
both protocols should retransmit LSAs in the same way (unicast
or multicast).  The question of whether retransmitted LSAs should
be unicast or multicast can be applied to both MDRs and MPRs.

Since you developed MPRs for MANETs long ago (without thinking about
OSPF), and you have a special interest in MPRs, it seems that your
approach is to try to fit MPRs into OSPF, even though this may not
be the best way to extend OSPF.  On the other hand, my approach was to
start with OSPF and try to find the best and simplest way to extend
OSPF to support MANETs.

Richard

>
>
> In most cases MPR will be more performant with less processing 
> overhead because the optimization is more efficient and less scenario 
> dependent.

>
>
> Best regards,
> Philippe
>
> Richard Ogier wrote:
>
>> Philippe Jacquet wrote:
>>
>>> Richard Ogier wrote:
>>>
>>>> Philippe Jacquet wrote:
>>>>
>>>>> 1.  You were the one who raised first the complexity issue and 
>>>>> that there could be problems to implement this feature in real 
>>>>> time.  I could not have raised it myself because I was precisely 
>>>>> asking you to explain me this feature. I didn't think about it in 
>>>>> details, but I assume that in making MDR last hop dependent in 
>>>>> such a more complex way than MPR are done, and knowing your 
>>>>> opinion about MPR complexity, yes I understand that you have 
>>>>> realized that there is a complexity issue about last hop dependent 
>>>>> MDR flooding. MPRs are much more simple to utilize and more 
>>>>> efficient and to my opinion your effort to make MDR comparable in 
>>>>> performance would probably lead to a very heavy protocol.
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>> But you agree that you raised this complexity issue the first time 
>>> in the answer you sent to me.
>>
>>
>>
>>
>>> Anyhow the O(n) complexity may be acceptable for an OSPF network 
>>> that update its LSA every 20 minutes but maybe not when updates 
>>> occurs for every 10 secondes.  Also the rule you described to me was 
>>> also taking into account the neighbors who already sent  the LSA and 
>>> the ACK and this cannot be computed off line and would make MDR 
>>> flooding even more complicated. Do you plan to change your rules? 
>>
>>
>>
>>