-
Notifications
You must be signed in to change notification settings - Fork 0
Home
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
- The first one is where a node can request to join the p2p network. 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.
- The last endpoint will reflect the status of the network, returning a list of encoded strings.
Add the new node to the node which contains the most free capacity in the network.
1(1)
|
2(2)
/
3(0)
4 is new node, joint to node 2
1(1)
|
2(2)
/ \
3(0) 4(0)
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)
1(1) 5(3)
|
2(2)
/
3(1)
6 is new node, network has free capacity in node 2, 3, & 5. but 5 has the most free capacity(3). 6 will join to 5.
1(1) 5(3)
| |
2(2) 6(2)
/
3(1)
There are several cases can happen while a node leaving from the network
1(1) 5(3)
|
2(2)
/
3(1)
5 is leaving, delete the entire node tree
1(1)
|
2(2)
/
3(1)
1(1)
|
2(2)
/
3(1)
3 is leaving, just delete node 3. (reorder happens at node 2, explain this later)
1(1) 2(2)
| ---> |
2(2) 1(1)
1(1)
|
2(2)
/
3(1)
1 is leaving, node 2 become root of the tree
2(2)
|
3(1)
1(1)
|
2(2)
/
3(1)
2 is leaving, node 3 will join to 1 (parent of the leaving node)
1(1)
|
3(1)
1(1) 5(3)
|
2(2)
/ | \
3(1) 4(0) 7(4)
2 is leaving, the child which has the most free capacity will replace the place of the leaving node 2.
1(1) 5(3)
|
7(4)
*3(1) *4(0)
remaining children (3, 4) join the network where nodes have the most free capacity.
1. 7 has the most free capacity, so 3 join to the node 7.
2. after that, 5 and 7 have same free 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)
reorder happens at node 7
Reorder happens after a node leaving from the network. It happens at child node or parent node of the leaving node. Recursively reorder the node to make sure that the tree's depth would become smaller. The node moving upwards based on its free capacity and its parent's free capacity.
if the node has sufficient free capacity (parent node free capacity +1), then reorder 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 reorder 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, reorder start from parent of the leaving node (it's 7)
3(3)
/ | \
4(0) 5(1) 6(0)
|
*7(5)
/ |
8(1) 9(1)
free capacity of node 7(3) is greater than the free capacity of node 5(0) + 1
3(3)
/ | \
4(0)*7(5) 6(0)
/ | \
8(1) 9(1) 5(1)
again process is continue at node 7.
free capacity of node 7(2) is greater than the free capacity of the node 3(0) + 1
7(5)
/ / \ \
/ / \ \
8(1) 9(1) 5(1) 3(3)
/ \
4(0) 6(0)
node 7 is reach the root of the tree. so reorder process will stop.
The trees in the network topology can be encoded as a single string. so trace of the network is represent by list of encoded strings. node is represent by id(#children/max capacity) and encoded string contains nodes with nested square brackets, which represent the children of each node.
Eg: 1
3(3)
/ \
4(0) 5(1)
encoded string: "3(2/3)[ 4(0/0) 5(0/1) ]"
Eg: 2
3(3)
/ | \
4(0) 5(1) 6(0)
|
7(5)
/ | \
8(1) 9(1) 1(0)
encoded string: "3(3/3)[ 4(0/0) 5(1/1)[ 7(3/5)[ 8(0/1) 9(0/1) 1(0/0) ] ] 6(0/0) ]"
Eg: 3
3(3) 10(2)
/ | \ |
4(0) 5(1) 6(0) 11(1)
|
7(5)
/ | \
8(1) 9(1) 1(0)
encoded string: [
"3(3/3)[ 4(0/0) 5(1/1)[ 7(3/5)[ 8(0/1) 9(0/1) 1(0/0) ] ] 6(0/0) ]",
"10(1/2)[ 11(0/1) ]"
]