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

From: Richard Ogier <[email-masked]>
Date: Fri, 14 Jul 2006 11:22:36 -0700

I want to point out a mistake that some people make
when simulating OSPF-MDR.
(The GTNetS code does this correctly.)

Rule: An MDR should not forward a new LSA that was received from
a MANET neighbor that covers all neighbors of the MDR.

The following simple example shows why this is important.
(I am assuming each router has a single MANET interface.)

R1 -- R2 -- R3

In this example, routers R2 and R3 may both become MDRs
(if R3 becomes an MDR before R2).
However, if R1 originates an LSA and R2 forwards the
LSA, it is not necessary for R3 to also transmit the LSA.
(It is possible to modify the MDR selection algorithm
to avoid selecting R3 as an MDR, but that would make
the algorithm more complex and would not completely avoid
the need to use the above rule.)

It makes sense to employ the above rule for MDRs, since
they are not source dependent, but is is NOT necessary to
employ the above rule for MPRs, since MPRs are source dependent,
so if the LSA is received from an MPR selector then there must
exist some neighbor that is not covered by the MPR selector.

In an email exchange, Philippe tried to justify not employing
the above rule for MDRs in his simulations, claiming
that the rule could also be used with MPRs.  This is NOT a valid
argument, since MPRs are already selected in a source
dependent manner as explained above.
Therefore, this rule will not benefit MPRs as much as it will
benefit MDRs.

Philippe also tried to justify not employing the above
rule for MDRs by saying that it is not practical to implement.
Note, however, that the above rule requires only O(n) time
to perform, where n is the number of neighbors.
Also note that the steps performed by OSPF when deciding
whether to forward a new LSA also require O(n) time
(see Section 13.3 of RFC 2328), so the above rule
does not add significant complexity to OSPF.

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.
So I think Philippe has run out of excuses. :-)

Richard

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

---

From: Philippe Jacquet <[email-masked]>
Date: Fri, 14 Jul 2006 22:21:13 +0200

Dear Richard,

It was not my intention to make this exchange public and I don't 
remember you asked me the permission to do so.

I was asking you about some technical explanations and wanted to have 
your advice about some preliminary simulations which suggested that some 
hybridation between MPRs and MDRs could improve flooding with a good 
margin. I didn't want to make it public because my results are too 
preliminary to be usefully discussed on this mailing list without 
creating unnecessary entropy.

About the point you discussed below  I would have told you in private 
(now in public but I think there is no offense):

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.

2. About inserting this feature for MPR,  I tend to agree with you and I 
wouldn't propose it in a protocol because it would be unnecessarily 
heavy for a scheme that is already very close to optimal (and which is 
already last hop dependent but in a much less complex way than yours). 
However in the theoretical plan I think the concept can be included in 
MPR as well, and in my last (private) email I was just asking if you 
have tried this.

About your last sentence that I should "have run out of excuse", I 
confess that I am not enough confident in english to be able to 
interpret it without error.

Best regards,

Philippe

---

From: Philippe Jacquet <[email-masked]>
Date: Fri, 14 Jul 2006 22:50:33 +0200

> a MANET neighbor that covers all neighbors of the MDR.

BTW You explained me in the private exchange that the rule is precisely

Rule: An MDR should not forward a new LSA that was received from
a MANET neighbor that covers the neighbors of the MDR that have NOT sent 
the LSA and NOT sent an ACK for this LSA.

This is rule (a) in your draft that you explained to me. This is not the 
same thing since the absolute inclusion of neighborhoods is less likely 
to happen and when it happens the static rules for MDR selection should 
simply take it into account in order to deselect this MDR in advance.

Philippe.

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 24 Jul 2006 19:02:54 +0200

Richard Ogier wrote:

> Philippe Jacquet wrote:
>> 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.
>
> 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. 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?

>
> I just wanted to make sure people don't make the mistake I mentioned
> when simulating or implementing OSPF-MDR, and to explain that omitting
> the rule (to suppress floods when all neighbors are covered) does
> not allow a fair comparison with MPRs.  Also, since you think this
> rule is too complex, I thought it would be appropriate to bring
> this discussion to the ospf-manet list.

But the way you brought is maybe less appropriate in term of fairness.

---

From: Richard Ogier <[email-masked]>
Date: Wed, 26 Jul 2006 07:32:19 -0700

Philippe Jacquet wrote:

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