Transcript Christopher Wilder - P2P Over MANET

MANETs, P2P, and P2P
MANET Overlays
An Introduction to the Components of Mobile
Resource Sharing on an Ad Hoc Overlay
Network
Chris Wilder
Introduction to MANETs
• Mobile Ad Hoc Network (MANET)
• The IETF – MANET Autoconfiguration (2007)
document defines a MANET as a routing domain
comprised of MANET routers [2]
• Started out as packet radio back in the 1970’s
and 80’s
• Under research for the past 10 years
• Only a small amount of MANETs are currently
used in the real world and are primarily used by
the military and emergency response teams
MANET Terminology
• MANET Neighbors
– Two or more MANET Routers that can directly
communicate with each other, without
needing other routers to bridging the
communication path between the
communicating routers
• Semi-Broadcast Interface (SBI)
– A broadcast capable interface that may exhibit
asymmetric reachability [2]
MANET Neighbors
N3
N4
N2
MR1
MR2
MR3
N1
N5
MR4
N6
Attributes of MANETs
•
•
•
•
•
•
•
•
Multihop Networks
Autonomous system of mobile routers and nodes
All elements reside on wireless domains
Nodes can join and leave the network at any time
Dynamic topology
Wireless connectivity implements node mobility
Primarily operates in the network layer (layer 3) as a means of routing, but can be implemented in
other layers as well
Asymmetric Reachability
–
Transitive communication:
•
–
Non-bidirectional communication:
•
•
Even though data send from A is able to be received by C, data sent from C may not reach A
MANETs do not scale well
–
–
–
–
•
Data sent from A can be received by B and data sent from B are reachable by C, but it is not certain that data sent from A
can be received by C
Network performance dissipates exponentially as the network grows larger
MANETs with anywhere between 2 to 100 MANET Routers don’t suffer from performance problems
A big or very big MANET, consisting of any where between 100 to 1000 or more MANET routers, has
scalability issues and comes at the high cost of performance degradation.
The scalability problem is caused by the required features of the MANET routing protocols which enable
them to successfully operate on a mobile ad-hoc network. Solutions to this problem are being researched
MANETs can be implemented as an overlay on top of any wired topology or network
MANET Asymmetric Reachability
N3
N4
N2
MR1
N6
N1
N5
MR3
MR2
MR4
MANET Components
•
MANET Interface (MI)
– An MI is commonly recognized by it’s unique time-varying asymmetric
Reachability[2]
– Connecting point where nodes can attach[1]
– Allows MANETs to connect to each other
– Every MANET Interface has a unique identifier, usually an IP address
• Routers that support both wired networks and MANETs have both an IP address and a
separate unique identifier to represent the MANET interface
•
MANET Router (MR)
–
–
–
–
–
Classified as having one or more MANET interfaces
May have zero or more non-MANET Interfaces
Only one MR is required to setup a MANET, however, the more the better
Hides MANET characteristics from all nodes that are not MANET aware.
Routers which support intercommunication have two or more interfaces which
includes a MANET interface (wireless) and one or more wired interfaces
– MANET packets are encapsulated in IP packets and vice versa
– Specific MANET routing protocols are used to route traffic through out a MANET
[1]
MANET Routing Protocols
• Only MANET routing protocols can be used on a MANET
• Any of the traditional routing protocols are not designed to work in a
unpredictable and dynamic network such as a MANET
• The MANET routing protocols are unstructured, which is the reason
why MANETs do not scale well.
• Ad-Hoc Routing Protocols
– Ad-Hoc On-Demand Distance Vector (AODV)
• Type = Reactive
– Searches for routing paths or routes on-demand
– If a route to a specific destination does not exist, then it is created
• When the route to a desired host doesn’t exits, route request (RREQ)
messages are generated and sent out using the expanding ring technique to
flood the network
• Problems
– Flooding the network with RREQ messages causes an initial network delay
– Performance degrades as the size of the network grows
MANET Routing Protocols
•
Ad-Hoc Routing Protocols (cont.)
– Optimized Link State routing (OLSR)
• Type = Proactive
– Routing records are actively updated and maintained as changes to the topology occur
– In practice, all nodes should be fully aware of their network
• Routing information is stores in a table structure
• Uses a technique called MultiPoint Relaying to optimize routing
– Visited nodes are recorded to avoid loops and ensure duplicate retransmissions don’t occur
• Problems
– Overhead is created by the constant routing traffic
– Not scaleable, comes at the cost of performance
– Zone Routing Protocol (ZRP)
• Type = Hybrid
– Uses both reactive and proactive routing protocols
• Uses both the reactive and proactive type routing protocols
• The network is separated into zones, by routing protocol
– Intrazone
» Proactive (local) – Intrazone Routing Protocol (IARP)
– Interzone
» Reactive (Global) – Interzone Routing Protocol (IERP)
• Bordercast Resolution Protocol (BRP) is used to maintain and control traffic between
zones
• Problems
– Not very scalable
– Inherits the weaknesses from both the Proactive and Reactive Routing protocols
Peer to Peer (P2P): An Overview
• Decentralized system of nodes that are connected to
each other, logically and/or physically, via an ad-hoc
connection
• Client-Server type architecture exist (e.g. Napster), but
are not used as much as they used to
• Implemented at the application layer (Layer-7) [4]
• Notoriously used for file sharing and transferring realtime data (i.e. internet telephone or instant messaging
services)
• Pure P2P does not have a distinction between client or
server nodes, each node operates as an individual
Types of P2P Architectures
• Structured
– Uses distributed hash tables (DHT) for the location of resources
– Examples: Chord, Pastry, etc.
• Unstructured
– Multicasting is send out queries for data (i.e. files, nodes, etc.)
– Examples: Gnutella, FastTrack
• Overlay
– Uses both structured and unstructured protocols as layers in an effort to
utilize the strengths of each protocol
• The structured layer may exists as the top layer
– Peers are organized into groups in the unstructured layer, using some criteria (i.e.
proximity, resource availability, etc)
• The unstructured layered is used as the bottom layer of the overlay
– Organized by the structured layer to optimize performance
– Example: Bit Torrent
P2P: Chord System
•
•
•
•
•
•
•
A structured approach to implementing a P2P system
Uses a distributed hash table to lookup nodes and locate resources
Decentralized, does not have a single point of failure
Symmetric
Fault tolerant or failure transparent
Adaptable to change, the system has the ability to adjust to nodes joining
and leaving (i.e. node churn)
The system supports the following operations[5]
– Addition and departure of Chord server nodes
– Insert, update, and lookup of unstructured key/value pairs
•
•
•
Insertions and lookups occur logarithmically
The sole responsibility of the Chord protocol is to use a specified key and
find which node in the system is in charge of storing the key’s
corresponding value
Generalized, it can be used to implement different types of systems
– Can be used as an alternative to the client/server model
P2P: Chord System
• Queries
– Used for looking up nodes and/or resources
– Occur in logarithmic time, in a system of N nodes only
log N nodes are queried with a specified key k
• Keys are well balanced [5] meaning each node
is responsible for a predefined number of keys
• Results in the success or a definitive failure [5]
• In an system N nodes:
– Lookups are average at O(log N)
– When the Nth node joins or leaves the network, only
an average of O(1/N) key/value pairs need to be
updated [5]
P2P: Chord System
• An overlay network of Chord nodes
• Each node, n, maintains a subset of key/value pairs and routing
table consisting nodes that are well known
• The logical model of the system of identifiers is a circle where each
node has a successor and a predecessor
• A proximity functions may be used to arrange nodes by identifiers,
location, etc.
• The routing tables are referred to as finger tables in which m is the #
of bits used in the binary representation of the key/node ID.
• Only m entries exist in a finger table
• Each node, n, has an entry for itself and its successors stored in its
finder table
• “The ith entry in the table at node n contains the identity of the first
node, s, that succeeds n by at least 2i-1 on an identifier circle
P2P: Chord System
Finger Table
n = 2, m = 3
Finger Table Index
Start
Interval
Successor
(i <= m)
(Node ID)
i
(n + 2i-1) mod m
[finger[i].start,
finger[i+1].start)
1
3
[3,4)
4
2
4
[4,6)
4
3
6
[6,2)
1
P2P: Chord System
Start
Int.
Succ.
0
[0,1)
1
1
[1,3)
1
3
[3,7)
4
Start
Int.
Succ.
2
[2,3)
2
3
[3,5)
4
5
[5,1)
7
Start
Int.
Succ.
3
[3,4)
4
4
[4,6)
4
6
[6,2)
7
0
1
7
6
2
5
3
4
Start
Int.
Succ.
5
[5,6)
0
6
[6,0)
7
0
[0,4)
1
P2P: Chord System - DHT
• Keys are an array of bytes to symbolize a random m-bit key
identifier
• Node identifiers are determined by hashing the IP address or some
unique ID of the node to the m-bit identifier space[5]
• Each key has an identifier and the key identifier is found by hashing
the key into an m-bit space
• Values are also considered as an array of bytes
• It is up to the application to define what the array of bytes represent
• Values may represent:
– Locations of resources such as an IP address or a pointer to some
location, etc.
– Identifiers, for example: filename or the id of a node in the network, etc.
– Actual data itself (e.g. files, etc.) [5]
P2P: Chord System - Hashing
Hash Function
Key (m = 3)
Key = 0x001
0
0
1
Hashes to 0x006
Array of Values or Identifiers
null
0
null
1
null
2
null
3
null
4
null
5
data
6
...
7
...
...
null
n-1
n
Data
1
0x006
0
1
1
0
0
0
1
0
1
P2P Over MANET
• A mobile ad hoc network with a peer to peer overlay
network
• A MANET will operate in the first four layers of the OSI
model, while P2P will run in the fourth through seventh
layer. This is only a general case
• Next generation of client based networks
• Can be implemented in more than one way considering
that:
– There is more than one MANET protocol
– P2P can be built as a structured, unstructured, or overlay type
network
– Each P2P network architecture has a multitude of protocols and
characteristics which inhibit their own unique features and
constraints
P2P Over MANET Protocol Stack
OSI
P2P
Application
Application
Presentation
Presentation
Session Layer
MANET
Session Layer
Transport
Transport
Transport
Network
Network
Data-link
Data-link
Physical
Physical
Homogeneous Characteristics of
P2P and MANET
• Supports node churning [2]; consistency of nodes entering and
leaving the network
• Self-organizing architectures [4]
• Traffic patterns closely resemble those caused by multi-hop
broadcasting or multicasting [3]
• Dynamic topology
• The ability for nodes to rearrange themselves when connecting to
the network
• Fault tolerant; resistant and transparent to errors
• Unique Identifiers are required to identify nodes
• Decentralized
• Nodes can act as a client and/or server node
• Nodes have the ability to perform routing services
Why P2P Over MANET
• P2P and MANETs share many similarities[4]
• P2P offers the stability that MANETs lack
– Overlaying P2P on top the unstructured routing protocols of a MANET
gives MANETs alleviates some of the problems that are difficult to solve
using just MANET routing protocols
– Frequent topology changes that occur in a MANET in some cases can
be better manage by an application layer protocol
• P2P Over MANET is not as expensive to scale as a MANET
• Differences between both networks compliment each other when
combined
• A MANET provides the underlying network for a P2P application to
reside on
• MANETs track the location of peers
• P2P manages the location of resources (data-centric
Building a P2P MANET Overlay
Architecture
•
•
•
No standard architectures currently exist
A common approach made when designing a P2P MANET Overlay is to layer the
P2P on top of the MANET [4]
Build a list of optimization and specification criteria
–
•
Ad-Hoc Routing Protocol
–
–
•
Consider the benefits and drawbacks
Size of network
P2P Architecture
–
–
•
Useful when selecting which protocols, topology, and architecture to use
Use a the P2P architecture that will offer the best solution to the network constraints
Compare and contract P2P protocols with the ad-hoc routing protocols
The structure of the overlay as a whole
–
–
–
–
–
How many layers
How is each layer implemented
Benefits and drawbacks of the structure of the overlay
What will the network be used for
What type of environment will the network exist in
Examples of P2P Over MANET
systems
• An integrated approach for P2P file sharing on a
MANET (Tang, Zhou, Kashyap, Chuieh)[4]
– Uses FASTTRACK as the application layer protocol
• FASTRACK is an unstructured P2P protocol
• Super peers are added to the P2P overlay to
–
–
–
–
–
Increase scaling capabilities
Reduce network delay
Assist in failure recovery
Mange node churn
Improve performance
• Each super peer is aware all the nodes and resources of it’s
underlying network
– The ad-hoc on-demand distance vector (AODV) adhoc routing protocol is used to implement the MANET
layer
Examples of P2P Over MANET
systems
•
An integrated approach for P2P file sharing on a MANET (Tang, Zhou,
Kashyap, Chuieh)[4]
– The AODV routing protocol and the FASTTRACK P2P protocol are both
unstructured
• Both use similar look up techniques
• Both use flooding to query the network
– An overview of how it works
• All peers are physically connected through the underlying MANET architecture
• Peers are grouped into multiple unstructured groups and each group is assigned a
super peer
• The super peers for each group are used to form the top unstructured P2P layer
• When a peer is searching for a file, the lower P2P layer is queried
• If the file is found, is location is returned to the requesting peer
• If the file is not found, the file request is sent to the super peer, and thus it is sent out on
the top layer network, to query all the super peers
– The AODV and FASTTRACK protocols are configured so that the file requested
and established route can be determined simultanesously[4]
Examples of P2P Over MANET
systems
• A better approach is to use a structured
P2P protocol such as chord and layer it
over the AODV MANET routing protocol.
– (See the image on the next slide)
References
[1] S. Corson and J. Macker. “Mobile Ad Hoc Networking (MANET):
Routing Protocol Performance Issues and Evaluation Considerations”,
IETF Network Working Group, January 1999, RFC 2501,
(http://www.ietf.org/rfc/rfc2501.txt).
[2] I. Chakeres, J. Macker, and T. Clausen, “Mobile Ad Hoc Network
Architecture draft-ieft-autoconf-manetarch-06”, IETF Internet-Draft
MANET Autoconfiguration (AUTOCONF), October 2007.
[3] Aisling O’ Driscoll, Susan Rea, and Dirk Pesch, “A Framework for
Supporting Structured Peer-to-Peer P2P Overlays over Large Scale
Mobile Ad-Hoc Networks (MANETs), Wireless World Research Forum,
CAWS, Cork Institute of Technology, Ireland.
[4] Bin Tang, Zongheng Zhou, Anand Kashyap, and Tzi-cker Chiueh, “An
integrated approach for P2P file sharing on multi-hop wireless
networks”, Department of Computer Science, Stoney Brook University.
[5] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari
Balakrishnan, “Chord: A scalable peer-to-peer look service for Internet
applications”, MIT-LCS-TR-819.