Subject: Re: [manet] A topology control question?

From: Ram Ramanathan <[email-masked]>
Date: Mon, 1 Mar 2004 10:00:55 -0500

These are good questions, and here are my belated comments.

On Feb 21, 2004, at 5:18 PM, Dong Wang wrote:

> Hi,
>  
>     Recently, I read several papers about topology control. My 
> understanding is that, topology control algorithms generate, or 
> derive, a simpler topology from the original one constructed under the 
> common maximum transmission range. And all routing algorithms then 
> select routes based on the new topology.
>  
>     Here are several points that I don't quite understand:
> 	 1.  	While maintaining connectivity, topology control aims at saving 
> energy by considering each node or considering the network as a whole?

Energy conservation is only one possible goal. The other, in my mind is 
interference reduction and hence capacity increase. If certain 
conditions are met, decreasing the power while still keeping the 
network biconnected often results in better throughput. Large number of 
nodes operating at max power close together are susceptible to the 
"parking lot" problem where they come up, are unable to get their 
discovery messages through and so self-organization fails.

People motivating topology control for energy savings should carefully 
consider the practical aspects. For instance, in many transceivers, 
transmit power reduction is done by adding more resistors in the path, 
which does nothing to save energy.

> 	 2.  	Seems each node adjusts its transmission level only when the 
> original network topology has been changed, no matter which node it's 
> going to transmit data to, does it?

In most papers I am aware of, yes. Note that the way papers treat 
topology control de facto defines the concept, but that does not mean 
that that is necessarily the way it should be (see below for 
elaboration).

> 	 3.  	Topology control removes some connectivity information from the 
> original topology, however, I observed that such a removed link 
> between a node and one of its neighbors may be the part of the 
> optimal route (which costs the lest energy) to a destination, 
> therefore topology control actually deviates from its purpose -- save 
> energy.

It depends upon the particular topology control algorithm. If you 
ensure that this never happens i.e, you never remove a link A->B unless 
there is a lower energy path A->C1...->Ck->B, this shouldn't happen?

If my recollection is right, the excellent paper by Roduplo and Meng 
(appeared in a JSAC special issue 3-4 years ago) formally sets up the 
conditiionns for this and gives an algorithm for topology control that 
is provably minimal energy (again, it is only my recollection, you 
should check it out).

But more generally, yes, topology control may result in excluding 
certain links that are physically possible from the purview of the 
routing control system, to the possible detriment of the performance. 
To extend your point to the interference reduction motivation, topology 
control may remove a link that is part of the optimal route, causing 
packets to take longer routes and increasing the net interference.

In other words, topology control (as commonly used) deliberately 
eliminates some resources (links) from being used. Why is this any 
good? Why not *know* about them but be selective in their use?

An answer to this needs context about the alternatives, and the 
tradeoffs involved. So, to put this in perspective, let me go up one 
level. I classify such control into three, and generalize it so it 
doesn't just apply to "power" but more generally, radio parameters. Let 
T be the richest possible topology resulting from the maximal use of 
parameters (e.g. maximum power). There are three kinds of parameter 
control.

1. Physical topology control. Here, node parameters are adjusted so 
that you get a topology that is a subset of T. Routing is given T and 
has to work with it. This is the implicit definition of topology 
control as used today (to my knowledge).
2. Routing topology control. Here, T is discovered and given to routing 
protocol. The routing protocol then deliberately excludes certain links 
from consideration as part of the topology database. It can change the 
links it is "blind to" depending on the situation,
3. Per packet control. This is strictly not topology control. Here, T 
is discovered and given to the routing protocol. The routing protocol 
uses all of its links in its routing database. When a packet is to be 
transmitted from A to B, power is reduced to just what is required. 
This relates to what I think you have in mind when you asked question 
#2.

As I said, the word "topology control" has generally come to mean 
"physical topology control". However, in the late 1980's there was an 
obscure but very good paper by Nachum Shacham that used topology 
control as routing topology control. Per packet control as in #3 is 
routinely used by military contractors who have been building ad hoc 
networks for a living.

Now for the pros and cons. The main observation is that there is a 
tradeoff between control overhead and the information. So #2 reduces 
overhead over #1 by being selectively "blind" to the changes in some 
percentage of the links ignoring their state. And #3 reduces overhead 
further by eliminating the need to even maintain (from a discovery 
point of view) neighbors. So for the same T' \subset of T produced by 
routing topology control and physical topology control, physical 
topology control has less overhead as it doesn't need to worry about 
some neighbors at all. Also, Hello interference is reduced. Plus, only 
#1 above eliminates the parking lot problem. Finally, doing #3 means 
adjusting power in the (fast) forwarding path, which might be a problem 
for high speed wireless networks.

So now to answer your question. Keepinng around that link that gave you 
the optimal path requires some work -- control overhead wise, and 
protocol complexity wise. Topology control (physical/routing) 
essentially takes the position that by giving up some links for 
simplicity and reduced overhead (which in turn burns energy and 
increases interference), you may actually win out because the 
situations like you describe are (maybe) rare.

Now, whether or not this position is justified is anybody's guess. I 
know of no work that compares, say, #1, #2 and #3. Or even articulates 
the position, or justifies it over per packet control. Most minds 
(including mine) are seduced by the inifinitely rich graph theoretic 
and distributed algorithm possibilities :-}).

I apologize for the long winded answer, but I hope it gives you a 
fuller picture. More importantly, I hope it encourages you (and others) 
to look into this "diferent kinds of topology control" further. There 
is a lot of scope for further research here.

-Ram

P.S. The terms "physical topology control" and "routing topology 
control" are not standard.

>     I will appreciate your explanation. Thank you.
>  
> Gary W
> University of Minnesota

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