Subject: [Ospf-manet] Re: Ospf-manet Digest, Vol 9, Issue 11

From: Aniket Desai <[email-masked]>
Date: Mon, 17 Jul 2006 11:37:25 -0400

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.

--- I just want to point out a small clarification. It is possible 
that the LSA is generated by an MDR-other router, which can cover all 
of its neighboring MDR's neighbors; in which case, the MDR in 
question does not forward this LSA. In a broadcast network, this LSA 
will be forwarded by the DR of that network, because LSAs are only 
accepted by adjacent routers in that situation; whereas in MANET, 
2-way neighbors can also accept the LSAs. Hence this rule is quite 
sensible for MANET.

However in a purely random network, using the dense connectivity 
parameters from Dr. Ogier's simulations (30 neighbors per router in 
50 node network), the probability of 2 routers having the exact same 
neighborhood is small (using simple calculations, we can verify it to 
be something in between (1/3)^12 and (1/3)^13). This optimization is 
useful if there is some special structure to the deployed OSPF 
network. Simple example: broadcast wireless network with an MDR-other 
hybrid node, which pumps plenty of LSAs in the MANET segment 
advertising changes in the other segments of the AS -- the only MDR 
of this wireless segment does not forward these LSAs again, as the 
hybrid *gateway* covers everyone else. In general, as the MANET 
network gets denser and denser, this optimization will play a role.

Aniket

At 12:00 PM 7/15/2006, you wrote:
>Send Ospf-manet mailing list submissions to
>         [email-masked]
>
>To subscribe or unsubscribe via the World Wide Web, visit
>         https://www1.ietf.org/mailman/listinfo/ospf-manet
>or, via email, send a message with subject or body 'help' to
>         [email-masked]
>
>You can reach the person managing the list at
>         [email-masked]
>
>When replying, please edit your Subject line so it is more specific
>than "Re: Contents of Ospf-manet digest..."
>
>
>Today's Topics:
>
>    1. Mistake to avoid when simulating OSPF-MDR (Richard Ogier)
>    2. Re: Mistake to avoid when simulating OSPF-MDR (Philippe Jacquet)
>    3. Re: Mistake to avoid when simulating OSPF-MDR (Philippe Jacquet)
>
>
>----------------------------------------------------------------------
>
>Message: 1
>Date: Fri, 14 Jul 2006 11:22:36 -0700
>From: Richard Ogier <[email-masked]>
>Subject: [Ospf-manet] Mistake to avoid when simulating OSPF-MDR
>To: [email-masked]
>Message-ID: <[email-masked]>
>Content-Type: text/plain; charset=us-ascii; format=flowed
>
>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
>
>
>
>
>
>
>
>------------------------------
>
>Message: 2
>Date: Fri, 14 Jul 2006 22:21:13 +0200
>From: Philippe Jacquet <[email-masked]>
>Subject: Re: [Ospf-manet] Mistake to avoid when simulating OSPF-MDR
>To: Richard Ogier <[email-masked]>
>Cc: [email-masked]
>Message-ID: <[email-masked]>
>Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
>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
>
>Richard Ogier wrote:
>
> > 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
> >
> >
>
>
>
>
>------------------------------
>
>Message: 3
>Date: Fri, 14 Jul 2006 22:50:33 +0200
>From: Philippe Jacquet <[email-masked]>
>Subject: Re: [Ospf-manet] Mistake to avoid when simulating OSPF-MDR
>To: Richard Ogier <[email-masked]>
>Cc: [email-masked]
>Message-ID: <[email-masked]>
>Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
>Richard Ogier wrote:
>
> > 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.
>
>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.
>
> >
> > 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
> >
> >
>
>
>
>
>------------------------------
>
>_______________________________________________
>Ospf-manet mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/ospf-manet
>
>
>End of Ospf-manet Digest, Vol 9, Issue 11
>*****************************************

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

---

From: Richard Ogier <[email-masked]>
Date: Thu, 20 Jul 2006 10:31:58 -0700

> simply take it into account in order to deselect this MDR in advance. 

That's not always possible since MDRs are source independent, and
the decision to forward an LSA can depend on which neighbor it was
received from.  Consider the following example.
 
    1
  / | \
2 - 3 - 4

Node 3 is the only selected MDR.
If node 2 floods an LSA, then node 3 will forward it.
But if node 1 floods an LSA, then there is no need
for node 3 to forward it, since node 1 covers all
of nodes 3's neighbors.

> of its neighboring MDR's neighbors; in which case, the MDR in question 
> does not forward this LSA. 

Right. That is my example above, but it seems to contradict your 
statement above.
But in some cases (such as the 3-node example I gave) it is possible to
deselect a redundant MDR in advance by making the algorithm a little
more complex.  (For example, an MDR can deselect itself if the set of
lower priority MDR neighbors is connected and covers all neighbors.)
But it is not clear that this will improve performance significantly.
(This can be tested in simulations.)

> In a broadcast network, this LSA will be forwarded by the DR of that 
> network, because LSAs are only accepted by adjacent routers in that 
> situation; whereas in MANET, 2-way neighbors can also accept the LSAs. 
> Hence this rule is quite sensible for MANET.
>
> parameters from Dr. Ogier's simulations (30 neighbors per router in 50 
> node network), the probability of 2 routers having the exact same 
> be something in between (1/3)^12 and (1/3)^13).

But the probability of one router having a neighborhood that is a subset of
another router's neighborhood is much larger, which is more relevant.
For example, if routers are positioned randomly in a circle, then routers
that are near the edge of the circle are more likely to have this
property.

> This optimization is useful if there is some special structure to the 
> deployed OSPF network. Simple example: broadcast wireless network with 
> an MDR-other hybrid node, which pumps plenty of LSAs in the MANET 
> segment advertising changes in the other segments of the AS -- the 
> only MDR of this wireless segment does not forward these LSAs again, 
> as the hybrid *gateway* covers everyone else. In general, as the MANET 

So we seem to agree with the rule that an MDR should not forward an LSA if
the neighbor from which it was received covers all neighbors, and that this
rule cannot be eliminated by deselecting MDRs in advance.  You gave one
example of a "special structure" (which is supported by OSPF-MDR), and
I also gave an example above for which the rule is useful.  It seems
we are in agreement, unless you think the MDR selection algorithm should
be modified to deselect MDRs when possible, as I mentioned above.

Richard

---

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

> that are near the edge of the circle are more likely to have this

This case is strongly related to the unit disk graph model. It seems to 
me like an optimization specifically taylored to the intensively 
simulated 2x2 square where a significant number of neighborhoods are 
truncated by the border of the square. I don't think this would 
generalize very well regarding real implementations.

Best regards,
Philippe

---

From: Aniket Desai <[email-masked]>
Date: Mon, 24 Jul 2006 13:37:16 -0400

Hi Dr. Jacquet,

I agree with your statement only in the case of all nodes having 
exactly the same type of wireless interface. However it is possible 
to imagine a hybrid networking scenario, where some nodes will have 
powerful interfaces with long reach. It is also possible that LSAs 
generated by such nodes will be received by routers which have sort 
of *local MDR scope* (please excuse my extremely vague use of 
terminology). Such *local* flooding of the LSAs can be suppressed if 
this kind of hybrid wireless MANET networking scenario emerged in 
future. I am assuming that this long range interface has chosen to 
remain MDR-other for some tactical purposes. Otherwise, if it was 
MDR, then no other local MDR would be selected and the situation 
being described would never arise.

In any case, I think the point being discussed was to examine the 
extra flooding step in Dr. Ogier's flooding algorithm. This step 
takes only O(n) because that's the complexity of comparison of 2 
sorted lists. The flooding algorithm anyway has to scan the entire 
neighbor list, so there is no added complexity. I also mentioned to 
Dr. Ogier that it would perhaps be better not to tweak MDR selection 
algorithm to reduce #MDRs further because a) it weakens the adjacency 
backbone, and b) this still does not eliminate the forwarding check. 
(again: MDR-other generating an LSA and encompassing its neighboring 
MDR's neighborhood completely).

Aniket

At 01:18 PM 7/24/2006, Philippe Jacquet wrote:
>>>parameters from Dr. Ogier's simulations (30 neighbors per router 
>>>in 50 node network), the probability of 2 routers having the exact 
>>>same neighborhood is small (using simple calculations, we can 
>>>verify it to be something in between (1/3)^12 and (1/3)^13).
>>
>>
>This case is strongly related to the unit disk graph model. It seems 
>to me like an optimization specifically taylored to the intensively

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 24 Jul 2006 20:08:21 +0200

Hi Aniket,

I agree that this kind of router will make them elligible to be MDR, and 
if it is the case the selection algorithm should take into account this 
situation. I see this rule as a kind of artificial. I would like to 
notice that the MPR selection does this automatically for a much reduced 
complexity. I may be wrong but the flooding should not need to scan the 
entire neighborhood since it broadcasts the LSA instead of unicasting. 
The adjacency check after ack reception does that but it is on a reduced 
topology. I also still not understand if the rule still take into 
account ACKs and LSA retransmissions. But Dr. Ogier will probably 
comment on this.

Best regards,
Philippe

Aniket Desai wrote:

> exactly the same type of wireless interface. However it is possible to 
> imagine a hybrid networking scenario, where some nodes will have 
> generated by such nodes will be received by routers which have sort of 
> *local MDR scope* (please excuse my extremely vague use of 
> remain MDR-other for some tactical purposes. Otherwise, if it was MDR, 
> then no other local MDR would be selected and the situation being 
> described would never arise.
>
> extra flooding step in Dr. Ogier's flooding algorithm. This step takes 
> only O(n) because that's the complexity of comparison of 2 sorted 
> lists. The flooding algorithm anyway has to scan the entire neighbor 
> list, so there is no added complexity. I also mentioned to Dr. Ogier 
> that it would perhaps be better not to tweak MDR selection algorithm 
> to reduce #MDRs further because a) it weakens the adjacency backbone, 
> and b) this still does not eliminate the forwarding check. (again: 
> MDR-other generating an LSA and encompassing its neighboring MDR's 
> neighborhood completely).
>
> Aniket
>
>>>> 50 node network), the probability of 2 routers having the exact

---

From: Aniket Desai <[email-masked]>
Date: Mon, 24 Jul 2006 14:56:00 -0400

Hi Dr. Jacquet,

You are right that the neighbor scan is done only for adjacent 
neighbors in classical OSPF flooding. Also, this rule can arise in 
certain exceptional circumstances; so I would say that it can be a 
tunable parameter.

I gave the example mentioned earlier, because I do not expect people 
letting a completely autonomous system being run in a typical MANET 
deployment (if at all it happens on large scale in future). One can 
change the MDR selection algorithm to force certain advantageous 
nodes to become MDR (depending upon policies, security, hardware 
capabilities etc.) and let the topology evolve around them; rather 
than letting the evolving topology dictate who becomes MDR. If at all 
that happens, then automatically the property of minimal MDRs is 
lost, and further optimizations can be performed at the time of 
forwarding. However it really depends upon to what degree we have a 
suboptimal MDR deployment. It is not essential that one has to 
implement forwarding optimizations (I agree with that much), and it 
would be nice if we had core forwarding and auxiliary forwarding 
modules in the final RFC.

With regards to MPRs, I am not sure at this point if a similar 
forwarding optimization can be used *on top of* MPR selection 
algorithm. So unfortunately due to my limited knowledge, I cannot 
comment on that part.

Thanks,

Aniket

At 02:08 PM 7/24/2006, Philippe Jacquet wrote:
>Hi Aniket,
>
>I agree that this kind of router will make them elligible to be MDR, 
>and if it is the case the selection algorithm should take into 
>account this situation. I see this rule as a kind of artificial. I 
>would like to notice that the MPR selection does this automatically 
>for a much reduced complexity. I may be wrong but the flooding 
>should not need to scan the entire neighborhood since it broadcasts 
>the LSA instead of unicasting. The adjacency check after ack 
>reception does that but it is on a reduced topology. I also still 
>not understand if the rule still take into account ACKs and LSA 
>retransmissions. But Dr. Ogier will probably comment on this.
>
>Best regards,
>Philippe
>
>Aniket Desai wrote:
>
>>Hi Dr. Jacquet,
>>
>>terminology). Such *local* flooding of the LSAs can be suppressed 
>>if this kind of hybrid wireless MANET networking scenario emerged 
>>in future. I am assuming that this long range interface has chosen 
>>to remain MDR-other for some tactical purposes. Otherwise, if it 
>>was MDR, then no other local MDR would be selected and the 
>>situation being described would never arise.
>>
>>Dr. Ogier that it would perhaps be better not to tweak MDR 
>>selection algorithm to reduce #MDRs further because a) it weakens 
>>the adjacency backbone, and b) this still does not eliminate the 
>>forwarding check. (again: MDR-other generating an LSA and 
>>encompassing its neighboring MDR's neighborhood completely).
>>
>>Aniket
>>
>>>>>in 50 node network), the probability of 2 routers having the 
>>>>>exact same neighborhood is small (using simple calculations, we 
>>>>>can verify it to be something in between (1/3)^12 and (1/3)^13).
>>>>
>>>>
>>>>
>>>This case is strongly related to the unit disk graph model. It 
>>>seems to me like an optimization specifically taylored to the 
>>>intensively simulated 2x2 square where a significant number of 
>>>neighborhoods are truncated by the border of the square. I don't 
>>>think this would generalize very well regarding real implementations.
>>>
>>>
>>>Best regards,
>>>Philippe
>>

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 25 Jul 2006 11:48:54 +0200

Dear Aniket, you are right and MANET also considered this situation from 
the early beginings. For MPR this a kind of natural since the selection 
is *explicit*. For example in RFC 3626, a neighbor holding a willingness 
parameter "WILL_ALWAYS" (level 7) will always be selected as MPR by its 
neighbors, forcing a dedicated set of nodes to be the backbone as you 
mentioned.  

In passing, this discussion points out the fact that there is advantage 
to make flooding kind of independent of the adjacency protocol because 
what is optimal for one may be damageable for the other.

Best regards,
Philippe

Aniket Desai wrote:

> change the MDR selection algorithm to force certain advantageous nodes 
> to become MDR (depending upon policies, security, hardware 
> that happens, then automatically the property of minimal MDRs is lost, 
> and further optimizations can be performed at the time of forwarding. 
> However it really depends upon to what degree we have a suboptimal MDR 
> deployment. It is not essential that one has to implement forwarding 
> optimizations (I agree with that much), and it would be nice if we had 
> core forwarding and auxiliary forwarding modules in the final RFC.
>
>> for a much reduced complexity. I may be wrong but the flooding should 
>> not need to scan the entire neighborhood since it broadcasts the LSA 
>> instead of unicasting. The adjacency check after ack reception does 
>> that but it is on a reduced topology. I also still not understand if 
>> the rule still take into account ACKs and LSA retransmissions. But 
>> Dr. Ogier will probably comment on this.
>>
>> Best regards,
>> Philippe
>>
>> Aniket Desai wrote:
>>
>>> Hi Dr. Jacquet,
>>>
>>> algorithm to reduce #MDRs further because a) it weakens the 
>>> adjacency backbone, and b) this still does not eliminate the

---

From: Aniket Desai <[email-masked]>
Date: Tue, 25 Jul 2006 18:46:08 -0400

Hello Dr. Jacquet,

I would like to comment on both the points:

1) We can also make MDR algorithm deterministic by simply treating 
priority as the highest tie-breaker rather than the MDR status of the 
interface. So in my view, MDR and MPR can both be deterministic.

2) I believe flooding and adjacency mechanisms are already modular in 
Dr. Ogier's draft. According to the draft, an LSA is received by all 
2-way or above neighbors; rather than just the adjacent neighbors 
(which is similar to a TC message being received by everyone in OLSR; 
BUT forwarded only by a select few). Thus the flooding procedure 
already concerns itself with the entire bidirectional neighborhood of 
the router. OSPF adjacencies are only important to preserve its 
acknowledgement/retransmission mechanism. It is certainly possible to 
change the adjacency forming/destroying mechanisms in Dr. Ogier's MDR 
draft and have a denser/sparser adjacency connectivity. I do not 
think that there is any correlation between flooding and adjacencies 
in Dr. Ogier's draft; and he can correct me otherwise.

After giving some thought to the contentious LSA forwarding issue; I 
conclude the following: In a broadcast domain, LSA will be forwarded 
by the DR of the network. Such a DR is adjacent to all routers on the 
network, and hence it has to scan all the neighbors. Equivalently, in 
a MANET situation, the local MDR will be adjacent to a *substantial* 
number of its bidirectional neighbors. Here is where it gets tricky. 
2 adjacent MDRs have a significant number of overlapping neighbors. I 
do not know how one can calculate the ratio of MDR's adjacent 
neighbors and the bidirectional neighbors on an average for the 
entire network. Perhaps Dr. Ogier can illustrate. Coming back to the 
point, if this ratio is high (close to 1), then an average MDR will 
end up scanning a significant portion of its neighborhood and doing 
the extra work will not be too imposing. An MDR-other or BMDR node 
need not do it, and can simply skip this step.

I believe that one can calculate the metric (#adjacent 
neighbors/#bidirectional neighbors) for a typical MDR in the limiting 
case (unit grid and increase the number of nodes). However I am a 
little rusty on probability, and will need some time to calculate 
this if no one else does it meanwhile. I would be very interested in 
finding what that number is, which my intuition tells me, is a 
constant (i.e. no dependence on radio range). On the other hand, I 
can simply follow Edison's lead and try to find the answer with simulations :-)

Finally the reasons why the blind versus intelligent forwarding is 
discussed are: a) MDR selection algorithm may contain inherent 
redundancies, which someone may actually prefer for robustness, and 
b) a hybrid router facing the internet may have an MDR-other 
interface on the local MANET segment and the MDR of that MANET 
segment can use intelligence in determining if the overload of LSAs 
it is receiving deserves to be forwarded. I cannot think of any other 
situation where intelligent forwarding is needed. And given my 
limited knowledge of OLSR, I believe an MPR based solution will need 
the same intelligent forwarding to prevent double flooding of LSAs. 
Please correct me if I am wrong.

Thanks,

Aniket

At 05:48 AM 7/25/2006, Philippe Jacquet wrote:
>Dear Aniket, you are right and MANET also considered this situation 
>from the early beginings. For MPR this a kind of natural since the 
>selection is *explicit*. For example in RFC 3626, a neighbor holding 
>a willingness parameter "WILL_ALWAYS" (level 7) will always be 
>selected as MPR by its neighbors, forcing a dedicated set of nodes 
>to be the backbone as you mentioned.
>
>In passing, this discussion points out the fact that there is 
>advantage to make flooding kind of independent of the adjacency 
>protocol because what is optimal for one may be damageable for the other.
>
>Best regards,
>Philippe
>
>
>
>Aniket Desai wrote:
>
>>Hi Dr. Jacquet,
>>
>>I gave the example mentioned earlier, because I do not expect 
>>people letting a completely autonomous system being run in a 
>>typical MANET deployment (if at all it happens on large scale in 
>>future). One can change the MDR selection algorithm to force 
>>certain advantageous nodes to become MDR (depending upon policies, 
>>security, hardware capabilities etc.) and let the topology evolve 
>>around them; rather than letting the evolving topology dictate who 
>>becomes MDR. If at all that happens, then automatically the 
>>property of minimal MDRs is lost, and further optimizations can be 
>>performed at the time of forwarding. However it really depends upon 
>>to what degree we have a suboptimal MDR deployment. It is not 
>>essential that one has to implement forwarding optimizations (I 
>>agree with that much), and it would be nice if we had core 
>>forwarding and auxiliary forwarding modules in the final RFC.
>>
>>>I agree that this kind of router will make them elligible to be 
>>>MDR, and if it is the case the selection algorithm should take 
>>>into account this situation. I see this rule as a kind of 
>>>artificial. I would like to notice that the MPR selection does 
>>>this automatically for a much reduced complexity. I may be wrong 
>>>but the flooding should not need to scan the entire neighborhood 
>>>since it broadcasts the LSA instead of unicasting. The adjacency 
>>>check after ack reception does that but it is on a reduced 
>>>>exactly the same type of wireless interface. However it is 
>>>>possible to imagine a hybrid networking scenario, where some 
>>>>nodes will have powerful interfaces with long reach. It is also 
>>>>possible that LSAs generated by such nodes will be received by 
>>>>routers which have sort of *local MDR scope* (please excuse my 
>>>>extremely vague use of terminology). Such *local* flooding of the 
>>>>LSAs can be suppressed if this kind of hybrid wireless MANET 
>>>>networking scenario emerged in future. I am assuming that this 
>>>>long range interface has chosen to remain MDR-other for some 
>>>>tactical purposes. Otherwise, if it was MDR, then no other local 
>>>>MDR would be selected and the situation being described would never arise.
>>>>
>>>>sorted lists. The flooding algorithm anyway has to scan the 
>>>>entire neighbor list, so there is no added complexity. I also 
>>>>mentioned to Dr. Ogier that it would perhaps be better not to 
>>>>tweak MDR selection algorithm to reduce #MDRs further because a) 
>>>>it weakens the adjacency backbone, and b) this still does not 
>>>>eliminate the forwarding check. (again: MDR-other generating an 
>>>>LSA and encompassing its neighboring MDR's neighborhood completely).
>>>>
>>>>Aniket
>>>>
>>>>>>>However in a purely random network, using the dense 
>>>>>>>connectivity parameters from Dr. Ogier's simulations (30 
>>>>>>>neighbors per router in 50 node network), the probability of 2 
>>>>>>>routers having the exact same neighborhood is small (using 
>>>>>>>simple calculations, we can verify it to be something in 
>>>>>>>between (1/3)^12 and (1/3)^13).
>>>>>>
>>>>>>
>>>>>>
>>>>>>

---

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

Philippe Jacquet wrote:

>>> neighborhood is small (using simple calculations, we can verify it 
>>> to be something in between (1/3)^12 and (1/3)^13).
>>
>>
>>

So you are saying that the optimization is specifically tailored to
a unit disk or a 2x2 square (where you assume the radio range is
one unit).  More generally, one might say the optimization is
tailored to dense networks with a small diameter.
Such networks are important, as are sparse networks and large
diameter networks.  (Also, I see that Aniket explained how this
optimization is important in hybrid networks.)
You may be correct that this optimization helps performance the most
in dense networks with a small diameter, but since such networks can
occur and should be supported, I think that is enough reason to use
the optimization.  The goal is to achieve good performance in a wide
variety of scenarios, including dense networks.

Richard

---

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

Philippe Jacquet wrote:

> selection is *explicit*. For example in RFC 3626, a neighbor holding a 
> willingness parameter "WILL_ALWAYS" (level 7) will always be selected 
> as MPR by its neighbors, forcing a dedicated set of nodes to be the 
> backbone as you mentioned.

As Aniket mentioned, the same can be done with MDRs.  OSPF already has a
parameter (Router Priority) for this purpose.  Since we are extending OSPF,
it makes sense to use Router Priority (as OSPF-MDR does) instead of
re-inventing this parameter and calling it something else (Willingness).

> protocol because what is optimal for one may be damageable for the other.

OSPF does not make flooding independent of adjacencies, and for good
reasons.  (It makes sense to align adjacencies with flooding relays,
since LSAs are retransmitted on adjacencies, and it makes sense to
retransmit LSAs between the relays that flood the LSAs.)
So I think you would need stronger arguments and/or extensive simulation
results to conclude that adjacencies should be selected
independently of flooding relays.

Richard