Subject: node routing status

From: Elizabeth Royer <[email-masked]>
Date: Thu, 17 Feb 2000 13:27:33 -0800 (PST)

Hello all,

We noted that in the recent implementation report for OLSR that
the protocol does not require all nodes to be routers.  We have
been discussing this for AODV, trying to determine whether we
should add that statement to our protocol specification.
Our discussion began that we should allow nodes to choose not
be routers if they so desire, but we then easily imagined
a scenario where _everyone_ in the network decides to turn off
their routing capabilities, so as not to drain their battery life 
forwarding other user's data.  This would obviously lead to
an ineffective network, where few (if any) users would be able
to receive data.

So the question we want to ask is, what is the opinion of the group
regarding whether users should be allowed to refuse to be routers, 
even if this leads to an effectively disconnected network?  We can 
envision allowing users to stop routing if their remaining battery 
power falls below a certain threshold, but how should this problem 
be handled otherwise?  

Regards,
Elizabeth

---

From: Ravi Prakash <[email-masked]>
Date: Thu, 17 Feb 2000 16:59:32 -0600 (CST)

When only a subset of nodes act as routers doesn't the picture start
resembling a cluster-based routing scheme with cluster-heads, gateways and
ordinary nodes?

If so, would existing solutions for cluster-head election be applicable to
the scenario you describe? If so, there is a rich body of research
starting from Linked Cluster Algorithm (LCA) by Baker, Ephremides and
Weiselthier (sp?) to now on this issue. 

Flame-shield: I said that the problem "resembles" but may not be "exactly
the same as" cluster-based scenario. So, please don't kill me if I
misunderstood something.

Thanks,

----Ravi.
========================================================================
Ravi Prakash ([email-masked])		www.utdallas.edu/~ravip
Department of Computer Science
The University of Texas at Dallas
Richardson, TX 75083-0688.  Phone: (972) 883-2289,   Fax: (972) 883-2349

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 17 Feb 2000 15:12:53 -0800

Hello Ravi,

>                                 So, please don't kill me if I
> misunderstood something.

It's a sad day when people cannot contribute their ideas to
the IETF mailing lists because of fear of rude treatment.

> resembling a cluster-based routing scheme with cluster-heads, gateways and

This isn't a very close similarity, because cluster-heads are
supposed to know about a hierarchy of other nodes in their neighborhoods,
whereas forwarding nodes may have a much more random selection of
destinations in their route tables.

Regards,
Charlie P.

---

From: Nick Triantafillis <[email-masked]>
Date: Fri, 18 Feb 2000 00:44:25 +0000

Such decision by the nodes participating in the Ad Hoc network will indeed
render the network ineffective in delivering data especially if partitions
occur as a result of that action. I would imagine it will also prove more
expensive in terms of both processing and battery power for the remaining
participating hosts (although that might depend on the operation of the
routing protocol) that haven't turned off their routing capabilities (won't
that also reduce the 'overall' ability of the network to deliver data or even
perhaps its average 'lifetime'?).

Considering the above you could:

1) Work under the assumption that most people (?) in this group have worked so
far: all hosts in the network are willing to participate and act as routers
and turning off their routing capabilities doesn't happen or is not allowed.
Therefore hosts will participate until their battery dies. Or maybe allow it
with constraints: only when there is an alternative route to the destination
with more battery power on average or with every node exceeding some battery
power level.

2) Work towards a routing protocol that will incorporate battery power (speed,
direction, transmission power/range and others) as a metric when discovering
routes and using them. A sort of "battery power friendly protocol" so that
hosts won't have their batteries drained and won't have to turn off their
routing capabilities. This approach should also increase the average 'lifetime'
of the network and on average partitions should occur later than with the
approach in (1).

3) Allow it but then there isn't much that you can do (at least nothing I can
think of right now). When partitions occur due to nodes turning off their
routing capabilities, you could perhaps ask (now how can we do that?) nodes to
increase if they can their transmission power or move to a more convenient
position in order to repair the partitions in the network.

Regards,

Nick

-----------------------------------------------------------------------------
Nikos Triantafillis             E-Mail: [email-masked]
Dept. of Computer Science
University College London       Phone: +44 (0)171 419 3695
Gower Street                    Fax:   +44 (0)171 387 1397
London WC1E 6BT, U.K.           http://www.cs.ucl.ac.uk/staff/N.Triantafillis
=============================================================================

In message <[email-masked]>,

---

From: Chip Elliott <[email-masked]>
Date: Thu, 17 Feb 2000 19:06:39 -0500

Hi Ravi and Elizabeth,

One could turn around Ravi's statement (if one wished!) and say
that some cluster-based schemes have a kind of prefabricated way to
deal with nodes that don't wish to forward - namely those nodes
simply fall into the category of cluster members.

That doesn't actually answer Elizabeth's homework problem, though,
since one then has the question of exactly how one should choose
the cluster heads. This becomes quite an open-ended problem
since it's an effort in multi-parameter optimization. As in her
basic example, one is trading connectivity for battery power.
As a more complex example, one is trading the overall drainage of
battery power needed to maintain a certain network topology vs.
the battery drainage at specific nodes. For example, is it better
to run everyone down to zero uniformly or sacrifice a few unlucky
victims? Usually there is a large element of predicting the future
in the answer that you're most interested in.

It seems to me the answer is irremediably "it depends" and in
particular it depends on what you're trying to have the network *do*.
In other words, this particular aspect of the design follows from
one's overall goals, rather than drives one's goals. As an example,
sometimes it makes sense to have a network with heterogenous
nodes - eg those which are people carrying things with batteries,
and those which are merely repeaters that don't need to move, or
that are attached to power supplies, etc. Then one might wish to
run down the repeaters' batteries but preserve as long as possible
those that are being carried by people.

I know that Jason Redi has been thinking a lot in this area.
Jason, do you have anything to contribute??

- Chip

---

From: Ravi Prakash <[email-masked]>
Date: Thu, 17 Feb 2000 19:17:19 -0600 (CST)

Hi Chip,

I agreee with you that the choice depends on the goals. While I do not
have a proof for my conjecture, if the goal is to maintain network
connectivity (and minimize the possibility of network partitioning),
gracefully degrading everybody's battery may be preferable to having a few
nodes "spending" all their energy and dropping off. 

I am making a few assumptions here:

1. The alive nodes continue to exhibit similar mobility pattern and
continue to move in the same area. 

2. All nodes rely on batteries and are not plugged into power supplies.

3. The nominal range of the nodes stays unchanged regardless of their
energy level (not a realistic assumption, I admit --- but we academics
love such things :-)).

If some nodes were to quickly drain their battery and drop out, while all
the others still had a significant portion of their energy left, the
network may start getting partitioned very early on. By insisting that
the relative difference between the energy levels of nodes always stays
within a small bound one may be able to postpone the occurrence of network
partitioning.  

Thanks,

----Ravi.

---

From: Chip Elliott <[email-masked]>
Date: Thu, 17 Feb 2000 20:55:57 -0500

Ravi,

I am not against academic thought - quite the contrary.
Very much in favor!

With your assumptions, you are turning this into an
exercise in graph theory. As such, it really can have
an analytic answer.

However a few assumptions still need to be nailed down for
this case:

1) What is the traffic flow through the network, ie, how
   do you expect nodes to expend their power on forwarding?

2) What is the graph topology? For instance, a uniform random
   laydown with near-earth (r**4) propagation will look very
   different from a circular node laydown superimposed atop a
   radio propagation model for the Manhattan streets.

3) What is the battery power distribution among the nodes?
   Making them all identical is certainly simplest.

And then you must also nail down the evaluation function for
how well a solution is ranked. Here something like message
completion rate (what percent of intended transmissions can
reach their ultimate destinations) might be appropriate. I'm not
sure how you count sources that have exhausted their batteries,
though - maybe all their transmissions fail?

A reminder that there's also some amount of control traffic
induced by a node dropping out of the network, and this control
traffic will further deplete the batteries of some/all nodes in
the remaining network. Ugh.

Cheers and all the best!

-- Chip

---

From: "Karl Pospisek" <[email-masked]>
Date: Fri, 18 Feb 2000 08:33:05 +0200

Hi All,

On 17 Feb 00, at 13:27, [email-masked] wrote:

> but we then easily imagined

The way to overcome this problem is to give suitable incentives for 
the subscribers to leave their equipment on ..

eg .. so many %free flier miles or %QOS minutes for every hour that the
equipment is operational.
Or make the equipment indispensable. Why would the subscriber turn his
equipment off . 
The subscriber might even own 2 of these MANET devices and set up his
own sub-net . (Whilst routing other data - of course ).

The routing ability need not waste *much* battery power if it is fairly
shared. The routing is supposed to be a "background" function - like
tracking mobile cells . In the MANET , I estimate that transmit distances
 and power would be micro-cell sized ( if not pico-cell : like bluetooth's
 scatternet. 
If the cells are not to be micro-sized, then a conventional hierarchy
approach is best.

Karl///
***************************************************
"All the bandwidth in the world can convey only a
fraction of what we are."
(Tom Petzinger, Wall Street Journal, 4/23/99)

****************************************************
* 
* Reply to :  [email-masked]
*
****************************************************
*         ALCATEL ALTECH TELECOMS -         
*    ENGINEERING DIVISION SOUTH AFRICA    
*                                       
* phone: +27(11)899-6965    fax : +27(11)899-6590    
*                                                
****************************************************
The information transmitted is intended only for the 
person or entity to which it is addressed and may 
contain confidential and/or privileged material.
Any review, retransmission, dissemination or other
use of, or taking of any action in reliance upon, this 
information by persons or entities other than the
intended recipient is prohibited.   If you received
this in error, please contact the sender and delete
the material.

---

From: Miguel Sanchez <[email-masked]>
Date: Fri, 18 Feb 2000 09:48:26 +0100

Hi Ravi and all,

Regarding to this point it comes to my mind one of the results in the article
titled "The capacity of wireless networks" by Piyush Gupta and P.R. Kumar
that was posted to this list some time ago.

In there, they studied the effect of adding additional relay-only nodes to
the ad-hoc network. While this is not the same as removing the relaying
function from some nodes, the results on that issue were that not too much
benefit can be obtain just by adding a small number of extra relays.

My conclusion here is that network throughput does not suffer if you disable
relaying function from nodes that are not using it, conversely, if you
disable this function on the main relays of the network the impact will be
very high. Because each node role will change with mobility, choosing a set
of candidates for relay removal is not an easy task. (It can be done if you
have some motion constraints).

Adding more relays can only improve network connectivity, however relay
function removal from some network nodes can trigger network partition. I can
think a kind of new routing algorithms that could take into account available
nodal energy and then try to make other neighboring node the main relay on
this area when running out of energy.

However, I think that allowing individual nodes to disable other node's data
forwarding can be dangerous for the goal of maintaining a full network
connectivity. Maybe some energy constraints can be included in the routing
algorithm so the traffic share can be balanced taking into account the energy
issue.

Regards,

--
Miguel Sanchez Lopez                            |       [email-masked]
Universidad Politecnica de Valencia             | voice:+3496 387 9700
Camino de Vera, 14                              | fax:  +3496 387 7579
46071 VALENCIA (Spain)                          |

---

From: Vincent Magret <[email-masked]>
Date: Fri, 18 Feb 2000 10:00:58 -0600

Hi all,

I basically agree with Miguel saying that including a possibility for a node to
disable its routing capability. Due to the mobility of each node, it will be
extremely hard to take the "right" decision whether to route packets or not. A
node that has decided to not route packets, it may move (or the  other node
surrounding it) creating a topology where the node routing capability becomes
crucial for the overall connectivity. As we can see and as someone stated: it
depends. We cannot have a routing protocol taking decision arbitrarily.

We can also think of security aspect where a "spurious" node turning down its
routing capacity simply to break connectivity between node.

Having a node taking its decision based on its "power" supply will not save
sufficient power to have this node running a lot more.

That's my 2 cents contribution.

Vincent.

---

From: Miguel Sanchez <[email-masked]>
Date: Fri, 18 Feb 2000 17:26:53 +0100

Just another comment,

Current WLAN technology, either DSSS/FSSS or the upcomming OFDM relies heavily on
several signal processing tasks that make each node's transceiver to draw a non
negligible power in the receiving end. This means that a 802.11 adapter of one
brand X needs 450 mA when transmitting and 300 mA when receiving.  (And you need
to receive a frame before you know it is yours or not :-)

So avoiding additional transmissions due to routing functions is only half of the
picture as Laura Feeney pointed out some time ago in a past meeting. Reception
counts too. And I'd say that from a global power point of view is more expensive
than transmission is for a single node.

Again, I don't have an answer to Ravi

Best,

---

From: "Karl Pospisek" <[email-masked]>
Date: Mon, 21 Feb 2000 09:09:47 +0200

> than transmission is for a single node.

Agreed - In a pico/micro cell sized adhoc network - transmission power is
not the dominant energy eater (although with  increases in
computational efficiency, it will become dominant *if* the bit-rate remains
constant ).

Karl Pospisek.

---

From: [email-masked]
Date: Mon, 21 Feb 2000 19:09:49 +0100

Hello MANETlanders,

Since the discussion started with reference to OLSR, I would like to add my
one cent contribution. 

When we proposed a power saving scheme in OLSR we had in mind that like in
HIPERLAN some nodes may temporary not be able to act as router because of
power/battery problems. The reason why a node has power problem is external
to the protocol, and it is difficult to force a node in sleep node to
remain active in the network. Therefore, it may not be relevant to look on
how optimally we can select non-routing nodes. 

The simplest way to implement power saving is just to ignore and remove
nodes in sleep node. But can we do something in between? Our suggestion is
to make such node to continue to receive its traffic after passing an
agreement with a power supporter router. This router will store packets
during sleep period and forward them during wake periods. 

With such implementation it will be possible to implement nodes in sleep
mode during 90 msec and in wake mode during 10 msec (these are just
figures), therefore increasing their battery life time by one order of
magnitude. Question: is it useful?

Best regards,
Philippe

A 10:00 18/02/00 -0600, Vincent Magret a écrit :
>Attachment Converted: "c:\eudora\attach\vincent.magret.vcf"
>