Transcript 现代通信新技术导论第六章分布式网络Chapter 6

现代通信新技术导论
第六章 分布式网络
Chapter 6 Distributed Networks
电控学院 电子工程学科部
司鹏搏 综合楼825室
[email protected]
1
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
–
–
–
–
–
–
–
–
–
6.1.1 Distributed Networks
6.1.2 Introduction to MANETs
6.1.3 Design of MANETs
6.1.4 Network Routing Overview
6.1.5 Proactive Protocols
6.1.6 Reactive Protocols
6.1.7 Energy Efficient and Unicast Routing
6.1.8 Energy Efficiency Multi-/Broadcast Routing
6.1.9 Geographic Routing
• 6.2 P2P Networks
2
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
• 6.2 P2P Networks
–
–
–
–
–
–
–
6.2.1 Introduction to P2P
6.2.2 Why P2P?
6.2.3 Overview of P2P
6.2.4 Unstructured P2P (Gnutella)
6.2.5 Structured P2P (with DHTs)
6.2.6 Performance of P2P Lookup Protocols
6.2.7 Bi-Dimensional P2P
3
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
–
–
–
–
–
–
–
–
–
6.1.1 Distributed Networks
6.1.2 Introduction to MANETs
6.1.3 Design of MANETs
6.1.4 Network Routing Overview
6.1.5 Proactive Protocols
6.1.6 Reactive Protocols
6.1.7 Energy Efficient and Unicast Routing
6.1.8 Energy Efficiency Multi-/Broadcast Routing
6.1.9 Geographic Routing
• 6.2 P2P Networks
4
现代通信新技术导论 第六章 分布式网络
6.1.1 Distributed Networks
• Distributed-Network-Layer Networks
– Ad Hoc networks (Mobile Ad Hoc networks, MANETs)
– Wireless sensor networks (WSNs)
– Mesh networks
• Distributed-Application-Layer Networks
– Peer-to-peer (P2P) networks
5
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
–
–
–
–
–
–
–
–
–
6.1.1 Distributed Networks
6.1.2 Introduction to MANETs
6.1.3 Design of MANETs
6.1.4 Network Routing Overview
6.1.5 Proactive Protocols
6.1.6 Reactive Protocols
6.1.7 Energy Efficient and Unicast Routing
6.1.8 Energy Efficiency Multi-/Broadcast Routing
6.1.9 Geographic Routing
• 6.2 P2P Networks
6
现代通信新技术导论 第六章 分布式网络
6.1.2 Mobile Ad Hoc Networks
• Characteristics
–
–
–
–
–
–
–
–
–
Distributed network
Cooperative network
Self-organized network
Self-recovery
No infrastructure needed
Mobile network, different from mesh networks
Dynamic topology, different from mesh networks
Heterogeneous nodes, different from wireless sensor networks
Un-directional data flow, different from wireless sensor networks
• Applications
– Extension to the cellular networks, battle fields, dangerous
exploring, after-disaster working, monitoring …
7
现代通信新技术导论 第六章 分布式网络
6.1.2 Key Elements of MANETs
• Formed dynamically through the cooperation of
independent nodes
• Nodes do not have any pre-specified roles
• Nodes make decision independently based on the
current network situation
• Nodes are expected to behave as
– Information sources/sinks
– Routers
• As routers, nodes must assist in discovery and
maintenance of network route
8
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
–
–
–
–
–
–
–
–
–
6.1.1 Distributed Networks
6.1.2 Introduction to MANETs
6.1.3 Design of MANETs
6.1.4 Network Routing Overview
6.1.5 Proactive Protocols
6.1.6 Reactive Protocols
6.1.7 Energy Efficient and Unicast Routing
6.1.8 Energy Efficiency Multi-/Broadcast Routing
6.1.9 Geographic Routing
• 6.2 P2P Networks
9
现代通信新技术导论 第六章 分布式网络
6.1.3 Design of MANETs
• Issues to be considered
–
–
–
–
–
–
–
–
–
–
Infrastructureless with distributed management
Frequent and unpredictable topology changes
Physical layer limitation
Limited link bandwidth and quality
Variation in node capabilities
Energy Considerations
Network reliability
Network security
Network scalability
Quality of service
10
现代通信新技术导论 第六章 分布式网络
6.1.3 Design of MANETs
• Physical Layer
– OFDM, DSSS, FHSS, …
– IEEE 802.11, Bluetooth, ZigBee, …
• MAC Layer
– CSMA/CA, CDMA, …
– IEEE 802.11, Bluetooth, ZigBee, …
• Network Layer
– The most important issue to be considered
– Different from other networks
• Wired distributed networks, e.g., Internet
• Wireless distributed networks, e.g., wireless mesh, WSN, …
11
现代通信新技术导论 第六章 分布式网络
6.1.3 MANETs Management
• Multihop network – each device must carry burden of routing
packets from source to destination
• Each Node handles part of the management of the network
• Fault detection is extremely difficult because of the distributed
design
12
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
–
–
–
–
–
–
–
–
–
6.1.1 Distributed Networks
6.1.2 Introduction to MANETs
6.1.3 Design of MANETs
6.1.4 Network Routing Overview
6.1.5 Proactive Protocols
6.1.6 Reactive Protocols
6.1.7 Energy Efficient and Unicast Routing
6.1.8 Energy Efficiency Multi-/Broadcast Routing
6.1.9 Geographic Routing
• 6.2 P2P Networks
13
现代通信新技术导论 第六章 分布式网络
6.1.4 Network Layer Routing Overview
• Network with nodes, edges
• Goal: Devise scheme for transferring
message from one node to another
– Which path?
– Who decides – source or
intermediate nodes or destination?
• Types
–
–
–
–
msg
Unicast routing
Energy efficiency & unicast routing
Multi-/broadcast routing
Geographical routing
14
现代通信新技术导论 第六章 分布式网络
6.1.4 Routing Problems
• Which Path?
– Generally try to optimize something:
•
•
•
•
Shortest path (fewest hops)
Shortest time (lowest latency)
Shortest weighted path (utilize available bandwidth)
……
• Who Determines Route?
– Source routing
• Or path routing
– Destination routing
• Or hop-by-hop routing
15
现代通信新技术导论 第六章 分布式网络
6.1.4 Who Determines Route
• Source (“Path”) Routing
– Source specifies entire route: places complete path to destination in
message header: A – D – F – G
– Intermediate nodes just forward to specified next hop: D would
look at path in header, forward to F
– Like airline travel – get complete set of tickets to final destination
before departing…
• Destination (“Hop-by-Hop”) Routing
– Source specifies only destination in message header: G
– Intermediate nodes look at destination in header, consult internal
tables to determine appropriate next hop
– Like postal service – specify only the final destination on an
envelope, and intermediate post offices select where to forward
next…
16
现代通信新技术导论 第六章 分布式网络
6.1.4 Comparison
• Source Routing
– Moderate source storage (entire route for each desired
dest.)
– No intermediate node storage
– Higher routing overhead (entire path in message header,
route discovery messages)
• Destination Routing
– No source storage
– High intermediate node storage (table w/ routing
instructions for all possible dests.)
– Lower routing overhead (just dest in header, only
routers need deal w/ route discovery)
17
现代通信新技术导论 第六章 分布式网络
6.1.4 Unicast, ID-centric Routing
• Given: a network/a graph
– Each node has a unique identifier (ID)
• Goal: Derive a mechanism that allows a packet sent from an
arbitrary node to arrive at some arbitrary destination node
– The routing & forwarding problem
– Routing: Construct data structures (e.g., tables) that contain
information how a given destination can be reached
– Forwarding: Consult these data structures to forward a given
packet to its next hop
• Challenges
– Nodes may move around, neighborhood relations change
– Optimization metrics may be more complicated than “smallest hop
count” – e.g., energy efficiency
18
现代通信新技术导论 第六章 分布式网络
6.1.4 Routing Features
• Every node participates in routing: no distinction between “routers”
and “end nodes”
• No external network setup: “self-configuring”
• Especially useful when network topology is dynamic (frequent network
changes – links break, nodes come and go)
• Mobile wireless hosts
– Can only communicate to the subset within range at given time
– Want to communicate with any other node
19
现代通信新技术导论 第六章 分布式网络
6.1.4 Routing Protocols
• Because of challenges, standard routing approaches not
really applicable
– Too big an overhead, too slow in reacting to changes
– Examples: Dijkstra’s link state algorithm; Bellman-Ford
distance vector algorithm
• Simple solution: Flooding
– Does not need any information (routing tables) – simple
– Packets are usually delivered to destination
– But
• Overhead is prohibitive
• Usually not acceptable, either
• Need specific, ad hoc routing protocols
20
现代通信新技术导论 第六章 分布式网络
6.1.4 Routing Protocols
• Main Question to Ask: When Does the Routing Protocol
operate?
• Option 1: Routing Protocol Always Tries to Keep its
Routing Data up-to-Date
– Protocol is proactive (active before tables are actually needed)
or table-driven
• Option 2: Route is only Determined when Actually
Needed
– Protocol operates on demand
• Option 3: Combine these Behaviors
– Hybrid protocols
21
现代通信新技术导论 第六章 分布式网络
6.1.4 Routing Protocols
• Is the Network Regarded as Flat or Hierarchical?
– Compare topology control, traditional routing
• Which Data is Used to Identify Nodes?
– An arbitrary identifier?
• The position of a node?
• Can be used to assist in geographic routing protocols because
choice of next hop neighbor can be computed based on destination
address
– Identifiers that are not arbitrary, but carry some structure?
• As in traditional routing
• Structure akin to position, on a logical level?
22
现代通信新技术导论 第六章 分布式网络
6.1.4 Routing Protocols
• Standardization Effort Led by IETF MANET Task Group
– http://www.ietf.org/html.charters/manet-charter.html
– 9 routing protocols in draft stage, 4 drafts dealing with broadcast /
multicast / flow issues
• Other Protocols Being Researched
– Utilize geographic / GPS info, ant-based techniques, etc.
• Typical Routing Protocols
– DSR: Dynamic Source Routing
• Source routing protocol
– AODV: Ad-hoc On-demand Distance Vector Routing
• “Hop-by-hop” protocol
– Both are “on demand” protocols: route information discovered
only as needed
23
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
–
–
–
–
–
–
–
–
–
6.1.1 Distributed Networks
6.1.2 Introduction to MANETs
6.1.3 Design of MANETs
6.1.4 Network Routing Overview
6.1.5 Proactive Protocols
6.1.6 Reactive Protocols
6.1.7 Energy Efficient and Unicast Routing
6.1.8 Energy Efficiency Multi-/Broadcast Routing
6.1.9 Geographic Routing
• 6.2 P2P Networks
24
现代通信新技术导论 第六章 分布式网络
6.1.5 Proactive Protocols
• Idea: Start from a standard routing protocol, adapt it
• Adapted distance vector: Destination Sequence Distance
Vector (DSDV)
– Based on distributed Bellman Ford procedure
– Add aging information to route information propagated by
distance vector exchanges; helps to avoid routing loops
– Periodically send full route updates
– On topology change, send incremental route updates
– Unstable route updates are delayed
– … + some smaller changes
25
现代通信新技术导论 第六章 分布式网络
6.1.5 Proactive Protocols
• Combine link-state protocol & topology control
• Optimized Link State Routing (OLSR)
• Topology control component: Each node selects a
minimal dominating set for its two-hop neighborhood
– Called the multipoint relays
– Only these nodes are used for packet forwarding
– Allows for efficient flooding
• Link-state component: Essentially a standard link-state
algorithms on this reduced topology
– Observation: Key idea is to reduce flooding overhead (here
by modifying topology)
26
现代通信新技术导论 第六章 分布式网络
6.1.5 Proactive Protocols
• Fisheye State Routing (FSR) makes basic observation:
When destination is far away, details about path are not
relevant – only in vicinity are details required
– Look at the graph as if through a fisheye lens
– Regions of different accuracy of routing information
• Practically:
– Each node maintains topology table of network (as in LS)
– Unlike LS: only distribute link state updates locally
– More frequent routing updates for nodes with smaller scope
27
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
–
–
–
–
–
–
–
–
–
6.1.1 Distributed Networks
6.1.2 Introduction to MANETs
6.1.3 Design of MANETs
6.1.4 Network Routing Overview
6.1.5 Proactive Protocols
6.1.6 Reactive Protocols
6.1.7 Energy Efficient and Unicast Routing
6.1.8 Energy Efficiency Multi-/Broadcast Routing
6.1.9 Geographic Routing
• 6.2 P2P Networks
28
现代通信新技术导论 第六章 分布式网络
6.1.5 Reactive Protocols
• DSR
– Draft RFC
• At http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-07.txt
– Source Routing
• Entire path to destination supplied by source in packet header
• Utilizes extension header following standard IP header to carry
protocol information (route to destination, etc.)
– Activities
• Route discovery
– Undertaken when source needs a route to a destination
• Route maintenance
– Used when link breaks, rendering specified path unusable
• Routing (easy!)
29
现代通信新技术导论 第六章 分布式网络
6.1.5 Route Discovery
• Route Request:
– Source broadcasts Route Request message for specified destination
– Intermediate node:
• Adds itself to path in message
• Forwards (broadcasts) message toward destination
• Cache overheard routes
– “Eavesdrop” on routes contained in headers
– Reduces need for route discovery
• May return Route Reply to source if it already has a path stored
• Route Reply
– Destination unicasts Route Reply message to source
• Will contain complete path built by intermediate nodes
30
现代通信新技术导论 第六章 分布式网络
6.1.5 Example
• C Broadcasts Route Request to F
A
D
E
Route Request
B
Source
C
Destination
F
G
H
31
现代通信新技术导论 第六章 分布式网络
6.1.5 Example
• C Broadcasts Route Request to F
A
D
E
Route Request
B
Source
C
Destination
F
G
H
32
现代通信新技术导论 第六章 分布式网络
6.1.5 Example
• H Responds to Route Request
A
D
E
B
Source
C
Destination
F
G
H
G,H,F
33
现代通信新技术导论 第六章 分布式网络
6.1.5 Example
• C Transmits a Packet to F
A
D
E
B
Source
C
G,H,F
Destination
F
G
H,F
H
F
34
现代通信新技术导论 第六章 分布式网络
6.1.5 Route Maintenance
• Used when link breakage occurs
– Link breakage may be detected using link-layer ACKs,
“passive ACKs”, DSR ACK request
– Route Error message sent to source of message being
forwarded when break detected
– Intermediate nodes “eavesdrop”, adjust cached routes
– Source deletes route; tries another if one cached, or issues
new Route Request
• Piggybacks Route Error on new Route Request to clear
intermediate nodes’ route caches, prevent return of invalid route
35
现代通信新技术导论 第六章 分布式网络
6.1.5 Issues
• Scalability
– Discovery messages broadcast throughout network
• Broadcast / Multicast
– Use Route Request packets with data included
• Duplicate rejection mechanisms prevent “storms”
– Multicast treated as broadcast; no multicast-tree
operation defined
• Scalability issues
– http://www.ietf.org/internet-drafts/draft-ietf-manetsimple-mbcast-01.txt
36
现代通信新技术导论 第六章 分布式网络
6.1.5 Reactive Protocols
• AODV
– Draft RFC at http://www.ietf.org/internet-drafts/draft-ietfmanet-aodv-10.txt
– “Hop-by-hop” protocol: intermediate nodes use lookup table
to determine next hop based on destination
– Utilizes only standard IP header
– Activities
• Route discovery
– Undertaken whenever a node needs a “next hop” to forward a packet to a
destination
• Route maintenance
– Used when link breaks, rendering next hop unusable
• Routing (easy!)
37
现代通信新技术导论 第六章 分布式网络
6.1.6 Reactive Protocols
• TORA
– Observation: In hilly terrain, routing to a river’s mouth is
easy – just go downhill
– Idea: Turn network into hilly terrain
• Different “landscape” for each destination
• Assign “heights” to nodes such that when going downhill,
destination is reached – in effect: orient edges between neighbors
• Necessary: resulting directed graph has to be cycle free
– Reaction to topology changes
• When link is removed that was the last “outlet” of a node, reverse
direction of all its other links (increase height!)
• Reapply continuously, until each node except destination has at
least a single outlet – will succeed in a connected graph!
38
现代通信新技术导论 第六章 分布式网络
6.1.6 Route Discovery
• Route Request:
– Source broadcasts Route Request message for specified destination
– Intermediate node:
• Forwards (broadcasts) message toward destination
• Creates next-hop entry for reverse path to source, to use when sending reply
(assumes bidirectional link…)
• Route Reply
– Destination unicasts Route Reply (RREP) message to source
• RREP contains sequence number, hop-count field (initialized to 0)
• Will be sent along “reverse” path hops created by intermediate nodes which
forwarded RREQ
– Intermediate node:
• Create next-hop entry for destination as RREP is received, forward along “reverse
path” hop
• Increment hop-count field in RREP and forward
– Source:
• If multiple replies, uses one with lowest hop count
39
现代通信新技术导论 第六章 分布式网络
6.1.6 Route Maintenance
• Used when Link Breakage Occurs
– Link breakage detected by link-layer ACK, “passive ACK”,
AODV “Hello” messages
• Detecting Node may Attempt “Local Repair”
– Send RREQ for destination from intermediate node
• Route Error (RERR) Message Generated
– Contains list of unreachable destinations
– Sent to “precursors”: neighbors who recently sent packet
which was forwarded over broken link
• Propagated recursively
40
现代通信新技术导论 第六章 分布式网络
6.1.6 Issues
• Scalability
– No inherent “subnetting” provision in routing
tables – one entry per destination
• Directionality
– Assumes there is at least one bidirectional path
between any two nodes
41
现代通信新技术导论 第六章 分布式网络
6.1.6 Alternative Approach
• Gossiping/Rumor Routing
– Turn routing problem
around: Think of an
“agent” wandering
through the network,
looking for data
(events, …)
– Agent initially perform
random walk
– Leave “traces” in the
network
– Later agents can use these
traces to find data
– Essentially: works due to
high probability of line
intersections
42
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
–
–
–
–
–
–
–
–
–
6.1.1 Distributed Networks
6.1.2 Introduction to MANETs
6.1.3 Design of MANETs
6.1.4 Network Routing Overview
6.1.5 Proactive Protocols
6.1.6 Reactive Protocols
6.1.7 Energy Efficient and Unicast Routing
6.1.8 Energy Efficiency Multi-/Broadcast Routing
6.1.9 Geographic Routing
• 6.2 P2P Networks
43
现代通信新技术导论 第六章 分布式网络
6.1.7 Energy Efficiency & Unicast Routing
• Goals
4
– Minimize energy/bit
A
3
1
• Example: A-B-E-H
– Maximize network
lifetime
2
1
2
3
B
D
• Time until first node
failure, loss of coverage,
partitioning
3
• Seems trivial – use
proper link/path
metrics (not hop count)
and standard routing
C
2
1
2
E
1
2
2
4
4
2 F
G
2
H
44
现代通信新技术导论 第六章 分布式网络
6.1.7 Energy Efficiency & Unicast Routing
• Previous path metrics do not perform particularly well
• One non-trivial link weight:
– wij weight for link node i to node j
– eij required energy,  some constant, i fraction of battery of
node i already used up
• Path metric: Sum of link weights
– Use path with smallest metric
• Properties: Many messages can be sent, high network
lifetime
– With admission control, even a competitive ratio logarithmic
in network size can be shown
45
现代通信新技术导论 第六章 分布式网络
6.1.7 Multipath Unicast Routing
• Instead of only a
single path, it can be
useful to compute
multiple paths
between a given
source/destination
pair
• Multiple paths can be
– Disjoint
– Braided
Disjoint paths
Source
Secondary path
Sink
Primary path
Braided paths
• Used
– Simultaneously
– Alternatively
– Randomly
Source
Sink
Primary path
46
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
–
–
–
–
–
–
–
–
–
6.1.1 Distributed Networks
6.1.2 Introduction to MANETs
6.1.3 Design of MANETs
6.1.4 Network Routing Overview
6.1.5 Proactive Protocols
6.1.6 Reactive Protocols
6.1.7 Energy Efficient and Unicast Routing
6.1.8 Energy Efficiency Multi-/Broadcast Routing
6.1.9 Geographic Routing
• 6.2 P2P Networks
47
现代通信新技术导论 第六章 分布式网络
6.1.8 Energy Efficiency Multi-/Broadcast Routing
• Distribute a Packet to
– all reachable nodes (broadcast)
– to a somehow (explicitly) denoted subgroup (multicast)
• Basic Options
– Source-based tree: Construct a tree (one for each source) to reach
all addressees
• Minimize total cost (= sum of link weights) of the tree
• Minimize maximum cost to each destination
– Shared, core-based trees
• Use only a single tree for all sources
• Every source sends packets to the tree where they are distributed
– Mesh
• Trees are only 1-connected ! Use meshes to provide higher redundancy
and thus robustness in mobile environments
48
现代通信新技术导论 第六章 分布式网络
6.1.8 Energy Efficiency Multi-/Broadcast Routing
Steiner tree
• For each source, minimize total cost
Source
Destination 2
2
2
1
Destination 1
• For each source, minimize
maximum cost to each destination
Shortest path tree
Source
Destination 2
2
2
1
Destination 1
49
现代通信新技术导论 第六章 分布式网络
6.1.8 Energy Efficiency Multi-/Broadcast Routing
Broadcast
Multicast
One tree
per source
Minimize
total cost
(Steiner tree)
Minimize
cost to each node
(e.g., Dijkstra)
Shared tree
(core-based tree)
Single
core
Mesh
Multiple
core
50
现代通信新技术导论 第六章 分布式网络
6.1.8 Wireless Multicast Advantage
• Broad-/Multicasting in wireless is unlike broad/multicasting in a wired medium
– Wired: locally distributing a packet to n neighbors: n times
the cost of a unicast packet
– Wireless: sending to n neighbors can incur costs
• As high as sending to a single neighbor – if receive costs are
neglected completely
• As high as sending once, receiving n times – if receives are tuned to
the right moment
• As high as sending n unicast packets – if the MAC protocol does
not support local multicast
• If local multicast is cheaper than repeated unicasts, then
wireless multicast advantage is present
51
现代通信新技术导论 第六章 分布式网络
6.1.8 Broadcast Incremental Power (BIP)
• How to broadcast, using the wireless multicast
advantage?
– Goal: use as little transmission power as possible
• Idea: Use a minimum-spanning-tree-type construction
(Prim’s algorithm)
• But: Once a node transmits at a given power level &
reaches some neighbors, it becomes cheaper to reach
additional neighbors
• From BIP to multicast incremental power (MIP):
– Start with broadcast tree construction, then prune
unnecessary edges out of the tree
52
现代通信新技术导论 第六章 分布式网络
6.1.8 BIP Algorithm
53
现代通信新技术导论 第六章 分布式网络
6.1.8 BIP Example
Round 2: A
Round 1: A
5
S
10
D
4
3
B
1
3
Round 3: A
B
S (1)
9
7
1
2
3
2
7
7
7
1
D
C
C
Round 4: A
C
Round 5: A
2
3
3
B
S (3)
7
B
S (5)
10
6
D
B
S (3)
1
D
3
7
D
C (1)
C (1)
54
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
–
–
–
–
–
–
–
–
–
6.1.1 Distributed Networks
6.1.2 Introduction to MANETs
6.1.3 Design of MANETs
6.1.4 Network Routing Overview
6.1.5 Proactive Protocols
6.1.6 Reactive Protocols
6.1.7 Energy Efficient and Unicast Routing
6.1.8 Energy Efficiency Multi-/Broadcast Routing
6.1.9 Geographic Routing
• 6.2 P2P Networks
55
现代通信新技术导论 第六章 分布式网络
6.1.9 Geographic Routing
• Routing tables contain information to which next hop a packet
should be forwarded
– Explicitly constructed
• Alternative: Implicitly infer this information from physical
placement of nodes
– Position of current node, current neighbors, destination known –
send to a neighbor in the right direction as next hop
– Geographic routing
• Options
– Send to any node in a given area – geocasting
– Use position information to aid in routing – position-based routing
• Might need a location service to map node ID to node position
56
现代通信新技术导论 第六章 分布式网络
6.1.9 Basics of Position-Based Routing
• “Most forward within range r” strategy
– Send to that neighbor that realizes the most forward
progress towards destination
– NOT: farthest away from sender!
• Nearest node with (any) forward progress
– Idea: Minimize transmission power
• Directional routing
– Choose next hop that is angularly closest to destination
– Choose next hop that is closest to the connecting line to
destination
– Problem: Might result in loops!
57
现代通信新技术导论 第六章 分布式网络
6.1.9 Problem: Dead Ends
• Simple strategies might send a packet into a dead end
58
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
• 6.2 P2P Networks
–
–
–
–
–
–
–
6.2.1 Introduction to P2P
6.2.2 Why P2P?
6.2.3 Overview of P2P
6.2.4 Unstructured P2P (Gnutella)
6.2.5 Structured P2P (with DHTs)
6.2.6 Performance of P2P Lookup Protocols
6.2.7 Bi-Dimensional P2P
59
现代通信新技术导论 第六章 分布式网络
6.2.1 Introduction to P2P
• Definitions
– Clay Shirky (www.shirky.com):
• A class of applications that take advantage of resources – storage, cycles,
content, human presence – available at the edges of the Internet.
– Milojicic et al. (HP):
• A class of systems and applications that employ distributed resources to
perform a critical function in a decentralized manner.
– Some other guys:
• A technology which “enables any network-aware device to provide services
to another network-aware device”
• Instead of Internet information being held in a few central
locations, Peer-to-Peer computing makes it theoretically possible
to access the files and data residing on every personal computer
connected to the Internet
60
现代通信新技术导论 第六章 分布式网络
6.2.1 Introduction to P2P
• Instead of Internet information being held in a few central locations,
Peer-to-Peer computing makes it theoretically possible to access the
files and data residing on every personal computer connected to the
Internet
• A peer in P2P network acts as both a client and a server in traditional
client/server architecture
P2P
Client/Server
61
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
• 6.2 P2P Networks
–
–
–
–
–
–
–
6.2.1 Introduction to P2P
6.2.2 Why P2P?
6.2.3 Overview of P2P
6.2.4 Unstructured P2P (Gnutella)
6.2.5 Structured P2P (with DHTs)
6.2.6 Performance of P2P Lookup Protocols
6.2.7 Bi-Dimensional P2P
62
现代通信新技术导论 第六章 分布式网络
6.2.2 Why P2P?
• Problem with Server-Client
Model
– Scalability
• As the number of users increases,
there is a higher demand for
computing power, storage space,
and bandwidth associated with
the server-side
– Reliability
• The whole network will depend
on the highly loaded server to
function properly
63
现代通信新技术导论 第六章 分布式网络
6.2.2 Why P2P?
• The Internet has three valuable fundamental
assets
– Information
– Computing resources
– Bandwidth
• All of which are vastly under utilized, partly due
to the traditional client-server model
64
现代通信新技术导论 第六章 分布式网络
6.2.2 Why P2P?
• First, no single search engine or portal can locate and
catalog the ever-increasing amount of information on
the Web in a timely way
• Moreover, a huge amount of information is transient
and not subject to capture by techniques such as Web
crawling
– Google claims that it searches about 1.3×108 web pages
– Finding useful information in real time is increasingly
difficult!
• Many information can not be capture by web crawling
– The world produces 2 exabytes(1015) of information every
year, only publishes 300 terabytes(1012)
65
现代通信新技术导论 第六章 分布式网络
6.2.2 Why P2P?
• Second, although miles of new fiber have been
installed
– The new bandwidth gets little use if everyone goes
to Yahoo for content and to eBay
– Instead, hot spots just get hotter while cold pipes
remain cold
• This is partly why most people still feel the
congestion over the Internet
– While a single fiber’s band-width has increased by
a factor of 106 since 1975, doubling every 16 months
66
现代通信新技术导论 第六章 分布式网络
6.2.2 Why P2P?
• Finally, new processors and storage devices continue
to break records in speed and capacity
– supporting more powerful end devices throughout the
network
• However
– Computation and storage continue to accumulate
around data centers
– They have to increase their workloads at a crippling
pace, thus putting immense pressure on space and
power consumption
67
现代通信新技术导论 第六章 分布式网络
6.2.2 Why P2P?
• The P2P Architecture
– Eliminates the single-source bottleneck
– Is used to distribute data and control and loadbalance requests across the Net
– Eliminates the risk of a single point of failure
– Allows direct access and shared space, and this
can enable remote maintenance capability
68
现代通信新技术导论 第六章 分布式网络
6.2.2 Why P2P?
•
Advantages of P2P model

The system is based on the direct
communication between peers

There is zero reliance on centralized
serviced or resources for operations

The system can survive extreme
changes in network composition

They thrive in a network with
heterogeneous environment

This model is highly scalable
69
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
• 6.2 P2P Networks
–
–
–
–
–
–
–
6.2.1 Introduction to P2P
6.2.2 Why P2P?
6.2.3 Overview of P2P
6.2.4 Unstructured P2P (Gnutella)
6.2.5 Structured P2P (with DHTs)
6.2.6 Performance of P2P Lookup Protocols
6.2.7 Bi-Dimensional P2P
70
现代通信新技术导论 第六章 分布式网络
6.2.3 Properties of P2P
• No central control, no central database
• No hierarchy
– Every node is both a client and a server
– The communication between peers is symmetric
• No global view of the system
– Scalability
• Availability for any peer
• Peers are autonomous
• System globally unreliable
– Robustness and security issues
71
现代通信新技术导论 第六章 分布式网络
6.2.3 Examples of P2P Usage
•
•
•
•
•
•
•
•
•
File-Sharing Applications
Distributed Databases
Distributed Computing (Grid Computing)
Collaboration
Distributed Games
Instant Messaging
Ad Hoc Networks
Application-Level Multicast
…
72
现代通信新技术导论 第六章 分布式网络
6.2.3 Overview of P2P
• Peer:
– A peer is a node on a P2P network that forms
the fundamental processing unit of any P2P
solution.
– Each peer has a unique Peer ID
– Each peer belongs to one or several Peer Group
– Each peer can communicate with other peers in
its group and also those in other groups
73
现代通信新技术导论 第六章 分布式网络
6.2.3 Overlay Networks
Overlay
IP
74
现代通信新技术导论 第六章 分布式网络
6.2.3 Traditional C/S Model
75
现代通信新技术导论 第六章 分布式网络
6.2.3 P2P Networks
Large Scale
Distributed
Centralized
With an index server
DNS，X.500，
Napster……
Wireless P2P networks
And
The lookup protocols
Distributed
Without an index server
Unstructured
Structured
For small-scale P2P networks
For large-scale P2P networks
Gnutella
Chord，Pastry，
Tapestry，CAN……
76
现代通信新技术导论 第六章 分布式网络
6.2.3 Pure P2P
77
现代通信新技术导论 第六章 分布式网络
6.2.3 Hybrid P2P
78
现代通信新技术导论 第六章 分布式网络
6.2.3 Centralized P2P (Napster)
• File-sharing system
• Almost distributed system
– The location of a document is centralized
– The "transfer" is peer-to-peer
• Problems
– Robustness
– Scalability (?)
79
现代通信新技术导论 第六章 分布式网络
6.2.3 Centralized P2P (Napster)
location
server
register
INTERNET
 Document x!
OK:
Document
Peer Z x?
IP = a.b.c.d
x
80
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
• 6.2 P2P Networks
–
–
–
–
–
–
–
6.2.1 Introduction to P2P
6.2.2 Why P2P?
6.2.3 Overview of P2P
6.2.4 Unstructured P2P (Gnutella)
6.2.5 Structured P2P (with DHTs)
6.2.6 Performance of P2P Lookup Protocols
6.2.7 Bi-Dimensional P2P
81
现代通信新技术导论 第六章 分布式网络
6.2.4 Unstructured P2P (Gnutella)
• Two phases (like Napster)
– Localization + exchange
• No server
• Open source
– gnutella.wego.com
• Distributed search
– The query is flooded
– Loop avoidance
– Limited TTL (not all nodes are visited)
82
现代通信新技术导论 第六章 分布式网络
6.2.4 Unstructured P2P (Gnutella)
83
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
• 6.2 P2P Networks
–
–
–
–
–
–
–
6.2.1 Introduction to P2P
6.2.2 Why P2P?
6.2.3 Overview of P2P
6.2.4 Unstructured P2P (Gnutella)
6.2.5 Structured P2P (with DHTs)
6.2.6 Performance of P2P Lookup Protocols
6.2.7 Bi-Dimensional P2P
84
现代通信新技术导论 第六章 分布式网络
6.2.5 Structured P2P (with DHTs)
• Based on distributed hash tables (DHTs)
• No flooding
– Exact matches
• Overhead
– Gnutella-like: O(n)
– DHT: O(log n)
• Examples
– CAN, Pastry, Chord, Kademlia, Tapestry, etc.
85
现代通信新技术导论 第六章 分布式网络
6.2.5 The Chord P2P Lookup Protocol
• Main Features of Chord
– Fully distributed
– Efficient lookup of a node which stores data items for a
particular search key
– Load balancing via Consistent Hashing
– Small routing tables: log n
– Small routing delay (average number of hop): log n
– Fast join/leave protocol
– Automatically adjusts internal tables to reflect changes
86
现代通信新技术导论 第六章 分布式网络
6.2.5 Consistence Hashing
• Assigns both nodes and
objects from an m-bit key
• Order these nodes around N105
an identifier circle
according to the order of
their keys (0 .. 2m-1). This
ring is known as the Chord
Ring
• Object with key k is
assigned to the first node
whose key is ≥ k (called the
successor node of key k)
D120
(0)
D20
N=128
Circular 7-bit
ID space
N32
N90
D80
Example: Node 90 is the “successor” of document 80.
87
现代通信新技术导论 第六章 分布式网络
6.2.5 Consistent Hashing
• Property 1
– If there are N nodes and K keys, then with high
probability, each node is responsible for (1+ )K/N
keys. ( = O(log N)
• Property 2
– When an (N+1) joins or leaves the network, the
responsibility of at most O(K/N) keys changes hand
(only to or from the node that is joining or leaving
88
现代通信新技术导论 第六章 分布式网络
6.2.5 Chord’s Fingers
(0)
1/4
1/2
Distance of N80’s
neighbors from
N80
1/8
Circular (log N)-bit
ID space
1/16
1/32
1/64
1/128
N80
Each node knows of only log N other nodes.
89
现代通信新技术导论 第六章 分布式网络
6.2.5 Chord Finger Table
N32’s
Finger Table
(0)
N113
N102
N=128
N32
N85
N40
N80
N79
33..33
34..35
36..39
40..47
48..63
64..95
96..31
N40
N40
N40
N40
N52
N70
N102
N52
N70
N60
Node n’s i-th entry: first node  n + 2i-1
90
现代通信新技术导论 第六章 分布式网络
6.2.5 Chord Lookup
(0)
N32’s
Finger Table
N113
N102
N32
N85
N40
N80
N52
N79
N70
33..33
34..35
36..39
40..47
48..63
64..95
96..31
N40
N40
N40
N40
N52
N70
N102
N80’s
Finger Table
81..81
82..83
84..87
88..95
96..111
112..15
16..79
N85
N85
N85
N102
N102
N113
N32
N70’s
Finger Table
71..71
72..73
74..77
78..85
86..101
102..5
6..69
N79
N79
N79
N80
N102
N102
N32
N60
Node 32, lookup(82): 32  70  80  85.
91
现代通信新技术导论 第六章 分布式网络
6.2.5 New Node Joining Procedure
N20’s
Finger Table
(0)
N113
N20
N102
N32
N40
N80
21..21
22..23
24..27
28..35
36..51
52..83
84..19
N52
N70
N60
92
现代通信新技术导论 第六章 分布式网络
6.2.5 New Node Joining Procedure
N20’s
Finger Table
(0)
N113
N20
N102
N32
N40
N80
21..21
22..23
24..27
28..35
36..51
52..83
84..19
N32
N32
N32
N32
N40
N52
N102
N52
N70
N60
93
Node 20 asks any node for successor to 21, 22, …, 52, 84.
现代通信新技术导论 第六章 分布式网络
6.2.5 After Joining
(0)
N113
N20
N102
D114..20
N32
N40
N80
N20’s
Finger Table
21..21
22..23
24..27
28..35
36..51
52..83
84..19
N32
N32
N32
N32
N40
N52
N102
N52
N70
N60
Node 20 moves documents from node 32.
94
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
• 6.2 P2P Networks
–
–
–
–
–
–
–
6.2.1 Introduction to P2P
6.2.2 Why P2P?
6.2.3 Overview of P2P
6.2.4 Unstructured P2P (Gnutella)
6.2.5 Structured P2P (with DHTs)
6.2.6 Performance of P2P Lookup Protocols
6.2.7 Bi-Dimensional P2P
95
现代通信新技术导论 第六章 分布式网络
6.2.6 Performance of P2P Lookup Protocols
Gnutella
Chord
F-Chord(1)
Degree（routing table size）
0
log 2 N
1.44log 2 N  2
Diameter（maximum hop）
N 1
log 2 N
0.720log 2 N
0.398log 2 N
 N 1
Average hop
2
log 2 N 2
Degree
N-1
Information of all nodes
included in the routing table
Optimal trade-off
Chord，Pastry，Tapestry……
O(log N)
Gnutella
0
1
O(log N)
N-1
Diameter
96
现代通信新技术导论 第六章 分布式网络
Main Contents
• 6.1 Mobile Ad Hoc Networks
• 6.2 P2P Networks
–
–
–
–
–
–
–
6.2.1 Introduction to P2P
6.2.2 Why P2P?
6.2.3 Overview of P2P
6.2.4 Unstructured P2P (Gnutella)
6.2.5 Structured P2P (with DHTs)
6.2.6 Performance of P2P Lookup Protocols
6.2.7 Bi-Dimensional P2P
97
现代通信新技术导论 第六章 分布式网络
6.2.7 Bi-Dimensional P2P
•
Bi-Dimensional P2P
•
Path Length
– Assume the Hash space to be 0,1, 2  1
– Assume all nodes exist in the Hash space
– Place all nodes on the 2m 2  2m 2 plain
m
– Definition, for any a, b, c, d  1, 2, 2m / 2  , the path length Lpath  na ,b , nc ,d  between na ,b
and nc ,d is defined as the number of hop for the lookup from na ,bto nc ,dassuming there
is only next node in each node’s routing table
– Maximum path length of Chord Lpath n1,1 , n2 ,2  2m  1.

m2
m2

98
现代通信新技术导论 第六章 分布式网络
6.2.7 Bi-Dimensional P2P
99
现代通信新技术导论 第六章 分布式网络
6.2.7 Performance Comparison
Degree
Diameter
Chord
m
m
F-Chord
1.44m  2
0.720m
m
2
m
2
m
2
MRBD-2(2)
2  log 2 2  m
log 2 2  log 2 2  m
MRBD-3(3)
m

 3m
3 log3 2 2  
log3 2  0.946m

 2
m log3 2  2  0.63m  2
MRBD-3(4)
m
2
3  log 4 2  0.75m
0.75m  2
100
现代通信新技术导论 第六章 分布式网络
A Brief Review
• MANETs
– Distributed
• Advantages
• Disadvantages
– Design Issues
– Routing Protocols
• P2P Networks
– Distributed
• Advantages
• Disadvantages
– Architecture
– Lookup Protocols
101