Internet DRAFT - draft-gomez-paro-manet
draft-gomez-paro-manet
INTERNET-DRAFT J. Gomez, A. T. Campbell
Columbia University
M. Naghshineh, C. Bisdikian
IBM, T.J. Watson Research Center
February 2001
<draft-gomez-paro-manet-00.txt>
Expires September 2001
PARO: A Power-Aware Routing Optimization Scheme for Mobile Ad hoc Networks
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
vand may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
Due to fact that mobile ad hoc nodes have a critical need to preserve
battery power, MANET routing protocols need to consider power saving
techniques during operations. In this Internet-Draft we discuss PARO,
a Power-Aware Routing Optimization protocol that minimizes the
transmission power necessary to forward packets between wireless
devices. Using PARO, intermediate nodes can forward packets between
source-destination pairs thus reducing the aggregate transmission
power consumed by wireless devices. An important property of PARO is
that it outperforms traditional broadcast-based routing protocols due
to its power efficient point-to-point on-demand nature. The protocol
is designed to operate as a stand-alone multihop routing protocol for
local-area wireless networks (e.g., single-hop home networks, single-
hop sensor networks, WLANs, etc.) and as a power-aware enhancement
for routing in wide-area MANETs.
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 1]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Applicability. . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . 4
1.4. Protocol Overview . . . . . . . . . . . . . . . . . . . . 5
2. Design Consideration
2.1 Link Assumptions . . . . . . . . . . . . . . . . . . . . . 5
2.2 Policy . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Cost Function. . . . . . . . . . . . . . . . . . . . . . . 6
3. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 7
3.1 The PARO Model. . . . . . . . . . . . . . . . . . . . . . . 7
3.2 PARO Functions . . . . . . . . . . . . . . . . . . . . . . 9
3.2.1 Overhearing . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.2 Redirecting . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.2.1 Compute Redirect . . . . . . . . . . . . . . . . . . . 10
3.2.2.2 Transmit Redirect . . . . . . . . . . . . . . . . . . . 11
3.2.3 Route-Maintenance . . . . . . . . . . . . . . . . . . . . 12
3.3 Packet Formats . . . . . . . . . . . . . . . . . . . . . . 12
3.3.1 Data packet . . . . . . . . . . . . . . . . . . . . . . . 12
3.3.2 Route-Redirect packet . . . . . . . . . . . . . . . . . . 12
3.3.3 Route-Maintenance packet. . . . . . . . . . . . . . . . . 13
3.4 State Tables . . . . . . . . . . . . . . . . . . . . . . . 14
3.4.1 Overhear Table Format . . . . . . . . . . . . . . . . . . 14
3.4.2 Redirect Table Format . . . . . . . . . . . . . . . . . . 14
4 Security Considerations . . . . . . . . . . . . . . . . . . . . 14
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Authors' Addresses
1. Introduction
Transmission power control used for communications impacts the
operational lifetime of devices in different ways depending on the
average transmission power consumption compared to the total average
power consumption of a device. For devices where transmission power
accounts for only a small percentage of the overall power consumed
(e.g., a wireless LAN radio attached to a notebook computer) reducing
or increasing the transmission power may not significantly impact the
device's operational lifetime. In contrast, for small
computing/communication devices with built-in/attached radios (e.g.,
cellular phones, PDAs, etc.) reducing transmission power may extend
the operational lifetime of a device significantly, thus, enhancing
the overall user experience.
This memo specifies PARO, a power-aware routing optimization protocol
for wireless networks where all nodes are located within the maximum
transmission range of each other. PARO can also perform power
optimization as a layer 2.5 routing scheme operating below
traditional layer 3 wide-area ad-hoc routing protocols. PARO uses
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 2]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
packet forwarding as a way to reduce the transmission power necessary
to deliver packets in the network, thus increasing the operational
lifetime of networked devices.
1.1. Applicability
PARO is applicable to wireless networks where all nodes are located
within transmission range of each other. To provide out-of-range
power-aware routing support, a layer 3 ad-hoc routing protocol (e.g.,
MANET routing protocol) should be used above PARO.
1.2. Terminology
node
A node with wireless transceiver.
forwarding node
A node forwarding packets between two other nodes.
source node
A node generating and transmitting data packets to another node.
control packet
route-redirect and route-maintenance packet.
data packet
An IP packet that is not a control packet.
route-redirect packet
A control packet transmitted by a potential forwarding node to
inform another node about the existence of a better power-aware
route.
route-maintenance packet
A control packet transmitted by source nodes in order to maintain
a route.
route-maintenance frequency
Rate of route-maintenance packets per second necessary to maintain
a route.
redirect timeout
Validity time of mappings in Redirect table.
overhear timeout
Validity time of mappings in Overhear table.
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 3]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
1.3 Motivation
Typically, more power is consumed during the transmission of
packets than their reception or during ``listening'' periods.
Transmission to a distant device at higher power levels may
consume a disproportionate amount of power in comparison to
transmission to a node in closer proximity. Figure 1 shows an
example of a network composed of three nodes located within
transmission range of each other. In this case, nodes A and B use
node C to forward packets to each other. The fact is that packet
forwarding can significantly reduce the transmission power
necessary to deliver packets between A and B nodes when node C is
located near the mid point, between nodes A and B. More than one
forwarding node can be added between source-destination nodes
resulting in even lower aggregate transmission power.
O <------------------> O <-------------------> O
A C B
Figure 1. Example of packet forwarding
In PARO, we propose that intermediate nodes forward packets
between source and destination pairs even if source-destination
pairs are located within direct transmission range of each other.
This operation requires that radios are capable of adjusting
transmission power on a per-packet basis. A consequence of this
approach is that traditional single-hop networks (e.g., local area
networks) can be considered as multi-hop networks requiring
routing protocols (similar to that found in traditional wide-area
ad-hoc networks) for data forwarding.
One common property of most wide-area routing protocols [1] [2]
[3] is that they discover routes using different versions of
``flooding-broadcast protocols'' by transmitting with maximum
power in order to minimize the number of forwarding nodes between
any source-destination pair. MANET routing protocols are based on
this principle and attempt to minimize the number of hops between
source-destination pairs. A good broadcast flooding algorithm is
crucial to the operation of any wide-area routing protocol to
ensure all nodes maintain identical routing databases. Delivering
data packets in a wireless network using a traditional ``minimum-
hop route'', however, require more transmission power to reach the
destination compared to an alternative approach that uses more
intermediate nodes.
Increasing the number of intermediate hops can be achieved by
reducing the transmission range used to discover routes in the
network. Reducing the transmission range, however, has the effect
of increasing the number of signaling packets transmitted.
However, a linear decrease in transmission power generates an
exponential increase of the number of signaling packets
transmitted to completely flood the network. In addition, it is
not possible to arbitrarily reduce the transmission power to any
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 4]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
value, thus potentially maximizing the number of forwarding nodes
between source destination pairs. Rather, there is a limitation on
the lower bound of transmission power needed to completely flood
routing information in the network that depends on the density
distribution of nodes in the network. This limitation restricts
nodes discovering some routes to other nodes if they use a
transmission power smaller than the "critical transmission power".
Signaling packets transmitted using less power than the critical
transmission power are likely to get lost rather than reaching the
final destination node.
Due to these challenges, wide-area routing approaches based on
broadcast flooding techniques are either inefficient (e.g., they
generate too many signaling packets for low broadcast transmission
power) or incapable of discovering routes that ``maximize'' the
number of intermediate forwarding nodes between source-destination
nodes, thus minimizing transmission power. The existing MANET
routing protocols are designed to use flooding techniques at
maximum power to discover routes. In addition, these protocols are
optimized to ``minimize'' the number of hops between source-
destination pairs so as to promote minimum end-to-end delay.
Because of these characteristics (i.e., flooding using maximum
power and maximizing the number of hops), MANET routing protocols
may not provide a suitable foundation for power-aware routing in
ad-hoc networks. As a result, there is a need to develop new
power-aware routing approaches.
1.4. Protocol Overview
The design of a power-efficient routing protocol should consider
both data transmission and route discovery. In terms of power
transmission, these protocols should be capable of efficiently
discovering routes involving multiple hops, thus minimizing the
transmission power in comparison to standard flooding-based ad-hoc
routing designs. PARO departs from traditional broadcast-based
design, and supports a node-to-node based routing approach that is
more suited to efficiently discovering power-aware routes in
wireless ad-hoc networks. In what follows, we provide an overview
of PARO and address link assumptions, routing policy, cost
function and protocol operations.
2. Design Consideration
2.1 Link Assumptions
PARO requires that radios are capable of dynamically adjusting the
transmission power used to communicate with other nodes.
Commercial radios including IEEE 802.11 and Bluetooth include a
provision for power control. PARO assumes that the transmission
power required to transmit a packet between node A and B is
somewhat similar to the transmission power between node B and A.
This assumption may be reasonable only if the interference/fading
conditions in both directions are similar in space and time which
is not always the case. Because of this constraint PARO requires
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 5]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
an interference-free Media Access Control (MAC) found in frequency
band radios such as Channel Sense Multiple Access (CSMA). CSMA
standards use collision avoidance techniques (RTS-CTS) to make
sure only one node transmits data packets at a time, thus
minimizing the interference caused by simultaneous transmissions.
PARO requires source and destination nodes be located within the
maximum transmission range of each other. This limitation suggests
that PARO can inter-operate with traditional layer 3 ad-hoc
routing protocols to provide energy-efficient routes in topologies
where source and destination nodes are outside the maximum
transmission range of each other and layer 3 packet forwarding
becomes necessary. PARO requires that every data packet
successfully received is acknowledged at the link layer and that
the nodes in the network are capable of overhearing any
transmissions by other nodes as long as the received signal to
noise ratio (SNR) is above a certain minimum value. Any node
should be capable of measuring the received SNR of overheard
packets. This includes listening to any broadcast, unicast and
control (e.g., acknowledgment) packets.
2.2 Policy
In PARO we focus on a policy that minimizes transmission power in
the network only. An alternative policy could attempt to balance
the power in the network (e.g., battery level). Policies that
minimize and balance power could be orthogonal to each other.
Choosing a route that balances power may not minimize transmission
power, however. As a result, inefficient use of power resources
could take place thus limiting the availability of power reserves
in future. While balancing the power reserves in the network is a
desirable property of a routing protocol, we have yet to consider
this in our work.
2.3 Cost function
In PARO the cost of a directional link connecting node A with node
B is defined by the minimum transmission power, Tmin(A,B), at node
A such that the receiver at node B is still able to receive the
packet correctly. In a network with several alternative routes
between a given source-destination pair, the cost of each
alternative route is the sum of the minimum transmission power of
each link along the route. We consider transmission power only,
thus, it neglects the cost of processing overheard packets and the
cost of keeping the radio in a listening mode.
PARO tries to find the route for which the aggregate transmission
power is minimized, and furthermore, it tries to discover this
route using as little transmission power as possible (e.g., the
power consumed by signaling packets). PARO accommodates both
static and mobile environments. For the case of static networks,
once a route has been found there is no need for route maintenance
unless some nodes are turned on or off. In a static network,
transmitting a large amount of data traffic clearly outweighs the
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 6]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
cost of finding the best power-efficient route. In this case, we
may not need to be as efficient while discovering such a route. In
mobile environments, however, there is a need for route
maintenance, which may outweigh the cost of data transmission in
some cases.
3 Protocol Details
3.1 The PARO Model
In PARO nodes operate in promiscuous mode and are capable of
overhearing packets transmitted by other nodes as long as their
received power is above a certain capture threshold. Prior to
transmitting a packet, a node updates the packet's header to
indicate the power used for its transmission. A node overhearing
another node's transmission can then use this state information
plus a localized measure of the received power to compute, using a
propagation model, the minimum transmission power necessary to
reach the transmitting node. In this simple manner nodes learn the
minimum transmission power toward neighboring nodes. PARO does
not, however, maintain routes to other nodes in the network in
advance but discover routes on a per-node on-demand basis. This
approach has the advantage that signaling packets, if any, are
transmitted only when an unknown route to another node is required
prior to data transmission, thus reducing the overall power
consumption in the network.
At first the operation of PARO may seem counter-intuitive because
in the first iteration of PARO the source node communicates with
the destination node directly without involving any packet
forwarding by intermediate nodes. Any node capable of overhearing
both source and destination nodes can compute whether packet
forwarding can reduce the transmission power in comparison to the
original exchange between source and destination nodes. When this
is the case an intermediate node may send a "route-redirect"
message to the source and destination nodes to inform them about
the existence of a more power efficient route to communicate with
each other. This optimization can also be applied to any pair of
communicating nodes, thus more forwarding nodes are added to a
route after each iteration of PARO reducing the end-to-end
transmission power. PARO requires several iterations to converge
toward a route that achieves the minimum transmission power.
The PARO model includes three main algorithm modules for
overhearing, redirecting and route-maintenance, as shown in Figure
2. The overhearing algorithm receives packets overheard by the MAC
and creates information about the current range of neighbor nodes.
Overheard packets are then passed to the redirecting module which
computes if route optimization through the intermediate node
results in power savings. If this is the case, the redirect module
transmits route-redirect messages to the nodes involved (e.g.,
source and destination nodes) and creates appropriate entries in
the redirect table. The overheard packet is then processed by the
packet classifier module which passes the packet to the higher
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 7]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
layers if both MAC and IP addresses match, drops the packet if
neither MAC nor IP addresses match or forwards the packet to
another node when only the MAC address matches. In the later case,
PARO searches the redirect table to find the next node in the
route for the packet and then searches the overhear table to
adjust the transmission power to reach the next node en-route.
L3 and Higher layers
^ |
| V
- - - - - - - - - - - - - - - - - - - - - - -- - - - -
| |
| -------------------
| MAC&IP |route-maintenance|
packet *|--| -------------------
classifier * | MAC | source nodes
-------->* |-------------------| | only
| * |--- | |
| *| | | |
| V sink | |
| | |
| route-redirect | |
| ----------------------- | |
| | | | | DLC
------------- |Redirect| <--|--|--*
|Redirecting|--> | table | <--|--* |
------------- | | | | |
^ | | |
| | | |
| | | |
------------ |Overhear| <--|--|--*
|Overhearing|--> | table | <--|--* |
------------ | | <--* | |
^ | | |
| | | |
- - - - - - - - - - - - - - - - - - - - - - - - - -
| MAC | | |
| V V V
- - - - - - - - - - - - - - - - - - - - - - - - - -
PHY
Figure 2. The PARO Model
When PARO receives a data packet from the higher layers it
searches the redirect table to see if a route toward the
destination node exists. If this is not the case, PARO searches
the overhear table to see if transmission power information
regarding the destination node is available. If this is not the
case, PARO transmits the packet using maximum transmission power
anticipating that the receiving node is located somewhere in the
neighborhood. Once the destination node replies with a packet of
its own then PARO's route optimization follows as described
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 8]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
previously.
PARO relies on data packets as the main source of routing
information in the network. When nodes are mobile and no data
packets are available for transmission, a source node may be
required to transmit explicit signaling packets to maintain a
route. The role of the route maintenance algorithm is to make sure
a minimum flow of packets is transmitted at all in order to
maintain the route when no data packets are available at the
source node.
3.2 PARO Functions
In this section, we briefly describe the overhearing, redirecting
and route-maintenance algorithms that operate in both static and
mobile networks.
3.2.1 Overhearing
The overhear algorithm processes packets successfully received by
the MAC and creates (or refreshes an entry if information
associated with the overheard node already exists) a cache entry
in the overhear table. This cache entry contains the triple
[ID,time,Tmin], where the ID is a unique identifier of the
overheard node (e.g., MAC or IP address), time is the time at
which the overheard event occurred and Tmin is the minimum
transmission power necessary to communicate with the overheard
node.
Using a propagation model that takes into account the transmitted
power, overheard power and node sensitivity it is possible to
compute the minimum transmission power Tmin between the
transmitting and overhearing nodes. Because of fading and other
channel impairments it is not recommended to compute the minimum
transmission power using one overheard packet only. A better
approximation is to take a moving worst-case approach, where the
overhear node buffers up to M previous measurements of the minimum
transmission power and then chooses the one with the highest
value.
Any node transmitting a packet to the next hop in the route has to
determine the next hop's current range, which may be different
from its last recorded position. Clearly, the preferable
transmission estimate is the one that transmits a packet using
minimum transmission range. In PARO, we address this issue by
transmitting a packet with an extra "delta" transmission range
than previously recorded, thus increasing the probability of
reaching the next hop node with the first attempt. Thus delta
represents how much the transmitting node over estimates the
transmission range of the next node en-route. The value of delta
depends on the average speed of nodes and the time interval
between the last time the next node en-route was overheard and the
current time; we refer to this interval as the "silence-interval".
The longer the silence-interval the greater the uncertainty about
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 9]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
the current range of the next node en route and therefore the
larger the value of delta. We resolve this problem by requiring
source nodes to transmit route-maintenance packets toward
destination nodes whenever no data packets are available for
transmission for a specific interval called route-timeout.
Transmission of route-maintenance messages only occur whenever a
node that is actively communicating with another node stops
transmitting data messages for a route-timeout interval. The
transmission of route-maintenance messages put an upper bound on
the silence-interval, thus, an upper bound on delta. The route
maintenance message contains no extra information beyond the
destination node and transmission power fields, thus it adds
little overhead.
3.2.2 Redirecting
The redirect algorithm is responsible for performing the route
optimization that leads toward discovering routes requiring less
transmission power. This module performs two basic operations:
compute-redirect, which computes whether a route optimization
between two nodes is feasible; and transmit-redirect, which
determines when to transmit route-redirect messages.
B
* O
Tmin(A,B) * *
* *
* * Tmin(C,B)
* *
* *
O * * * * * * * * * * * O
A Tmin(A,C) C
Figure 3. route-redirect
3.2.2.1 Compute Redirect
Figure 3 illustrates how compute-redirect operates. In this
example nodes A, B and C are located within maximum transmission
range from each other and, initially, node A is communicates
directly with node B. Because node C is capable of overhearing
packets from both A and B nodes, it can compute whether the new
route A<->C<->B has a lower transmission power than the original
route A<->B. More precisely, node C computes that a route
optimization between nodes A and B is feasible if:
Tmin(A,B) > alpha (Tmin(C,A) + Tmin(C,B)) [1]
Similarly, we define the optimization percentage of adding a node
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 10]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
between two other nodes in a route, Opt, as:
Opt = (Tmin(C,A) + Tmin(C,B)) / (Tmin(A,B) [2]
The factor alpha in Equation 1 above, restricts the area between
two nodes where a potential forwarding node is allowed to transmit
route-redirect messages. For networks where nodes are static and
saving battery power is important (e.g., a sensor network) alpha
can be set around 1.1-1.2, meaning that even a small improvement
in transmission power is worth the drawback of adding an extra
node (e.g., hop) to the route. Once a node computes that route
optimization is feasible, it creates an entry in its redirect
table. Because of mobility, a forwarding node may move to a
location where it no longer helps to optimize the transmission
power between two nodes. In this case, it is necessary to remove
such a node from the path using another route-redirect message.
3.2.2.2 Transmit Redirect
In PARO, several nodes may simultaneously attempt to transmit
route-redirect messages to one node. Because only one intermediate
node between two nodes is added at a time, any route-redirect
message except the one transmitted by the node computing the
lowest Opt percentage represents wasted bandwidth and power
resources. For sparsely populated networks, this may not be a
problem. However, this is clearly an issue for densely populated
networks where several route-redirect messages would be
anticipated. The transmit-redirect procedure addresses this issue
by giving priority to transmit a route-redirect message to
intermediate nodes computing lower route optimization values
first. In this manner, a potential forwarding node overhearing a
route-redirect advertisement from another node offering a route-
redirect with a lower Opt value would refrain from transmitting
its own route-redirect request
There are several ways to give preferential access to certain
messages in a distributed manner. We used a simple approach which
consists of applying a different time-window before transmitting
the route-redirect message after the triggering event takes place
(e.g., the lower the Opt value computed, the shorter the
intermediate node waits to transmit its route-redirect request).
The actual lower and upper bound of the waiting interval are set
such that they do not interfere with predefined timers used by the
MAC protocol, making these bounds MAC dependent.
In the unlikely scenario that more than one route-redirect request
is transmitted, the target node will choose the one providing a
lower Opt value. After receiving a route-redirect message, a node
modifies its own redirect-table putting the source of the redirect
message as the next hop in the route for the specific source-
destination route.
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 11]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
3.2.3 Route-Maintenance
In static networks no route maintenance is required once the
initial route between source and destinations nodes has been found
other than when nodes are turned on or off. PARO relies on data
packets as the main source of routing information. In the case of
mobile nodes, data traffic alone may not be sufficient to maintain
routes. Consider the extreme case of a source node transmitting
packets once every second to a destination where every node moves
at 10 meters/second on average. In this example information about
the range of the next node en route would be outdated as a basis
for the transmission of the next packet. Depending on node density
and mobility there is a need to maintain a minimum rate of packets
between source and destination pairs in order to discover and
maintain routes as forwarding nodes move in and out of existing
routes. In PARO a source node transmits route-maintenance packets
when there are no data packets available to be sent within a
route-timeout interval.
3.3 Packet Formats
3.3.1 Data packet
A PARO data packet is a standard IP packet with a new IP option
containing power related information.
Currently the following type of control information is defined in
the PARO IP option (details are for further study):
Transmission power Transmission power used to transmit route-
redirect packet.
3.3.2 Route-Redirect packet
A route-redirect packet is an ICMP packet of which
- the source address is the IP address of the sending node
- the destination address is the destination node of the route-
redirect message
- the type is PARO control packet and the code is route-redirect
The payload of the route-redirect packet carries transmission
power related information in the following format
0 1 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- -+-+-+-+-+-+-+-+-
| Type | length | Data... | Type ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- -+-+-+-+-+-+-+-+-
Type Indicates the particular type of control information.
Length Indicates the length (in bytes) of the following data
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 12]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
field within. The length does not include the Type and
Length bytes.
Data This field may be zero or more bytes in length. The
meaning, format and length of the data field is
determined by the Type and Length fields.
Currently the following type of control information is defined
(details are for further study):
Route source
IP address of source node.
Route destination
IP address of destination node
Optimization percentage (Opt)
Ratio of optimized route with original route (see Section 3.2.1.1).
Transmission power
Transmission power used to transmit route-redirect packet.
3.3.3 Route-Maintenance packet
A route-maintenance packet is an ICMP packet of which
- the source address is the IP address of the source node
- the destination address is the final destination node of the
route
- the type is PARO control packet and the code is route-
maintenance
The payload of the route-maintenance packet carries transmission
power related information in the following format
0 1 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- -+-+-+-+-+-+-+-+-
| Type | length | Data... | Type ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- -+-+-+-+-+-+-+-+-
Type Indicates the particular type of control information.
Length Indicates the length (in bytes) of the following data
field within. The length does not include the Type and
Length bytes.
Data This field may be zero or more bytes in length. The
meaning, format and length of the data field is
determined by the Type and Length fields.
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 13]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
Currently the following type of control information is defined
(details are for further study):
Packet Counter
Used to let intermediate nodes in the route detect missing packets.
Transmission power
Transmission power used to transmit route-redirect packet.
3.4 State Tables
3.4.2 Overhear Table Format
An entry in the overhear table contain the following fields:
- Timestamp
- IP address of the overheard node
- Minimum transmission power to reach the overheard node
3.4.1 Redirect Table Format
An entry in the overhear table contain the following fields:
- Timestamp
- IP address of the source node of the route
- IP address of the destination node of the route
- IP address of next node en-route
- IP address of previous node en-route
4 Security Considerations
Currently, PARO does not specify any special security measures.
This internet-draft assumes that all nodes participating in the
PARO protocol do so without malicious intent to modify or corrupt
packet information as well as the ability of the network to route
packets. Nodes participating in PARO benefit from the relay
capability of other nodes that motivates their participation in
the protocol. Encryption techniques can be used in the air
interface to prevent attack by outsiders.
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 14]
INTERNET-DRAFT Power-Aware Routing Optimization 26 February 2001
Acknowledgments
This is work is supported in part by IBM Research and an NSF
Wireless Technology award ANI-99-79439.
References
[1] David B. Johnson and David A. Maltz, The Dynamic Source Routing
Protocol for Mobile Ad Hoc Networks, Internet-Draft, draft-ietf-
manet-dsr-02.txt, 1999, work in progress.
[2] D. Park and M. Scott Corson, Temporally-Ordered Routing
Algorithm (TORA) version 1: Functional specification. Internet-
Draft, draft-ietf-manet-tora-spec-00.txt", 1997. Work in progress.
[3] Charles E. Perkins and Elizabeth M. Royer and Samir R. Das, Ad
Hoc On-Demand Distance Vector (AODV) Routing, Internet-Draft,
draft-ietf-manet-aodv-03.txt, 1999, work in progress.
Authors' Addresses
Javier Gomez-Castellanos, Andrew T. Campbell
Department of Electrical Engineering, Columbia University
Rm. 801 Schapiro Research Building
530 W. 120th Street, New York, N.Y. 10027
phone: (212) 854 3109
fax : (212) 316 9068
email: [javierg,campbell]@comet.columbia.edu
Mahmoud Naghshineh, Chatschik Bisdikian
IBM Watson Research Center
30 Saw Mill River Road,
Hawthorne, NY, 10953
phone: (914) 784-6231
fax : (914) 784-6205
email: [mahmoud,bisdik]@us.ibm.com
Gomez, Campbell, Naghshineh,Bisdikian Expires September 2001[Page 15]
