Subject: RE: [manet] MPRF [flooding protocol] document initial revision

From: "Spagnolo, Phillip A" <[email-masked]>
Date: Tue, 24 Feb 2004 06:23:33 -0800

Richard,
You are correct on the WOSPF draft.  We suggest the following change to
the draft.  This should be an easy change.  Thanks for helping.

Phil

_______________________________________________________________________
5.  Protocol Data Structures

   This section defines extensions to Section 5 of [OSPF].

          LSF duplicate table

               The Link State Flood duplicate table keeps track of which
               LSFs have been seen.  Each tuple in the table consists of
               the originator's Router ID, the flooding sequence number,
               the time at which the entry expires, and a flag that 
               indicates whether the LSF has been flooded.  The table
               should be empty upon initialization.

13.1.  LSF message generation

   Each wireless interface originates an LSF every LSF_INTERVAL.  Each
   time a node generates an LSF it MUST increment the flooding sequence
   number and add the LSF to the duplicate table.  In this table, the
   node records a duplicate tuple: (originator address, flooding
   sequence number, expiration time, flooded flag).  The flooded flag 
   denotes whether the LSF has been flooded by this node before.  The 
   LSF MUST be removed from the duplicate table after it expires.

13.2.  LSF message processing

   Each incoming LSF is searched for in the duplicate table.

     1    If the LSF is in the duplicate table, or if the LSF is older 
          than the LSF found in the table proceed with the bullets.  
          An LSF is know to be older if the sequence number of the LSF 
          in the table is greater than the received LSF's sequence 
          number.  Standard modulo sequence number comparisons should 
          be applied.
            a.  If the sender is in the MPR selector table, but the 
                flooded flag is not TRUE in the duplicate table then 
                the LSF is flooded out all MANET interfaces, the

                flooded flag is set to TRUE in the duplicate table, 
                and the LSF packet is discarded
            b.  Else, The LSF packet is discarded.
	    
     2    Else, the LSF is added to the LSF duplicate table, and the
          LSAs are processed according to section 13.3.
            a.  If the sender is in the MPR selector table, the LSF is
                flooded out all MANET interfaces, and the flooded flag
                is set to TRUE in the duplicate table.
            b.  Else, the flooded flag is set to FALSE in the 
                duplicate table.

> -----Original Message-----
> From: Richard Ogier [mailto:[email-masked]] 
> Sent: Saturday, February 21, 2004 8:47 AM
> To: Charles E. Perkins
> Cc: Mobile Ad Hoc IETF working group
> Subject: Re: [manet] MPRF [flooding protocol] document 
> initial revision
> 
> 
> Here is an example where the MPRF protocol does not work.
> (Although it can be fixed as explained below.)
> 
> 
>       8
>     /   \
>    2-----5
>   / \   / \
>  /   \ /   \
> 1     /     7
>  \   / \   /
>   \ /   \ /
>    3-----6
>     \   /
>       9
> 
> 
> Node 1 is the source (originator of flooded packets),
> and its MPRs are nodes 2 and 3.
> Node 2 selects node 6 as MPR (to cover 3, 7, and 9)
> Node 3 selects node 5 as MPR (to cover 2, 7, and 8).
> 
> Node 1 originates a packet, which is relayed by nodes 2 and 3.
> Suppose node 5 receives the packet first from node 2, then 
> from node 3.
> Suppose node 6 receives the packet first from node 3, then 
> from node 2.
> (I explain below how this is possible.)
> Since node 2 is not an MPR selector of node 5, node 5 does not relay
> the packet when it is received from node 2, but creates an entry
> in the Flooding History (step 5.1 in the draft).
> Then, when node 5 receives the packet from node 3 (its MPR selector),
> node 5 ignores the packet (step 2 in the draft).
> Therefore, node 5 does not relay the packet.
> Similarly, node 6 does not relay the packet.
> Therefore, node 7 never receives the packet.
> 
> I think the solution is for each node to remember
> which flooded packets it has already transmitted.
> If a node receives a flooded packet from an MPR selector,
> and has not yet transmitted the same packet, then it
> should relay the packet.
> 
> I think the same problem exists in
>   draft-spagnolo-manet-ospf-wireless-interface-00
> 
> I can think of 3 situations that can result in the
> above example (in which node 5 receives the packet first from
> node 2, and node 6 receives the packet first from node 3):
> 
>   1. Very long propagation delays.
>   2. As stated in the Introduction of the draft, link layer
>      broadcast can be accomplished using iterated unicast.
>   3. If the flooded packet is sent reliably to all neighbors using
>      ACKs with retransmissions, then the first transmission from
>      node 2 (resp. 3) might be received only by node 5 (resp. 6).
> 
> Regards,
> Richard
> 
> P.S. Regarding the terms "reflood" and "retransmit".
> 
> "Reflood" means to flood the packet again to all nodes.
> RFC 2328 for OSPF uses this term correctly, but some
> people have recently used it to mean "relay".
> 
> "Retransmit" means for the same node to transmit the packet again,
> usually because an ACK was not received.
> It will be very confusing when we talk about reliable flooding
> with ACKs, if we use the word "retransmit" to mean both
> retransmission from the same node, and relaying a packet
> received from another node.
> 
> When talking about a node relaying a packet, I suggest using
> either the term "relay" or "transmit".
> 
> 
> 
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/manet
> 

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

---

From: "Richard Ogier" <[email-masked]>
Date: Wed, 25 Feb 2004 08:19:14 -0800

To Phil and the authors of the MPRF draft:

Although your suggested modification is simple,
it is also *very* inefficient.  For example,
in a simulation I ran for a network with 500
nodes and a diameter of 4 hops, the modification
you suggested results in 200 transmissions of
a single flooded packet, whereas the original
(incorrect) version results in only 21 transmissions.

The reason for the inefficiency is easy to see.
Since each node computes its MPRs independently,
if each node computes an average of 6 MPRs, then
to reach all nodes 4 hops away can require
6*6*6 = 216 transmissions. This is because each
MPR of each MPR of each MPR of the originator
must transmit the packet.

To fix this, I suggest the following modification.
The key is to choose a unique neighbor that transmitted
a given flooded packet, one that different receivers
will agree on.  In the original version, each node
selected the neighbor from which the flooded packet was
*first* received, but as my example showed, different
receivers may not agree on this choice.

One solution is for each node to select the neighbor
with the minimum address from which the flooded packet
was received, and to relay the packet only if this
neighbor is an MPR selector.  However, this is still
not efficient because a neighbor selected in this manner
may actually be farther from the originator than
the receiving node. Ideally, only neighbors that are
closer to the originator should be considered.
Therfore, it makes sense to consider the TTL of the
received flooded packet when making the decision to forward.

Therefore, in my suggested modification, each node selects
the neighbor with lexicographic maximum value of
(TTL, neighbor address) from which a given flooded packet
(identified by the FPI) was received, and relays the packet
if and only if this selected neighbor is an MPR selector.
In the example I gave, only node 5 would relay the
packet, since node 3 is its MPR selector, assuming that
node 3 has a larger address than node 2.
This requires that the Flooding History Table (for the MPRF draft)
or the LSF Duplicate Table (for the WOSPF draft) include the
following additional information for each flooded packet:
the TTL and the address of the neighbor from which the
packet was received.

As with distance-vector routing, there is a timing issue here.
If a node immediately forwards a flooded packet the first time
it is received from an MPR selector, then it might later receive
the same packet from a neighbor with larger value of
(TTL, neighbor address) that is not an MPR selector, in which case
it did not have to relay the packet. Therefore, if a node receives
the same flooded packet from multiple neighbors before it relays
the packet, it should select the neighbor as described above,
and relay the packet if and only if the selected neighbor
is an MPR selector.  Therefore, it may be beneficial to wait
a small amount of time before deciding whether to forward
a received flooded packet.

As stated in draft-ogier-manet-ospf-extension-00.txt,
for link-state routing protocols that can compute the next hop p(u)
to each destination u, where I assume that p(u) is selected
consistently by all nodes, e.g., using router ID to break ties,
then a better flooding rule is to relay a received (non-duplicate)
flooded packet if and only if p(u) is an MPR selector, regardless of
which neighbor the packet was received from.  (So nodes do not have
to know which neighbor the packet was received from.)  Assuming that
the MANET extension of OSPF uses MPRs for flooding LSAs, I think
this is the flooding scheme that should be used.  If I am correct,
then this rule should be used in both Cisco's OSPF extension and
in your WOSPF draft.  (If you do this, then please give me credit
as appropriate.)

Regards,
Richard