Description
Preamble: In this homework, you are required to write a C/C++/Java/Matlab program to implement the method for “Topology Management of Overlay Networks” described in Section 2.2.2 of Andrew S. Tanenbaum’s Distributed Systems book and in attached reading supplement 1 (The paper “T-Man: Fast Gossip-based Constructions of Large-Scale Overlay Topologies” by Mark Jelasity and Ozalp Babaoglu). This algorithm is also known as Jelasity and Babaoglu’s algorithm. The gist of this algorithm is discussed in the next paragraph (use the above references for the detailed descriptions). In this algorithm, every node in the network maintains a list of neighbors. During the network-initialization phase, each node randomly selects k neighbors and places them into its neighbor list. During the networkevolution phase, in each cycle of the iterative algorithm, every node randomly selects one of its neighbors, and then sends a list consisting of the identifiers of its neighbors and of itself to that neighbor. The selected neighbor also sends its neighbors list back to the node which initiated the action. Upon receiving the new neighbor list, the nodes select the nearest k nodes from both the new and old lists as their neighbors and discards all the others. You will write a sequential program that implements Jelasity and Babaoglu’s algorithm so that in each cycle the nodes in the network initiate communication with each of their neighbors one by one. Your program MUST accept N, the total number of nodes in the network, and k, the number of neighbors each node maintains as the input parameters. Tasks: There are 3 tasks as part of this homework which are elaborated below: 1. (Dynamic Ring Topology): Consider the case where the nodes are identified using integers (1, 2…N) and the distance between two nodes a and b is defined by the Euclidean distance. In a plane with point a at (x1, y1) and point b at (x2, y2), the Euclidean distance between them is defined as √(𝑥1 − 𝑥2 ) 2 − (𝑦1 − 𝑦2 ) 2 Using this distance will result in a ring. You will write a program that will accept N, the total number of nodes in the network, k, the number of neighbors each node maintains, n, the number of radius values, r1, r2, r3…, the sequence of ‘r’ values whose total number is specified by the above n. The value of r is reread every 5 iterations. Your program should adapt (i.e. changing the old value of r to the new value of r) in order to generate the ring whose radius is the last input value of r. However, this adaptation can only be done by incrementing the radius by one in every 3 iterations. a. Using your implementation of the algorithm, you must report the sum of distances of neighboring nodes during the initialization phase and after each running cycle. The sum of distances between neighboring nodes is defined as where neighbors(nodei) indicates all the nodes stored in the neighbor list of (nodei) b. For convenience, a node’s location is given by (cos θ, sin θ) where θ is the length of the arch or angle from the node to the positive x-axis in radians. 2. (Binary Tree Topology): You will modify the program to only accept N and k as inputs for this case. The topology you will be constructing is the binary tree. The following is an excerpt from Babaoglu’s paper describing how this topology can be obtained. “Binary tree: A low diameter topology can be constructed from a binary tree: the profiles are binary strings of length m, excluding the all zero string. Distance is defined as the shortest path length between the two nodes in the following undirected rooted binary tree. The string 0 . . . 01 is the root. Any string 0a2…m has two children a2 . . . am0 and a2 . . . am1. Strings starting with 1 are leaves. This topology is of interest because (unlike the previous ones) it has a very short (logarithmic) diameter of 2m.” The graphic given below shows you an example of the naming of nodes using binary strings. Here m=4 i.e. nodes are named with binary strings of length 4. The distance between the nodes “5” and “10” is 1. The distance between nodes “5” and “6” is 4. The distance between nodes “5” and “13” is 5. The root node is always considered to be at level 1. In this case the leaves are at level 4. A node whose value is between 2x and 2x+1 -1 will be at level x+1. a. Given below is a sample code to find the distance between any two nodes a and b. int dist (int a, int b) { int bits = 32; int alevel=bits; int blevel=bits; int commonprefix=0; int mask = 1 << bits-1; // find the level of node a while( (mask & a) == 0 ) { a <<= 1; alevel–; } // find the level of node b while( (mask & b) == 0 ) { b <<= 1; blevel–; } int length = Math.min(alevel,blevel); while( (mask & ~(a ^ b)) != 0 && length>0) { b <<= 1; a <<= 1; commonprefix++; length–; } return alevel – commonprefix + blevel – commonprefix; } 3. (Crescent Moon Topology): Change your code and the definition of distance so that a network shaped as a “crescent moon” results from running the code. Explain your definition of distance for this case. 4. Additional Instructions: In the task 1, dynamic ring topology, when the ring radius increases, your program will map all nodes on the original circle to a larger circle. The connections between nodes should not change, that is the neighbor lists of each node remain the same, only the node location is modified. In the homework report, you should show the results of testing your program using N=1000 nodes and k=30 neighbors and running it for 50 cycles. o For the task 1 – dynamic ring topology, your homework report should show the results of testing your program using N=1000 nodes, k=30 neighbors, n=5, r1=1, r2=4, r3=5, r4=8, r5=10 and running it for 50 cycles. You are also required to draw a two-dimensional plot showing the sum of distances between neighboring nodes after each running cycle of the initialization phase. In the plot, the vertical axis represents the sum of distances and the horizontal axis represents the number of cycles. You can use any tool of your choice to generate the plot. 5. Questions a. What methods do you use to ensure that there are no separated nodes in the dynamic ring topology and the crescent moon topology? b. Can a node’s neighbor list show the same node in multiple entries? Submission (Thursday, 01/19/2017, 5 Pm): 1. Your source code containing the main method must be named TMAN.. The names of the other supporting classes, if any, is up-to your choice. 2. Comment every module/class/function in your code and use descriptive variable names. 3. Your program MUST run using the command line arguments as shown below. It must accept the input arguments N, k and topology, where the topology can be one of D, B or C which represents dynamic ring, binary tree and crescent moon respectively. The total number of cycles is fixed at 50 for this homework. a. For the dynamic ring topology, your program MUST accept additional parameters n and r1,r2,r3…. The sequence of radii will be comma separated i.e. 1,3,5,6,7. Format: TMAN N k topology n r1,r2,r3,…,rn Below is an example for the different languages. The example also illustrates a sample input for the dynamic ring topology. Note that the values of n and r’s will not be provided for the other topologies. 4. The output of the program is the sum of distance for each cycle. For 1, 5, 10 and 15 cycles the program produces the node graph files (png, jpg, gif…) and a file that contains the neighbor list for each node. Any output file name should have a prefix – _N_k. e.g. D_N100_k3 Then, the sum of distances file is named .txt e.g. D_N100_k3.txt The node graph file is name _. e.g. D_N100_k3_10.png The neighbor list file is named _. e.g. D_N100_k3_10.txt 5. There are two files that you will be uploading as part of the homework submission. A tar file and a PDF file. Do NOT tar the PDF file. a. Upload the following files within a SINGLE tar file named “yourLastName_hw1.tar”: The source code of your program A file named “makefile” to compile the program. The TA will type only “make” to compile the program. Other methods are not allowed. A text file named “readme.txt” that precisely specifies the running environment including the operating system, language written, compiler version and any software needed to run your program. It also describes the program structure such – C: gcc TMAN N k topology – C++: g++ TMAN N k topology – Java: java TMAN N k topology – Matlab: matlab TMAN N k topology – C: gcc TMAN N k D 5 1,3,5,6,7 – C++: g++ TMAN N k D 5 1,3,5,6,7 – Java: java TMAN N k D 5 1,3,5,6,7 – Matlab: matlab TMAN N k D 5 1,3,5,6,7 as files, classes and significant methods. If your source code is in multiple files, describe briefly the content of each file. All these files should be tarred into a file i.e. the following command should work to create the tar file. $> tar cvf .tar * b. A PDF document (yourLastName_hw1.pdf) describing the definition of distance for the crescent moon topology and all results. Include the plots and the answers to the questions. Also, include your source code in the PDF. The source code MUST be pasted towards the end of the PDF. Include all your classes/modules/functions in the PDF file. NOTE: The PDF file MUST NOT be tarred. You will have two files to submit. A tar that contains your source code, readme file and a make file, and a PDF file that contains plots, answers to questions, definition of distance for the crescent moon and pasted text of your source code. 6. The tar file and the PDF must be uploaded to Canvas. Submission Policy: Do NOT include binary files. Use the file names as specified above. Incorrect submission formats will lead to a grade reduction. All submissions are expected by the deadline specified in the homework assignment. Grade is automatically reduced by 25% for every late day. Make sure to test your submitted code using the tar file. If untar, make, compile or any other command needed to executed your program do NOT work, your homework grade will be zero.
