Subject: [Ospf-manet] Re: Ospf-manet Digest, Vol 10, Issue 1

From: Aniket Desai <[email-masked]>
Date: Tue, 12 Sep 2006 15:33:26 -0400

Hello,

There are some issues with this simplified multicast retransmission 
mechanism. I am talking by treating Ogier draft as a reference, 
according to which, each router will acknowledge a multicast LSA only 
once. This rule is quite sensible, because no matter how much 
optimization is carried out, an average interface will hear each LSA 
more than once due to inherent broadcast redundancy. It has no way of 
knowing which is retransmitted, since the retransmitted LSA is also 
multicast now. You can argue that the router can examine the source 
of this packet, find the neighbor, examine if this neighbor is 
adjacent and maybe examine a special bit in the LSA that indicates 
whether this is nth flood of this LSA (where n > 1). In this case: a) 
more processing is done, and b) even if there was only 1 neighbor 
which should have sent an ack, there can potentially be multiple 
neighbors which will send the ack. Thus there is tradeoff even from 
overhead perspective. Thus what advantage that can be gained by 
saving unicast retransmissions will be lost by redundant 
acknowledgements. It may prove beneficial to do this in certain 
cases, but this is not conformant to how I interpret OSPF's 
retransmission mechanism (OSPF does not do multicast retransmissions 
even in broadcast domains...why introduce this for MANET?).

Also, the flooding algorithm as implemented right now can easily be 
optimized. In my view, the following should be a sketch of the algorithm:

1. If the interface is MANET:

- Determine the MDR status of this interface.

If MDR:
Scan the entire bidirectional neighborhood. Put LSA on appropriate 
retransmission list. For each neighbor, check if an ack for this LSA 
has been received. Check if each neighbor is in sender's RNL. Do a 
conditional flooding at the end.

If other:
Scan only the adjacent neighborhood and put LSA on appropriate 
retransmission list.

This way, only MDR nodes will be scanning the whole of neighborhood, 
which any legacy OSPFv3 router would have done anyway. Right now, the 
check to determine the MDR status is done at the very end, which 
means an MDR-other interface will unnecessarily scan the entire 
neighbor list. This can be avoided. If someone still has qualms about 
that, the first step can be modified as:

If MDR:
Scan adjacent neighborhood, put LSA on retransmission list and 
*blindly flood* it out. This saves computational overhead at the cost 
of perhaps some extra overhead. It may not be a bad idea for 
robustness purposes afterall.

I don't think OSPF intends to perform multicast retransmissions. If 
there is a clever way by which multicast retransmissions can be sent 
out, it definitely needs more elaboration and an outline. This means: 
a) how retransmission and floods should be done, b) how 
acknowledgements should be sent out, c) how incoming LSA are 
processed, etc. Also, each node does not have to do an O(n) search. 
Since for an n node network, adjacency graph should be O(n), using 
the easy version of flooding (MDR scanning only its adjacencies), the 
number of scans can be much reduced. Finally, neighbor scanning is 
unavoidable, because each interface must put an LSA on the 
retransmission list anyway.

In a really bad situation, where LSAs are lost frequently and 
generated almost immediately, *no-ack* can be used in the OSPF 
options fields. Now, the MDR can do a blind flooding in the simplest case.

Thanks,

Aniket

At 12:00 PM 9/12/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. Re: Mistake to avoid when simulating OSPF-MDR (Philippe Jacquet)
>
>
>----------------------------------------------------------------------
>
>Message: 1
>Date: Tue, 12 Sep 2006 16:03:02 +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,
>
>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
>
>
>End of Ospf-manet Digest, Vol 10, Issue 1
>*****************************************

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

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 18 Sep 2006 13:37:53 +0200

Hi!

Your email opens very interesting perspectives, but I did not understand 
all of the details.

About the use of broadcast in LSA retransmission. It was known from the 
begining that the key of manet OSPF is in the extensive use of broadcast 
transmission. Thus it should be natural that broadcast retransmissions 
should be beneficial as well (ACK are also broadcasted). Since there is 
no distinction between transmission and retransmission I don't see the  
point about introducing a specific bit in the LSA.

About the benefit, it should be pretty clear. If you have an adjacent 
neighborhood of size M=100, with a failure probability of p=0.5, then 
you would need to open pM=50 retransmission procedures, each of them 
leading to an average of 1/(1-p)=2 retransmissions, i.e. 100 effective 
retransmissions. With broadcast retransmissions you will have an average 
of log M/log (1/p)<6 retransmissions which is more efficient.

Thanks,
Philippe

Aniket Desai wrote:

> multicast now. You can argue that the router can examine the source of 
> this packet, find the neighbor, examine if this neighbor is adjacent 
> and maybe examine a special bit in the LSA that indicates whether this 
> is nth flood of this LSA (where n > 1). In this case: a) more 
> processing is done, and b) even if there was only 1 neighbor which 
> should have sent an ack, there can potentially be multiple neighbors 
> which will send the ack. Thus there is tradeoff even from overhead 
> perspective. Thus what advantage that can be gained by saving unicast 
> retransmissions will be lost by redundant acknowledgements. It may 
> prove beneficial to do this in certain cases, but this is not 
> conformant to how I interpret OSPF's retransmission mechanism (OSPF 
> does not do multicast retransmissions even in broadcast domains...why 
> introduce this for MANET?).
>
> check to determine the MDR status is done at the very end, which means 
> an MDR-other interface will unnecessarily scan the entire neighbor 
> list. This can be avoided. If someone still has qualms about that, the 
> first step can be modified as:
>
> If MDR:
> Since for an n node network, adjacency graph should be O(n), using the 
> easy version of flooding (MDR scanning only its adjacencies), the 
> generated almost immediately, *no-ack* can be used in the OSPF options 
> fields. Now, the MDR can do a blind flooding in the simplest case.
>
> Thanks,
>
> Aniket
>

---

From: Richard Ogier <[email-masked]>
Date: Mon, 18 Sep 2006 15:24:31 -0700

Philippe,

Philippe Jacquet wrote:

> Hi!
>
> Your email opens very interesting perspectives, but I did not 
> understand all of the details.
>
> About the use of broadcast in LSA retransmission. It was known from 
> the begining that the key of manet OSPF is in the extensive use of 
> broadcast transmission. Thus it should be natural that broadcast 
> retransmissions should be beneficial as well (ACK are also 
> broadcasted). Since there is no distinction between transmission and 
> retransmission I don't see the  point about introducing a specific bit 
> in the LSA.

There is no distinction between transmitted and retransmitted LSAs if 
all LSAs are Acked,
which may be what you are assuming.  But as Aniket pointed out, we are 
trying to
reduce the number of Acks by having each router Ack each multicast LSA 
only once.
To do this, a router must know whether a received LSA is a 
retransmission, which is
possible if all retransmitted LSAs are unicast.  As Aniket mentioned, it 
is possible to
indicate via a bit that a multicast LSA is a retransmission, but this 
would increase the
number of routers that must Ack.  (Another method is mentioned below.)

> retransmissions. With broadcast retransmissions you will have an 
> average of log M/log (1/p)<6 retransmissions which is more efficient.

This is a valid point, and multicast retransmissions can be done with 
either MDRs or MPRs.
But I think the failure probability will be smaller than 0.5 if adjacent 
neighbors are selected
using a link quality measure.
An MDR could have a large number of adjacent neighbors, so multicasting 
retransmitted
LSAs could potentially reduce overhead.  But this should be done in a 
way that avoids
increasing the Ack overhead significantly.  One way to do this is to 
multicast retransmitted
LSAs and include in the LSU packet a list of neighbors that should Ack 
each LSA
in the LSU.  This would require a change in the LSU format.

To summarize, we have discussed four ways to retransmit and ack LSAs:

1. Ack the first reception of an LSA, and ack duplicate LSAs received
as a unicast.  Retransmited LSAs are unicast (OSPF-MDR does this).

2. Ack every received LSA.
Retransmitted LSAs are multicast (Philippe proposes this).

3. Ack the first reception of an LSA, and ack each retransmitted LSA as
indicated by a bit.  Retransmitted LSAs are multicast (Aniket mentioned 
this).

4. Ack the first reception of an LSA, and ack any LSA received in an LSU
that contains the router in the Ack list.  Retransmitted LSAs are multicast.

The last method requires a significant change to the LSU format, but methods
2 and 3 can be evaluated in simulations, with either MDRs or MPRs.

Richard