Transcript Middleware issues for ad hoc networks

Middleware issues:
From P2P systems to Ad Hoc Networks
Franca Delmastro
[email protected]
Pervasive Computing & Networking Lab (PerLab)
IIT-CNR Pisa
MobileMAN Project
Helsinki, June 7th 2004
Middleware for Ad Hoc networks

Ad Hoc networks and P2P systems:

The distribution of services and data can fit well
with the decentralized nature of Ad Hoc
networks

In both cases nodes interactions are temporary

Resources are distributed among heterogeneous
nodes

Systems must be reliable in case of node
failures and disconnections events
The fundamentals of the
structured overlay network


CAN, Chord, Pastry et al. represents a family of
middleware solutions for large-scale P2P
systems
They use a Distributed Hash Function (DHT) to
map physical addresses to a logical address
space

Information and workload are uniformely
distributed on the network

System scalability with the number of nodes is
the main objective for ad hoc networks
The Pastry model




The overlay network is a circular address space
where nodes and data are logically mapped.
There is no correspondence between logical
and physical distances
Subject-based routing reduce the lookup cost to
a logarithmic cost
There are a lot of applications implemented for
this solution, and many others are adaptable to
this routing policy
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 sends 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 providing 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 for ad hoc networks
Forcing the network routing with the subject-based
policy can reduce network performances
Using Cross-Layer to CROSS-ROAD
CROSS-layer Ring Overlay for AD hoc networks

Applications
Middleware
NeSt
Transport


Network
MAC
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

Using a proactive LINKSTATE routing protocol, each
node knows the entire
network
Hazy Sighted Link-State



Optimization of Proactive routing protocols
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.
(*) 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
provide 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