Subject: [manet] scalability in ad hoc networks

From: Dmitri Deshun Perkins <[email-masked]>
Date: Tue, 17 Sep 2002 16:35:54 -0400 (EDT)

Hello:

I have read several papers on routing in ad hoc networks (i.e., manet
and sensor). The term scalability is often used. Does the manet group
have some specific idea of what is meant by scalable? I have a few
questions here.

1. Are we saying an algorithm is scalable depending on its performance
   (e.g., packet delivery ratio) versus network density? traffic load?
   control overhead? or some combination of performance measures?

2. What is considered a small, medium, or large network?

These questions are motivated by some simulations done using
glomosim. For example, for various network sizes, mobility
patterns and traffic loads, protocol A and protocol B achieve very
very similar throughput, but protocol A produces significantly more
control packets.

3. While, we may conclude that protocol B uses control packet more
efficienty (number of packet deliver per control packet), can we say
that is more scalable since the performance of both protocols is the
same (at least from an external view)? That is, both protocols
deliver the same number of packets, but one must work harder to do
so, which may impact battery usage.

Thanks for your time and thoughtful responses.

==================================================
Dmitri D. Perkins, Assistant Professor
The Center for Advanced Computer Studies
University of Louisiana at Lafayette
P.O. Box 44330, Lafayette, LA 70503

office: (337)482-6732   fax: (337)482-5791
http://www.cacs.louisiana.edu/~perkins
==================================================

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

---

From: Phillip Neumiller <[email-masked]>
Date: Tue, 17 Sep 2002 18:02:18 -0400

Hi Dmitri,

I can not speak for the MANET list, but I hope
some others do on this important topic.  From a 
practical  perspective, EVERYTHING MATTERS!  I don't
think it is  appropriate to talk about "REAL" ad hoc
network scalability without the following in hand
(but that's just my opinion and I am often wrong):

o **The traffic model**, i.e. how much peer-to-peer 
  versus how much Internet bound.  You can ignore
  the latter like much of the work so far -OR- you
  can take it seriously.  In my view, MANETs are
  most useful when they DYNAMICALLY extend the
  global Internet.  Some examples here would be
  Exponential Poisson, Self Similar or Periodic
  inter-arrival times (and/or packet lengths)
  roughly estimating video, voice, and data traffic. 
  Perhaps even more important is the mobile node
  density / geo-spacial distribution which can 
  severely affect unfairness and congestion in 
  CSMA type MACs like 802.11b.  Once you have
  a variety of traffic models in your hand, you
  need to determine what are realistic connection
  models, i.e. what is the mean number of hops
  for my peers?  What is the network diameter that
  I typically reside in?  Are there bottleneck when
  I gateway through other nodes to the Internet?
  Does my protocol use hops as its only routing
  metric and offer me congested routes?  What is the
  mean route convergence time under nominal load?
  What is the degredation curve for residual bandwidth
  as network diameter increases (assuming nominally
  active nodes with 1/2 diameter median hop)?

o **The propagation model**.  Is deployment indoors or 
  out?  What is the morphology?  This interacts with 
  mobility model.  Some examples here would be
  Urban, Suburban, Dense Urban, with varying
  degrees of Foliage.  Don't forget Rayleigh,
  Ricean, and Log normal shadow fading.  Better
  consider hilly, and flat morphologies as well.
  Indoors, consider useable data rates with their
  associated ranges for acceptable BERs, ambient
  interference, wall, cubicle penetration, etc.
  How do these devices react to high speed mobility
  and multi-path and dopler?

o **Mobility model**.  How are these devices coming
  and going (how small are the cells)?  
  Every radio is different, and all of them cause
  different things to happen to the link layers
  and TCP/IP.  Some example mobility models may
  include Random, Markovian, Pedestrian, column,
  linear, urban, exponential correlated.  Randwom
  waypoint sardeen testing is good too.

If you want an anti-septic definition see the
Kumar-Gupta paper or the MIT results and many others.
I find these definitions of scalability only of
limited use because they tend to bound scalability
asymptotically but mean almost nothing in practical 
scale networks of 10s of nodes.  In practical ad
hoc networks you  will likely run into one of the
many above factors before you run into asymptotic
scalability of your routing protocols.  

NOTE:  Many of the above issues took MANY years to 
resolve for cellular networks, and it is un-realistic
to assume they will be resolved quickly for ad hoc
networks.  Errors propagate in nasty ways in ad hoc
networks.  Hopping over three 10E-02 BER links in
a row becomes a (.9) ^ 3 = 72% reliable.  This 
adds up quickly all over your network.  Many routing
algorithms work best if links are assumed bi-directional,
and to ensure this reduces cell size and range.  

NOTE:  It is very important to use an on-demand
protocol (reactive) and everybody seems to
agree to that on the MANET list as far as I tell.

NOTE:  The MAC can have a dramatic affect on MANET
performance in many practical situations.

NOTE:  Nobody in the IETF wants to work on L2 triggers
to foster better cross-layer interaction between
RF L2s and the IP stack.  (a pet peeve of mine that is
likely to remain for the foreseeable future :-)

NOTE:  If smart antenna technology could be made
in a tiny package it would solve the lion share of
problems that plauge MANET scalability!!!  No more
hidden nodes, no more exposed nodes, incredible data 
rates at long range because of improved SNR, less
self interference, etc. etc. etc.

NOTE:  Key distribution is VERY tricky in ad hoc
networks and a research topic.  Security in general
for ad hoc networks is a mystery as far as key and/or
certificate management scalability goes.

I hope this helps frame some aspects of the scalability
problem in a practical way.  Much of the work to date
has been theoretical, which OK, but I sure would like
to see some more practical results.  The IEEE has
published a few papers with test bed results, but often
a large number of the above factors were not part of
the controlled experiments.  Let the experimental
stage of MANET begin!  Gentlemen, turn off your 
simulators!!!!

Thanks and best regards,

Phil Neumiller
MeshNetworks, Inc.

-----Original Message-----
From: Dmitri Deshun Perkins [mailto:[email-masked]]
Sent: Tuesday, September 17, 2002 4:36 PM
To: [email-masked]
Subject: [manet] scalability in ad hoc networks

Hello:

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet
****************************************************************************
This e-mail is intended only for the addressee named above and may contain
confidential, proprietary or privileged information. If you are not the
named addressee or the person responsible for delivering the message to the
named addressee, please inform us promptly by reply e-mail, then delete the
e-mail and destroy any printed copy. The contents should not be disclosed to
anyone and no copies should be made. We take reasonable precautions to
ensure that our emails are virus free. However we accept no responsibility
for any virus transmitted by us and recommend that you subject any incoming
e-mail to your own virus checking procedures. 
_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: Phillip Neumiller <[email-masked]>
Date: Tue, 17 Sep 2002 18:02:18 -0400

Hi Dmitri,

Thanks and best regards,

Phil Neumiller
MeshNetworks, Inc.

-----Original Message-----
From: Dmitri Deshun Perkins [mailto:[email-masked]]
Sent: Tuesday, September 17, 2002 4:36 PM
To: [email-masked]
Subject: [manet] scalability in ad hoc networks

Hello: