Subject: [Fwd: performance comparaison between Ad Hoc routing protocols]

From: Cesar Santivanez <[email-masked]>
Date: Thu, 14 Feb 2002 19:52:33 -0500

I am resending this e-mail, since for some reason it did not get posted ...

Cesar

Subject: Re: performance comparaison between Ad Hoc routing protocols
From: Cesar Santivanez <[email-masked]>
To: [email-masked]
Cc: [email-masked]
Date: Thu, 07 Feb 2002 09:45:30 -0500

Hi Richard,

[email-masked] wrote:

> 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.

That is the whole point ....  Routing protocols should be mobility and traffic sensitive ...
As the bandwidth and data traffic increase, the `relative cost' of the control overhead
decreases... There is an inherent trade off between control overhead and sub-optimal
routng cost.  Scalability analysis has shown that best peformance can be achieved when
these two sources of overhead (or cost) are kept balanced.
This means that if we allow data traffic demands to increase, then we should also
let the `control overhead'  to increase accordingly ...

Now, dynamic adaptation to mobility and traffic may sound far fetch now, but it is
something to explore in the future... For the time being, I would suggest to tune
protocols to minimize the `total overhead'  at the maximum expected traffic load ...
This way your protocol will work efficiently when you need this efficiency the most,
while  under light load -- in most cases -- we may not care about expending extra control
overhead bits since we  have bandwidth to spare  ...

> > There are many instances in my experience where a mechanism that takes more
> > overhead ends up doing better in terms of user metrics.
>
> I'm not sure if you mean "total overhead" here.

I think Ram was referring to `control 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).

Yeap.. Specially since `better' may mean less delay, less jitter, etc.
What the `total overhead' metric gives you is an indication of the amount of
capacity  left for data traffic. So, gives you the `potencial' for data
transmission.

> Full flooding also achieves better
> reliability by using more total overhead than other flooding mechanisms.

Well, the `total overhead' framework assumes that the network layer provides
reliable transmissions, that is, that never gives up until a packet reaches its
destination. Thus, for efficient flooding techniques's total overhead's computation
you would have to consider all the retransmissions required until getting the
data packet to its intended destination.  So, the total overhead assumes the
`reliable' version (e.g. using network layer ACKs) of the protocols.

> 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
>

Well, this is not the whole history ...  Total overhead relates to remaining capacity, but for ALL the
possible flows. You are assuming that only flow 1 --> 4 has traffic to sent, and I agree that in such a
particular scenario you'll be better off with load balancing over least interfering paths.
But if you consider the maximum combined rates of all the flows ( 1->6,  1 -> 7,  2 ->6,  2->7, etc.)
you will see that the protocol with less total overhead is the one that achieves greater total
throughput (granted, there are fairness issues -- specially in the presence of bottleneck links --
so we are not maximazing the minimum flow throughput here).
So, if you are sure what traffic pattern you have, to may beat the total overhead design criteria.
But if you are assuming that all flows are potentially possible, a better desing criteria would be to
minimize the expected total overhead ...

The total overhead metric allow for tractable models to be derived. It is not perfect since it ignores
fairness issues (as well as the effect of bottleneck links) by assigning the same cost to all
transmissions as oppose to assigning a smaller cost to transmission over `unused' areas
of the network (due to the inherent assumption that the network load is high and diverse
-- several flows -- and all areas of the network are going to be used).

I'll be more than happy to discuss/explore better metrics that addresses the
`total overhead' shortcomings while still allowing for meaningful tractable models
to be developed...

Regards

Cesar

> Richard
>
> > 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]
> > > ------------------------
> > >
> >