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 a 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

How re order happens?

Re order happens after a node leaving from the network. It happens at child node or parent node of the leaving node. Recursively re order the node to make sure that the tree's depth would become smaller. The node moving up words based on its capacity and its parent's capacity.

if the node has sufficient capacity (parent node capacity +1) than its parent, then re order the node with its parent. it means make the parent node as child of the node. this process continue till the node capacity is not enough to re order or it reaches the root of the node

	    3(3)
          /  |  \
       4(0) 5(1) 6(0)
	     |
            7(5)
          /  |  \
       8(1) 9(1) 1(0)

node 1 is leaving, re order start from parent of the leaving node (it's 7)

	    3(3)
          /  |  \
       4(0) 5(1) 6(0)
	     |
           *7(5)
          /  |  
       8(1) 9(1) 

capacity of node 7(3) is greater than capacity of node 5(0) + 1

	    3(3)
          /  |  \
       4(0)*7(5) 6(0)
          /  |  \
       8(1) 9(1) 5(1)

again process is continue. capacity of node 7(2) is greater than capacity of the 3(0) + 1

	    7(5)
         /  /  \  \
        /  /    \   \
     8(1) 9(1) 5(1) 3(3)
                    /  \
                  4(0) 6(0)

node 7 is reach the root. so re order process will stop.