Embed Size (px)
Citation preview
1
P2P =
“Structured Overlay Networksfor Peer-to-Peer systems”
Luigi Liquori, • 97 Ph.D. Università degli studi di Torino
• 07 H.d.R. “Habilitation à diriger les recherches”, École Nat Sup des Mines de Nancy
• 08 “Habilité au fonctions de professeurs de Universités’’ 2008-2012
• 10 Research Director, Équipe LogNet, INRIA Sophia Antipolis Méditerranée
2
Course setting
o COURSE = P2P : “Future Internet and Overlay Networks”
o HH = around 40h (20h by me and +20h by Prof. Legout)
o MODULE = “Structured Overlay Networks P2P systems”
o Exams = SW project
o PRE = General notions of systems and networks
o OPT = “Computability”, “Data-bases”, “Logics”, “Security”
o POST = “Design, analyze and implement p2p networks and overlay-based applications”
3
Topics : structured overlay networks for P2P
o CHORD (Stoica & al), lessons o Academic and pedagogical a sort of “PASCAL/BASIC” in overlay networks
o KADEMLIA (Maymounkov and Mazières), lessons o Academic with free implementations and widely used (emule)
o BIT TORRENT, (Cohen) ½ of the course <<<< A. LEGOUTo Non academic, with free implementations and widely used
o SKYPE (Zennström & Friis), lessono Non academic : open, use Kademlia, very widely used for VOIP
o INTERCONNECTING OVERLAY NETW (Liquori), lesson o Academic but practical : allow different overlay protocols to communicate
o NAT TRAVERSAL, lessons o How stablish and maintain TCP/IP/UDP connections traversing gateways
4
Other issues (micro survey) in the course
o Publish/subscribe paradigm
o Content-centric routing (Jacobson & al. CONEXT 09)
o Ontologies for internet computability
o Coordination languages to deal with algorithmic aspects
o Trust and reputation issues
o Denial of service attacks
o “Inter netting” overlay networks
o Principles of “Internet computability”
5
“Spot on”
1. A quick window of the module (lesson 1)o Preludio : some internet factso Course vision : “Computer scale-up to internet”o Step 1 : Reference model of future interneto Step 2 : Reference model of internet computer
2. Inside submodule “Structured overlay networks for p2p” (lessons 3-4)o Chord, lecture
o Topology, routing, and churno Kademlia, lecture
o Topologyo Routing (put, get), o Churn (join, leave)
3. Inter-netting structured overlay networks (lesson 7)o Dealing with network partitions
6
Preludio : some internet facts
o Internet traffic : ~80% is P2P and ~20% is Web
o Some leading p2p protocols :
o Some leading p2p class of applications : file exchangeo In progress: VOIP, TVIP, STREAMIP, CLOUD
o General p2p anarchy : no coordination, no cooperation
o Total p2p heterogeneity : protocols, topology, security, devices, users ..
o P2P “inter-routing” is almost impossibleo Often with the same purpose but ≠ routing and topologies
o Actor 1 : Resource discovery
o Actor 2 : Resource coordination
o “ …les ingredients pour … un modèle de calcul pour l’internet ! ”
o Actor 3 : Peers organization
o Actor 4 : Peers reputation
7
Course vision : “Computer scale-up to internet”
o 1946. von Neumann. “Principle of large scale computing machines”o “Large Scale” in 1946 means ENIAC
o 1946-2010. From ENIAC to Cray XT5 Jaguar and G5K via iPhone
o 20XX. “Large scale” means “Internet scale”
o Von Neumann architecture
does not scale-up to internet
8
o “Inter-netting” heterogeneous overlay networkso The “Cerf & Kahn ’77” cannot lead to a standardized p2p communication layer
o Backward compatibility of all existent p2p protocolso P2P inventors are often next door computer scientists or users’ communities
o Competition vs. Collaboration
o Interconnecting etherogeneous ONo Exaustive routing is almost achieved
o Content-based routing (Jacobson)o Logical payloado Hybrid topologies and underlay networks
o Peers organization via social-based & reputation primitives
o Genericity : add many services on the top of the ON
Step 1 : reference model of future internet
9
Step 2 : reference model of an internet computer
o Internet Computer (IC) : abstraction on top of an overlay networko Peers are physically connected via IP/adhoc/MANETo Peers are logically organized in a Virtual Organization
o IC Reference modelo Bus = Internet and routing
o Memory = ΣkK DHTk (distributed hash table)
o CPU = ΣkK CPUk (distributed central units)
o IC Programming modelo Language = Protocolo Word = Packeto Pointer = Addresso Type = Port
o Universality, Genericity, Polymorphism, “Turing completeness”
o Virtual intermittenceo Resource discoveryo Reputationo Orchestration
10
“Spot on”
1. A quick window of the module (lesson 1)o Preludio : some internet factso Course vision : “Computer scale-up to internet”o Step 1 : Reference model of future interneto Step 2 : Reference model of internet computer
2. Inside submodule “Structured overlay networks for p2p” (lessons 3-4)o Key figures (reminder)o Chord, lecture
o Topology, routing, and churno Kademlia, lecture
o Topologyo Routing (put, get), o Churn (join, leave)
3. Inter-netting structured overlay networks (lesson 7)
11
Physical Network
Overlay Network
A
B
C
Treat n hops through IP network as m (less than m) hops in an overlay network
General picture of overlay networks
12
Key figures in SON (reminder)
o Data discovery is deterministic : a.k.a. 2nd generation overlays
o Distributed Hash Table (DHT) : stores (key, value) pairs in nodes
o Key-based routing : N.lookup(K) route from the node N generator of the lookup to the node M that owns the key K via a routing path of “closer” nodes (according to a given metric distance in a logical key space)
o Routing table : local table that maintain links to other nodes
o Churn : rate of node joins and leaves in a p2p network
13
Key figures in SON (cont’d)
o Overlay topologies
o Exhaustive lookup with logarithmic complexity
o Uniformity vs. proximity of key storage
o Consistent hashing of keys and IPs via SHA-1
o Peer joino Getting a logic IDo Positioning into the overlay structure o Stabilize the overlay (maintenance)
o Opportunistic vs. Active maintenance of routing tables
o Bootstrapping of an overlay network
o Peer leaveo Faulty routing tableso Fair play vs. non fair play
leaving
14
Chord 1 : Consistent Hashing
o SHA-1: {IP} U {KEYS} -> NAT
o SHA-1(IP) = NIP
o SHA-1(fookey) = Kfoo
o Node Nx stores
all keys Ky such that
Nx ≤ Ky < pred(Nx)
15
Chord 2 : (Local) Finger Tables
o On every node N
o finger : array[1...m]
o 2m is the logical space
o finger[k] = succ(N + 2k-1) mod 2m with 1 ≤ k ≤ m
16
Chord 3 : Recursive routing
8 < finger[6] ≤ 54
42
17
Chord 4 : Churn
18
Chord 5 : Bootstrapping
19
Chord 6 : Stabilization
20
Kademlia 1
o Peer-to-peer (key,value) storage and lookup system
o A number of desirable features not simultaneously offered by any previous peer-to-peer system
o It minimizes the number of messages to learn topology
o Stabilization spreads automatically during key lookup
o Nodes can route queries through low-latency paths
o Parallel, asynchronous msg to avoid timeout delays from failed nodes
o Basic mechanisms to resists to certain basic denial of service attacks
21
Kademlia 2
o Keys are “opaque”, 160-bit quantities
o Participating computers each have a node ID in the 160-bit key space. (key, value) pairs are stored on nodes with IDs “close” to the key for some notion of closeness
o A node-ID-based routing algorithm lets anyone locate servers near a destination
o XOR metric for distance between points in the key space
o XOR is symmetric, allowing Kademlia participants to receive lookup queries from precisely the same distribution of nodes contained in their routing tables
22
XOR metric 1
o Given two 160-bit identifiers, x and y, Kademlia defines the distance between them as their bitwise exclusive or (XOR) interpreted as an integer, i.e. d (x, y) = x ⊕ y
o d (x, x) = 0
o d (x, y) > 0 if x ≠ y,
o For all x, y. d (x, y) = d (y, x)
o d (x, y) + d (y, z) d (x, z)≧
o d (x, y) ⊕ d (y, z) = d (x, z)
o For all a 0, b 0. ≧ ≧ a + b a ≧ ⊕ b
23
XOR metric 2
o XOR is unidirectional
o For any given point x and distance > 0, there is exactly one △point y such that d (x, y) = △
o Unidirectionality ensures that all lookups for the same key converge along the same path, regardless of the originating node
o Caching (key, value) pairs along the lookup path alleviates hot spots
o XOR topology is also symmetrico d (x, y) = d (y, x) for all x and y
24
XOR : do it ….
25
Topology : do it ….
26
Node state 1
o For each 0 i < 160, every node keeps a list of ≦ (IP address, UDP port, Node ID) triples for nodes of distance between 2i and 2i+1 from itself
o We call these lists “k-buckets”
o The size is not fixed a priori but is chosen such that any given k nodes are very unlikely to fail within an hour of each other (for example k = 20)
i XOR distance
Bucket
0 [20, 21) (IP address,UDP port,Node ID) 0-1
......(IP address,UDP port,Node ID) 0-k
1 [21, 22) (IP address,UDP port,Node ID) 1-1
......(IP address,UDP port,Node ID) 1-k
2 [22, 23) (IP address,UDP port,Node ID) 2-1
......(IP address,UDP port,Node ID) 2-k
…
i [2i, 2i+1) (IP address,UDP port,Node ID) i-1
......(IP address,UDP port,Node ID) i-k
…
159 [2159, 2160) (IP address,UDP port,Node ID) 159-1
......(IP address,UDP port,Node ID) 159-k
i-bucket
27
Node state 2
o Each k-bucket is kept sorted by time last seen
o Least-recently seen node at the head
o Most-recently seen at the tail
28
Build buckets : do it ….
29
Node state 3
o When a Kademlia node receives any message (request or reply) from another node, it updates the appropriate k-bucket for the sender’s node ID
o If the sending node already exists in the recipient’s k-bucket, the recipient moves it to the tail of the list
o If the node is not already in the appropriate k-bucket and the bucket has fewer than k entries, then the recipient just inserts the new sender at the tail of the list
o If the appropriate k-bucket is full, then the recipient pings the k-bucket’s least-recently seen node to decide what to doo If the least-recently seen node fails to respond, it is evicted from the
k-bucket and the new sender inserted at the tailo If the least-recently seen node responds, it is moved to the tail of the
list, and the new sender’s contact is discarded
30
Routing and upgrade buckets : do it ….
31
Kademlia in the P2P system 1
o In the eMule,a P2P file exchange software, Kademlia network has two table : the Key words table and the Data index table
Hash(Wii)
Hash(trick)
(data name, data length, Hash(data))
(I Love Wii.txt, 30, 1011…001)
(Wii tips and tricks.pdf, 375, 1110…101)
(data name, data length, Hash(data))
(Wii tips and tricks.pdf, 375, 1110…101)
(Card trick.mpg, 65000, 1000…100)
Key Value
Hash(Wii)
To Find: Wii tips and tricks.pdfKey words: Wii, tricks
Key Value
Hash(tricks)
Hash()=>SHA-1,160bit
Key words table
32
Kademlia in the P2P system 2
o Data index table:
1011…001
(IP, UDP Port, node ID)
(218.164.185.90, 3347, 1011…001)
(125.230.122.183, 3475, 1011…011)
Key Value
1011…001
To Find: 1011…001 Data index table
33
Nodes in Kademlia
34
Files in Kademlia
35
Hash of “break” only !
Keywords in Kademlia
36
“Spot on”
1. A quick window of the module (lesson 1)o Preludio : some internet factso Course vision : “Computer scale-up to internet”o Step 1 : Reference model of future interneto Step 2 : Reference model of internet computer
2. Inside submodule “Structured overlay networks for p2p” (lessons 3-4)o Chord (previous lecture)
o Topology, routing, and churno Kademlia (this lecture)
o Topologyo Routing (put, get), o Churn (join, leave)
3. Inter-netting structured overlay networks (lesson 7)o Dealing with network partitions
37
o Example 1: Two DHT-based overlay networks (key,value)o One pair is stored in DHT1 and searched for in DHT2
o Many pairs stored in both DHTs can be foundo Two companies wishing to share/aggregate information o Better fault-tolerance, and data availability
o Example 2: An Overlay Network get some nodes isolatedo So called “network partitions”o Alternative physical routing via ON inter-routing
Inter netting structured overlay networks
38
o VIP: SREG (Id,Mode,FromCard,ToCard, Payload)
o VIP: SUPD (Id,Mode,FromCard,ToCard, Payload)
o RDP: SREQ (Id,Mode,FromCard,ToCard, Payload
o RDP: SRESP (Id,Mode,FromCard,ToCard, Payload)
o RDP: SNOTIF (Id,Mode,FromCard,ToCard)
o Mode {LOGIN, LOGOUT, ACCEPT, REJECT, LOOP, ☺, ☠,…}
o Card = (IP-PORT-PKI)
o Service ::= HumW | RunW | StockW | ProgW | DataW | LinkW
o Payload ::= ORi=1..m(ANDj=1..n j)i
where ::= (Service,Constraints*) | NOT()
(Techi) Inside Protocols
[RunW=Intel,Time ≥ 10m) AND [ProgW=LINUX, Distro=DEB]
OR
[RunW=Intel,Time ≥ 10m) AND [ProgW=LINUX, Distro=OSX]
OR
[RunW=AMD, Time ≥ 10m] AND [ProgW=VISTA, Distro=BUG]
Payload looks like a first-order logic language…
Pattern-matching algorithms and
Constraint Logic Programming
for routing content-based networks
