Peer-to-peer (P2P) Networks - Basic Algorithms
HTML-код
- Опубликовано: 21 авг 2024
- This video explains the basic algorithms used in implementing a P2P network. The theory covered here is based on the popular P2P network algorithsm Chord, Kademlia and Tapestry.
For more details, see my P2P tutorial:
tutorials.jenko...
Or - see my P2P video playlist:
• P2P Networks
11 years later your video helped me. Thanks
Great !! :-D ... I am actually thinking about making a few new videos about P2P technology. A bit has happened in those 11 years :-D
@@JakobJenkov Go for it sir.
@@JakobJenkov Please do
12 years later, your video helped me much better than others. 🔥 Thank you Sir Jakob !
You are welcome! ... got a new introduction to P2P networks coming soon - with a few updates ! ... covering a few more P2P network topologies ! 🙂
If you click the link in the description of the video (click "show more" first), I have a tutorial online with more details than this video, in case you are interested.
Best job done to explain the peer to peer networks. Bravo and thanks.
Hi Mubasher - glad it helped you! :-)
@@JakobJenkov Hi, I need a favor, can you please suggest me some framework in which all peers are fully connected, I mean each possess the IP list of all peers in the network?
This is exactly what I was looking for .. All I could search about peer to peer networks was a bunch of scholar papers . But this video really simplified everything . Thanks a lot man !
This is really good stuff !
Great job explaining DHT routing, disregard the negative comments.
Yes, each peer in a 2^64 node network would have 64 connections. The connections may not need to be open at all times. But the IP address and port number of the peer must be known so a connection can be established. That means that a node may not have to search for these 64 nodes that it is "connected" to, but the rest of the 2^64-64 nodes that it is *not* connected to, it will have to search for.
Jakob your videos are always useful and a treat to watch
Thanks :-)
I've been working as a software developer for almost 12 years now and this is something that I didn´t know, so thank you very much for the video!
outstanding explanation of a chord peer to peer system. thank you so much this will help immensely with my assignment
I often visit your website for Java solutions, nice to see you for the first time, many thanks!
IIRC Tapestry's leaving algo is lazy, it certainly is in Pastry. Nodes don't inform all the nodes when leaving the network, they only inform the last hop cache "leaves" (typically 4 each side in their address space). There is a constant gossip/maintenance going on that happens during routing and also when nodes join (which is implemented as a routing procedure from the bootstrap node to oneself as the tables alway update/self-correct with the regular routing process).
Thank you for the explanation of these basics, it's really clear!
Great video! Exactly what I needed
Cool! ... what do you need it for? Working on an exciting P2P project?
@@JakobJenkov Yes! A distributed computing system
This is a great video! Thank you so much for sharing. There is one minor thing that puzzles me.
If you calculate the chord distance and take (a-b)=x and N=y then: (x + 2^y) mod 2^y
In my understanding of the modulo operation, the result should always be x. I thought that is what a modulo does. It eradicates a multiplicity of a certain value, in this case 2^y. It would not even matter if i write (x + 2^(y*c)) mod 2^y, the result should still be x.
But lets try it with an example, just to see if i am totally wrong here: (7 + 16) mod 16 = 23 mod 16 = 7
and if you try: (7 + (16 * 16)) mod 16 = (7 + 256) mod 16 = 263 mod 16 = 7
Am i missing something? =/
It's been a while since I visited the distance calculations, so I'd have to look into that. However, I would recommend you to use the Kademlia distance function instead of the chord distance function. It is easier to calculate. By the way, I will be implementing a Kademlia routing table soon, I think :-)
I have a small tutorial on my website (tutorials.jenkov.com). But I originally started by looking at wikipedia. Their P2P page has links to research papers etc. about the most commonly known P2P systems (Chord, Kademlia, Pastry, Tapestry etc.)
Excellent Jakob. Very well explained. This gives me a hustle to think about a subtle solution for a performance bottle neck we face in our product. I'll try it in C++ and let you know how it works. Thanks again
Awesome explanation, thanks a lot!
You are welcome! :-)
Hi Pradeep, you need some way which the peers can get to know each other when they at first know no other peers in the system. Either you host a set of boot peers, or you can have some kind of UDP broadcast message (works only on local network). Once a peer has been connected to a P2P network, it can attempt to contact any of the previous peers in the network when starting up, instead of relying on the boot peers.
Hello Jakob, that is what I am working on.. Here I am finding some problem with UDP broadcast message, when I create UDP[java] server and client on my pc they do communicate but I am getting problem to connect them in different machines, i.e I created jar files of server and client and i tried it on different systems and It is not working, can you please help me with some java code by tht I can create jar files or applets to check it on different machines.. thnqs for your support
Hi Pradeep, I cannot help you with that right now, unfortunately. I don't know enough how about how UDP works on a global scale, meaning how to get UDP through NAT, firewalls etc.
Jakob Jenkov I got it..and it may be useful to some one else,This is Client side code..it has to be made into jar, enter ip address of receiving[server] system in the place of 139.00....... as shown in code..
import java.io.IOException;
import java.net.*;
//import com.dansd.UDP.Messenger;
public class Messenger extends Thread{
static int port = 4662;
public static void main(String[] args) throws Exception{
new Messenger("139.00.000.00",4662).send("Fox".getBytes());
System.out.println("Sent");
}
private int sessionPort;
private String sessionHost;
private byte[] currentMessage;
public Messenger(){
this("localhost");
}
public Messenger(String host){
this(host, 4662);
}
public Messenger(String host, int port){
sessionPort = port;
sessionHost = host;
}
public void send(byte[] message){
this.currentMessage = message;
this.run();
}
public void run(){
DatagramSocket clientSocket = null;
try {
clientSocket = new DatagramSocket();
} catch (SocketException e) {
e.printStackTrace();
}
InetAddress IP = null;
try {
IP = InetAddress.getByName(sessionHost);
} catch (UnknownHostException e) {
e.printStackTrace();
}
byte[] receiveData = new byte[1024];
byte[] sendData = currentMessage;
DatagramPacket sendPacket = new DatagramPacket(sendData, sendData.length, IP, sessionPort);
try {
clientSocket.send(sendPacket);
} catch (IOException e) {
e.printStackTrace();
}
DatagramPacket receivePacket = new DatagramPacket(receiveData, receiveData.length);
try {
clientSocket.receive(receivePacket);
} catch (IOException e) {
e.printStackTrace();
}
receiveData = receivePacket.getData();
onResponse(receiveData);
clientSocket.close();
}
//User should override this
public void onResponse(byte[] response){
System.out.println("RESPONSE: "+new String(response));
}
}
//The server code, this has to be converted to jar file start jar [nothing is needed to change in this code] .. and double click client jar to send packet to receiver end..//
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.net.*;
import java.io.*;
public class UDPMulticastServer{
JFrame frame;
JPanel panel;
JButton button1,button2;
JTextArea area;
JScrollPane pane;
Thread thread;
MulticastSocket socket;
public static void main(String[] args) {
UDPMulticastServer u = new UDPMulticastServer();
}
public UDPMulticastServer(){
frame = new JFrame("Broadcast Server");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setUndecorated(true);
frame.getRootPane().setWindowDecorationStyle(JRootPane.PLAIN_DIALOG);
panel = new JPanel();
panel.setLayout(null);
area = new JTextArea();
button1 = new JButton("Start");
button1.setBounds(210, 10, 75, 40);
button1.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
new StartServer();
}
});
panel.add(button1);
button2 = new JButton("Stop");
button2.setBounds(300, 10, 75, 40);
button2.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent ae){
thread.interrupt();
socket.close();
area.append("Server is stopped
");
button1.setEnabled(true);
button2.setEnabled(false);
}
});
button2.setEnabled(false);
panel.add(button2);
pane = new JScrollPane(area);
pane.setBounds(10, 60, 365, 250);
panel.add(pane);
frame.add(panel);
frame.setSize(400, 400);
frame.setVisible(true);
}
public class StartServer implements Runnable{
InetAddress address;
StartServer(){
thread = new Thread(this);
thread.start();
button1.setEnabled(false);
button2.setEnabled(true);
}
public void run(){
try{
byte[] buffer = new byte[65535];
int port = 4662;
String address = "224.0.0.0";
String address1 = "235.0.0.1";
String address2 = "235.255.0.1";
String address3 = "224.0.255.1";
String addresStr[] = {address, address1, address2, address3};
try{
socket = new MulticastSocket(port);
InetAddress add = InetAddress.getByName(address);
socket.joinGroup(add);
InetAddress add1 = InetAddress.getByName(address1);
socket.joinGroup(add1);
InetAddress add2 = InetAddress.getByName(address2);
socket.joinGroup(add2);
InetAddress add3 = InetAddress.getByName(address3);
socket.joinGroup(add3);
InetAddress str[] = {add, add1, add2, add3};
area.append("Server is started
");
while(true){
try{
//Receive request from client
for(int i=0; i < str.length; i++){
DatagramPacket packet = new DatagramPacket(buffer, buffer.length, str[i], port);
socket.receive(packet);
addresStr[i] = packet.getAddress().toString();
InetAddress client = packet.getAddress();
int client_port = packet.getPort();
area.append("Received : '" + new String(buffer).trim() + "' from " + addresStr[i] + "
");
// send information to the client
String message = "your request
";
buffer = message.getBytes() ;
packet = new DatagramPacket(buffer, buffer.length, client, client_port);
socket.send(packet);
}
}
catch(UnknownHostException ue){}
}
}
catch(java.net.BindException b){}
}
catch (IOException e){
System.err.println(e);
}
}
}
}
//thnq
Jakob Jenkov Hello Jakob, As now I can transfer small packets in UDP. Can you help me in Routing Table.. by that I can set up peer to peer network..
Pradeep babu I don't (yet) have a functioning routing table. I will have one later this year I think, but that will be too late for you, right?
Peer 0 has a direct connection to peer 8. The shortest path to peer 8 is 1 hub - a direct connection. The packet does not go through peer 1 and 2, if it is for peer 8.
Very good and clear explanation. Helped me alot. Thanks. Please post more on networks
I will ! 🙂
there is a decentralized Utopia ecosystem, it is also decentralized, so it is anonymous
Cool - I don't know this Utopia. Maybe I will take a look at it sometime.
I wish you made many videos on P2P and how to make a decentralized application, why did you stop? I am a developer and I wish to learn P2P and make applications using it.
Then you will be happy to know that I have just resumed my studies into P2P networks this year ;-) ... I stopped because I could not find all the solutions to the problems of designing a P2P network. But over the years I have found solutions for most of these problems, and this year I have found what I believe to be a new P2P routing table design which I believe solves many of the remaining challenges of P2P networks. I will be making videos about this, and topics related to this, in the future. I cannot promise exactly when, but they are coming sooner or later :-)
You greatly explained how Peers found other peers after joint but didn't explain how a new coming peer find a participating peer to ask for joining
Yes, this is a big challenge. A common approach is to have some "boot" peer that the operator of the network always keeps running, so new peers know this peer is always present. It can also be a group of peers etc. An alternative would be to post the location of some boot peers to a public directory service of some kind. On a local network you might be able to do some network broadcasting to discover other peers. All in all, this is an issue that each network operator has to decide how to solve. I have not found any good, standard solution for this (so far).
Peer 0 has peer 1, 2, 4 and 8 in its routing table, and thus it can contact each of those.
Which node is responsible for generating (and assigning) GUIDs?
That is a central design decision that each P2P network designer must decide themselves. In a trusted network each peer can generate its own GUID. In an untrusted network, each node must be assigned a GUID by a trusted entity (e.g. a "boot peer" or some similar mechanism).
One thing is not clear for me. Let’s suppose I’m creating a P2P application. How can the first joining peer find the boot peer. I have to add the address of boot peer as a constant to my application, right? But in these case the boot peer can’t leave the network, because every new joinging peer will use the boot peer to sync the routing table. I must be wrong, because this way the boot peer works as a server, not a peer. Sorry if my question is dumb, I’m not familiar with networks.
If the boot peer is found on a local network, you might be able to discover it using multicast / broadcast functionality. Otherwise the boot peer must be known when a peer joins the first time. When rejoining the network, the peer might be able to start with one of the peers it had in its routing table the last time - if any of them are still part of the network.
Tak. God introduktion!
Very well explained! helped me a lot! Thank you!
The best video!
Thank you very much :-)
Thank you very much :-)
Very useful video. Thanks !
This question might not be directly related. But how does a computer in a local private network make a connection to another in a different private network?
Bloody amazing :)
Thanks :-)
Building the routing table from scratch is probably the slowest part.
Nice video. Very clear.
What does he mean by “reference” here, when he says that the peers hold references to other peers in the network? Does he mean a way to find the peer in the physical world for example hold the IP address for the peer in order to be able to actually communicate with it?
Typically a "reference" to another peer is the peer's GUID + IP address / tcp port number. That's enough to create a connection to that peer when needed.
@@JakobJenkov so basically knowledge to connect to the peer in the real physical world (outside the logical GUID space), right? Thanks.
@@govardhangd9387 Yes
Great video! I haven’t seen this question asked yet, but say peer 4 leaves the network and never returns. Is GUID 4 never going to be assigned to any node ever again? I understand 2^64 is a very very large number of possibilities and may never fill up, but if that’s the case is it okay for there to be large gaps between GUIDs that are actually online?
Exactly how GUIDs are assigned to peers in a P2P network is sometimes left out of the papers describing the algorithms - even though GUID assignment is one of the most important aspects of P2P networks. I am actually working on a new P2P topology that is different from what I describe in this video, and there GUIDs are assigned by nodes already in the network. But my topology enables the network to "know" "all" peers + GUIDs in the network - so if peer 4 leaves, the peer that assigned peer 4 it's GUID will know very quickly, so the peer GUID can be reused. I call it the "Polymorph Polyring Topology". It's described here:
jenkov.com/tutorials/p2p/polymorph.html
thanks u so much, i was seen your tutorial, that's so useful.
Hi Pyro2501! What type of p2p system are you trying to set up? A lot of the algorithms are for specific goals. Depending on your system needs, and depending on how bleeding edge it is, then you may have to come up with your own algorithm. I found a lot of great articles on IEEE xplore. I suggest getting an account especially if you're a student.
Thank you, very useful!
Which element is the slowest during in P2P's? Like building an routing table, management, etc?
Great video!!!.
Thanks a lot.
How do peers connect over the internet? How do p2p applications avoid router configurations port forwarding? I need your help
Hi Mr Jenkov. Thanks for this great explaination. Quick question tho. Does each node use the xor distance when its deciding which other nodes to connect to? Because it first seemed to me that each node runs xor on other node ids, and then chooses other nodes if their distance is close or equal to 2 ^ n. For example, node 4 should connect to nodes 5,6,0,12 because xor result of 5 and each of these nodes in same order are: 1,2,4,8. So this seems valid but when you run it on node 1, it doesn't connect it to 3! but in your video you connected 1 to 3.
Hi Sep, different P2P routing algorithms use different distance functions. In my illustrations I use the Chord distance function which simply subtracts one node ID from the other, to find out the distance between them. That also means, that dist(A,B) is not equal to dist(B,A) . Kademlia uses XOR as distance function, and that changes *which* other nodes each node keeps in its routing table - but not *how many* nodes, and the overall principle of having nodes in the routing table with exponentially growing distance is also the same. By the way, using XOR as distance function then dist(A,B) is the same as dist(B,A).
@@JakobJenkov Thanks for clarification. Looking at your website tutorial made it all more simple. (tutorials.jenkov.com/p2p/peer-routing-table.html). I noticed that every now and then through my java programming career I have checked your website. You helped me a lot. Keep up the good work.
Hello jakob, last commend i made you clearly make me understand well p2p networks, thank you again for that. Now i have one question about sockets TCP. I've created an Client-Server app and the the server retrasmmit the messages from one client to other 4 clients, but im getting TOO OFTEN an "conection timed out" ecxeption and the connection breaks, why is this happening and why so often?
ERROR:Exception java.net.SocketException: recvfrom failed: ETIMEDOUT (Connection
timed out).
One more thing i' ve seen it happen when clients are sending (strings) message inside a loop.
okay i thought that was only a logical connection. But if thats true and you got a network 2^64 nodes wouldn't that mean that every node would have to have 64 physical connections. Also if you join the network why do you have to look for peers if they are conencted physically to you anyway. Sorry if i am bothering you but i really want to understand this.
So Peer 0 has the full route to Peer 8? Cause let say the physical connections looks like this 0--1--2--8 (shortest path from 0 to 8). 1 and 2 don't have 8 in there routing table so the packet would have to tell them how to route it, correct?
Okay the only part i don't understand is when peer 0 wants to contact peer 15 then like you said it will first try to contact peer 8. But how does it send a message to peer 8 cause most likely there will be no physical connection between them. So if 0 is physically connected to 1 and 2 how does it decide which to send the message for 8 and how do these nodes decide on how to forward the packet. If could explain that it would be really nice.
Thank a lot for the video, it's really helpful.
By the way the distance formula it's not clear up to me.
Are you saying that
distance(a,b) = (b-a + 2^N) mod (2^N)
where the symbol " ^ " means the power of two?
In that case it's not clear enough.
Thanks in advance.
Regards,
Daniele
Yes, that is what I said. However, the distance formula from Kademlia
distance(a,b) = a XOR b
is much easier to calculate, and has other advantages too.
Hello jakob, I am working on p2p systems for my master thesis. Now I have UDP server and client. How can I make connection between two or three different systems, i.e p2p way when each of them atleast knew other then they can connect.
Very useful video indeed. But would love to know...Why P2P ignore their own broadcast..?
+dilshan shan I am not sure I understand what you mean - ignore their own broadcast?
Hi
i want to ask how the boot peer decides what exactly GUID to give to each joining peer (knowing that peers join and leave frequently) and how each peer uses the fuction to create his own table (i get it only with peer with GUID:0)
Either the boot peer assigns GUIDs, or a GUID is chosen at random by the joining peer. In any case you need to find a way to avoid GUID spoofing - peers trying to join with another peer's GUID to impersonate it.
good work....
Using XOR, wouldn't peer0 not also have peers 15, 14 and 12 in its routing table?
At what time in the video?
Starting at 20:40 and going to almost the end
Hi Jenkov,
good introduction to Kademlia algorithm.
But there is something I don't understand. After calculating the distance to add the right node in the routing table, if the node is not connected we choose the closest one (superior I guess). But with this rule, we lost the "symmetry" of Kademlia and then if "the closest we add instead of the right one" leave, we will not be notify about it, and lose the Kademlia XOR advantage. Moreover, we lose the integrity of the routing table.
Please, can you explain to me how avoid this ? Thanks
Yes, if the peer with the "perfect GUID" is not online, and you choose the closest peer, then A might choose X and B might choose Y. But that is okay. A P2P network will not always be perfectly balanced, but that is okay. It will rebalance itself from time to time.
Ok thank you very much for your time and answer, but my problem is, in your algorithm, you said if a peer leave, it just notify all node of its routing table. But if A add X because it is the closest but not the perfect one, then X didn't have A in its table (assume X find all perfect peer), then A will not be notify of X leaving. That's what I mean with "lose the symmetry".
Thanks again for your help.
Peers are also removed if you try to locate it, but it is not part of the network. It is not only when a peer explicitly sends "leave" messages that routing tables are cleaned.
Jakob Jenkov ok perfect, thank you for your help. Great video and articles on your website btw
anyway, have you invested with earnmore.site
..i heard they are really paying their
investors....
Thnks for your reply! I have another question I am compiling a state of the art research document of P2P for a project im working on. Do you know of any good P2P resources online? As there is masses of info I am just having a problem finding decent P2P material regarding algorithms.
A little more energy could have made it lot better
;-)
1.5x is perfect
@Amy Tan Via a public node. There is no other way.
+Jakob Jenkov Hi, can you provide a P2P file sharing program built in java source code? or any reference for building a P2P file sharing in java. Thanks
Muhammad Hannan Unfortunately I never finished the one I started, so I can't. But - I am working on a cloud project where we are discussing if we should offer P2P as part of th services. But we haven't decided yet.
Follow- up: We have decided to add P2P functionality to our cloud project, but it will still take some time before we get there, as you can see from the time from my last comment and until this comment :-)
Hello, thanks a lot for this vidéo ;) i have a question please 1) which is the dht the more suitable for the cloud computing (ipv6 network) ?
That is a good question. I don't have the answer, unfortunately.
Jakob Jenkov
OK , thanks :) Pastry for example works with ipv6 ?
Ah, all of Chord, Kademlia and Pastry can work with IP v. 6 . Personally I think Kademlia (based on Chord) is the most elegant algorithm, but they are all very similar.
Jakob Jenkov
OK, thanks again :) what about bittorent dht ? i have to choice one of them
and for the mement i know working only with Pastry..
I don't know that much about how BitTorrent works, unfortunately.
Thank you very much.. perhaps the video could be a bit shorter :-)
Anyone in 2022 👍
What do you mean, exactly? :-)
Would like to know more but in short , this video is good indeed but quite long , can you post a small video please. for beginers !!!
It's LITERALLY only 25 minutes.
i lost my train of thought.
boring..
+BISHAWDEO MISHRA This isn't an entertainment show... :-)
You did an amazing job then!
No, its not an entertainment show, but the ways you explain makes me falling asleep xD