Subject: Re: performance comparaison between Ad Hoc routing protocols

From: Ram Ramanathan <[email-masked]>
Date: Wed, 06 Feb 2002 16:29:15 -0500

> 
>   - Although control traffic is not a quality-of-service measure, a protocol 
>     that generates less control traffic:
> 
>     - uses less energy,
>     - is more likely to scale to a larger number of nodes,
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Why so?

The "pure flooding" protocol (in which every data packet is flooded
throughout  the network) consumes zero overhead. Does that mean it
scales to infinite number of nodes? :)

The flippancy of the above example notwithstanding, one should really
look at the TOTAL OVERHEAD (sum of control message overhead + sub-optimal
route overhead (extra bandwidth wasted due to longer paths). There are
many instances in my experience where a mechanism that takes more
overhead ends up doing better in terms of user metrics.

For a more formal treatment of TOTAL OVERHEAD, see

Making Link State Routing Scale for Ad Hoc Networks, in Mobihoc 2001 by
C. Santivanez et al

On the Scalability of Routing for Ad Hoc Networks, to appear in Infocom 2002,
by C. Santivanez et al

>     - is more likely to perform well in lower bandwidth radios such
>       as those used by the military.
> 
> 
> -----------------------
> Richard Ogier
> Sr. Research Engineer
> SRI International
> 333 Ravenswood Ave.
> Menlo Park, CA 94025
> Tel: 650-859-4216
> Fax: 650-859-4812
> Email: [email-masked]
> ------------------------
>

---

From: [email-masked]
Date: Wed, 06 Feb 2002 12:41:29 -0800

> hi all body
> is there any new studies wich made a comparaison between all routing
> protocols (espicially AODV and OLSR) .
> thank you 
> best regards

I ran some ns-2 simulations comparing TBRPF to OLSR and AODV,
using the corrected ns-2 code for OLSR.  The simulation results 
can be found at the TBRPF web site: 
http://www.erg.sri.com/projects/tbrpf/

The results are summarized below.  Comments are welcome.

Protocols compared:

   - TBRPF code for ns-2.1b8
     Available from http://www.erg.sri.com/projects/tbrpf/sourcecode.html
     Uses the same 'C' code as our Linux implementation

   - OLSR code for ns-2.1b7
     Available from http://hipercom.inria.fr/olsr/
     Bug affecting packet size was fixed.

   - AODV code for ns-2.1b8
     Available from http://www.cs.ucsb.edu/~eroyer/aodv.html

   - Link-layer notification was not used for any of the protocols
     (it is available with the TBRPF and AODV code but not with the OLSR code).

Simulation model:

  - ns-2 version 2.1b8
  - WaveLAN IEEE 802.11 MAC with rate 2Mb/s and range 250m
  - 50 and 100 nodes
  - Two area sizes: 670m x 670m and 1500m x 300m
  - Mobility model: No mobility, and random waypoint model with 0 pause 
    time and maximum speed 20 m/s.
  - 20 simultaneous CBR traffic streams:
    - Source and destination of each stream are selected randomly 
    - Duration of each stream is 30 seconds
    - Size of each data packet is 512 bytes
    - Packet generation rate per stream is increased from 2 to 8 packets/s
  - Each simulation was run for 500 simulated seconds.

Rationale for the simulation parameters: 

  - We chose a wide range of characteristics to ensure that we did not 
    use only scenarios that favor TBRPF or proactive protocols (no 
    mobility and high mobility, square area and long rectangular area, 
    50 and 100 nodes).  
  - We chose a stream duration of 30s to provide a moderate amount of 
    traffic dynamics without giving too much advantage to proactive 
    protocols.  (Note that the Aalborg Univ. study used 10s for 
    comparison of OLSR and AODV, which gives proactive protocols more 
    advantage than 30s)
    
Summary of results:

  - In every scenario, TBRPF achieved the highest delivery percentage of all
    three protocols: up to 15% more than OLSR and 23% more than AODV.

  - In every scenario, TBRPF generated significantly less routing control 
    traffic than the other protocols: up to 60% less than OLSR and 36% 
    less than AODV.  This is true despite the fact that TBRPF sends
    HELLOs twice as frequently as OLSR.
    
  - TBRPF and OLSR achieved similar delay curves.  When the network was 
    congested, AODV tended to achieve smaller delays than the other protocols 
    with mobility, and larger delays with no mobility.

Remarks:

  - This study did not use link-layer notification.  It is important to 
    also compare the protocols with link-layer notification, since this 
    allows one to achieve a delivery fraction close to 100%.
    (A comparison of TBRPF with AODV using link-layer notification can
    be also be found at the TBRPF web site.)

    - uses less energy,

-----------------------
Richard Ogier
Sr. Research Engineer
SRI International
333 Ravenswood Ave.
Menlo Park, CA 94025
Tel: 650-859-4216
Fax: 650-859-4812
Email: [email-masked]
------------------------

---

From: [email-masked]
Date: Wed, 06 Feb 2002 19:02:53 -0800

Hi Ram,

> route overhead (extra bandwidth wasted due to longer paths). 

I agree that overhead due to suboptimal routes should be considered.
Our simulation results at the TBRPF web site include graphs that
show the average hop count.  TBRPF and OLSR usually use shorter paths
than AODV, and in our simulations with link-layer notification,
TBRPF typically uses paths that are 10-15% shorter than AODV.

One problem with total overhead is that it is highly dependent on the
amount of data traffic sent, whereas routing control traffic is often
fairly independent of this.

> There are many instances in my experience where a mechanism that takes more

I'm not sure if you mean "total overhead" here.  
But since the min-hop path is not always the best path, it is certainly
possible for a protocol to perform better by using longer paths
(and thus more total overhead).  Full flooding also achieves better 
reliability by using more total overhead than other flooding mechanisms.
And the following example, in which neither of the two disjoint paths
from 1 to 4 uses a min-hop path, shows that sometimes throughput can be 
increased by using more total overhead:

       5-6 
      /   \ 
     /     \ 
1 - 2 - 3 - 4 
 \     / 
  \   / 
   6-7

Richard