Home

Overview

A REST API application to simulate a p2p network with a tree topology. Following are the endpoints to interact with the program using HTTP calls

1. The first one is where a node can request to join the p2p network.
2. In this step we just assign the node to the best-fitting parent (the node with the most free capacity). With the second endpoint, the node can communicate to the service that it is leaving the network. In this case, we want to reorder the current node tree (not all the network) to build the solution where the tree has the fewest number of depth levels.
3. The last endpoint will reflect the status of the network, returning a list of encoded strings.

How a new node join to the network?

Add the new node to a node which contains most capacity in the network.

case 1: have a node with enough capacity

             1(1)
	      | 
	     2(2)
	    /   
	  3(0)  

4 is new node, joint to node 2
	    
             1(1)
	      | 
	     2(2)
	    /   \
	  3(0)  4(0)

case 2: there are no capacity to join

             1(1)             
	      | 
	     2(2)
	    /   \
	  3(0)  4(0)

5 is new node, will form a new tree
	    
             1(1)              5(3)
	      | 
	     2(2)
	    /   \
	  3(0)  4(0)

case 3: have more nodes with enough capacity

             1(1)              5(3)
	      |                 
	     2(2)              
	    /   
	  3(1)  

6 is new node, have enough capacity in node 2, 3, & 5. but 5 has more capacity(3). 6 will join to 5.
	    
             1(1)              5(3)
	      |                 |
	     2(2)              6(2)
	    /   
	  3(1)  

How new node leave from the network?

There are several cases can happen while a node leaving from the network

case a: leaf node is leaving

case a-1: leaving node is the root of the tree

             1(1)              5(3)
	      |                 
	     2(2)              
	    /   
	  3(1)  

5 is leaving, delete the entire node tree
	    
             1(1)             
	      |                 
	     2(2)             
	    /   
	  3(1)  

case a-2: leaving node is not the root of the tree

             1(1)           
	      |                 
	     2(2)              
	    /   
	  3(1)  

3 is leaving, just delete node 3. (re order happens at node 2, explain this later)
	    
             1(1)          2(2)    
	      |     --->    |         
	     2(2)          1(1)             

case b: leaving node has exactly one child

case b-1: leaving node is the root of the tree

             1(1)              
	      |                 
	     2(2)              
	    /   
	  3(1)  

1 is leaving, node 2 become root of the tree
	    
             2(2)             
	      |                 
	     3(1)              

case b-2: leaving node is not the root of the tree

             1(1)           
	      |                 
	     2(2)              
	    /   
	  3(1)  

2 is leaving, node 3 will join to 1 (parent of the leaving node)
	    
             1(1)         
	      |          
	     3(1)               

case c: leaving node has more than 1 child

             1(1)              5(3)
	      |                 
	     2(2)              
	   /  |  \
	3(1) 4(0) 7(4)   

2 is leaving, the child which has more capacity will reply the place of the leaving node 2. 
	    
             1(1)              5(3)
	      |                 
	     7(4)              
	     
	*3(1) *4(0)
 
remaining children (3, 4) join to the network where node has more capacity. 
1. 7 has more capacity, so 3 join to the node 7. 
2. after that 5 and 7 have same capacity(3). so 4 can join to either 7 or 5. 

             1(1)            7(4)              5(3)
	      |              / \                |
	     7(4)  ---->  1(1)  3(1)           4(0)
	      |
	     3(1) 
          
           re order happens at node 7