PDF version of the paper: link
Speculative
Multipath Routing for Sensor Network Data Aggregation
|
Abstract—The paper describes the Speculative Mutipath
Routing algorithm (SMR) useful for routing data from a large number of nodes to
few super nodes (sinks). SMR is
useful for application scenarios where data aggregation is the primary network
objective and exact routing to a single node is less important that achieving
routing of global data to a node or a set of nodes. We assume that the network
is dynamic where links can go down and come up. Multipath routing is provided
by maintaining multiple routes, each associated with a route quality. Route quality is based on network link characteristics
– data throughput and delay. Applications can choose one or more routes based
on route quality. SMR uses the hop-by-hop routing paradigm using routing tables
at each node containing routes to difference sink via different links with
route quality associated with each entry. The convergence algorithm for network
repair used by SMR is faster compared to similar approaches (path-vector
algorithms). SMR is guaranteed to be loop free. The advantage of SMR over the
other related protocols are: 1) keep the protocol (message) overhead to a
minimum. 2) Provide load balancing between the sinks. 3) Ensure fast recovery
from link/node failures (reduce convergence time).
Index Terms— data aggregation,
routing, speculative routing, route quality, directed acyclic graph
I.
INTRODUCTION
NTERNET as we know
it now, was designed in such a way that all nodes regardless of their physical
location and surroundings were similar. Sensor networks are conceptually
different – they interact with the physical surroundings. Their main motive is
to collect information (temperature reading, humidity, motion detection, pressure,
light). Hence, unlike nodes on the Internet, they can gain considerably (in
form of performance, bandwidth, usability, and precision) if the information to
be collected can be coupled with the information about the information
source. This coupling of local
information with the location information can result in data aggregation
techniques that were earlier not possible. Location information can be combined
with data to do in-network aggregation. The paper presents Speculative
Mutlipath Routing (SMR), a routing framework for sensor network data
aggregation. The primary goal is to route data from a set of sensors to a
collection of special nodes (sinks) connected to the main workstation.
In-network processing is done at each node, while the data is being routed to
the sinks. In-network processing takes advantage of the information about the
physical location of a sensor node to compress data (and discard irrelevant
data). Possible application scenarios are:
·
Avalanche Prediction
on Mountains: Sensors are spread around to collect snow pack information
(temperature, density, humidity, thickness). Data from the neighboring sensors
can be aggregated to save on valuable transmission bandwidth of the sensor
nodes.
·
Parking
Meters that give Tickets: Still camera can be attached to a parking meter.
A vehicles speed can be calculated by two consecutive parking meters. This can
be done locally by the cameras Collaborate between themselves to find speed
without sending the information to any central location. Tremendous bandwidth
gain is achieved since images are processed locally between neighboring parking
meters.
·
Super High
Resolution Image [SUPER-RES-1] Generation:
Goal is to use a set of low resolution video camera to generate a super
high resolution image. Images from neighboring nodes can be compressed together
since they will be similar compared to the ones that are far apart.
SMR uses routing tables (Speculative
Routing Tables) to keep track of routes to the sinks. Not only do we maintain
an entry for the best route to a sink node, but one entry for every possible
link from the node to its immediate neighbors. We assume a link layer protocol
to maintain the neighbor list. The details of the link layer protocol is beyond
the scope of this paper. A route quality metric is associated with each routing
table entry. At any time multiple routes to a particular sink are available.
Moreover, there is one set of entries for every sink in the system. Hence at
any time multiple paths are available with raking based on a quality metric. An
application is free to either use the best path or a set of paths. Latter is
useful for either sending the same set of data to multiple links (data duplication) or doing data mutation. Data duplication is useful
when the links are wireless and there is a possibility of collisions. In Data
mutation, a piece of data is broken into chunks and each chunk sent to one link
from the set of links. Data mutation provides a good way to maximize
utilization of each link in the network [MADDEN, CONSIDINE].
SMR does not assume anything about the physical channel and thus
can easily be applied to either a wired or a wireless network. In our current
application scenario, we use a mesh topology with wired links. For a more
general topology, SMR
can
be used over an overlay [OVERLAY]. E.g. a distributed sensor network
applications where sensors are spread over a Wide Area Network.
“Speculation
involves trading with the intention of profiting from changes in the prices for
futures contracts, rather than from a desire to hedge specific risks” [FIN-MKT]
SMR follow a
similar strategy, where we speculate our next hop to take based on the entries
in the routing table by looking at the route quality of the full path from the current node to the
destination (any one of the sinks). But instead of following the same path to
the destination (which itself can vary based on the route quality), a data
packet will again decide about the path to take by checking the routing table
when it reaches the next hop node. Hence data packets speculate the route in hope that there will be a better destination/path
available later, on its way to a sink.
II.
Motivation
Current routing protocols for ad-hoc networks including AODV
(Ad-hoc On-Demand Distance Vector [AODV]), DSR (Dynamic Source Routing [DSR]),
and DSDV (Dynamic Destination Sequenced Distance Vector Routing [DSDV]) have
been geared towards providing a routing primitive that given a source A and
destination B, can route data from A to B with a protocol geared more towards
wireless network. The second set of protocols mainly, BGP [BGP], OSPF [OSPF],
RIP [RIP] are meant for wired inter networks like Internet, but are based on
the same philosophy.
DSDV
relies on periodic advertisements and global knowledge of connectivity information.
This makes the protocol to scale poorly because of the message overhead and the
amount of state information required at each node. DSR and AODV are both
on-demand with
route discovery and
route maintenance done when a route is
actually required. This removes the need for periodic messages for proper
functioning of the protocol. But DSR has the additional overhead of carrying
the source route in each data packet. AODV is an improvement over DSDV, which
eliminates the need for periodic broadcast or route advertisements.
AODV is distance vector and thus each node maintains only the
distance vector to the destination that can lead to loops. Once a path to a
destination is set for routing from a source to a destination, it remains
active until data is flowing through it. There is no mechanism to switch to a
path with a better route metrics. Moreover, the metric used in AODV is hop
count, which may not always give the best characteristics of a path to a
destination. SMR is expected to be dynamic, where data can switch to a
different route based on the changing route
quality. In general DSDV, DSR and AODV need unique identifiers (or IP
addresses) to be assigned to each node for the proper functioning of the
protocol. This may add to extra bandwidth overhead in the messages, which needs
to carry them around for node identification.
RIP is based on distance vector routing where each node maintains
an entry for each node in the network and make use of shortest path
computation. OSPF is link state routing protocol, where a node needs to
maintain the whole topology state locally. This is done by each router (OSPF
node) broadcasting the whole topological information to all the participants.
Although topology broadcast used by OSPF solves the problems faced by RIP including
the count-to-infinity problem, the bandwidth overhead is not acceptable in
ad-hoc networks. Since each node maintaining some information about each and
every node in the network, RIP and OSPF can’t be used for sensor networks,
where the number of sensor nodes can be large. BGP based on path vector routing
[PATH-VECTOR] is a better alternative than OSPF/RIP. It solves the scalability
problems in OSPF/RIP. BGP exchanges distance vectors that specifies complete
path to the destination. BGP scales well with number of nodes. But each update
carries the whole identifier list of the nodes in the path. This could create a
problem for large spanning networks, where the update messages can grow large. Another
drawback in most of the routing protocol including BGP meant for the Internet
is that they rely on unique naming scheme for the protocol to work. The problem
with unique naming is that for large networks, ensuring a unique naming across
the whole network can mean extra overhead in terms of bandwidth. Individual
naming may not be easy to achieve in the future very large scale sensor
networks. But even if it is possible, the message containing route information
may grow large for large diameter networks.
The general research focus has been on destination driven
protocols, where the primary goal is to route the data to a particular
destination specified by the source. But the trend
shows
that in general ad-hoc networking specifically for sensor driven networks can
do without exact destination oriented routing, where each node may want to route
messages to a separate destination. The current need is to come up with routing
primitive that is not based on the optimal (or near optimal) path to a
specified node, but on
QoS
requirement of the application – for a real-time application like trying to
aggregate information about a moving vehicle on a highway using multiple
sensors, network delay is more important than trying to ensure that a high
bandwidth link is available for each message to the common destination (a
central base station). Here we assume
that the messages consume small bandwidth compared to the maximum available
bandwidth available between the sensors. On the other hand, for a bandwidth
application load balancing may be the primary concern. A set of video cameras
arranged in a mesh topology to generate a super resolution [SUPER-RES-1, 2]
image falls under this category. SMR is a step towards a decentralized routing
protocol with close association with data aggregation in sensor networks
(either wired or wireless).
III.
Network Model
The network consists up of sensor nodes where the topology is
prone to frequent changes. We assume that the nodes can come up and go down
anytime. We differentiate between two types of sensor nodes: sinks and basic
nodes (referred to as nodes in the rest of the paper). The sink nodes, like the
basic nodes can also generate date. But sinks nodes are assumed to be connected
by high bandwidth links to a central base station responsible for collecting
the data originating from the sensor network. Links can be either wired or
wireless. We don’t make any explicit distinction between the two. We assume a
link layer protocol that will take care of maintaining list of connected
neighbors to a node. For a wireless network, the link layer protocol may
consist up broadcasting messages to neighbor containing a group identifier sent
to all nodes in its range. All nodes receiving the broadcast can either
acknowledge the message or disregard the same if they already have the maximum
number of neighbors the network allows (a pre-defined system parameter). For
wired networks, the link layer protocol will consist up of keep-alive messages send on the wired links to the immediately
connected neighbors.
Our
current topology is a wired mesh with each node connected to at most 4
neighbors by 100Mbps Ethernet links. The sinks are located in the 4 corners of
the mesh and one in the center. (See Figure 1). We don’t have any restriction on
the location of the sinks, but we do assume a high bandwidth link between the
sink and the central base station (shown as Workstation in Figure 1). For the
rest of the paper, we use a simpler version of the mesh topology consisting of
6 nodes connected in a mesh as shown in Figure 2. There are 6 sink nodes
labeled from 1 through 4.
IV.
Speculative Multipath Routing Algorithm
The basic protocol can be summarized as a being modeled over the
hop-by-hop paradigm common in present day Internet [BGP] and more commonly in
peer-to-peer systems [FREENET, NAPSTER, GNUTELLA]. SMR consist up of
exploratory phase, where periodic exploratory messages (EM) are sent though out
the network from a sink. EMs are used to
populate routing tables that will be eventually used to route data. Periodic EMs ensure that a routing table reflects the correct
state of the paths available to a node at a given time. Multiple paths to a
sink are available via different links on the node in the routing table.
Moreover, a routing table also list path to all the sinks in the network. Single
or multiple link can be chosen to send data based on the application need and
link stability. The routing tables created using EMs
can then be used to route data to the sinks. An application can either choose a
specific sink to send data to or in general leave the destination (one of the
sinks) field empty and let the protocol decide the best way to route data to
any one of the sinks. We are more interested in the latter, where we don’t
explicitly specify the final destination of the data.
The primary objectives of the routing algorithm are:
·
Given a set of
sink nodes(S1, S2…), we need to route data from a set of nodes to the
sinks irrespective of which sink the data is routed to
·
Require multiple paths to be available at each
node – load balancing, network redundancy
·
The routing protocol should be able to
reconstruct new routes when links go down – network is dynamic
·
Need to ensure that loops do not form in the
network
EMs in SMR follow a gradient field (GF). Gradient field
is specific to a sink and is used by
EMs
originating at that sink. A gradient field provides the
EMs
with possible paths that an EM can explore. GF repair algorithm ensures that the
inverted Gradient Field (which itself is a directed graph) forms a Destination
Oriented Directed Acyclic Graph (DAG) [DAG-1] for a particular sink. This is
used for data routing to sinks using the speculative routing tables at each
node. Invalidation messages are used to remove paths with broken/congested
links from the routing table.
SMR does not guarantee shortest path to a sink. We assume a
connected network at all time (Even when a node goes down), but it is quite
possible to take care of network partitions [PARK]. A link layer protocol is
assumed that takes care of populating and updating the neighbor list at each
node.
The reasons to restrict the EMs
from following a gradient field are three-fold. First a gradient field ensures
that the EMs don’t go into loops and can
easily terminate. The property is due to the level assignment algorithm that we
use to create the GF as explained in the next section. Secondly since the GF
diverges from a sink to all other possible nodes, the EMs are able to take a diverse set of
paths enabling the best possible use of most of the available network links.
Thirdly, the repair algorithm for convergence in case of nod/link failure used
by SMR is faster (refer to section VIII for details) than that used by other
related protocols, specifically BGP. The inverted gradient field itself has
similar advantages. Firstly, it is loop free and no data packet can go into
loops. Secondly, at each hop, the data packets normally move one step closer to
the sink, thus ensuring that the number of transmissions in the network is kept
to a minimum. This saves on scarce resources at the nodes, especially if the network
is wireless.
A.
Gradient Field
A gradient field (GF) is rooted at sink with one GF associated
with each sink. GFs are created by using a create-gf
broadcast starting at the sink. Creation of one GF is independent from the
other hence each node will maintain a separate data structure for each GF at a
node. GFs are denoted by GF/Sx, where Sx is the sink that roots that particular
gradient field. To build a GF for a sink Sx, a broadcast rooted at Sx is
performed using create-gf messages.
Every create-gf message is of the
form <Sx, level>, where Sx is
the identifier string for the sink for which the GF is being created. A level
is an integer that is incremented on each hop as the create-gf traverses the network. Two levels associated with a link (one
for each of the two nodes connected through the link) gives the direction of
the flow of EMs as described below. A level
assigned to a node implies that the node is already part of the GF for Sx and
thus will discard any further EMs with sink
set to Sx. We next describe the GF
formation algorithm in details.
When a gf-create:<Sx,
level> broadcast message reaches a node, if it is not already part of that
GF, then the level of the node is the level number in gf-create message. If the node already has an assigned level for
the GF associated with Sx, then the message is discarded without any further
processing. In the case, when the message is accepted and level assigned to the
node, the level field in <Sx, level> is incremented and message is
rebroadcast to all the links besides the on which the message arrived. A sink
will be at level 0. A level is maintained for each GF the node is part of.
Hence in a 4 sink configuration, each node will have 4 levels. Levels also act
as indicators of the direction that a packet should follow. i.e. in a GF, an EM
will go from a node with low level to a node with a higher level. Figure 3
shows a GF for sink S1 on the 6 node test topology. The level starts at 0 at node S1 and keeps on
increasing as we move away from S1.
A GF can be considered a DAG because of the way it is created
using level assignment with links directed away from the sink. This ensures
that an EM traversing the GF, after few numbers of hops is guaranteed [COSTAS]
to come to a node with no outgoing links, and thus needs to be terminated. Hence
EM messages are never caught in loops. Each node maintains GF, one for every
sink in the network. Every sink send its own set of EMs
on its corresponding GF.
A GF on one hand is responsible for directing the EMs to possible paths that they can take in the network,
while on the other hand the inverted gradient field is used as the Destination Oriented Directed Acyclic Graph
(DAG) for a particular sink. The Destination Oriented DAG is used for
routing data from nodes to a sink. Thus a GF not only affects the routing table
entries via the paths that the EMs can take,
but also in actual creation of paths for the routing. Figure 4. shows the
destination oriented DAG for node S1.
B.
Routing data to Sinks
As mentioned earlier, the inverted GF is used for routing the
data to a sink. The graph obtained by using the reverse paths on the GF for a
sink gives a directed graph. The levels assignment from the GF is used as the
levels for that DAG. Since any path in such a graph always proceeds in the
direction of decreased level, the directed graph will be acyclic (DAG)
[COSTAS]. It is also destination oriented since all nodes have directional
links in such a way that they can send data to the sink whose GF was used to
create the DAG. Hence the DAG is destination oriented for a particular
sink. Data flow is from a node with a
higher level to a node with a lower
level.
A Destination Oriented DAG with destination as Sink Sx is denoted by the
DAG/Sx. Figure 4 shows the DAG, DAG/S1 for sink S1.
C.
Two Neighbor Nodes with Same Level
During level assignment for GF formation, two neighbor nodes may
get assigned same levels. This will also get reflected in the corresponding destination
oriented DAG. Same levels on both sides
of a link, in essence means that no data can flow between the two nodes via
that link. This is derived directly from the fact that data in the destination oriented
DAG flows from a node with a high level to a node with a lower level ensuring
that at each step we get closer to the destination (a sink). In case of a GF,
the intuition is that we try to use links that gets an EM away from a sink on
each step.
D.
Route Maintenance
Links can go down and new nodes can join the network. This makes
the network destination disoriented. A destination disoriented DAG will have a
node with at least one node (besides the sink) which has no outgoing links. Our
goal is to get from a destination disoriented DAG to a destination oriented DAG
to ensure proper working of the routing algorithm. We use Full Reversal
Algorithm [GAFNI] to perform the transition back to a destination oriented DAG.
Fixing routes using Full Reversal Algorithm constitutes changing levels in such
a way that every node has at least one outbound link.
1)
Full Reversal Algorithm
Full Path Reversal Algorithm was first proposed by [GAFNI] and
later used by [PARK] and others. A detailed analysis is given by [COSTAS]. The
algorithm is simple -each node other that the destination (sink) that has no
outgoing link reverses the directions of all it’s incoming links. Reversal of
direction is performed by increasing the level of the node that has no outgoing
link. A level of the node will be larger than the heights of all its neighbors.
This process is continued until all the nodes in the network besides the sink,
has one outgoing link. The algorithm is expected to scale well in both time and
work needed to complete the link reversals. The complexity in both time and
work is shown to be O(m2),
where m is the number of nodes that
become destination disoriented (as shown in [COSTAS]).
As explained earlier, each sink is associated with a GF. Each GF
has its own set of EMs that periodically purge
the values in the speculative routing table with the fresh values. We now
describe the speculative routing tables and how they are created.
E.
Speculative Routing Tables
By using destination oriented DAG with Full Reversal Algorithm, we are able to guarantee loop free routes
to a sink, even in a case of a link failure. Since we have 4 sinks available,
we ideally want to utilize all the 4 sinks equally for dissipating data to the
central workstation, so as to use maximum available bandwidth without
overloading a particular link. Since each node is part of 4 DAGS, it can send
data through any of the sinks (provided there is no network partition). So we need
a quality metric to decide which is the best DAG to use (i.e. we want the data
to itself decide which is the best possible sink to choose). Moreover, even in
a single DAG, multiple outbound links will be available – here too, we require
a quality metric to decide the best route to the sink. Speculative Routing
Tables store route qualities with path parameters (path identifier, next hop
information – link) about the best possible path to all the sinks. Data can be
sent to multiple links by selecting multiple links based on the route quality.
The primary requirements from the Speculative Routing Table are:
·
Maintain one entry for each sink through all
links in a node (inbound entries set to 0). Thus with a network topology having
M sinks with each node having N links (outbound + inbound), there will be M*N
entries in the routing table
·
Interested in the relative goodness of the paths
·
Require that we are able to rank the routes to
each sink through a link from a node based on some metric (Route Quality)
Each entry in the routing table is of the form <Rq,
PID, TIM>, with one entry for each immediate neighbor that the node
is connected to for a given sink as the destination. Thus for each sink in the
network, there will be one set of entry. Rq
gives the routing metric for choosing the next hop to the sink, while the PID (path identifier) is required to
distinguish between various paths through a link to the same destination sink
but via different nodes in the network. TIM keeps track of the bottleneck
throughput in the path. We further discuss about Speculative Routing Table in
the next section.
V.
Populating the Speculative Routing Tables
We start with an initial set of route qualities with the
assumption that all links are equally loaded. The initial set is changed by the
use of Exploratory Messages (EMs) on a
periodic basis. An EM is specific to a sink and travel in only the GF of that
Sink. On reaching a dead end (no outgoing links in the GF), the EM is discarded.
An EM for one Sink will not affect routes to other sinks even though it may be
possible to reach other sinks via the same DAG.
A.
Route quality, Route utility and Link utility
Multiple paths are available via multiple DAGs with sinks as
their destination. Each DAG itself contains multiple routes to the same
sink. An entry in the speculative
routing table defines the route quality to a specific sink using a particular
link (next hop). An entry in the routing table is of the form <Rq, PID, TIM>.
Rq (
Route quality) represents the
quality metric of the route from the current node to the sink. It is updated
using
Route_util. In the current
design, we set
Route_quality to the
inverse of
Route_util. Thus a higher
value of Route_quality is better than a lower one. A more useful mapping from
Route_quality to
Route_utility would take into account the data aggregation gain
obtained when using a certain path.
Route_util
for a path starting from node
to a sink
is the
weighted sum of the individual
Link_util from current node to the sink
defined as:
is defined as the level assigned to node
in the DAG associated with sink
.
is the level assigned to the node
.
When a data packet selects a path using the routing table, the packet
is sure to take the first hop for the path selected, hence the link utility of
the fist hop that the packet takes is weighted the most. Each consecutive link
in that specific path from the node to the sink is weighted down based on the
distance of the path from the sink. Hence a link in a path that is closer to
the sink will have lower influence in the route utility of that path. Link_util is defined in the next
subsection. If a link does not exist or if the link is inbound (coming into the
node), then the route quality value in the table is zero.
1)
Link Utility
Link Utility
for a link will constitute some parameter that characterizes that link. Current
routing protocols, both wired [RIP, OSPF] and wireless [DSR, AODV], uses hop
count as the routing metric. Hop count metric doesn’t take into account the link
characteristics (link loss, delay, bandwidth availability), leading to paths
with bottleneck and congested links being used. In wireless networks,
minimizing the hop count can also lead to reduction in signal strength that
decreases the signal to noise ratio. This reduces the effective data rate for
the link. In other words, long distance links will ensure small number of hops,
but the links will be forced to operate at slower speeds [BARUCH]. Similar
results are obtained in [ETX], which shows that a shorter path with more number
of hops can be better than a path with lesser hops. Hence a pure hop count
metric, which calculates the shortest hop count to the destination, will not
get the best path. Moreover, multiple routes to the same destination each
having the same hop count can be available.
Hence we need
a link quality metric to characterize the link. There are two available metrics
that characterizes a link – link delay and link throughput.
- Link delay: Time taken by an EM to traverse through the
link. This can be calculated by time tagging a packet and calculating the
time difference when the EM has finished traversing the link (reaching the
next node). Since we need to calculate the link utility for the reverse link, we can’t use the
EM (since it traverses the forward direction). We give a possible solution
to calculate the reverse link utility later in the paper where we use a probe message. The probe message will be time stamped
when it is sent and then again when it is received. The difference between
the two time stamps gives the link delay.
- Link Throughput:
Link throughput gives the amount of bandwidth available for use in a
link in bits transmitted per unit of time. This can be
calculated by keeping track of the amount of data being transferred and
using the remaining bandwidth as the throughput value. But as discussed
later, this results in route instability. We tag data packets with a
unique sequence number and count the number of tagged data packets
received (excluding the retransmitted data packets if any). Using probe
messages for calculating throughput is not a solution because of variation
of loss rate with varying message size [ETX, DRAVES]. Hence, using probes
messages that will be much smaller than the actual data packets will
results in inaccurate results.
Link delay by itself has the problem that it doesn’t take into
account the loss rate of the link, an important factor that should be
considered. A metric purely on link throughput will not be able to consider
link load. We propose a combination of the two. A possible combination of Link
delay and throughput (before normalization) is:
Here
is the throughput for
link
. For an EM going from node
to
, the throughput will be of the asymmetric link
(
). Same holds true for
, where the link delay is calculated for the reverse link.
A lower value of link
utility (Link_util) indicates a better link. i.e. a route with a smaller route utility
is preferred.
is a constant that can be set according to a specific application
in mind. For large data transfer, we set
(throughput more
important). For real-time applications, we can set
(quick response is more
important). In our case
, can be set to be anything greater than 1 since high
throughput is more important than real-time response. Once,
Link_util is obtained for a link, all
the
Link_util for a route can be
added to get route utility. Route utility currently is same as route quality. Later
we can use a better function to map route utility to route quality. A possible
function could takes into account the number of hops in a path. Route quality
for a path to a sink via link goes into routing tables. Normalized link utility
that is used to calculate the route utility is given by the following:
is the maximum
bandwidth provided by the single-duplex link from node
to
, (100,000Kbps in our
case).
can be set to a
reasonably large value (few msec)
indicating the maximum time a packet can be delayed traversing a link.
is calculated by the
node
by keeping track of
the data packets received from
.
is calculated by using probe messages as explained later on
in the paper.
The route quality metric defined using Route_util and Link_util
have the following feature:
- Reduce the total transmission time from a node to its
sink., but not at the expense of reduced throughput
- Use high throughput links
- Give more importance to links closer to the source
- Takes into account both link delay and throughput
- Safe guard against delayed probe messages due to
queuing delays, unfair channel policies.
The route quality metric will favor shorter paths with higher
loss rate (low throughput) than longer paths with ideal links (no loss). This
ensures that we choose a path with smaller number of hops, thus ensuing that
the chances for channel interference from neighboring is minimized. For a wired
network with Ethernet links, we expect the throughput (delivery ratio) to be 1,
thus the route utility will just be the sum of the normalized link delays. The
preferred route in this case will be the one with the minimum total delay. The
preferred path will be the one with the maximum route quality i.e. the minimum
route utility.
We still need to
define the update policy that purges the old entry in the routing table
and puts in the new route quality as an EM reaches a node. We elaborate on update policy in the next section. We
now focus on EMs that carry the route utility
metrics.
B.
Exploratory Messages (EMs)
We use the already existing GFs for sending EMs
as mentioned earlier. An EM is of the form <Sx, RQ, PID>, where RQ is the
cumulative link utility of the reverse links from the start of the EM (which
will be the sink node Sx) to the node which intercepts this EM. When the EM is
progressing on its way down (following the GF), it updates route quality for Sx
via the link L though which the EM was received in the routing table of the
receive Node
An EM can also keep track of the bottleneck bandwidth (throughput)
in a route that it traverses. This can easily be done by inserting an
additional field in the EM to keep track of the minimum throughput in a path
from the source to a node. Hence the new EM format becomes: <Sx, RQ, TMIN, PID>, where TMIN
is the bottleneck bandwidth encountered so far. Keeping track of bottle neck
bandwidth ensures that we never select a path that may possibly have a low
bandwidth path that was not visible when the data packet makes a decision about
the next hop node.
C.
EM Transmission – Random vs Uniform
Two approaches can be taken for propagating an EM in the network
– random and uniform. In the uniform transmission, we use a periodic broadcast.
At each node, an EM is forwarded to all possible links (allowed by the GF).
Alternatively, a sink can choose to send an EM periodically, but
if multiple outbound links are available, a subset of the available link is
chosen at random to send the
EMs. For
generating the forwarding set for sending the EM, a subset of the possible
outbound neighbor links is used. Each link can be picked from the possible
outbound links with equal probability. This ensures that all available paths
are explored equally. Choosing each link with equal probability helps
update
link qualities of all possible paths. This consumes less bandwidth than the
former approach, but doesn’t cover all paths at each time cycle. Since, we
don’t expect that the link utility of
all
links itself will be changing; it makes sense to not update the link utility of
all the links periodically.
Sending EMs periodically equally
spaced in time could be a problem when the congestion itself is happening
periodically. If data generation in the network is periodic, few links can get
congested on a periodic basis. If the periodic cycle of the congestion and the EMs don’t match, the route quality of the congested path will
not change. The periodic broadcast could be improved by adding a small jitter
in the send time of each EM.
D.
Speculative Routing Table Update Policy
When an EM arrives at a node with a new value of the route
quality for a route from the node to the sink via a link, the old value should
be purged and replaced with the new. A link may receive EMs
for different routes for the same sink, so it is important to keep track of the
full path that the EM took to reach the node. Instead of keeping full
information about the path, we assign path Ids (PID) to a route. PIDs are added
to distinguish between route qualities from various paths. Using PIDs, the
route quality for a path in the routing table can be invalidated if needed (due
to broken links or congestion). Invalidated entries can be replaced by new
values from the EMs or, backup entries (as
described later) can replace purged entries if better path information is not
available.
1)
Path Identifier (PID) Generation
The PID field is added to every EM to keep track of the links
traversed by the EM. Each outgoing/incoming link on a node is assigned a binary
identifier (BID). BID can be of any preset length (3, 4, 5 ...bits). PIDs are generated from binary ids
(BID) by concatenation of BIDs of the outbound links that the EM encounters.
Hence an EM starts with a PID set to NULL. As it progresses its way down a GF,
the BID corresponding to the link on which the EM is sent is concatenated with
the PID in the EM. On reaching a node, the PID for the route is the value of
the PID field in the EM. We can now look at the processing algorithm for the EMs.
2)
Update Algorithm
Update algorithm is responsible to purge the old entries in the
routing table with the new ones if an EM for a path already present in the
table is received. If an EM with a better path is received, the old entry is
removed and a new one is added. When a node receives an EM:<Sx, Rq, TMIN,
PID>, if the PID matches with the entry SRT[Sx, L] in the table corresponding
to the link (L) on which the EM was received and the origin of the EM (a sink
node - Sx), the old value of PID is replaced by new value (PID). If PID doesn’t
match, if both the route quality value in the EM (Rq) and the bottleneck
threshold (TIM) is better that the corresponding values in SRT[Sx, L], then current
values of SRT[Sx, L] is replaced by that on the EM. i.e. a new path to Sx is
chosen via the link L. Figure 8 gives the pseudo code for the EM processing
algorithm.
E.
Invalidation Message (INVAL)
If an entry in the SRT is not refreshed in a predefined time
interval, the entry is purged. This can happen if the EM corresponding to that
path is not received due to a link failure in that path. A congested link can also
lead to the EM getting delayed and result in a timeout at a node for that path.
A timeout triggers an invalidation message that is used to invalidate entries
in routing table of nodes that have the same route prefix as the path with the
faulty link.
Invalidation Message (INVAL) is of the form <Sx,
Route_prefix>, where Route_prefix is the PID for the route from Sx to the
current node who is sending the INVAL. INVAL sent to all the outgoing links. As
the INVAL travels via links, the BID of the outgoing links via which the INVAL
travels is appended to the Route_prefix. On receiving an INVAL:<Sx,
Route_prefix> from the Link L, Route_prefix is matched with the PID from the
entry <Sx, L, RQ, PID> in routing table. If PID and Route_prefix match,
RQ is set to 0. A better approach is to set the entry to a backup value as
explained later. The INVAL is then sent to outbound links after appending the
BID of the link to Route_prefix. If there is no match, then INVAL is discarded.
Note that invalidation message only removes a route via a link from the routing
table (i.e. invalidates the Rq field
in the routing table). The next hop field is maintained.
F.
Back Up Entries
When an entry in the routing table needs to be purged after an
INVAL message is received (or generated), instead of setting the entry to 0, we
set it to the backup entry. Moreover, it may happen that the current value in
the EM's route quality field is worse than the previous route quality value for
that
path.
Here instead of retaining the current path (i.e. using the lower but updated
route quality from the EM), a new path can be installed from one of the backup
entries for that particular sink/link combination. We maintain multiple entries for the same
<Sx, L> combination. One will need to update the backup entries as we
update the primary (best) entry.
VI.
Using the Speculative Routing Table
Since we don’t care about which node the data goes, a full
routing table look up is done to select the next link based on Quality metric.
Multiple links can be selected (for sending duplicate data/mutated data) by
using links with good quality metrics. The routing decision is on a hop by hop
basis. In case of ties, links can be chosen based on number of hops given by
the level (or at random). A node that itself is a sink doesn’t need to consult
its own routing tables since it can directly send the data to the central
workstation.
1)
Need for Multiple Paths
With multiple paths are available for routing to a sink (or a set
of sinks), the application is free to decide the strategy to use for data
routing based on the application need or even physical channel condition. There
are two possibilities:
·
Data Duplication: It involves sending the same
data to multiple links. When data need to be sent, it is duplicated and forwarded
on multiple paths to the same destination. Data Duplication helps in achieving
redundancy since now, even if few data packets are lost, the original data is
still recoverable. This is especially useful
when the links are wireless and there is a possibility of collisions [MADDEN].
·
Data Mutation: Data to be sent can be broken
into smaller chunks, and individual chunks can be sent on the available paths. Since
we use all possible paths to the destination, maximum utilization of links is
achievable. Data mutation is useful when the links can be considered reliable.
E.g. the wired mesh topology with wired Ethernet links between nodes [MADDEN,
CONSIDINE].
Both data duplication and mutation comes at a cost. In the
former, care needs to be taken for ensuring that if multiple copies of the same
data are received, one copy can be discarded. Mutation efficiency will depend
on the aggregation function to be used in the network and the data
characteristics. Since we are doing in-network processing as data flows from a
node towards the sink, mutated data may not be in the form that it could be
used for aggregation without recombining all the chunks. Hence all the separate
chunks will flow towards the sink without being aggregated, reducing the
efficiency achievable via data aggregation.
Application scenario, where super high resolution images are being
generated from low resolution images using a sensor network, data duplication
is not a problem, while mutation will depend on the image representation being
used for super high resolution imaging.
VII.
Implementation Issues
A.
Separation of Control and Data Plain
The intent is to separate the data from the control plain. The data plain consists up of the data
generated from the node sources. Q messages that are used to calculate the
delay in a link used for data also use the data plain. Control plain consists
up of the CONF messages (required to build the GF/DAG), INVAL messages (for
invalidating routes), EM (probe messages for route quality updates) and Q_ACK
message (for delivering the link metric to the originator node of the Q message).
If the physical channel is wireless, the separation of data from the control
plain can be used to reduce the power consumption of the sensor node’s transmitter.
Data Plain needs to be high bandwidth. The transmitter can operate at high
bandwidth, thus increased power level. Messages in the Control Plain are of low
bandwidth making it possible to operate the node transmitter at low power. This
reduces the over all power consumption of the node.
Control plain needs to be made more reliable compared to a data
plain. Loss of a sensor reading may not affect the over all system
performance/accuracy by a large amount compared to a loss of a control message.
A loss of a CONF may result in reduced links in the network making data
aggregation less efficient. Loss of an EM can result in delayed updates to the
routing table resulting in INVAL messages being generated in the network due to
timeout resulting in unnecessary invalidation of routing table entries in nodes
using the route. From Shannon’s equation for
channel capacity, the control plain can gain signal fidelity at the cost of
reduced bandwidth making the control plain more reliable.
B.
Calculating Data Throughput
It is possible to find the link throughput (via effective data
rate of a channel) by keeping track of the number of data packets in the link (in
reverse direction, towards the sink) in a given time interval. But this can
lead to oscillation between routes. A link will become preferred if its
throughput is high. Once data packets migrate to the preferred link, it will
become loaded resulting in low link quality. Thus the data traffic will shift
back to a new link, which will again get loaded after sometime. Thus a data throughput
calculated using effective channel data rate will result in route instability. A
solution is to use probe messages for calculating the delivery rate. The probe
messages needs to be of sufficient large size so that they see the loss rate
that actual data packets will encounter. But having sufficiently large probe
messages add to a large bandwidth overhead in the network. An alternate
strategy is to tag a fixed number of data packets periodically. We tag the data
packets flowing in the link to measure the effective data throughput. A
periodic timer triggers a data packet tagging cycle. A fixed number of packets
that are flowing in the up link direction (towards the sink) will be tagged
with a unique sequence number generated randomly from a large number space i.e.
all packets in the same tagging cycle will have same sequence number. On the
other end of the link, the number of packets with the same sequence number is
counted. This gives the delivery rate for the up link. The approach is similar
to that used in [YARIS]. See related work for details.
For an 802.11b wireless LAN setup, retransmissions are handled at
the LLC layer of the 802.11 MAC. When a data packet is lost or corrupted, the
receiver node will send back a positive or negative acknowledgement, depending
on the outcome of the error detection process. In case the acknowledgement is
lost, the sender will retransmit the packet after a certain period of time,
referred to as the Automatic Repeat Request (ARQ). Since, the data packets
retransmitted will be exactly the duplicate of the previous lost/corrupted one
(sequence numbers in the MAC header are preserved in all retransmissions of a
data packet/fragment [IEE-802.11]), we need to find a way to ensure that we are
able to distinguish between original and the retransmitted data packets. A
possible solution is to modify the 802.11 LLC to remove the tag bits from the
packet header, when an ARQ is initiated. Hence the receiver can calculate the
delivery rate by the counting the tagged packet with a specific sequence number.
For wired medium like wired LAN [IEEE-802.3], retransmissions of
corrupted and lost packets is done at the higher level, since the standards
doesn’t define a reliable data-link layer. Thus makes it possible to count the
number of tagged data packets at the receiving end easily by snooping at the
network layer itself for the tagged data packets.
C.
Calculating Link Delay
To calculate the link delay of the reverse path, a pre-EM can be
sent before the actual EM. Pre-EM contains a unique identifier that is left at
every node that the pre-EM traverses in the network following the GF. On
reaching a node, pre-EM sends a probe
message back to the node via the link it just arrived. This is used to
calculate the link delay of the link the probe just traversed by comparing the
time stamps of the sent and receive time of the probe. The route utility can
then be calculated by using the link delay and the link throughput value from
the current node. The first probe will be received by a node that had sent the
pre-EM. This node on receiving pre-EM will send the EM. EM will follow the same
exact trail by following the pre-EM via the identifier left by the pre-EM. As
the EM traverses the nodes, it aggregates the link utility calculated above.
A simple approach for calculating the link delay would be to send
the probe messages periodically in the reverse link from each node. But using Pre-EMs
to initiate the probes helps in two ways:
·
Probes are sent only when a new link delay value
is required, thus conserving bandwidth
·
The sinks can control the EM transmission rate
and hence, the rate at which the probes will be sent (since a pre-EM triggers a
probe, while a pre-EM is initiated by an EM)
The link delay in general can be considered as a combination of
transmission delay, propagation delay and the queuing delay. Queuing delay
depends on the link utilization, while transmission and propagation delay is
independent of link load. Thus under high link load, queuing delay will be
significant and will affect the link delay. Under low link utilization, queuing
delay is negligible and the link delay will consist up of the transmission and
propagation delay. As shown in [ARPANET-METRIC], using link delay as the
quality metric alone can lead to route oscillations under high link load (where
the queuing delay is significant). Under low to moderate load, queuing delay is
negligible. i.e. the link delay gives the correct picture of the link. A probe
message can also be delayed due to unfair physical channel policies, a common
problem faced by 802.11b under high loads [DRAVES, BRAHIM, ETX]. We argue that
since the link utility value will still be updated based on the new throughput
calculations, the overall link utility will not deviate from the actual link
utility at the current time. For wired networks, where the throughput
approaches one (loss rate is negligible or nill), we can use average value of
link delay, averaged over the last few values. This will reduce the route oscillation when
the link load increases on a link.
VIII.
Related Work
Our approach resembles Path vector routing [PATH-VECTOR], where
the updates used for route maintenance carry the route information about the
full path to the destination (sinks in our case). [PEI] presents convergence delay bounds of
path-vector routing protocol using a simplifier version of BGP called Simple
Path Vector Protocol (SPVP). Results are provided for SPVP with various
convergence protocols (a state where all nodes have reached a consensus
regarding the best path to the destinations) including SPVP-AS (SPVP Assertion),
SPVP-GF (SPVP Ghost Flushing), SPVP-RCN (SPVP Route Cause Notification) (refer
[PEI] for
details). SMR is similar to SPVP-GF with respect to the convergence algorithm,
where withdrawl messages are used immediately after a link failure to remove
the paths previously advertised for the path with the failed link. They show
that convergence delay is of the order of O(n2),
where n is number of nodes in the
system (for a clique with n nodes). Although
SMR also uses invalidation (withdrawl) messages, but they are chiefly used for
cases where a link is congested but still up. For broken links, as discussed
earlier we use the full path reversal algorithm on the DAG, which has a complexity in both time and work
of O(m2), where m is the number of nodes that become
destination disoriented (as shown in [COSTAS]). Cleary the repair algorithm of
SMR scales better since it is independent of the number of total nodes in the
network; where as the one used in path vector algorithm depends on the network
size. Moreover since the m is
normally be much smaller than n, time
complexity of SMR repair algorithm is better.
SMR’s route invalidation scheme seems similar to BGP, a path
vector routing protocol. The update messages in BPG contain the withdrawn route field that is used to
specify the routes that need to be withdrawn because of the local routing
policy. SMR uses invalidation messages (INVALs) to withdraw paths due to congested
links upstream in a path (link failure handled differently)
SMR is similar to next hop routing, where each node only
maintains information about their immediate neighbors [FREENET, TAPASTRY]. SMR
adds route quality metric in this hop-by-hop paradigm.
Gradient Broadcast (GRAB) [GRAB] constructs a cost field. The
cost field is rooted at a sink similar to our approach of rooting the gradient
field rooted at a sink. The difference lies in the fact that we don't associate
any cost metric to the gradient fields. A gradient field only gives possible
paths to a sink. Gradient broadcast uses the cost assigned to every node while
forming the cost field as the sole metric to do routing. We can have multiple
sinks, unlike GRAB which is based on a single sink. Problem with the "cost
field" is that since the cost metric is tightly coupled with the field,
the field maintenance becomes a primary concern. This can be a problem for
large ad-hoc networks. In our case, since the GF only provides a direction to
the data, field maintenance is secondary. EMs
take care of informing downstream nodes of broken links (and faulty nodes).
Hence we can delay GF repair. TAG [TAG] also uses in-network aggregation while
routing messages to a central root. The routing to the root is done by creating
a reverse tree using a simple broadcast. A broadcast message from the root
assigns levels (increased by one for each hop the message travel) to every
node. This forms a tree rooted at the root node (see [TAG] for details). When
data from a node needs to be routed to the sink, it is send to its parents.
This is done recursively until the data reaches the root. We also follow a
similar philosophy for constructing the DAG for routing. We use a DAG for
routing instead of a tree, which is more prone to failures. They do propose
some optimization to their system including maintaining multiple parents and
metrics for switching from one parent to another. [CONSIDINE] also uses the
tree approach to route data.
A.
Link Utility Metric
A commonly used approach that is used with the hop count, is
selecting the shortest route with the fastest bottleneck link. This approach
will not work for the wireless networks, where there is inter-channel
interference. In addition, data rate of other links besides the bottle neck
link needs to be considered.
ETX depends on count of the probe messages to calculate the
delivery ratios for the asymmetric link. Since it is based on probe broadcast,
whose data rate will be much smaller that that of the actual data, the delivery
ratio will not reflect the channel loss rate that at the operational data rate.
Another problem with ETX is that since the metric is based on aggregating probe
message in a relative long time (10 seconds, in the scenario given in [ETX]),
it may not react to the changing link quality. This was show to happen in
[DRAVES]. The problem can be mitigated by increasing the frequency of the probe
messages and decreasing the collection time. But this will lead of extra
bandwidth overhead. A related problem in ETX is node mobility. AS shown by
[DRAVES], ETX performed poorly compared to the simple hop-count metric when a
node become mobile (single node moving, while other nodes are still fixed). SMR’s
link throughput metric is based on the throughput calculations using actual
data packets being transferred. Hence the problem of variable loss rate doesn’t
arise. Secondly, to calculate the link delay, SMR uses one probe message (EM)
to calculate the link delay.
[BARUCH] uses the medium time metric (MTM) that assigns a weight
to each link in the network that is proportional to the amount of time used by
sending a packet on that link. MTM doesn’t explicitly take link loss rate into
account.
[YARIS] use a link quality metric calculated based on the
delivery rate of each link. The routing metric for a path is given by the
product of the delivery rates of individual links in the path. Their approach
to calculate the delivery rate is similar to ours. To calculate the delivery
rate for a link, nodes tag the packets with a sequence number. The delivery
rate is calculated by keeping track of the packets received out of the last 32
packets sent. As explained earlier too, this approach for calculating deliver
rate is better than the one used in ETX, which uses link layer broadcast
probes, which are much smaller than the actually data packets. Since the metric
is the product of the various link throughputs, it doesn’t consider channel
interference from neighboring channels.
B.
Anycast and SMR
Anycasting is an inter-network service where a host, application,
or user wishes to locate a server which supports a particular service but, if
several servers support the service, does not care which server is used. This philosophy
resembles the one used in SMR, where the data from the sensor nodes can be
delivered to anyone of the sinks (though preferably to the one that maximizes
network throughput). IP anycast has not been popular due to various reasons
including:
·
Load balancing is not possible in IP anycast: Since
router metric is hop count, IP anycast is not sensitive to loads (server or
link/route)
·
Simpler alternative to IP anycast exists – A Application
layer anycast on one hand is easy to deploy and while on the other provides
better load balancing. A server can monitor the load of host and select the
least loaded one.
Application level anycasting provides a better notation of load
balancing in the network but IP anycast is more robust and scales well with the
number of servers in the anycast group. Integration of SMR in IP anycast can
help in addition of load balancing facility in the network.
SMR based IP anycast service can be summarized as:
·
The network will consist up of SMR routers,
sinks and end host. End host will use the anycast service to reach anyone of
the sinks. SMR routers act as mediators.
·
SMR routers can be spread around in the Internet
·
IP anycast can be used to locate the SMR routers
– a host will send the data message to the common anycast address assigned to
the SMR routers
·
Since SMR routers are expected to be spread out
the Internet, a host will be able to find one close to it, ensuring that the message
delivery delay between the host and the SMR router is small.
·
Once the SMR router receives the message, it can
use the SMR protocol to deliver the message to the best sink.
IX.
Discussion
A.
Path Diversity
As we diverge out, the DAG structure for directing data to the
sinks ensures that the number of nodes that will be sending the data via a node
closer to a sink will increase. A node that lies further away from the sinks
will have less data flowing through it compared to a node that is closer to the
sinks. Since the number nodes in the network will always be much larger than
the number of sinks, this will hold true in majority of the cases. Thus it
becomes important to ensure path diversity at the links closer to the sinks
compared to the start of the route. SMR ensures that the right half of the path
(near the sink) has more diversity compared to the left half (data origin).
B.
Node Identifiers for Sensor Nodes
Globally Unique node identifiers are required for maintaining the
neighbor list in SMR. For any path-vector algorithm, node identifiers are also
used to maintain the path vector. As discussed before, SMR also maintain
path-vectors. It may not be a hard job to assign globally unique identifiers
(GUID) to the nodes in the network. The hardware manufacturer can assign it
when the node hardware is first made [MAC-ADDRESSES] or could be assigned on
the fly by using a random number from a large number space [TAPASTRY]. Although,
it is not possible to totally get rid of the GUID, especially in an ad-hoc
wireless domain, using it for routing can lead to high protocol overhead. GUIDs
need to be used at the link layer to maintain the list of immediately connected
neighbors. Since the maintenance of neighbor list only involves the GUIDs to
travel just one hop, the bandwidth overhead won’t be cumulative. But using
GUIDs for path identifiers will result in a GUID being added at each hop. This
will result in a linear growth of the message (EMs)
size with the size of the network. SMR confines the GUIDs to the link layer
only. For EMs, SMR uses local ids (BID) that
are just few bits in size. BID size depends on the required fan out from a sensor node; hence it
scales irrespective of the number of nodes in the network. For wireless sensor
networks, message size is of importance. To conserve power while transmitting,
the nodes need to keep the message size to a minimum. Hence message overhead becomes important. For
the wired communication, this is not the case. But to maintain generality, we
try to keep the protocol overhead to a minimum.
C.
BGP and SMR
BGP has similar notation of local maxima [BGPRFC] based on
routing policies at each node for selecting paths based on ranking. But since
the data in BGP cannot switch routes at each hop once they select a particular
path to a destination, the functionality of BGP is limited. E.g. as mentioned
in [BGP], it is not possible for one
AS (can be considered as a node in out
network notation) to send traffic to a neighboring AS intending that the
traffic take a different route from that taken by traffic originating in the
neighboring AS. In SMR, this is quite possible. Data in SMR can switch routes
at each hop. This is possible since in SMR, we don’t specify destination
explicitly. The destination can be anyone of the available sinks in the
network. Hence, on reaching a node, each packet can decide which link to choose
irrespective of the path taken by the current data from the node. This is bound
to happen if there is an alternate path available that gives better route
quality.
The major difference between SMR and BGP (and path-vector
algorithms in general) is the notion of destination. BGP has a fixed
destination which is carried all along by the data packet, while it is routed
to a destination (sink). This is not true for SMR. A data packet in SMR has no
destination field. Data is routed to the best possible destination (one of the
sinks) at anytime. This destination can change at anytime depending on the network
state as the data packet moves from one node to another based on the routing
table entries.
BGP can be maintained loop free by the periodic using the
periodic update messages. Loops are removed by comparing the next hop to a
destination with the current and advertised routes. There are two problem
associated with this philosophy for loop removal. Loops can still be formed if
the time interval between two advertisements is large (Minimum Route
Advertisement Interval - MRAI). Secondly, the path vector in the
advertisements needs to be compared with the corresponding entry in the local
routing table, leading to extra processing overhead. SMR on the other hand have
no such problems since loop free paths are guaranteed due to DAG maintenance
and thus is independent of any route advertisements (EMs
in SMR).
D.
Mutable vs. Immutable Path Identifiers
BGP uses a path vector consisting up of a list of IP address
prefix in the Update messages to
carry the path information to a destination. The path vector is also used to
withdraw paths that are no longer valid from nodes in the network. The path
vector is mutable. i.e. individual IP
prefixes can be obtained from it and used. BGP also uses them for loop
detection in the network. We follow a similar strategy, where the path
identifier (PID) is a list of BIDs. Current design doesn’t use the feature of
mutability of PID. But mutable PIDs can be used for source routing [DSR] if needed at a later stage. Every data packet
can carry the exact path (via a PID) that it needs to follow to the sink. A
possible application scenario for source routing is in data aggregation. If the
number of nodes participating in the data aggregation is small, then a set of
static route to the sinks may be useful.
Immutable path identifiers can be generated by hashing the node
identifiers of each node in the path from the sink to a node. A possible hash
function can be the MD5 hash that generates a 128 bit MD5 signature. It can
take in the current signature in the PID field of the EM and concatenate it
with the node identifier of the node. The concatenated PID can then be used to
generate the MD5 signature. The problem with this approach is that the path
identifiers are now immutable. i.e.
we can’t get any information about the path from the final identifier generated
for the path.
X.
Future Directions
SMR can be used on an overlay with nodes spread around on the
Internet. It can be used for aggregating NACKs from a reliable multicast
protocol. NACK implosion is a common problem in networks using reliable
multicast. NACKs can be aggregated at each node in the multicast tree and sent
to the sender. SMR ensures that NACKS
themselves are not lost and arrive at the publisher of the data in the network
using the best route (based on route quality metric).
SMR can be used in the security markets for more efficiently
matching buy/sell orders in an ECN (Electronic Communication Network) [FIN-MKT].
The current ECNs have a central order book that contains all the buy/sell
orders outstanding at any time. Everyone interested in trading shares send
their orders to this central order book. They are matched based on the time
constraint set in the order. For a matched order, an acknowledgement is sent
back to the investor. We envision the central log-book to be decentralized. The
log-book is distributed consisting up of a set of nodes maintaining their own
mini log-books (replication of these mini log-books can be done for even better
fault-tolerance) A node in the network can be considered as a place, where a
buy/sell orders can be generated at a time. Other events including cancel and
modify order, found in Inet [INET] and other common ECNs can also be generated.
The route quality metric indicates the buy/sell
gain with the amount of monitory overhead that the transaction will encounter.
The overhead will be the sum of the per transaction cost (or based on the
number of shares sold/bought) charged by each node that participated in
completing the order. A node charging lower fee will attract more transaction
messages, since a route via it will result in a better route quality. Note that
an order can be matched partially, which will reduce the number of outstanding
shares in that order. The order can be modified, which also results in reducing
the number of outstanding shares in the order. An order can be cancelled, which
will remove it completely from the mini-log book containing that order.
Each company’s share assigned a primary. Primaries are the sinks
in SMR terminology. There will be one primary per listed company. A sink is
responsible for:
·
When a companies share opens for trading, it is
responsible for broadcasting the initial opening price.
·
Broadcasting the current limit prices for the
stock of that company
·
Assigning the Liquidity Flag [OUCH-SPEC] for the execution order and send the
final execution order details to the investor (which is connected to the
network via one of the nodes). Liquidity flag determines if the transaction
execution has reduced/increased the liquidity [FIN-MK] of a stock. Based on the
liquidity, the transaction will either receive a rebate (if increase liquidity)
or will be charged a extra fee (reduce liquidity)
All nodes trading in a particular company’s share forms the part
of the DAG rooted at the sink. When a order is executed partially/fully in a
node via its mini-order table, the execution price and the order details (number
of shares, reference number of the transaction, time of execution) are sent to
the sink (primary) using the DAG. Sink will periodically, using the EM, broadcast
the control information (limit prices, order execution information, liquidity
gain/loss) to the nodes currently subscribed to the company’s stock.
References
[AD-HOC] E.M. Royer and C-K Toh, “A
Review of Current Routing Protocols for Ad-hoc mobile wireless networks”, IEEE
Personal Communications, April 1999.
[MANET] Internet Engineering Task Force.
MANET WG Charter. http://www.ietf.org/html.charters/manet-charter.html.
[DSR] J. Broch, D. Johnson, and D. Maltz.
“The Dynamic Source Routing Protocol for Mobile
Ad Hoc Networks”, Internet Draft, December 1998.
[AODV] C.Perkins, E. Belding-Royer, S.
Das, , RFC 3561-“Ad hoc On-Demand Distance Vector (AODV) Routing”, Network
Working Group, July 2003.
[DSDV] C. Perkins and P. Bhagwat, “Highly
Dynamic Destination Sequenced Distance Vector Routing(DSDV) for Mobile Computers”, In ACM SIGCOMM, pp. 234-244, Oct.
1994.
[SUPER-RES-1] Bose, N.K., Boo, K.J., High
Resolution Image Reconstruction with Multisensors, International Journal of
Imaging Systems and Technology , No. 4, 1998, pp. 294-304.
[SUPER-RES-2] R. Chan, T. Chan, M. Ng, W.
Tang, and C. Wong, Preconditioned iterative methods for high-resolution image
reconstruction with multisensors, Proceedings to the SPIE Symposium on Advanced
Signal Processing: Algorithms, Architectures, and Implementations, Vol. 3461, San Diego CA,
July, 1998
[MADDEN] Samuel R. Madden, Michael J.
Franklin, Joseph M. Hellerstein, and Wei Hong. TAG: a Tiny AGgregation Service
for Ad-Hoc Sensor Networks. OSDI, December, 2002.
[CONSIDINE] Jeffrey Considine, Feifei Li,
George Kollios and John W. Byers. Approximate Aggregation Techniques for Sensor
Databases”, 20th IEEE Int'l Conference on Data Engineering (ICDE '04), Boston, MA,
April 2004
[PATH-VECTOR] J. Garcia-Lunes-Aceves and
S. Murthy. A Path-Finding Alogirthm for Loop-Free Routing. IEEE/ACM Transaction
On Networking, 5(1), February 1997.
[GRAB]Fan Ye, Gary Zhong, Songwu Lu,
Lixia Zhang, ``GRAdient Broadcast: A Robust Data Delivery Protocol for Large
Scale Sensor Networks,'' to appear in ACM Wireless Networks (WINET), Vol. 11,
No.2, March 2005.
[PARK] V. D. Park and M. S. Corson, "A highly
adaptive distributed routing algorithm for mobile wireless networks," in
IEEE Infocom, 1997
[COSTAS] C. Busch, S. Surapaneni, and S.
Tirthapura. Analysis of Link Reversal Routing Algorithms for Mobile
Ad Hoc Networks. Proceedings of the 15th ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA 2003), pp. 210-219, San Diego, California,
June 2003.
[GAFNI] E. M. Gafni and D. P. Bertsekas.
Distributed algorithms for generating loop-free routes in networks with
frequently changing topology. IEEE trans. on commun., COM-29:11–18, 1981.
[BGP-APP] Rekhter, Y., and P. Gross,
"Application of the Border Gateway Protocol in the Internet", RFC
1772, T.J. Watson Research Center, IBM Corp., MCI, March 1995
[BGPRFC] Rekhter, Y., T. Li, "A
Border Gateway Protocol 4 (BGP-4)", RFC 1771, T.J. Watson Research Center,
IBM Corp., MCI, March 1995
[MADDEN] Samuel R. Madden, Michael J.
Franklin, Joseph M. Hellerstein, Wei Hong, “TAG: a Tiny AGgregation Service for
Ad-Hoc Sensor Networks”, OSDI, December, 2002.
[CONSIDINE] Jeffrey Considine, Feifei Li,
George Kollios and John W. Byers. Approximate Aggregation Techniques for Sensor
Databases”, 20th IEEE Int'l Conference on Data Engineering (ICDE '04), Boston, MA,
April 2004.
[FREENET] I. Clarke, O. Sandberg, B.
Wiley, and T. Hong. Freenet: A distributed anonymous information storage and
retrieval system. In Proceedings of the ICSI Workshop on Design Issues in
Anonymity and Unobservability, Berkeley,
California, June 2000.
[NAPSTER] Napster. At http://www.napster.com.
[GNUTELLA] Gnutella. At http://
gtk-gnutella.sourceforge.net
[TAPASTRY] Tapestry: A Resilient
Global-scale Overlay for Service Deployment, Ben Y. Zhao, Ling Huang, Jeremy
Stribling, Sean C. Rhea, Anthony D. Joseph, and John D. Kubiatowicz. Appears in IEEE Journal on Selected Areas in
Communications, Vol 22, No. 1, January 2004
[OVERLAY] David G. Andersen, Hari
Balakrishnan, M. Frans Kaashoek, Robert Morris, "Resilient Overlay
Networks", Proc. 18th ACM SOSP, Banff, Canada, October 2001.
[FIN-MKT]
Levinson, Marc, “Guide to financial markets”, Princeton, N.J.,
Bloomberg Press, 3rd Edition, 2003.
[PEI] Dan
Pei, Beichuan Zhang, Dan Massey, and Lixia Zhang. "An Analysis of
Path-Vector Routing Protocol Convergence Algorithms", Techinical Report,
UCLA CSD TR-040009, March 2004.
[BARUCH] Baruch Awerbuch and Dave
Holmer and Herb Rubens, High Throughput Route Selection in Multi-Rate Ad Hoc
Wireless Networks, Wireless On-demand Network Systems, Kluwer MONET, Special
Issue on "Internet Wireless Access: 802.11 and Beyond", Jan 2004
[DRAVES] R. Draves, J. Padhye,
and B. Zill. "Comparison of Routing Metrics for Static Multi-Hop Wireless
Networks", Proc. of Sigcomm 2004, Portland,
OR, USA,
September 2004
[ETX] Douglas S. J. De Couto,
Daniel Aguayo, John Bicket, and Robert Morris, "A High-Throughput Path
Metric for Multi-Hop Wireless Routing", Proc. of the Ninth Annual
International Conference on Mobile Computing and Networking (MobiCom '03), San
Diego, California, September 2003
[YARVIS] Mark D. Yarvis, W.
Steven Conner, Lakshman Krishnamurthy, Jasmeet Chhabra, Brent Elliott, and Alan
Mainwaring, "Real-World Experiences with an Interactive Ad Hoc Sensor
Network," Proceedings of the International Workshop on Ad Hoc Networking
(IWAHN 2002), Vancouver, British Columbia, Canada, August, 2002
[ARPANET-METRIC] A. Khanna and J.
Zinky. The revised ARPANET routing metric. Proceedings of the SIGCOMM '88
Symposium, pages 45--56, August 1988
XMOHAN