Transcript CROSS-ROAD: CROSS-layer Ring Overlay for AD hoc networks

CROSS-ROAD:
CROSS-layer Ring Overlay for AD Hoc
Networks
Franca Delmastro
[email protected]
IIT-CNR Pisa
Cambridge, March 23rd 2004
Ring Overlay & Pastry Model




The ring overlay is a circular address space where
nodes and data are logically mapped.
Pastry uses a DHT to convert nodes and data identifiers
on logical addresses that are used to route messages
through the network
There is no correspondence between logical and
physical distances
It provides a subject-based data routing that often
requires a multi-hop network routing to reach the
destination.
Logical & Physical distances
Pastry Ring
0 2128 - 1
The Pastry Ring
(K2 ,V)
(K1 ,V)
L2 = H(K2 )
L1 = H(K1)
0 2128 - 1
L1
X2
N1
L2
N2
X1
X1 = H(N1)
X2 = H(N2)
Pastry routing tables
02212102
0 2128 - 1
10233001
10233102
10233232
10323302
11301233
Pastry Multi-hop Routing
02212102
0 2128 - 1
33301201
23301201
23301101
Route(23302121)
10233102
23000101
22301203
Compare(10233102, 23302121) = 0
bestMatch(RoutingTable[0], 23302121 ) =
22301203
Joining the Ring



X has to know a own physical
neighbor already present in
the ring (node A)
0 2128 - 1
A route a message with key
equal to X
X
Z
Pastry Routing table of node X
is initialized using routing
tables of contacted nodes:

LS(X) = LS(Z)

NS(X) = NS(A)

RT(X) is a join of the routing
tables of other nodes,
according to the prefix shared
metric
Bk
Route(X)
B2
A
X
Join(X)
B1
Disconnection from the ring



Each node executes a polling procedure to discover
“remote” nodes status (referred only to routing table
knowledge).
A “remote” node is considered disconnected from the
Pastry network if it doesn’t answer to a polling message
before a timeout expiration
After a disconnection event, the sender of the polling
message has to update its routing tables contacting
other “remote” nodes to fill in entries related to that
node.
Pastry Pros & Cons

Pros:




DHT allows an uniform distribution of IDs and
workload on nodes taking part to the service
The subject-based routing defines a logarithmic lookup
cost on the network dimension (O(log N))
A lot of application can adapt their contents to this
routing strategy
Cons:


Routing tables management based on remote
connections can be a big overhead on ad hoc networks
Forcing the network routing with the subject-based
policy can reduce network performances
Using Cross-Layer to CROSS-ROAD

Applications
Middleware

NeSt
Transport

Network
In order to build an overlay
network, the middleware can
directly use the Network
Routing table.
Node ID = H(IPaddress)
Since each ring is associated
to a service, the routing
protocol has to provide
Service Location
MAC

Using a proactive LINKSTATE routing protocol, each
node knows the entire
network
Middleware routing can send messages directly to their
FINAL destination.
Efficient proactive Link-State

Proactive routing protocols are usually considered
inefficient for ad hoc networks

An optimization has been studied: “Hazy Sighted Link
State”* (HSLS)

Each node sends periodical LSU packets on the network
with frequencies inversary proportional to the routing
hops number.

“Hazy” knowledge of distant nodes. Their status is not
frequently updated as the 1-hop neighbors.

Simulations showed that HSLS scales with the network
size.
(*) C. Santivanez, I. Stavrakakis et al., “Making Link-State Routing Scale for Ad Hoc Networks”,
MobiHoc 2001
(*) C. Santivanez, I. Stavrakakis et al., “On the Scalability of Ad Hoc Routing Protocols”, INFOCOM 2002
CROSS-ROAD overlay

Working hypothesis:

A
Middleware
level
B
A

Network
level
B
Nodes providing service S
Each node has to be
characterized by at
least:
(IPaddress, Services,
1hop-neighbors)

Ad Hoc Network nodes
The Network level
gives a graph
representing the
network topology to
the Nest
The middleware
level can access to
this graph and
recover relevant
information for itself
Interactions with NeSt
Middleware
Data
Abstraction
Local
Provided
services
Node A
Node B
Middleware
Middleware
NeSt
NeSt
Network
Data
Abstraction
Middleware
Data
Abstraction
Network
Network
Application
messages
Topology
update and
remote
services
LSU routing pkt containing
services publications and
topology updates
Network
Data
Abstraction
CROSS-ROAD Routing Tables
CROSS-ROAD Routing Table
Destination ID
= H(IP address)

Cost

Each node defines the
ring autonomously
CROSS-ROAD routing
table contains only nodes
taking part to the service
(Leafset and Neighborset
disappear)

Network Routing Table
Destination
IP address
Next Hop
IP add.
Cost
Services

Middleware routing
protocol is limited to a
peer-to-peer connection
Messages forwarding is
realized by the network
routing protocol
Pastry vs CROSS-ROAD

PASTRY:

Join operation requires
many remote
connections to recover
routing tables contents
HIGH COST at middleware
level

CROSS-ROAD:

Join operation does not
require remote
connections: each node
can build its ring
autonomously
NO COST at middleware
level
Pastry vs CROSS-ROAD

PASTRY:

The detection of
disconnection events
requires polling cycles
towards remote nodes
HIGH COST at middleware
level

CROSS-ROAD:

Disconnection events are
detected by the netwrok
routing protocol through
LSU packets
NO COST at middleware
level
Pastry vs CROSS-ROAD

PASTRY:

Routing table fixed size
involves a not complete
knowledge of the
network
HIGH COST for tables
management due to remote
connections following
topology updates

CROSS-ROAD:

Routing table size
depends on the number
of nodes taking part to
the service
NO COST at middleware
level: local interactions with
NeSt are sufficient to
update routing tables
Pastry vs CROSS-ROAD

PASTRY:

Subject-based routing
involves a multi-hop
middleware routing
O(log(N)) middleware
lookup cost

CROSS-ROAD:

Subject-based routing
involves a peer-to-peer
connection
O(1) middleware lookup
cost, the remaining is a
routing task
CROSS-ROAD Software Architecture
CROSS-ROAD
NodeHandle
CROSS-ROAD
Node
NeSt
Service
Notification
Endpoint
Topology
Abstraction
(GRAPH)
Hash ID
Factory
CROSS-ROAD
Messages
CROSS-ROAD
Routing Table
Link-State Routing
Topology
table
Routing Table
LSU
Management
P2P
CommonAPI
Client/Server
Manager
Routing
Messages
Socket
Manager
Further optimizations: Cost Metrics

Possible metrics to determine the best route from a
source to a destination:

Number of routing hops

Path reliability based on nodes mobility

Mobility index: number of times that a node changed its
position in a specified time interval.

It can be determined by the Network routing protocol
consequently to LSU packets reception.

It can be used by CROSS-ROAD to define the best
nodes for replicas storage.