This directory contains the simulator distribution software which consists of two programs: (1) traffic_gen and (2) sim. The simulator software is completely independent from the rest of the code distribution. To compile traffic_gen and sim do: >make depend >make For a quick start check the examples in the "examples/" directory. traffic_gen =========== traffic_gen is used to generate a detailed simulation description that is then interpreted by sim. traffic_gen takes two arguments: >traffic_gen input.sc seed a) input.sc contains a brief description of the experiment scenario. input.sc contains three types of commands: * events num avg wjoin wleave wfail winsert wfind - this command generates "num" events with a Poisson distribution and an arrival rate of 1/avg. avg is expressed in ms. wjoin, wleave, wfail, winsert, and wfind represents integer weights associated to the basic five types of event: (1) node joining the system (wjoin), (2) node leaving the system (wleave), (3) node failing (wfail), (4) document insertion (insert), and (5) document lookup (find). These weights determine the probability that an event is of certain type. Let wtotal = wjoin+wleave+wfail+winsert+wfind. Then, a new event is a join with a probability of wjoin/wtotal, a leave event with probability wleave/wtotal, and so on. * wait time - this command introduces a pause between the previous and the next event * exit - this command signals the termination of the simulation b) "seed" represents the seed of the random number generator used to run the simulation. sim === sim implements the Chord protocol according to the pseudocode in the "pseudocode.txt" file. For the parameters used by the simulator and their settings see the "def.h" file. sim executes the list of events generated by traffic_gen. sim takes one mandatory parameter as an input: > ./sim -i input.ev sim can also take a random seed: > ./sim -i input.ev -s seed sim can further tweak aspects of its behavior. type "sim ?" for details. a) input.ev - is generated by traffic_gen, and contains the list of events to be executed by the simulator. There are size types of events: * join n t - node n joins the system at time t. The node contacted by n is chosen randomly. * leave n t - node n leaves the system at time t * fail n t - node n fails at time t * insert n id t - insert document id at time t; the operation is initiated by node n * find n id t - find document id at time t; the operation is initiated by node n * exit t - terminate simulation at time t An Example ========== Typically, running a simulation involves three steps: a) create a simulation description file. Below is an example of such description file, example.sc. > cat example.sc # create a network consisting of three nodes; # a node joins the system every 1 sec on the average events 3 1000 1 0 0 0 0 # wait 10 sec for the network to stabilize wait 10000 # insert 5 documents in the network events 5 1000 0 0 0 1 0 # generate a total of 10 events; each event is a document insertion # with probability 0.5 and a document lookup with probability 0.5 events 10 1000 0 0 0 10 10 # wait 1 sec to complete all operations wait 1000 # end the simulation exit 2) use the description file to create an event file, i.e., the file that contains all events to be executed by the simulator. (Note that the actual example.ev file shown below may differ from machine to machine due to the differences in the number generators.) > traffic_gen example.sc 31 >! example.ev > cat example.ev join 14473638 239 join 5410292 1075 join 7430505 1553 insert 5410292 6797233 12890 insert 14473638 1442499 13244 insert 5410292 3167227 13304 insert 7430505 846385 13624 insert 5410292 4720281 14478 insert 7430505 15494887 20820 find 5410292 1442499 22108 insert 5410292 625215 22131 insert 5410292 5147555 24283 find 5410292 846385 24715 find 5410292 5147555 24868 find 14473638 3167227 25391 insert 5410292 2591805 26092 insert 14473638 6075249 26738 find 5410292 3167227 27571 exit 28571 3) perform simulation by interpreting the event file. The output records each event. The output of sim records each simulated event. For document insertions and queries we also give the number of hops and timeouts of the lookup operation to locate the document. A timeout occurs when the operation initiator contacts a dead finger. In this case, the initiator backtracks and tries the next best finger. The output also displays the status of each node at the end of the simulation, i.e., its finger list, document list, and the list of outstanding requests, if any. The "pending documents" displays the list of documents whose insertion has failed. This list is used to differentiate between the documents which are not found because the insertion of these documents failed in the first place, and other failure cases. Among other cases of failures are (1) the node that initiates the query is not present in the system. This is either because the node has not joined the system yet or it has left the system before the operation has completed. These situations happen because traffic_gen cannot predict the dynamic behavior of the system. For instance, as soon as a join event is initiated, traffic_gen may use immediately that node to initiate a query. Example: # node 10 joins the system at time 100 node 10 joins at 100 # insert document 11 at time 101 from node 10 insert 10 11 101 The problem is that by time 101 the join has not completed. A node is consider to be present (i.e., the join operation to complete) only after another node points to the new node as its own successor; setPresent() in finger.c. (2) the document is not stored at the node returned by the lookup operation. NOTE: For the purpose of studying Chord, the failure due to (2) are the only relevant ones, as they actually represent a lookup failure due to an transient inconsistent routing state rather than an artifact of the interactions between traffic_gen and sim, or because the document was not inserted in the system in the first place. >sim -i example.ev -s 13 node 14473638 joins at time 239.000000 node 5410292 joins at time 2013.000000 node 7430505 joins at time 2163.000000 insert doc request (hops= 0 timeouts= 0 ); document 6797233 inserted at node 7430505 at time 13209.000000 insert doc request (hops= 0 timeouts= 0 ); document 1442499 inserted at node 5410292 at time 13496.000000 insert doc request (hops= 1 timeouts= 0 ); document 3167227 inserted at node 5410292 at time 13837.000000 insert doc request (hops= 1 timeouts= 0 ); document 846385 inserted at node 5410292 at time 14112.000000 insert doc request (hops= 1 timeouts= 0 ); document 4720281 inserted at node 5410292 at time 15085.000000 insert doc request (hops= 1 timeouts= 0 ); document 15494887 inserted at node 5410292 at time 21176.000000 insert doc request (hops= 1 timeouts= 0 ); document 625215 inserted at node 5410292 at time 22454.000000 find doc request (hops= 1 timeouts= 0 ); document 1442499 found at node 5410292 at time 22454.000000 insert doc request (hops= 1 timeouts= 0 ); document 5147555 inserted at node 5410292 at time 24495.000000 find doc request (hops= 1 timeouts= 0 ); document 846385 found at node 5410292 at time 25177.000000 find doc request (hops= 1 timeouts= 0 ); document 5147555 found at node 5410292 at time 25177.000000 find doc request (hops= 0 timeouts= 0 ); document 3167227 found at node 5410292 at time 25830.000000 insert doc request (hops= 1 timeouts= 0 ); document 2591805 inserted at node 5410292 at time 26375.000000 insert doc request (hops= 1 timeouts= 0 ); document 6075249 inserted at node 7430505 at time 27621.000000 find doc request (hops= 1 timeouts= 0 ); document 3167227 found at node 5410292 at time 28063.000000 Exit: 28571.000000 --------- Node = 5410292 (1) finger list: 7430505, 14473638 (h=7430505, t=14473638, size=2) doc list: 2591805, 5147555, 625215, 15494887, 4720281, 846385, 3167227, 1442499 request list: Node = 7430505 (1) finger list: 14473638, 5410292 (h=14473638, t=5410292, size=2) doc list: 6075249, 6797233 request list: Node = 14473638 (1) finger list: 5410292, 7430505 (h=5410292, t=7430505, size=2) doc list: request list: 7430506/0/14473638/7430505 (h=7430506, t=7430506) pending documents: