Subject: Re: [manet] (no subject) CDS vs. MPRs

From: Richard Ogier <[email-masked]>
Date: Mon, 01 Mar 2004 10:44:03 -0800

All,

In this message I will try to summarize and address several comments
and questions recently posted regarding MPR/CDS flooding in MANETs,
and to suggest what I think is a good solution, based on some
preliminary simulations I did over the weekend. (I plan to post
more complete simulation results sometime next week.)
I am not at the meeting this week, but hopefully some of these
comments will be addressed at the meeting.

The recent comments I am addressing include the following:

1. Some nodes may not be able to determine the neighbor (previous hop)
   that transmitted the flooded packet.
2. Reliability (i.e., packet loss) is a concern.
3. A CDS can be computed based on 2-hop neighbor information,
   without having to compute or advertise MPRs.

Making the forwarding decision independent of the previous hop
not only addresses item 1, but also improves reliability (item 2).
This is because a given flooded packet might not be received
from a particular neighbor (e.g., MPR selector) due
to a collision or bad link, but might be received from some
other neighbor (in which case the node can still relay
the packet if the forwarding decision is independent of
the previous hop).

A second factor that can influence reliability is the
selection of MPRs using the greedy algorithm (based on
differential degree). This results in MPRs that are close
to the perimeter of the reception region and are therefore
more likely to be short lived or unstable. This issue can
be addressed by using min ID instead of the greedy algorithm.
(Using min ID also results in a faster, simpler algorithm.)

If min ID is used, then another advantage is that nodes can
select themselves as MPRs (or as CDS nodes) based only
on 2-hop neighbor information. This allows faster recovery
from link breakages, since a node can select itself as an
MPR or CDS node immediately when a neighbor node reports
a link breakage.

Therefore, as someone suggested, it might be best to have an
algorithm in which each node decides whether it should be in
the CDS based on 2-hop neighbor information, as long as:

1. The number of the nodes in the CDS is close to the
   minimum achievable based on this information.
2. Packets that are flooded via the CDS reach all nodes
   along paths that are approximately min-hop.

Moreover, as I suggested recently, we can require all nodes
to participate in the CDS flooding algorithm, but allow a node
the OPTION to also forward a flooded packet if the node is
a (self-selected) MPR of the first neighbor from which
the packet was received.  This option can be used if
the node can determine the previous hop, and if it is
important for the packet to be flooded along min-hop paths.

Over the weekend, I ran some simulations to compare a
CDS algorithm based on 2-hop neighbor information, to
the MPR-based CDS defined by Rules 1 and 2 in the INRIA report
http://www.inria.fr/rrrt/rr-4597.html

(Note that the MPR-based CDS is NOT based only on 2-hop neighbor
information, but actually 3-hop neighbor information, since
MPRs are based on 2-hop information and are advertised to
neighbors.)

500 nodes were randomly placed in a unit square, with
transmission radius equal to 0.4, which resulted in
a network of diameter 4. The results are averaged
over 10 random graphs.  The following measures are compared
for the MPR-based CDS algorithm and the CDS algorithm
based only on 2-hop neighbor information (which will be
described in my report next week).

- Average size of the CDS
- Average length (hops) of min-hop paths between all pairs
- Average length (hops) of CDS paths between all pairs (using
  only CDS nodes as intermediate nodes).
- Ratio of the above two average lengths

Results for the MPR-based CDS:
  Average CDS size: 19.10
  Average length of min-hop paths: 1.808
  Average length of CDS paths: 1.960
  Ratio of CDS hops to min hops: 1.084 (8.4% increase)

Results for the CDS based only on 2-hop neighbor info:
  Average CDS size: 15.80
  Average length of min-hop paths: 1.808
  Average length of CDS paths: 1.986
  Ratio of CDS hops to min hops: 1.098 (9.8% increase)

Other CDS algorithms can be used, which may result in
more CDS nodes but shorter paths.
BTW, the average size of the CDS consisting of all MPRs was
about 200.

The above results are preliminary, and simulations are needed
with mobile nodes that measure packet loss, etc.
But the above results and arguments indicate that
the best solution might be to use a CDS based only
on 2-hop neighbor information.

Regards,
Richard

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