diff options
33 files changed, 7076 insertions, 0 deletions
diff --git a/sources/fabrice/pacemaker/ChangeLog.txt b/sources/fabrice/pacemaker/ChangeLog.txt new file mode 100644 index 0000000..d67b739 --- /dev/null +++ b/sources/fabrice/pacemaker/ChangeLog.txt @@ -0,0 +1,40 @@ +2008/09/30: + * rotate .log files every hour, delete after 10 hours + * started planetlab analysis with pm_planal + +2008/09/26: + * Bug: refilling candidates with always the same bad peers prevents + querying the servers + * Bug: server rejecting children connections because it has no parent, + should make an exception for servers + * Set min reconnect time to 10 minutes + * Set reconnect time to master to 10 minutes + +2008/09/25: + * Experiment: started on all peers at 09:00 + * Prevent accepting a child when no parents + * Drop a well connected peer when an orphan is connecting + +2008/09/25: + * Experiment: started on first 100 peers at 23:30 + * Experiment: started on first 50 peers at 16:00 + * Set ndegree to 10 for servers + * Choose first candidates with smallest distance + * Disconnect from children with the same distance + * Remove old files: + * Remove old log files after uploading them, except the current one + * Remove old binaries and pretend to still have them + * Bug fixes: + * Most logs where deleted by mistake between 18h and 23h + +2008/09/24: + * Bug fixes + - IdentifiedMsg provides remote correct port + - ByeMsg does not requires IDENTIFIED state to trigger handler + - Export new binary only with argument -new_binary + - Import new binary only with option "auto_update" + +2008/09/23: + * Automatically propagates new binaries + * Propagates HeartBeatMsg to all neighbours + * Master and Server peers implementaed diff --git a/sources/fabrice/pacemaker/avt2trace.ml b/sources/fabrice/pacemaker/avt2trace.ml new file mode 100644 index 0000000..e032acb --- /dev/null +++ b/sources/fabrice/pacemaker/avt2trace.ml @@ -0,0 +1,85 @@ +open Sets + +open SimulTypes +open SimulTrace + +let input_line ic = + let s = String.lowercase (input_line ic) in + for i = 0 to String.length s - 1 do + match s.[i] with + '\t' -> s.[i] <- ' ' + | _ -> () + done; + s + + +let filename = Sys.argv.(1) + +let _ = + let events = ref [] in + + let min_time = ref max_float in + let max_time = ref min_float in + let npeers = ref 0 in + let ic = open_in filename in + begin + try + while true do + let line = input_line ic in + match String2.split_simplify line ' ' with + id :: nsessions :: sessions -> + let id = !npeers in + let rec iter sessions = + match sessions with + | [] -> () + | begin_time :: end_time :: sessions -> + let begin_time = float_of_string begin_time in + let end_time = float_of_string end_time in + min_time := min begin_time !min_time; + max_time := max end_time !max_time; + events := (begin_time, id, true) :: (end_time, id, false) :: !events; + iter sessions + | _ -> + Printf.printf "Unexpected line [%s]\n" + (String.escaped line); + assert false + in + iter sessions; + incr npeers; + | _ -> assert false + done; + with + End_of_file -> close_in ic; + end; + + Printf.printf "Sorting...\n%!"; + let events = List.sort compare !events in + let ndays = 1 + int_of_float ((!max_time -. !min_time) /. 86400.) in + let oc = open_out (filename ^ ".dat") in + trace_output oc (Peers !npeers); + trace_output oc (Days (ndays, 60 * 24)); + for i = 0 to !npeers - 1 do + trace_output oc (Peer (i,0., "avt")); + done; + let rec iter round next_round events = + match events with + [] -> () + | (time, p, status) :: tail -> + + if time < next_round then begin + trace_output oc (if status then + On p + else + Off p); + iter round next_round tail + + end else begin + trace_output oc (Round (round+1)); + iter (round+1) (next_round +. 60.) events + end + + in + trace_output oc (Round 0); + iter 0 (!min_time +. 60.) events; + trace_output oc End; + close_out oc
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/build.ocp b/sources/fabrice/pacemaker/build.ocp new file mode 100644 index 0000000..70cc473 --- /dev/null +++ b/sources/fabrice/pacemaker/build.ocp @@ -0,0 +1,70 @@ +pp = "camlp4o.opt" + +requires = [ "cdk"; "simul"; "net" ] + +begin "gentrace" + files = "gentrace.ml" + type = program +end + +(* Compute: + peers_per_round (number of peers online per round) + availability (real availability, and expected measured availability) + sessions (CDF of sessions lengths) +*) +begin "compavail" + files = "compavail.ml" + type = program +end + +begin "usetrace" + files = "usetrace.ml" + type = program +end + +begin "pingtrace" + files = "pingtrace.ml" + type = program +end + +begin "liartrace" + files = "liartrace.ml" + type = program +end + +begin "overnettrace" + files = "overnetTrace.ml" + type = program +end + +begin "avt2trace" + files = "avt2trace.ml" + type = program +end + +begin "doplots" + files = "doplots.ml" + type = program +end + + +begin "pacemaker" + files = [ + "pMTypes.ml"; + "pMConst.ml"; + "pMNetwork.ml"; + "pMOptions.ml"; + "pMArgs.ml"; + "pMGlobals.ml"; + "pMLog.ml"; + "pMHandlers.ml"; + "pMDriver.ml" ] + type = program +end + + +begin "pm_planal" + + files = [ "pM_pl_plot.ml" ] + type = program +end diff --git a/sources/fabrice/pacemaker/compavail.ml b/sources/fabrice/pacemaker/compavail.ml new file mode 100644 index 0000000..567dbbf --- /dev/null +++ b/sources/fabrice/pacemaker/compavail.ml @@ -0,0 +1,238 @@ +open SimulTrace +open SimulTypes + +(* Compute peers_per_round *) + +let day = 60 * 24 + +type peer = { + mutable availabilities : int array; + } + +let ndays = ref 0 + +let anon_args = ref [ Sys.argv.(0) ] +let accuracy_arg = ref 0 +let subdir = ref None + +let _ = + Arg.parse [ + "-subdir", Arg.String (fun s -> + subdir := Some s), "<subdir> : set subdir for data files"; + "-accu", Arg.Int ((:=) accuracy_arg), " <n>: period between heartbeats"; + "-ndays", Arg.Int ((:=) ndays), " <n> : number of days"; + ] + (fun t -> anon_args := t :: !anon_args) "" + + +let subdir = + match !subdir with + None -> failwith "You must specify a subdirectory for data files" + | Some dir -> + Unix2.safe_mkdir (Filename2.of_string dir); + dir + + +let argv = Array.of_list (List.rev !anon_args) +let trace = argv.(1) +let accuracy = if !accuracy_arg = 0 then 60 else !accuracy_arg + +let peers, nrounds, do_round = trace_read trace + +let nrounds = + if !ndays <> 0 then + day * !ndays + else nrounds + +let peers_per_round = Array.create nrounds 0 +let sessions = ref [] + +let npeers = Array.length peers + +let peers2 = Array.init npeers (fun _ -> + { + availabilities = [| 0; 0;0;0;0;0;0;0 |] + }) + +let _ = + let hour = ref 0 in + let next_ticket = ref (Random.int accuracy) in + for round = 0 to nrounds - 1 do + + do_round round; + let nb_on = ref 0 in + for i = 0 to npeers -1 do + let p = peers.(i) in + let p2 = peers2.(i) in + + if p.state = ON then begin + p2.availabilities.(0) <- p2.availabilities.(0) + 1; + p.session <- p.session + 1; + incr nb_on + end else + if p.session > 0 then begin + sessions := p.session :: !sessions; + p.session <- 0; + end + done; + + + if round = !next_ticket then begin + incr hour; + next_ticket := accuracy * !hour + Random.int accuracy; + for i = 0 to npeers - 1 do + let p = peers.(i) in + let p2 = peers2.(i) in + if p.state = ON then + p2.availabilities.(1) <- p2.availabilities.(1) + accuracy + done + end; + + if round mod accuracy = 1 then begin + for i = 0 to npeers - 1 do + let p = peers.(i) in + let p2 = peers2.(i) in + if p.state = ON then + if p.session > 5 then begin + p2.availabilities.(2) <- p2.availabilities.(2) + 60; + if p.session > 10 then begin + p2.availabilities.(3) <- p2.availabilities.(3) + 60; + if p.session > 20 then begin + p2.availabilities.(4) <- p2.availabilities.(4) + 60; + if p.session > 30 then begin + p2.availabilities.(5) <- p2.availabilities.(5) + 60; + if p.session > 40 then begin + p2.availabilities.(6) <- p2.availabilities.(6) + 60; + if p.session > 50 then begin + p2.availabilities.(7) <- p2.availabilities.(7) + 60; + end end + end end + end + end + done + end; + + + peers_per_round.(round) <- !nb_on + done + +(* +let _ = + let oc = open_out "peers_per_round.txt" in + for round = 0 to nrounds - 1 do + output_string oc (Printf.sprintf "%d %d\n" round peers_per_round.(round)) + done; + close_out oc + +let _ = + let oc = open_out "peers_per_round.plot" in + output_string oc (Printf.sprintf " +set out 'peers_per_round.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'peers_per_round.eps' +set yrange [0:%d] +set xrange [0:%d] +set ylabel 'Number of available peers' +set xlabel 'Time (minutes)' + +set data style lines + +plot \"peers_per_round.txt\" using ($1):($2) title 'Peers' + " npeers nrounds); + close_out oc + *) + +let _ = + if !accuracy_arg = 0 then + let avail = Array.init 8 (fun _ -> Array.create npeers 0) in + for i = 0 to npeers - 1 do + for k = 0 to 7 do + avail.(k).(i) <- peers2.(i).availabilities.(k) + done + done; + Array.iter (fun avail -> + Array.sort compare avail) avail; + + let oc = open_out (Printf.sprintf "%s/availpolicies.txt" subdir) in + for i = 0 to npeers - 1 do + output_string oc (Printf.sprintf "%d " i); + for k = 0 to 7 do + output_string oc (Printf.sprintf "%.3f " + (float_of_int avail.(k).(i) /. float_of_int nrounds)) + done; + output_string oc "\n"; + done; + close_out oc + else + let error = Array.create npeers 0 in + for i = 0 to npeers - 1 do + error.(i) <- + abs (peers2.(i).availabilities.(1) - peers2.(i).availabilities.(1)) + done; + Array.sort compare error; + + let oc = open_out ( + (Printf.sprintf "%s/availpolicies_%d.txt" subdir accuracy)) in + for i = 0 to npeers - 1 do + output_string oc (Printf.sprintf "%d " i); + output_string oc (Printf.sprintf "%.3f " + (float_of_int error.(i) /. float_of_int nrounds)); + output_string oc "\n"; + done; + close_out oc + +let npoints = 30 + +let _ = + + + let every = + if npeers > npoints then + Printf.sprintf " every %d " (npeers / npoints) else "" in + + let oc = open_out ( + Printf.sprintf "%s/availpolicies.plot" subdir) in + output_string oc (Printf.sprintf " +set out 'availpolicies.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'availpolicies.eps' +set key left +set yrange [0:%d*21.0/20] +set xrange [0:%d*21.0/20] +set ylabel 'Availability' +set xlabel 'CDF of peers' + +set data style linespoints + +plot \"availpolicies.txt\" %s using ($1):($2) title 'Real Availability', \"availpolicies.txt\" %s using ($1):($3) title 'Measured Availability (random)', \"availpolicies.txt\" %s using ($1):($4) title 'Measured Availability (5)',\"availpolicies.txt\" %s using ($1):($5) title 'Measured Availability (10)',\"availpolicies.txt\" %s using ($1):($6) title 'Measured Availability (20)',\"availpolicies.txt\" %s using ($1):($7) title 'Measured Availability (30)',\"availpolicies.txt\" %s using ($1):($8) title 'Measured Availability (40)',\"availpolicies.txt\" %s using ($1):($9) title 'Measured Availability (50)' + " 1 npeers every every every every every every every every); + close_out oc + +(* +let _ = + let sessions = Array.of_list !sessions in + let nsessions = Array.length sessions in + Array.sort compare sessions; + let oc = open_out "sessions.txt" in + for i = 0 to nsessions - 1 do + output_string oc (Printf.sprintf "%d %d\n" i sessions.(i)) + done; + close_out oc; + + let oc = open_out "sessions.plot" in + output_string oc (Printf.sprintf " +set out 'sessions.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'sessions.eps' +set logscale y +set yrange [1:%d] +set xrange [0:%d] +set ylabel 'Session Length (minutes)' +set xlabel 'CDF of sessions' + +set data style lines + +plot \"sessions.txt\" %s using ($1):($2) title 'Sessions', 60 title '1 hour' + " sessions.(nsessions-1) nsessions); + close_out oc +*)
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/data/Makefile.plots b/sources/fabrice/pacemaker/data/Makefile.plots new file mode 100644 index 0000000..e27049d --- /dev/null +++ b/sources/fabrice/pacemaker/data/Makefile.plots @@ -0,0 +1,45 @@ +FIGURES=\ + figs/ask_root_msgs.eps \ + figs/max_distance_per_round.eps \ + figs/mean_avail_distance.eps \ + figs/peers_per_round.eps \ + figs/sessions.eps \ + figs/connections.eps \ + figs/error_avail.eps \ + figs/ping_error_avail.eps \ + +#availability.eps connections.eps all_availability.eps all_error_avail.eps error_avail.eps ping_error_avail.eps liars_measure.eps + +all: figs $(FIGURES) $(FIGURES:.pdf=.eps) + +figs: + mkdir -p figs + +%.eps: %.cdf +%.cdf: %.txt + sort -n -k 2 $*.txt | cat -b > $*.cdf + +figs/mean_avail_distance.eps: \ + usetrace0x10/mean_avail_distance1.cdf \ + usetrace0x10/mean_avail_distance2.cdf \ + usetrace0x10/mean_avail_distance3.cdf \ + usetrace0x10/mean_avail_distance4.cdf \ + usetrace0x10/mean_avail_distance5.cdf \ + usetrace0x10/mean_avail_distance6.cdf \ + usetrace0x10/mean_avail_distance7.cdf \ + usetrace0x10/mean_avail_distance8.cdf \ + +figs/connections.eps: usetrace0x10/connections3.txt +usetrace0x10/connections3.txt: usetrace0x10/connections2.txt + cat -n usetrace0x10/connections2.txt > usetrace0x10/connections3.txt +usetrace0x10/connections2.txt: usetrace0x10/connections.txt + tac usetrace0x10/connections.txt > usetrace0x10/connections2.txt + +figs/peers_per_round.eps: figs/peers_per_round.plot usetrace0x10/peers_per_round.txt + gnuplot < figs/peers_per_round.plot + +%.eps: %.plot + gnuplot < $*.plot + +%.pdf: %.eps + epstopdf $*.eps diff --git a/sources/fabrice/pacemaker/data/Makefile.simul b/sources/fabrice/pacemaker/data/Makefile.simul new file mode 100644 index 0000000..739a4bd --- /dev/null +++ b/sources/fabrice/pacemaker/data/Makefile.simul @@ -0,0 +1,64 @@ +BIN_DIR=/home/lefessan/devel/onzego/research/pace-maker +USETRACE_BIN=$(BIN_DIR)/usetrace +COMPAVAIL_BIN=$(BIN_DIR)/compavail +PINGTRACE_BIN=$(BIN_DIR)/pingtrace +LIARTRACE_BIN=$(BIN_DIR)/liartrace + +COMPAVAIL_DATA= compavail/availpolicies.txt + +USETRACE_DATA= \ +usetrace$(NSELFISH)x$(ACCURACY)/ask_root_msgs.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/availability.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/connections.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/error_avail.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/lost_tickets.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/max_distance_per_round.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/mean_avail_distance1.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/mean_avail_distance2.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/mean_avail_distance3.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/mean_avail_distance4.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/peers_per_round.txt \ +usetrace$(NSELFISH)x$(ACCURACY)/sessions.txt + +PINGTRACE_DATA= \ +pingtrace$(NDEGREE)/ping_availability_$(NDEGREE).txt \ +pingtrace$(NDEGREE)/ping_error_avail_$(NDEGREE).txt + +LIARTRACE_DATA= \ +liartrace$(NLIARS)x$(NPROBES)/liar_measured_$(NLIARS)x$(NPROBES).txt \ +liartrace$(NLIARS)x$(NPROBES)/liar_measuredE_$(NLIARS)x$(NPROBES).txt \ +liartrace$(NLIARS)x$(NPROBES)/liar_number_$(NLIARS)x$(NPROBES).txt \ +liartrace$(NLIARS)x$(NPROBES)/liar_real_$(NLIARS)x$(NPROBES).txt \ +liartrace$(NLIARS)x$(NPROBES)/liar_real.txt + +DATA= $(COMPAVAIL_DATA) + +all: $(DATA) + for i in 10 20 30 60 120; do \ + $(MAKE) -f Makefile.simul NSELFISH=0 ACCURACY=$$i selfish; \ + done + for i in 0 10 20 30 40 50 60 70 80 90; do \ + $(MAKE) -f Makefile.simul NSELFISH=$$i ACCURACY=60 selfish; \ + done + for i in 5 10 15 20 25 30; do \ + $(MAKE) -f Makefile.simul NDEGREE=$$i ping; \ + done + for i in 1 2 3; do \ + $(MAKE) -f Makefile.simul NLIARS=5 NPROBES=$$i liars; \ + done + +selfish: $(USETRACE_DATA) +ping: $(PINGTRACE_DATA) +liars: $(LIARTRACE_DATA) + +$(LIARTRACE_DATA): trace.dat + $(LIARTRACE_BIN) -subdir liartrace$(NLIARS)x$(NPROBES) -nliars $(NLIARS) -probes $(NPROBES) trace.dat + +$(USETRACE_DATA): trace.dat + time $(USETRACE_BIN) -subdir usetrace$(NSELFISH)x$(ACCURACY) -accuracy $(ACCURACY) -nselfish $(NSELFISH) trace.dat + +$(COMPAVAIL_DATA): trace.dat + time $(COMPAVAIL_BIN) -subdir compavail trace.dat + +$(PINGTRACE_DATA): trace.dat + time $(PINGTRACE_BIN) -subdir pingtrace$(NDEGREE) -degree $(NDEGREE) trace.dat diff --git a/sources/fabrice/pacemaker/data/usetrace.tex b/sources/fabrice/pacemaker/data/usetrace.tex new file mode 100644 index 0000000..1495c26 --- /dev/null +++ b/sources/fabrice/pacemaker/data/usetrace.tex @@ -0,0 +1,137 @@ +\documentclass[11pt,a4paper]{article} + +\usepackage{epsfig} + +\newcommand{\figurebox}[1]{#1} + +\def\figheader{fig:} + +\newcommand{\psfigure}[3]{ % {scale}{filename=label}{caption} + \begin{figure}[t]\begin{center}% + \epsfig{file=#2,width=#1\hsize}% + \begin{quote}\let\normalsize\small\caption{#3\label{\figheader#2}}\end{quote}% + \end{center} + \vspace{-0.8cm}% +\end{figure}} + +\newcommand{\psfigureR}[3]{ % {scale}{filename=label}{caption} + \begin{figure}[t]\begin{center}% + \epsfig{file=#2,width=#1\hsize,angle=-90}% + \begin{quote}\let\normalsize\small\caption{#3\label{\figheader#2}}\end{quote}% + \end{center} + \vspace{-0.8cm}% +\end{figure}} + +\begin{document} + +\input{data.tex} + +\section*{Simulation Parameters} + +Here are the parameters used to compute the simulation: + +\begin{tabular}{|l|l|} +\hline +Network size: &\npeers peers\\ +Length: &\nminutes minutes (\ndays days)\\ +Availability: & Uniform Distribution in [0.1;1.0]\\ +Deconnections per day:& Uniform Distribution in [1;10]\\ +Timezones:& Uniform Distribution in [0;12]\\ +\hline +\end{tabular}\\ + + For each peer, we randomly choose an availability and a number of +disconnections per day. We then compute its probabilities of coming online +and offline using Markov Chains. We use these probabilities in the +simulation. + + Note that the uniform distribution of availabilities is not standard in +peer-to-peer systems, but here, we want to show that the measured +availability is not different from the real availability, so the +distribution of availabilities does not matter. We will check later that +the mesh behaves correctly with a powerlaw, but the mesh is not the focus +of this paper... + + Timezones are used to obtain a diurnal pattern: during day, peers have +twice their normal probability of coming online and half their normal +probability of going offline. + +\section*{Simulation Results} + +Here are some values obtained during the simulation: + +\begin{tabular}{|l|l|} +\hline +Number of Sessions : &\nsessions sessions\\ +\hline +\end{tabular} + +\section*{Simulation Mesh} + + We simulate a network of peers connected in a mesh around a server. The +server diffuses tickets every hours to measure the availability of peers. + + In the current simulation, the mesh protocol is the following: the server +has a degree of 10 children, and each peer has a degree of 5 children and 5 +parents. To connect to the mesh, a peer first queries the server, which +replies with a list of its children. The peer then queries the children. +Every children either accepts the peer as a child, or send a random of its +children. The process iterates until the peer is connected to 5 different +parents. + + We take the following (local) decisions to improve the system: +\begin{itemize} +\item At every round, one a peer has a free child slot, it chooses among +all the candidates who queried it during the round (one minute) the one +with the best measured availability. +\item A peer disconnects its children which are at the same distance from +the server as it. (hey, this is not a local property ! we should only +do it after a ticket diffusion or during the query !) +\end{itemize} + + Every round in the simulation takes one minute. From a communication +point of view, it allows us to assume some timeout on messages that allows +detection of peer disconnection (TCP keepalive is 30 seconds). + +\begin{center} + +\psfigureR{1.5}{sessions}{CDF of Sessions lengths. Note that the median +session length is around two hours. It does not follow a powerlaw, but we +don't really.} + +\psfigureR{1.5}{max_distance_per_round}{Maximal distance to the server over + time. Note that the diameter of the network is not too high.} + + \psfigureR{1.5}{peers_per_round}{Number of peers online over time. Note +that since the timezones of peers are only on 12 hours, we observe some +diurnal pattern that we would not observe if the distribution was over 24 +hours.} + +\psfigureR{1.5}{connections}{Time spent between the beginning of a peer +session and the connection to its first parent. Only in some rare cases, it is +above 7 minutes. Since in our system, we focus on long session times +(median session length is two hours), this delay is neglectible.} + +\psfigureR{1.5}{mean_avail_distance}{Mean Availability of Connected Peers +depending on their distance to the server. It shows that peers at distance +1 from the server have a much better availability, and so on...} + +% \psfigureR{1.5}{availpolicies}{} + + \psfigureR{1.5}{ask_root_msgs}{The number of AskRoot messages sent +per minute to the server in our mesh.} + + +\psfigureR{1.5}{availability}{Measured availability compared to real +availability. Note that the difference between the real availability and +the availability measured using tickets is very close.} + \psfigureR{1.5}{error_avail}{} + + \psfigureR{1.5}{all_availability}{} + \psfigureR{1.5}{all_error_avail}{} + + \psfigureR{1.5}{ping_error_avail}{} + \psfigureR{1.5}{liars_measure}{} + +\end{center} +\end{document} diff --git a/sources/fabrice/pacemaker/doplots.ml b/sources/fabrice/pacemaker/doplots.ml new file mode 100644 index 0000000..99e861e --- /dev/null +++ b/sources/fabrice/pacemaker/doplots.ml @@ -0,0 +1,1046 @@ +open SimulGraphes + +let data_dir = Filename2.of_string "/home/lefessan/devel/onzego/research/pace-maker/data" +let current_dir = Filename2.of_string "." + + +let _ = + Unix2.safe_mkdir (Filename2.of_string "figs"); + List.iter (fun basename -> + File.of_string (Filename2.add_basename current_dir basename) + (File.to_string (Filename2.add_basename data_dir basename))) + [ "Makefile.simul"; "Makefile.plots"; "usetrace.tex"] + + +let npeers1, exp = + let exp = ref false in + let npeers = ref 0 in + let ic = open_in "trace.dat" in + for i = 0 to 10 do + match SimulTrace.trace_input ic with + SimulTrace.Exponential -> exp := true + | SimulTrace.Peers n -> npeers := n + | _ -> () + done; + !npeers, !exp + +let _ = + Printf.printf "1/ Update simulations\n%!"; + Sys.command "make -f Makefile.simul" + + +let _ = + Printf.printf "2/ Prepare data for plots\n%!" + + +let max_error_abs, max_error_rel = + let errors_abs = ref [] in + let errors_pct = ref [] in + File.iter_lines (fun line -> + match String2.split_simplify line ' ' with + [ _; avail1; avail2 ] -> + let avail1 = float_of_string avail1 in + let avail2 = float_of_string avail2 in + let error_abs = abs_float (avail1 -. avail2) in + let error_pct = if avail1 > 0.0001 then + error_abs /. avail1 else 0. in + errors_abs := error_abs :: !errors_abs; + errors_pct := error_pct :: !errors_pct; + | _ -> assert false + ) (Filename2.of_string "usetrace0x60/availability.txt"); + let errors_abs = List.sort compare !errors_abs in + let errors_pct = List.sort compare !errors_pct in + let oc = open_out "usetrace0x60/availability2.txt" in + let count = ref 1 in + let max_error_abs = ref 0. in + let max_error_rel = ref 0. in + List.iter2 (fun e1 e2 -> + Printf.fprintf oc "%d %f %f\n" !count e1 e2; + incr count; + if e1 > !max_error_abs then max_error_abs := e1; + if e1 > !max_error_rel then max_error_rel := e1 + ) errors_abs errors_pct; + close_out oc; + !max_error_abs, !max_error_rel + +let npeers = + Printf.printf "figs/availability.plot\n%!"; + let np, _,_ = on_file "usetrace0x60/availability.txt" in + let npoints = 1000000 in + let every = if np > npoints then np / npoints else 1 in + let oc = open_out "figs/availability.plot" in + Printf.fprintf oc " + +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/availability.eps' +set yrange [0:1] +set xrange [0:%d*51.0/50] +set ylabel 'Availability' +set xlabel 'CDF of peers' + +set key left +set data style linespoints + +plot \"usetrace0x60/availability2.txt\" every %d using ($1):($2) title 'Absolute Error', \"usetrace0x60/availability2.txt\" every %d using ($1):($3) title 'Relative Error' + " + np every every + ; + close_out oc; + np + +let nsessions = + Printf.printf "figs/sessions.plot\n%!"; + let nsessions, mins, maxs = on_file "usetrace0x10/sessions.txt" in + + let npoints = 1000 in + let every = if nsessions > npoints then nsessions / npoints else 1 in + + let oc = open_out "figs/sessions.plot" in + Printf.fprintf oc " + +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/sessions.eps' + +set logscale y +set yrange [1:%.0f] +set xrange [0:%d] +set ylabel 'Session Length (minutes)' +set xlabel 'CDF of sessions' + +set data style lines +set key left + +plot \"usetrace0x10/sessions.txt\" every %d using ($1):($2) title 'Sessions', 60 title '1 hour' + " + maxs.(1) nsessions every + ; + close_out oc; + nsessions + +let variance_of filename = + let ic = open_in filename in + let count = ref 0 in + let prevs = ref [||] in + let diffs = ref [||] in + (try + let line = input_line ic in + incr count; + let line = String2.split_simplify line ' ' in + prevs := Array.create (List.length line) 0.; + diffs := Array.create (List.length line) 0.; + let prevs = !prevs in + let diffs = !diffs in + List2.iteri (fun i x -> + let x = float_of_string x in + prevs.(i) <- x; + diffs.(i) <- x) line; + while true do + let line = input_line ic in + incr count; + let line = String2.split_simplify line ' ' in + List2.iteri (fun i x -> + let x = float_of_string x in + let y = max (x -. prevs.(i)) ( prevs.(i) -. x) in +(* if i = 1 then + Printf.printf "%d %.1f->%.1f = %.1f\n" i prevs.(i) x y; *) + prevs.(i) <- x; + diffs.(i) <- y +. diffs.(i)) line; + done + + with End_of_file -> ()); + let diffs = !diffs in + if !count > 0 then begin + for i = 0 to Array.length diffs - 1 do + diffs.(i) <- diffs.(i) /. float_of_int !count; + done; + end; + !count, diffs + + +let nminutes = + Printf.printf "figs/mean_avail_distance.plot\n%!"; + let ntime, _, _ = on_file "usetrace0x10/mean_avail_distance1.txt" in + let every = max 1 (ntime / 200) in + let oc = open_out "figs/mean_avail_distance.plot" in + Printf.fprintf oc " + +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/mean_avail_distance.eps' +set yrange [0:1001] +set xrange [0:%d] +set ylabel 'Mean availability (1/1000)' +set xlabel 'CDF of minutes' +set title 'Mean avail/distance %d peers%s' + +set key bottom +set data style lines + +# We don't print distance=5 because the variance is too high + + plot \"usetrace0x10/mean_avail_distance1.cdf\" every %d using ($1):($3) title 'distance 1'" + ntime npeers (if exp then " exp" else " uni")every; + + (try + for i = 2 to 10 do + let filename = Printf.sprintf "usetrace0x10/mean_avail_distance%d.txt" i in + if Sys.file_exists filename then + let _, diffs = variance_of filename in + if diffs.(1) < 5. then begin + Printf.fprintf oc ",\"usetrace0x10/mean_avail_distance%d.cdf\" every %d using ($1):($3) title 'distance %d'" i every i + end else begin + Printf.printf "stopping at curve %d\n" i; + raise Exit + end + done with Exit -> ()); + Printf.fprintf oc "\n"; + close_out oc; + ntime + +let nsessions = + Printf.printf "figs/connections.plot\n%!"; + let nconns,_, maxs = on_file "usetrace0x10/connections.txt" in + let oc = open_out "figs/connections.plot" in + + let npoints = 1000 in + let every = nconns / npoints in + Printf.fprintf oc " + +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/connections.eps' + +set yrange [1:%.1f*21/20] +set xrange [0:%d*51/50] +set ylabel 'Time to first connection (minutes)' +set xlabel 'CDF of connections' + +set key left +set data style lines + + plot \"usetrace0x10/connections3.txt\" every %d using ($1/%d):($2) title 'Connection time (minutes)' + " maxs.(1) nconns every every; + close_out oc; + nsessions + +let _ = + Printf.printf "figs/peers_er_round.plot\n%!"; + let oc = open_out "figs/peers_per_round.plot" in + let ntime, _, maxs = on_file "usetrace0x10/peers_per_round.txt" in + + Printf.fprintf oc " + +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/peers_per_round.eps' +set xrange [0:%d] +set yrange [0:%.0f*21/20] +set ylabel 'Number of available peers' +set xlabel 'Time (minutes)' + +set data style lines + +plot \"usetrace0x10/peers_per_round.txt\" using ($1):($2) title 'available peers' + " ntime maxs.(1); + close_out oc + +(* +let _ = + let oc = open_out "ask_root_msgs.plot" in + let ntime, _, maxs = on_file "ask_root_msgs.txt" in + + Printf.fprintf oc " + +set out 'ask_root_msgs.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'ask_root_msgs.eps' +set xrange [0:%d] +set yrange [0:%.0f*21/20] +set ylabel 'AskRoot messages per minute' +set xlabel 'Time (minutes)' + +set data style lines + +plot \"ask_root_msgs.txt\" using ($1):($2) title 'AskRoot msgs(%d peers)' + " ntime maxs.(1) npeers; + close_out oc + + +let _ = + let ntime, _, maxs = on_file "max_distance_per_round.txt" in + let oc = open_out "max_distance_per_round.plot" in + + Printf.fprintf oc "set out 'max_distance_per_round.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'max_distance_per_round.eps' +set xrange [0:%d] +set yrange [0:%.0f*12/10] +set ylabel 'Maximal distance from server' +set xlabel 'Time (minutes)' + +set data style lines + + plot \"max_distance_per_round.txt\" using ($1):($2) title 'maximal distance' + " ntime maxs.(1); + close_out oc + + +let _ = + let plots = ref [] in + for nselfish = 1 to 99 do + let filename = Printf.sprintf "availability_%d.txt" nselfish in + if Sys.file_exists filename then + plots := nselfish :: !plots + done; + + let oc = open_out "all_availability.plot" in + + Printf.fprintf oc " +set out 'all_availability.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'all_availability.eps' +set yrange [0:1] +set xrange [0:%d] +set ylabel 'Availability' +set xlabel 'CDF of peers' + +set key left +set data style lines + + plot \"availability.txt\" using ($1):($2) title 'real availability' " npeers; + List.iter (fun nselfish -> + Printf.fprintf oc ", \"availability_%d.txt\" using ($1):($3) title 'measured availability (%d selfish peers)'" + nselfish nselfish + ) (List.rev !plots); + Printf.fprintf oc "\n"; + close_out oc; + + +(* + let oc = open_out "all_lost_tickets.plot" in + let filename = match !plots with + [] -> + "lost_tickets.txt" + | max :: _ -> + Printf.sprintf "lost_tickets_%d.txt" max + in + let nhours, mins, maxs = on_file filename in + + Printf.fprintf oc " +set out 'all_lost_tickets.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'all_lost_tickets.eps' +set yrange [0:%.0f] +set xrange [0:%d] +set ylabel 'Number of lost heartbeats' +set xlabel 'Time (minutes)' + +set key left +set data style lines + + plot \"lost_tickets.txt\" using ($1):($2) title 'lost heartbeats (0 selfish peers)'" + maxs.(1) nhours; + + + List.iter (fun nselfish -> + Printf.fprintf oc ", \"lost_tickets_%d.txt\" using ($1):($2) title 'lost heartbeats (%d selfish peers)'" + nselfish nselfish + ) (List.rev !plots); + Printf.fprintf oc "\n"; + close_out oc; +*) + + + + + + + + let maxe = ref 0.1 in + List.iter (fun plot -> + let filename = Printf.sprintf "error_avail_%d.txt" plot in + let _, _, maxs = on_file filename in + maxe := max !maxe maxs.(1) + ) !plots; + + let oc = open_out "all_error_avail.plot" in + + Printf.fprintf oc " +set out 'all_error_avail.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'all_error_avail.eps' +set yrange [0:%.1f] +set xrange [0:%d] +set ylabel 'Error on measured availability' +set xlabel 'CDF of peers' + +set key left +set data style lines + + plot \"error_avail.txt\" using ($1):($2) title 'error (no selfish peers)'" + !maxe npeers; + + + let w = ref 0 in + List.iter (fun nselfish -> + incr w; + Printf.fprintf oc ", \"error_avail_%d.txt\" using ($1):($2) title 'error (%d%% selfish peers)' lw %d" + nselfish nselfish !w + ) (List.rev !plots); + Printf.fprintf oc "\n"; + close_out oc; +() +*) + +let max_error = + let _, _, maxs = on_file "usetrace0x60/error_avail.txt" in + let oc = open_out "figs/error_avail.plot" in + Printf.fprintf oc " + +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/error_avail.eps' +set yrange [0:%.4f] +set xrange [0:%d+2] +set ylabel 'Error in measured availability' +set xlabel 'CDF of peers' +set data style lines + +plot \"usetrace0x60/error_avail.txt\" every 2 using ($1):($2) title 'error' + " maxs.(1) npeers; + close_out oc; + maxs.(1) + +let _ = + let max_error = ref max_error in + let degrees = ref [] in + for degree = 1 to 100 do + let filename = Printf.sprintf "pingtrace%d/ping_error_avail_%d.txt" degree degree in + if Sys.file_exists filename then begin + let _, _, maxs = on_file filename in + max_error := max !max_error maxs.(1); + degrees := degree :: !degrees; + end + done; + let oc = open_out "figs/ping_error_avail.plot" in + Printf.fprintf oc " + +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/ping_error_avail.eps' +set yrange [0.001:1] +set xrange [0:%d+2] +set ylabel 'Error in measured availability' +set xlabel 'CDF of peers' +set data style lines +set key left +set logscale y + +plot \ + \"usetrace0x60/error_avail.txt\" every 2 using ($1):($2) title 'diffusion error'" + (*!max_error*) npeers; + List.iter (fun degree -> + Printf.fprintf oc ",\"pingtrace%d/ping_error_avail_%d.txt\" every 2 using ($1):($2) title 'ping error (%d observers)'" degree degree degree) + (List.rev !degrees); + + Printf.fprintf oc "\n"; + close_out oc + + (* + +let _ = + let degrees = ref [] in + let maxa = ref 0.1 in + for degree = 1 to 20 do + for nprobes = 1 to 5 do + let filename = Printf.sprintf "liar_measured_%dx%d.txt" + degree nprobes in + if Sys.file_exists filename then + let _, _, maxs = on_file filename in + maxa := max !maxa maxs.(1); + degrees := (degree, nprobes) :: !degrees + done; + done; + + let maxa = 1.3 *. !maxa in + let oc = open_out "liars_measure.plot" in + Printf.fprintf oc " + set xtics (\"5\" 7200, \"10\" 20400, \"15\" 21600, \"20\" 28800) +set out 'liars_measure.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'liars_measure.eps' +set yrange [0:%.1f] +set xrange [0:%d] +set ylabel 'Network Availability' +set xlabel 'Time (days)' + +set data style lines + + plot \"liar_real.txt\" using ($1):($2) title 'real (without liars)'" + maxa nminutes; + + List.iter (fun (degree, nprobes) -> + Printf.fprintf oc + ", \"liar_measured_%dx%d.txt\" using ($1):($2) title 'measured (%d challenges, %d observers)'" degree nprobes nprobes degree + ) !degrees; + Printf.fprintf oc "\n"; + close_out oc + +let _ = + let _, _, maxs = on_file "error_avail.txt" in + let oc = open_out "error_avail.plot" in + Printf.fprintf oc " +set out 'error_avail.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'error_avail.eps' +set yrange [0:%.3f] +set xrange [0:%d+2] +set ylabel 'Error in measured availability' +set xlabel 'CDF of peers' +set data style lines + +plot \"error_avail.txt\" every 2 using ($1):($2) title 'error' +" maxs.(1) npeers; + close_out oc + +let _ = + let npoints = 50 in + let every = 1 + npeers / npoints in + let files = ref [] in + let maxi = ref 0. in + for i = 1 to 300 do + let filename = Printf.sprintf "error_avail_period%d.txt" i in + if Sys.file_exists filename then begin + let _, _, maxs = on_file filename in + for_every every filename; + maxi := max maxs.(1) !maxi; + files := i :: !files + end + done; + + let oc = open_out "error_avail_periods.plot" in + Printf.fprintf oc " +set out 'error_avail_periods.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'error_avail_periods.eps' +set yrange [0.0001:%.3f] +set xrange [0:%d+2] +set ylabel 'Error in measured availability' +set xlabel 'CDF of peers' +set data style linespoints +set key left + +plot " !maxi npeers; + + match List.rev !files with + [] -> () + | n :: tail -> + Printf.fprintf oc " \"error_avail_period%d.txt\" every %d using ($1):($2) title 'error (period %d minutes)'" n every n; + List.iter (fun n -> + Printf.fprintf oc ", \"error_avail_period%d.txt\" every %d using ($1):($2) title 'error (period %d minutes)'" n every n + ) tail; + + Printf.fprintf oc "\n"; + close_out oc + + + +let _ = + let npoints = 50 in + let every = 1 + npeers / npoints in + let files = ref [] in + let maxi = ref 0. in + for i = 1 to 40 do + let filename = Printf.sprintf "error_avail_ndays%d0.txt" i in + if Sys.file_exists filename then begin + let _, _, maxs = on_file filename in + for_every every filename; + maxi := max maxs.(1) !maxi; + files := i * 10 :: !files + end + done; + + let oc = open_out "error_avail_ndays.plot" in + Printf.fprintf oc " +set out 'error_avail_ndays.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'error_avail_ndays.eps' +set yrange [0.0001:%.3f] +set xrange [0:%d+2] +set ylabel 'Error in measured availability' +set xlabel 'CDF of peers' +set data style linespoints +set key left + +plot " !maxi npeers; + + match List.rev !files with + [] -> () + | n :: tail -> + Printf.fprintf oc " \"error_avail_ndays%d.txt\" every %d using ($1):($2) title 'error (%d days)'" n every n; + List.iter (fun n -> + Printf.fprintf oc ", \"error_avail_ndays%d.txt\" every %d using ($1):($2) title 'error (%d days)'" n every n + ) tail; + + Printf.fprintf oc "\n"; + close_out oc + +let _ = + let oc = open_out "data.tex" in + + Printf.fprintf oc "\\def\\npeers{%d }\n" npeers; + Printf.fprintf oc "\\def\\nminutes{%d }\n" nminutes; + Printf.fprintf oc "\\def\\ndays{%d }\n" (nminutes / 24 / 60); + Printf.fprintf oc "\\def\\nsessions{%d }\n" nsessions; + + close_out oc + + + open SimulGraphes + +let npeers = + + let np, _,_ = on_file "availability.txt" in + let npoints = 1000000 in + let every = if np > npoints then np / npoints else 1 in + let oc = open_out "availability.plot" in + Printf.fprintf oc " +set out 'availability.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'availability.eps' +set yrange [0:1] +set xrange [0:%d*51.0/50] +set ylabel 'Availability' +set xlabel 'CDF of peers' + +set key left +set data style linespoints + +plot \"availability.txt\" every %d using ($1):($2) title 'Real Availability', \"availability.txt\" every %d using ($1):($3) title 'Measured Availability (random)' + " + np every every + ; + close_out oc; + np + +let nsessions = + + let nsessions, mins, maxs = on_file "usetrace0x10/sessions.txt" in + + let npoints = 1000 in + let every = if nsessions > npoints then nsessions / npoints else 1 in + + let oc = open_out "figs/sessions.plot" in + Printf.fprintf oc " + +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/sessions.eps' + +set logscale y +set yrange [1:%.0f] +set xrange [0:%d] +set ylabel 'Session Length (minutes)' +set xlabel 'CDF of sessions' + +set data style lines +set key left + +plot \"sessions.txt\" every %d using ($1):($2) title 'Sessions', 60 title '1 hour' + " + maxs.(1) nsessions every + ; + close_out oc; + nsessions +*) + +(* +let variance_of filename = + let ic = open_in filename in + let count = ref 0 in + let prevs = ref [||] in + let diffs = ref [||] in + (try + let line = input_line ic in + incr count; + let line = String2.split_simplify line ' ' in + prevs := Array.create (List.length line) 0.; + diffs := Array.create (List.length line) 0.; + let prevs = !prevs in + let diffs = !diffs in + List2.iteri (fun i x -> + let x = float_of_string x in + prevs.(i) <- x; + diffs.(i) <- x) line; + while true do + let line = input_line ic in + incr count; + let line = String2.split_simplify line ' ' in + List2.iteri (fun i x -> + let x = float_of_string x in + let y = max (x -. prevs.(i)) ( prevs.(i) -. x) in +(* if i = 1 then + Printf.printf "%d %.1f->%.1f = %.1f\n" i prevs.(i) x y; *) + prevs.(i) <- x; + diffs.(i) <- y +. diffs.(i)) line; + done + + with End_of_file -> ()); + let diffs = !diffs in + if !count > 0 then begin + for i = 0 to Array.length diffs - 1 do + diffs.(i) <- diffs.(i) /. float_of_int !count; + done; + end; + !count, diffs + +let nminutes = + let ntime, _, _ = on_file "mean_avail_distance1.txt" in + + let oc = open_out "mean_avail_distance.plot" in + Printf.fprintf oc " + set out 'mean_avail_distance.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'mean_avail_distance.eps' +set yrange [0:1001] +set xrange [0:%d] +set ylabel 'Mean availability (1/1000)' +set xlabel 'Time (minutes)' + +set key bottom +set data style lines + +# We don't print distance=5 because the variance is too high + + plot \"mean_avail_distance1.txt\" using ($1):($2) title 'distance 1'" + ntime; + + (try + for i = 2 to 10 do + let filename = Printf.sprintf "mean_avail_distance%d.txt" i in + if Sys.file_exists filename then + let _, diffs = variance_of filename in + if diffs.(1) < 5. then begin + Printf.fprintf oc ",\"mean_avail_distance%d.txt\" using ($1):($2) title 'distance %d'" i i + end else begin + Printf.printf "stopping at curve %d\n" i; + raise Exit + end + done with Exit -> ()); + Printf.fprintf oc "\n"; + close_out oc; + ntime + +let nsessions = + let nconns,_, maxs = on_file "connections.txt" in + let oc = open_out "connections.plot" in + let npoints = 10000 in + let every = if nconns > npoints then (nconns-1) / npoints else 1 in + + let nconns = + let nconns' = every * (nconns / every) + 1 in + if nconns' <> nconns then begin + + let nconns' = nconns' + every in + Printf.printf "every: %d, nconns: %d, nconns': %d\n" every nconns nconns'; + let oc = open_out_gen [Open_append] 0o644 "connections.txt" in + for i = nconns+1 to nconns' do + Printf.fprintf oc "%d %.0f\n" i maxs.(1) + done; + close_out oc; + nconns'+1 + + end else nconns in + + + + Printf.fprintf oc " + set out 'connections.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'connections.eps' + +set yrange [1:%.1f*21/20] +set xrange [0:%d*51/50] +set ylabel 'Time to first connection (minutes)' +set xlabel 'CDF of connections' + +set key left +set data style lines + + plot \"connections.txt\" every %d using ($1):($2) title 'Connection time (minutes)' + " maxs.(1) nconns every; + close_out oc; + nsessions + +let _ = + let oc = open_out "peers_per_round.plot" in + let ntime, _, maxs = on_file "peers_per_round.txt" in + + Printf.fprintf oc " + +set out 'peers_per_round.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'peers_per_round.eps' +set xrange [0:%d] +set yrange [0:%.0f*21/20] +set ylabel 'Number of available peers' +set xlabel 'Time (minutes)' + +set data style lines + +plot \"peers_per_round.txt\" using ($1):($2) title 'available peers' + " ntime maxs.(1); + close_out oc + + *) + +let _ = + let oc = open_out "figs/ask_root_msgs.plot" in + let ntime, _, maxs = on_file "usetrace0x10/ask_root_msgs.txt" in + + let every = max 1 (ntime / 200) in + Printf.fprintf oc " + +set out 'figs/ask_root_msgs.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set xrange [0:%d] +set yrange [0:%.0f*21/20] +set ylabel 'AskRoot messages per minute' +set xlabel 'CDF of minutes' + +set data style lines + +plot \"usetrace0x10/ask_root_msgs2.txt\" every %d using ($1):($3) title 'AskRoot msgs(%d peers)' + " ntime maxs.(1) every npeers; + close_out oc + +let _ = + let ntime, _, maxs = on_file "usetrace0x10/max_distance_per_round.txt" in + let oc = open_out "figs/max_distance_per_round.plot" in + let every = max 1 (ntime / 200) in + + Printf.fprintf oc " +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/max_distance_per_round.eps' +set xrange [0:%d] +set yrange [0:%.0f*12/10] +set ylabel 'Maximal distance from server' +set xlabel 'Time (minutes)' + +set data style lines + + plot \"usetrace0x10/max_distance_per_round2.txt\" every %d using ($1):($3) title 'maximal distance(%d peers)' + " ntime maxs.(1) every npeers; + close_out oc + +let _ = + let plots = ref [] in + for nselfish = 1 to 99 do + let filename = Printf.sprintf "usetrace%dx60/availability.txt" nselfish in + if Sys.file_exists filename then + plots := nselfish :: !plots + done; + + (* + let oc = open_out "figs/selfish_impact.plot" in + + Printf.fprintf oc " + +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/selfish_impact.eps' +set yrange [0:1] +set xrange [0:%d] +set ylabel 'Availability' +set xlabel 'CDF of peers' + +set key left +set data style lines + + plot \"availability.txt\" using ($1):($2) title 'real availability' " npeers; + List.iter (fun nselfish -> + Printf.fprintf oc ", \"availability_%d.txt\" using ($1):($3) title 'measured availability (%d selfish peers)'" + nselfish nselfish + ) (List.rev !plots); + Printf.fprintf oc "\n"; + close_out oc; +*) + +(* + let oc = open_out "all_lost_tickets.plot" in + let filename = match !plots with + [] -> + "lost_tickets.txt" + | max :: _ -> + Printf.sprintf "lost_tickets_%d.txt" max + in + let nhours, mins, maxs = on_file filename in + + Printf.fprintf oc " +set out 'all_lost_tickets.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'all_lost_tickets.eps' +set yrange [0:%.0f] +set xrange [0:%d] +set ylabel 'Number of lost heartbeats' +set xlabel 'Time (minutes)' + +set key left +set data style lines + + plot \"lost_tickets.txt\" using ($1):($2) title 'lost heartbeats (0 selfish peers)'" + maxs.(1) nhours; + + + List.iter (fun nselfish -> + Printf.fprintf oc ", \"lost_tickets_%d.txt\" using ($1):($2) title 'lost heartbeats (%d selfish peers)'" + nselfish nselfish + ) (List.rev !plots); + Printf.fprintf oc "\n"; + close_out oc; +*) + + + + + + + + let maxe = ref 0.1 in + List.iter (fun plot -> + let filename = Printf.sprintf "usetrace%dx60/error_avail.txt" plot in + let _, _, maxs = on_file filename in + maxe := max !maxe maxs.(1) + ) !plots; + + let oc = open_out "figs/selfish_impact.plot" in + + Printf.fprintf oc " + +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'figs/selfish_impact.eps' +set yrange [0:%.1f] +set xrange [0:%d] +set ylabel 'Error on measured availability' +set xlabel 'CDF of peers' + +set key left +set data style lines + + plot \"usetrace0x60/error_avail.txt\" using ($1):($2) title 'error (no selfish peers)'" + !maxe npeers; + + + let w = ref 0 in + List.iter (fun nselfish -> + incr w; + Printf.fprintf oc ", \"usetrace%dx60/error_avail.txt\" using ($1):($2) title 'error (%d%% selfish peers)' lw %d" + nselfish nselfish !w + ) (List.rev !plots); + Printf.fprintf oc "\n"; + close_out oc; +() + + (* + +let max_error = + let _, _, maxs = on_file "error_avail.txt" in + let oc = open_out "error_avail.plot" in + Printf.fprintf oc " +set out 'error_avail.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'error_avail.eps' +set yrange [0:%.4f] +set xrange [0:%d+2] +set ylabel 'Error in measured availability' +set xlabel 'CDF of peers' +set data style lines + +plot \"error_avail.txt\" every 2 using ($1):($2) title 'error' + " maxs.(1) npeers; + close_out oc; + maxs.(1) + +let _ = + let max_error = ref max_error in + let degrees = ref [] in + for degree = 1 to 100 do + let filename = Printf.sprintf "ping_error_avail_%d.txt" degree in + if Sys.file_exists filename then begin + let _, _, maxs = on_file filename in + max_error := max !max_error maxs.(1); + degrees := degree :: !degrees; + end + done; + let oc = open_out "ping_error_avail.plot" in + Printf.fprintf oc " +set out 'ping_error_avail.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'ping_error_avail.eps' +set yrange [0.01:1] +set xrange [0:%d+2] +set ylabel 'Error in measured availability' +set xlabel 'CDF of peers' +set data style lines +set key left +set logscale y + +plot \ + \"error_avail.txt\" every 2 using ($1):($2) title 'diffusion error'" + (*!max_error*) npeers; + List.iter (fun degree -> + Printf.fprintf oc ",\"ping_error_avail_%d.txt\" every 2 using ($1):($2) title 'ping error (%d observers)'" degree degree) + (List.rev !degrees); + + Printf.fprintf oc "\n"; + close_out oc + + + +let _ = + let degrees = ref [] in + let maxa = ref 0.1 in + for degree = 1 to 20 do + for nprobes = 1 to 5 do + let filename = Printf.sprintf "liar_measured_%dx%d.txt" + degree nprobes in + if Sys.file_exists filename then + let _, _, maxs = on_file filename in + maxa := max !maxa maxs.(1); + degrees := (degree, nprobes) :: !degrees + done; + done; + + let maxa = 1.3 *. !maxa in + let oc = open_out "liars_measure.plot" in + Printf.fprintf oc " + set xtics (\"5\" 7200, \"10\" 20400, \"15\" 21600, \"20\" 28800) +set out 'liars_measure.eps' +set terminal postscript eps enhanced \"Helvetica\" 20 +set out 'liars_measure.eps' +set yrange [0:%.1f] +set xrange [0:%d] +set ylabel 'Network Availability' +set xlabel 'Time (days)' + +set data style lines + + plot \"liar_real.txt\" using ($1):($2) title 'real (without liars)'" + maxa nminutes; + + List.iter (fun (degree, nprobes) -> + Printf.fprintf oc + ", \"liar_measured_%dx%d.txt\" using ($1):($2) title 'measured (%d challenges, %d observers)'" degree nprobes nprobes degree + ) !degrees; + Printf.fprintf oc "\n"; + close_out oc + *) + +(* +let _ = + let oc = open_out "data.tex" in + + Printf.fprintf oc "\\def\\npeers{%d }\n" npeers; + Printf.fprintf oc "\\def\\nminutes{%d }\n" nminutes; + Printf.fprintf oc "\\def\\ndays{%d }\n" (nminutes / 24 / 60); + Printf.fprintf oc "\\def\\nsessions{%d }\n" nsessions; + + close_out oc + *) + +let _ = + Printf.printf "3/ Compute plots\n%!"; + Sys.command "make -f Makefile.plots"
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/finalplots.ml b/sources/fabrice/pacemaker/finalplots.ml new file mode 100644 index 0000000..83824a3 --- /dev/null +++ b/sources/fabrice/pacemaker/finalplots.ml @@ -0,0 +1,626 @@ +open SimulGraphes + +let npeers = + + let np, _,_ = on_file "uniform/availability.txt" in + let npoints = 1000000 in + let every = if np > npoints then np / npoints else 1 in + let oc = open_out "availability.plot" in + Printf.fprintf oc " +set out 'availability.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'availability.eps' +set yrange [0:1] +set xrange [0:%d*51.0/50] +set ylabel 'Availability' +set xlabel 'CDF of peers' + +set key left +set data style linespoints + +plot \"uniform/availability.txt\" every %d using ($1):($2) title 'Real Availability', \"uniform/availability.txt\" every %d using ($1):($3) title 'Measured Availability (random)' + " + np every every + ; + close_out oc; + np + + +let nsessions = + + let nsessions, mins, maxs = on_file "uniform/sessions.txt" in + + let npoints = 1000 in + let every = if nsessions > npoints then nsessions / npoints else 1 in + + let oc = open_out "sessions.plot" in + Printf.fprintf oc " + set out 'sessions.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'sessions.eps' + +set logscale y +set yrange [1:%.0f] +set xrange [0:%d] +set ylabel 'Session Length (minutes)' +set xlabel 'CDF of sessions' + +set data style lines +set key left + +plot \"uniform/sessions.txt\" every %d using ($1):($2) title 'Sessions', 60 title '1 hour' + " + maxs.(1) nsessions every + ; + close_out oc; + nsessions + + +let variance_of filename = + let ic = open_in filename in + let count = ref 0 in + let prevs = ref [||] in + let diffs = ref [||] in + (try + let line = input_line ic in + incr count; + let line = String2.split_simplify line ' ' in + prevs := Array.create (List.length line) 0.; + diffs := Array.create (List.length line) 0.; + let prevs = !prevs in + let diffs = !diffs in + List2.iteri (fun i x -> + let x = float_of_string x in + prevs.(i) <- x; + diffs.(i) <- x) line; + while true do + let line = input_line ic in + incr count; + let line = String2.split_simplify line ' ' in + List2.iteri (fun i x -> + let x = float_of_string x in + let y = max (x -. prevs.(i)) ( prevs.(i) -. x) in +(* if i = 1 then + Printf.printf "%d %.1f->%.1f = %.1f\n" i prevs.(i) x y; *) + prevs.(i) <- x; + diffs.(i) <- y +. diffs.(i)) line; + done + + with End_of_file -> ()); + let diffs = !diffs in + if !count > 0 then begin + for i = 0 to Array.length diffs - 1 do + diffs.(i) <- diffs.(i) /. float_of_int !count; + done; + end; + !count, diffs + +let nminutes = + let ntime, _, _ = on_file "uniform/mean_avail_distance1.txt" in + + let oc = open_out "mean_avail_distance.plot" in + Printf.fprintf oc " + set out 'mean_avail_distance.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'mean_avail_distance.eps' +set yrange [0:1001] +set xrange [0:%d] +set ylabel 'Mean availability (1/1000)' +set xlabel 'Time (minutes)' + +set key bottom +set data style lines + +# We don't print distance=5 because the variance is too high + + plot \"uniform/mean_avail_distance1.txt\" using ($1):($2) title 'distance 1'" + ntime; + + (try + for i = 2 to 10 do + let filename = Printf.sprintf "uniform/mean_avail_distance%d.txt" i in + if Sys.file_exists filename then + let _, diffs = variance_of filename in + if diffs.(1) < 5. then begin + Printf.fprintf oc ",\"uniform/mean_avail_distance%d.txt\" using ($1):($2) title 'distance %d'" i i + end else begin + Printf.printf "stopping at curve %d\n" i; + raise Exit + end + done with Exit -> ()); + Printf.fprintf oc "\n"; + close_out oc; + ntime + +let nsessions = + let nconns,_, maxs = on_file "uniform/connections.txt" in + let oc = open_out "connections.plot" in + let npoints = 10000 in + let every = if nconns > npoints then (nconns-1) / npoints else 1 in + + let nconns = + let nconns' = every * (nconns / every) + 1 in + if nconns' <> nconns then begin + + let nconns' = nconns' + every in + Printf.printf "every: %d, nconns: %d, nconns': %d\n" every nconns nconns'; + let oc = open_out_gen [Open_append] 0o644 "connections.txt" in + for i = nconns+1 to nconns' do + Printf.fprintf oc "%d %.0f\n" i maxs.(1) + done; + close_out oc; + nconns'+1 + + end else nconns in + + + + Printf.fprintf oc " + set out 'connections.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'connections.eps' + +set yrange [1:%.1f*21/20] +set xrange [0:%d*51/50] +set ylabel 'Time to first connection (minutes)' +set xlabel 'CDF of connections' + +set key left +set data style lines + + plot \"uniform/connections.txt\" every %d using ($1):($2) title 'Connection time (minutes)' + " maxs.(1) nconns every; + close_out oc; + nsessions + +let _ = + let oc = open_out "peers_per_round.plot" in + let ntime, _, maxs = on_file "uniform/peers_per_round.txt" in + + Printf.fprintf oc " + +set out 'peers_per_round.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'peers_per_round.eps' +set xrange [0:%d] +set yrange [0:%.0f*21/20] +set ylabel 'Number of available peers' +set xlabel 'Time (minutes)' + +set data style lines + +plot \"uniform/peers_per_round.txt\" using ($1):($2) title 'available peers' + " ntime maxs.(1); + close_out oc + +let _ = + let oc = open_out "ask_root_msgs.plot" in + let ntime, _, maxs = on_file "uniform/ask_root_msgs.txt" in + + Printf.fprintf oc " + +set out 'ask_root_msgs.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'ask_root_msgs.eps' +set xrange [0:%d] +set yrange [0:%.0f*21/20] +set ylabel 'AskRoot messages per minute' +set xlabel 'Time (minutes)' + +set data style lines + +plot \"uniform/ask_root_msgs.txt\" using ($1):($2) title 'AskRoot msgs(%d peers)' + " ntime maxs.(1) npeers; + close_out oc + + +let _ = + let ntime, _, maxs = on_file "uniform/max_distance_per_round.txt" in + let oc = open_out "max_distance_per_round.plot" in + + Printf.fprintf oc "set out 'max_distance_per_round.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'max_distance_per_round.eps' +set xrange [0:%d] +set yrange [0:%.0f*12/10] +set ylabel 'Maximal distance from server' +set xlabel 'Time (minutes)' + +set data style lines + + plot \"uniform/max_distance_per_round.txt\" using ($1):($2) title 'maximal distance' + " ntime maxs.(1); + close_out oc + +let _ = + let plots = ref [] in + for nselfish = 1 to 99 do + let filename = Printf.sprintf "uniform/availability_%d.txt" nselfish in + if Sys.file_exists filename then + plots := nselfish :: !plots + done; + + let oc = open_out "all_availability.plot" in + + Printf.fprintf oc " +set out 'all_availability.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'all_availability.eps' +set yrange [0:1] +set xrange [0:%d] +set ylabel 'Availability' +set xlabel 'CDF of peers' + +set key left +set data style lines + + plot \"uniform/availability.txt\" using ($1):($2) title 'real availability' " npeers; + List.iter (fun nselfish -> + Printf.fprintf oc ", \"uniform/availability_%d.txt\" using ($1):($3) title 'measured availability (%d selfish peers)'" + nselfish nselfish + ) (List.rev !plots); + Printf.fprintf oc "\n"; + close_out oc; + + +(* + let oc = open_out "all_lost_tickets.plot" in + let filename = match !plots with + [] -> + "lost_tickets.txt" + | max :: _ -> + Printf.sprintf "lost_tickets_%d.txt" max + in + let nhours, mins, maxs = on_file filename in + + Printf.fprintf oc " +set out 'all_lost_tickets.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'all_lost_tickets.eps' +set yrange [0:%.0f] +set xrange [0:%d] +set ylabel 'Number of lost heartbeats' +set xlabel 'Time (minutes)' + +set key left +set data style lines + + plot \"lost_tickets.txt\" using ($1):($2) title 'lost heartbeats (0 selfish peers)'" + maxs.(1) nhours; + + + List.iter (fun nselfish -> + Printf.fprintf oc ", \"lost_tickets_%d.txt\" using ($1):($2) title 'lost heartbeats (%d selfish peers)'" + nselfish nselfish + ) (List.rev !plots); + Printf.fprintf oc "\n"; + close_out oc; +*) + + + + + + + + let maxe = ref 0.1 in + List.iter (fun plot -> + let filename = Printf.sprintf "uniform/error_avail_%d.txt" plot in + let _, _, maxs = on_file filename in + maxe := max !maxe maxs.(1) + ) !plots; + + let oc = open_out "all_error_avail.plot" in + + Printf.fprintf oc " +set out 'all_error_avail.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'all_error_avail.eps' +set yrange [0:%.1f] +set xrange [0:%d] +set ylabel 'Error on measured availability' +set xlabel 'CDF of peers' + +set key left +set data style lines + + plot \"uniform/error_avail.txt\" using ($1):($2) title 'error (no selfish peers)'" + !maxe npeers; + + + let w = ref 0 in + List.iter (fun nselfish -> + incr w; + Printf.fprintf oc ", \"uniform/error_avail_%d.txt\" using ($1):($2) title 'error (%d%% selfish peers)' lw %d" + nselfish nselfish !w + ) (List.rev !plots); + Printf.fprintf oc "\n"; + close_out oc; +() + + +let max_error = + let _, _, maxs = on_file "uniform/error_avail.txt" in + let oc = open_out "error_avail.plot" in + Printf.fprintf oc " +set out 'error_avail.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'error_avail.eps' +set yrange [0:%.4f] +set xrange [0:%d+2] +set ylabel 'Error in measured availability' +set xlabel 'CDF of peers' +set data style lines + +plot \"uniform/error_avail.txt\" every 2 using ($1):($2) title 'error' + " maxs.(1) npeers; + close_out oc; + maxs.(1) + +let _ = + let max_error = ref max_error in + let degrees = ref [] in + for degree = 1 to 100 do + let filename = Printf.sprintf "uniform/ping_error_avail_%d.txt" degree in + if Sys.file_exists filename then begin + let _, _, maxs = on_file filename in + max_error := max !max_error maxs.(1); + degrees := degree :: !degrees; + end + done; + let oc = open_out "ping_error_avail.plot" in + Printf.fprintf oc " +set out 'ping_error_avail.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'ping_error_avail.eps' +set yrange [0.01:1] +set xrange [0:%d+2] +set ylabel 'Error in measured availability' +set xlabel 'CDF of peers' +set data style lines +set key left +set logscale y + +plot \ + \"uniform/error_avail.txt\" every 2 using ($1):($2) title 'diffusion error'" + (*!max_error*) npeers; + List.iter (fun degree -> + Printf.fprintf oc ",\"uniform/ping_error_avail_%d.txt\" every 2 using ($1):($2) title 'ping error (%d observers)'" degree degree) + (List.rev !degrees); + + Printf.fprintf oc "\n"; + close_out oc + + + +let _ = + let degrees = ref [] in + let maxa = ref 0.1 in + for degree = 1 to 20 do + for nprobes = 1 to 5 do + let filename = Printf.sprintf "uniform/liar_measured_%dx%d.txt" + degree nprobes in + if Sys.file_exists filename then + let _, _, maxs = on_file filename in + maxa := max !maxa maxs.(1); + degrees := (degree, nprobes) :: !degrees + done; + done; + + let maxa = 1.3 *. !maxa in + let oc = open_out "liars_measure.plot" in + Printf.fprintf oc " + set xtics (\"5\" 7200, \"10\" 14400, \"15\" 21600, \"20\" 28800) +set out 'liars_measure.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out 'liars_measure.eps' +set yrange [0:%.1f] +set xrange [0:%d] +set ylabel 'Network Availability' +set xlabel 'Time (days)' + +set data style lines + + plot \"uniform/liar_real.txt\" using ($1):($2) title 'real (without liars)'" + maxa nminutes; + + List.iter (fun (degree, nprobes) -> + Printf.fprintf oc + ", \"uniform/liar_measured_%dx%d.txt\" using ($1):($2) title 'measured (%d challenges, %d observers)'" degree nprobes nprobes degree + ) !degrees; + Printf.fprintf oc "\n"; + close_out oc + +let _ = + File.of_string (Filename2.of_string "Makefile") "FIGURES=availability.eps max_distance_per_round.eps peers_per_round.eps mean_avail_distance.eps connections.eps sessions.eps ask_root_msgs.eps all_availability.eps all_error_avail.eps error_avail.eps ping_error_avail.eps liars_measure.eps + +#availpolicies.eps + +usetrace: $(FIGURES) $(FIGURES:.eps=.plot) usetrace.pdf + +availability.plot max_distance_per_round.plot peers_per_round.plot mean_avail_distance.plot connections.plot sessions.plot:uniform/availability.txt uniform/max_distance_per_round.txt uniform/peers_per_round.txt uniform/connections.txt uniform/sessions.txt + doplots + +mean_avail_distance.eps: mean_avail_distance.plot uniform/mean_avail_distance1.txt + gnuplot < mean_avail_distance.plot + +ping_error_avail.eps: uniform/error_avail.txt ping_error_avail.plot uniform/ping_error_avail_10.txt + gnuplot < ping_error_avail.plot + +liars_measure.eps: liars_measure.plot uniform/liar_real.txt + gnuplot < liars_measure.plot + +all_availability.eps: uniform/availability_0.txt all_availability.plot + gnuplot < all_availability.plot + +all_error_avail.eps: uniform/error_avail_0.txt all_error_avail.plot + gnuplot < all_error_avail.plot + +all_lost_tickets.eps: uniform/lost_tickets_0.txt all_lost_tickets.plot + gnuplot < all_lost_tickets.plot + +%.eps: %.plot uniform/%.txt + gnuplot < $*.plot + +%.pdf: %.eps + epstopdf $*.eps + +usetrace.pdf: $(FIGURES:.eps=.pdf) usetrace.tex + pdflatex usetrace.tex +" + +let _ = + File.of_string (Filename2.of_string "usetrace.tex") + "\\documentclass[11pt,a4paper]{article} + +\\usepackage{epsfig} + +\\newcommand{\\figurebox}[1]{#1} + +\\def\\figheader{fig:} + +\\newcommand{\\psfigure}[3]{ % {scale}{filename=label}{caption} + \\begin{figure}[t]\\begin{center}% + \\epsfig{file=#2,width=#1\\hsize}% + \\begin{quote}\\let\\normalsize\\small\\caption{#3\\label{\\figheader#2}}\\end{quote}% + \\end{center} + \\vspace{-0.8cm}% +\\end{figure}} + +\\newcommand{\\psfigureR}[3]{ % {scale}{filename=label}{caption} + \\begin{figure}[t]\\begin{center}% + \\epsfig{file=#2,width=#1\\hsize,angle=-90}% + \\begin{quote}\\let\\normalsize\\small\\caption{#3\\label{\\figheader#2}}\\end{quote}% + \\end{center} + \\vspace{-0.8cm}% +\\end{figure}} + +\\begin{document} + +\\input{data.tex} + +\\section*{Simulation Parameters} + +Here are the parameters used to compute the simulation: + +\\begin{tabular}{|l|l|} +\\hline +Network size: &\\npeers peers\\\\ +Length: &\\nminutes minutes (\\ndays days)\\\\ +Availability: & Uniform Distribution in [0.1;1.0]\\\\ +Deconnections per day:& Uniform Distribution in [1;10]\\\\ +Timezones:& Uniform Distribution in [0;12]\\\\ +\\hline +\\end{tabular}\\\\ + + For each peer, we randomly choose an availability and a number of +disconnections per day. We then compute its probabilities of coming online +and offline using Markov Chains. We use these probabilities in the +simulation. + + Note that the uniform distribution of availabilities is not standard in +peer-to-peer systems, but here, we want to show that the measured +availability is not different from the real availability, so the +distribution of availabilities does not matter. We will check later that +the mesh behaves correctly with a powerlaw, but the mesh is not the focus +of this paper... + + Timezones are used to obtain a diurnal pattern: during day, peers have +twice their normal probability of coming online and half their normal +probability of going offline. + +\\section*{Simulation Results} + +Here are some values obtained during the simulation: + +\\begin{tabular}{|l|l|} +\\hline +Number of Sessions : &\\nsessions sessions\\\\ +\\hline +\\end{tabular} + +\\section*{Simulation Mesh} + + We simulate a network of peers connected in a mesh around a server. The +server diffuses tickets every hours to measure the availability of peers. + + In the current simulation, the mesh protocol is the following: the server +has a degree of 10 children, and each peer has a degree of 5 children and 5 +parents. To connect to the mesh, a peer first queries the server, which +replies with a list of its children. The peer then queries the children. +Every children either accepts the peer as a child, or send a random of its +children. The process iterates until the peer is connected to 5 different +parents. + + We take the following (local) decisions to improve the system: +\\begin{itemize} +\\item At every round, one a peer has a free child slot, it chooses among +all the candidates who queried it during the round (one minute) the one +with the best measured availability. +\\item A peer disconnects its children which are at the same distance from +the server as it. (hey, this is not a local property ! we should only +do it after a ticket diffusion or during the query !) +\\end{itemize} + + Every round in the simulation takes one minute. From a communication +point of view, it allows us to assume some timeout on messages that allows +detection of peer disconnection (TCP keepalive is 30 seconds). + +\\begin{center} + +\\psfigureR{1.5}{sessions}{CDF of Sessions lengths. Note that the median +session length is around two hours. It does not follow a powerlaw, but we +don't really.} + +\\psfigureR{1.5}{max_distance_per_round}{Maximal distance to the server over + time. Note that the diameter of the network is not too high.} + + \\psfigureR{1.5}{peers_per_round}{Number of peers online over time. Note +that since the timezones of peers are only on 12 hours, we observe some +diurnal pattern that we would not observe if the distribution was over 24 +hours.} + +\\psfigureR{1.5}{connections}{Time spent between the beginning of a peer +session and the connection to its first parent. Only in some rare cases, it is +above 7 minutes. Since in our system, we focus on long session times +(median session length is two hours), this delay is neglectible.} + +\\psfigureR{1.5}{mean_avail_distance}{Mean Availability of Connected Peers +depending on their distance to the server. It shows that peers at distance +1 from the server have a much better availability, and so on...} + +% \\psfigureR{1.5}{availpolicies}{} + + \\psfigureR{1.5}{ask_root_msgs}{The number of AskRoot messages sent +per minute to the server in our mesh.} + + +\\psfigureR{1.5}{availability}{Measured availability compared to real +availability. Note that the difference between the real availability and +the availability measured using tickets is very close.} + \\psfigureR{1.5}{error_avail}{} + + \\psfigureR{1.5}{all_availability}{} + \\psfigureR{1.5}{all_error_avail}{} + + \\psfigureR{1.5}{ping_error_avail}{} + \\psfigureR{1.5}{liars_measure}{} + +\\end{center} +\\end{document} +" + + + + + +let _ = + let oc = open_out "data.tex" in + + Printf.fprintf oc "\\def\\npeers{%d }\n" npeers; + Printf.fprintf oc "\\def\\nminutes{%d }\n" nminutes; + Printf.fprintf oc "\\def\\ndays{%d }\n" (nminutes / 24 / 60); + Printf.fprintf oc "\\def\\nsessions{%d }\n" nsessions; + + close_out oc +
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/genrand.ml b/sources/fabrice/pacemaker/genrand.ml new file mode 100644 index 0000000..718762f --- /dev/null +++ b/sources/fabrice/pacemaker/genrand.ml @@ -0,0 +1,27 @@ +open BigEndian + +let _ = + Printf.printf "genrand <filename> <nrandom>\n%!" + +let filename = Sys.argv.(1) +let n = Int64.of_string Sys.argv.(2) + +let block = 4096 +let blockL = Int64.of_int block + +let _ = + let bound = 1 lsl 29 in + let oc = open_out filename in + let s = String.create (4 * block) in + let nblocks = Int64.to_int (Int64.div n blockL) + 1 in + for i = 1 to nblocks do + for x = 0 to block - 1 do + + str_int s (x*4) (Random.int bound) + + done; + output_string oc s + + done; + close_out oc +
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/gentrace.ml b/sources/fabrice/pacemaker/gentrace.ml new file mode 100644 index 0000000..be75c4e --- /dev/null +++ b/sources/fabrice/pacemaker/gentrace.ml @@ -0,0 +1,141 @@ +open SimulTypes +open SimulTrace + +let day = 60 * 24 + +type peer2 = { + lambda : float; + mu : float; + decs : int; + mutable timezone : int; + + } + +let _ = + if Array.length Sys.argv < 4 then begin + Printf.printf "./gentrace trace_name npeers ndays\n"; + Printf.printf "ERROR: bad number of arguments\n"; + exit 2 + end + +let trace = Sys.argv.(1) +let npeers = int_of_string Sys.argv.(2) +let ndays = int_of_string Sys.argv.(3) +let nrounds = day * ndays +let exponential = ref ( + Array.length Sys.argv = 5 && Sys.argv.(4) = "exp") + +let _ = Random.self_init () + +let oc = open_out trace + +let _ = + trace_output oc (Peers npeers); + trace_output oc (Days (ndays, day)); + if !exponential then + trace_output oc Exponential; + () + + +let peers = Array.init npeers (fun i -> + + let avail = Random.int 900000 in + let decs = 1 + Random.int 10 in + let timezone = Random.int (60 * 12) in + + let x = float_of_int avail /. 900000. in + + let avail = (if !exponential then + max 0.02 (min 1. (exp(1. -. log(2. +. 65. *. x)))) + else + 0.02 +. 0.98 *. x + ) + in + trace_output oc (Peer (i, avail, Printf.sprintf "%d %d" decs timezone)); + + let lambda = float_of_int decs /. (60. *. 24.) in + let mu = avail *. lambda /. (1. -. avail) in + let p2 = { + decs = decs; + lambda = lambda; + mu = mu; + timezone = timezone; + } in + let p = { + avail = avail; + i = i; + descr = ""; + session = 0; + day = true; + state = OFF; + real_avail = 0; + real_decs = 0; + } in + p,p2 + ) + +let peer_round round p p2 = + if p.state = ON then + p.real_avail <- p.real_avail + 1; + + if round = p2.timezone then begin + p.day <- not p.day; + p2.timezone <- p2.timezone + 12 * 60; + end; + + let x = float_of_int (Random.int 900000) /. 1000000. in + if p.state = ON then begin + let lambda = if p.day then p2.lambda /. 2. else p2.lambda *. 2. in + if x < lambda then begin + p.state <- OFF; + p.real_decs <- p.real_decs + 1; + trace_output oc (Off p.i); + end + end + else + begin + let mu = if p.day then p2.mu *. 2. else p2.mu /. 2. in + if x < mu then begin + p.state <- ON; + trace_output oc (On p.i); + end + end + +let _ = + for round = 0 to nrounds - 1 do + trace_output oc (Round round); +(* + let daytime = round mod day in + utput_string oc (Printf.sprintf "Round %d %d %02d:%02d\n" round + (round / day) (daytime / 60) (daytime mod 60) + ); *) + (* Printf.printf "Round %d/%d\n%!" round nrounds; *) + for x = 0 to npeers - 1 do + let p,p2 = peers.(x) in + peer_round round p p2 + done + done + +let _ = + Array.iter (fun (p,p2) -> + if p.state = ON then begin + p.real_decs <- p.real_decs + 1; + p.state <- OFF; + end; + ) peers + +(* +let _ = + Array.iteri (fun i p -> + Printf.printf "%d: %.3f --> %.3f (%d: %.3f)\n" i p.avail + (float_of_int p.real_avail /. float_of_int nrounds) + p.decs + ((float_of_int p.real_avail /. float_of_int p.real_decs) /. 60. ) + ) peers + *) + +let _ = + trace_output oc End; + close_out oc + +
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/liartrace.ml b/sources/fabrice/pacemaker/liartrace.ml new file mode 100644 index 0000000..e227dc0 --- /dev/null +++ b/sources/fabrice/pacemaker/liartrace.ml @@ -0,0 +1,308 @@ + +open Sets + +open SimulTrace +open SimulTypes +open SimulGraphes + + + + let day = 60 * 24 +(* +Every peer is responsible to "observe" $degree$ other peers in the system. +Such peers are usually peers with which it is exchanging some resources. + +TODO: currently, a peer has the knowledge of when another it is observing +is online when testing the probability to send a challenge. We should change +that, so that when a peer is online, the probability of sending a challenge +is independant from the status of the observed peer. + +*) + +type observer = { + mutable observer : int; + mutable observed : int; + mutable next : int; + } + +type peer2 = { + mutable observers : observer IntMap.t; + mutable observing : observer IntMap.t; + mutable availabilities : int array; + mutable liar : float; (* liar by how much, not liar = 1. ? *) + mutable excluded : bool; + mutable is_liar : bool; + } + +let probes = ref 1 +let degree = ref 5 +let nliars = ref 5 +let anon_args = ref [ Sys.argv.(0) ] +let ndays = ref 0 +let subdir = ref None + +let _ = + Printf.printf "Version 2.0\n%!"; + Arg.parse [ + "-subdir", Arg.String (fun s -> + subdir := Some s), "<subdir> : set subdir for data files"; + "-dist", Arg.Set print_distribution, " : print distribution"; + "-ndays", Arg.Int ((:=) ndays), " <n> : number of days"; + "-degree", Arg.Int ((:=)degree), " <n> : number of observers"; + "-nliars", Arg.Int ((:=)nliars), " <n> : number of liars(%)"; + "-probes", Arg.Int ((:=)probes), " <n> : number of challenges"; + ] + (fun t -> anon_args := t :: !anon_args) "" + + + +let subdir = + match !subdir with + None -> failwith "You must specify a subdirectory for data files" + | Some dir -> + Unix2.safe_mkdir (Filename2.of_string dir); + dir +let nliars = !nliars +let degree = !degree +let probes = !probes + +let argv = Array.of_list (List.rev !anon_args) +let trace = argv.(1) + + +let _ = + if trace = "" then + failwith "You must at least specify the name of the trace file"; + Random.self_init () + +let peers, nrounds, do_round = trace_read trace + +let nrounds = + if !ndays <> 0 then + day * !ndays + else nrounds + +let npeers = Array.length peers + + +let nrounds = + if Array.length argv = 3 then + day * int_of_string argv.(2) + else nrounds + +let peers2 = Array.init npeers (fun i -> + let p = { + observers = IntMap.empty; + observing = IntMap.empty; + availabilities = [| 0; 0 |]; + liar = 1.0; + excluded = false; + is_liar = false; + } in + + p) + +let npeersf = float_of_int npeers + +let _ = Printf.printf "Find observers\n%!" + +let rec find_observer i p = + let x = Random.int npeers in + let op2 = peers2.(x) in + if x = i || + op2.excluded || + IntMap.mem x p.observers then find_observer i p + else + let ob = { + observer = x; + observed = i; + next = 7200; (* 5 days *) + } in + p.observers <- IntMap.add x ob p.observers; + op2.observing <- IntMap.add i ob op2.observing + + +let _ = + for i = 0 to npeers - 1 do + + let p = peers2.(i) in + for x = 1 to degree do + find_observer i p + done + + done + +let rec find_liar x = + if x = npeers then () else + let n = Random.int npeers in + let p2 = peers2.(n) in + if p2.liar > 1.001 then find_liar (x+1) else + let p = peers.(n) in + let avail = p.avail in + if avail > 0.95 then find_liar (x+1) else + let max_lying = 1. /. avail in + let lying = Random.float max_lying in + p2.liar <- 1.01 +. lying; + p2.is_liar <- true + +let _ = Printf.printf "Find liars\n%!" + +let _ = (* 5% of liars ? *) + let liars = Printf.sprintf "liars_%d.dat" nliars in + if Sys.file_exists liars then + let ic = open_in liars in + (try + while true do + let line = input_line ic in + match String2.split line ' ' with + [num; liar] -> + peers2.(int_of_string num).liar <- float_of_string liar; + peers2.(int_of_string num).is_liar <- true + + | _ -> assert false + done + with End_of_file -> ()); + close_in ic + else + for i = 1 to npeers * nliars / 100 do + find_liar 0 + done; + let oc = open_out (Printf.sprintf "liars_%d.dat" nliars) in + for i = 0 to npeers - 1 do + if peers2.(i).is_liar then + Printf.fprintf oc "%d %f\n" i peers2.(i).liar + done; + close_out oc + +let _ = Printf.printf "Find liars...done\n%!" + +let liars = Array.create nrounds 0 +let measured_availabilities = Array.create nrounds 0. +let real_availabilities = Array.create nrounds 0. + +let measured_availabilitiesE = Array.create nrounds 0. +let real_availabilitiesE = Array.create nrounds 0. + +let _ = + let rec iter_observers p list = + match list with + [] -> () + | o :: tail -> + let po = peers.(o) in + if po.state = ON then + p.availabilities.(1) <- p.availabilities.(1) + 1 + else + iter_observers p tail + in + + for round = 0 to nrounds - 1 do + do_round round; + + let ticket = 0 = (round+59) mod 60 in + + for i = 0 to npeers - 1 do + let p = peers.(i) in + let p2 = peers2.(i) in + if p.state = ON then begin + p2.availabilities.(0) <- p2.availabilities.(0) + 1; + if ticket then + p2.availabilities.(1) <- p2.availabilities.(1) + 60; + if not p2.excluded then + let to_replace = ref [] in + IntMap.iter (fun o ob -> + let p2 = peers2.(o) in + if p2.excluded then + to_replace := o :: !to_replace + ) p2.observers; + + List.iter (fun o -> + p2.observers <- IntMap.remove o p2.observers; + let op2 = peers2.(o) in + op2.observing <- IntMap.remove i op2.observing; + find_observer i p2 + ) !to_replace; + + IntMap.iter (fun _ ob -> + let p = peers.(ob.observed) in + let p2 = peers2.(ob.observed) in + if (not p2.excluded) && p.state = ON && ob.next <= round && + Random.int 180 = 0 + then begin + ob.next <- round + 24 * 60; + + for x = 1 to probes do + let y = Random.float p2.liar in + if y > 1.0 then begin + Printf.printf "Probe failed for %d\n%!" i; + p2.excluded <- true; + assert (p2.is_liar ) + end + done + + end + ) p2.observing + + end + done; + + if round > 20 then + let measured_availE = ref 0. in + let real_availE = ref 0. in + let measured_avail = ref 0. in + let real_avail = ref 0. in + for i = 0 to npeers - 1 do +(* let p = peers.(i) in *) + let p2 = peers2.(i) in + assert (p2.liar >= 0.); + assert (p2.availabilities.(0) >= 0); + assert (p2.availabilities.(1) >= 0); + + measured_availE := !measured_availE +. + ( p2.liar *. + (float_of_int p2.availabilities.(1)) ); + if not p2.is_liar then + real_availE := !real_availE +. + float_of_int p2.availabilities.(0); + + if (not p2.excluded) then begin + if p2.liar > 1.001 then + liars.(round) <- liars.(round) + 1; + + measured_avail := !measured_avail +. + ( p2.liar *. + (float_of_int p2.availabilities.(1)) ); + real_avail := !real_avail +. + float_of_int p2.availabilities.(0) + end + done; + let roundf = float_of_int (1+round) *. npeersf in + let measured_avail = !measured_avail /. roundf in + let real_avail = !real_avail /. roundf in + measured_availabilities.(round) <- measured_avail; + real_availabilities.(round) <- real_avail; + + let measured_availE = !measured_availE /. roundf in + let real_availE = !real_availE /. roundf in + measured_availabilitiesE.(round) <- measured_availE; + real_availabilitiesE.(round) <- real_availE; + done; + + value_per_time string_of_float + (Printf.sprintf "%s/liar_measured_%dx%d" subdir degree probes) + measured_availabilities "avail"; + + value_per_time string_of_float + (Printf.sprintf "%s/liar_real_%dx%d" subdir degree probes) + real_availabilities "avail"; + + value_per_time string_of_float + (Printf.sprintf "%s/liar_measuredE_%dx%d" subdir degree probes) + measured_availabilitiesE "avail"; + + value_per_time string_of_float + (Printf.sprintf "%s/liar_real" subdir) + real_availabilitiesE "avail"; + + value_per_time string_of_int + (Printf.sprintf "%s/liar_number_%dx%d" subdir degree probes) liars "avail"; +
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/notes.txt b/sources/fabrice/pacemaker/notes.txt new file mode 100644 index 0000000..fb8bdc8 --- /dev/null +++ b/sources/fabrice/pacemaker/notes.txt @@ -0,0 +1,15 @@ + peerolyse:~/devel/onzego% time ./research/p2p_avail/gentrace trace_10000x1000_1 10000 1000 +./research/p2p_avail/gentrace trace_10000x1000_1 10000 1000 1183.25s user 2.83s system 99% cpu 19:46.89 total + + + + peerolyse:~/articles/p2p_avail_metro/simulation% time gentrace trace_500x365_1 500 365 +gentrace trace_500x365_1 500 365 22.19s user 0.05s system 99% cpu 22.267 total + + +In the current implementation of gentrace, all the timezones are in the +first 12 hours. + + +To obtain big graphs, don't use -Tps, but Tjpg with display + dot -Tjpg graph_000000.dot -o graph.jpg diff --git a/sources/fabrice/pacemaker/overnetTrace.ml b/sources/fabrice/pacemaker/overnetTrace.ml new file mode 100644 index 0000000..c84bf20 --- /dev/null +++ b/sources/fabrice/pacemaker/overnetTrace.ml @@ -0,0 +1,130 @@ +open Sets + +open SimulTypes +open SimulTrace + +let input_line ic = String.lowercase (input_line ic) + +let ts = ref 1042666697 + +let npeers = 3000 + +let peers = Array.create npeers false +let avail = Array.create npeers 0 + +let counter = ref 0 +let map = ref StringMap.empty + +let add_hosts = ref true + +let blacklist = ref StringSet.empty + +let find_host name = + try + StringMap.find name !map + with Not_found -> + if !add_hosts && not (StringSet.mem name !blacklist) then + let id = !counter in + Printf.printf "New host %d\n%!" !counter; + map := StringMap.add name id !map; + incr counter; + id + else + -1 + +let f round oc i = + Printf.printf "CURRENT: %d\n%!" i; + let ic = open_in (Printf.sprintf "pd_%d" i) in + + let line = input_line ic in + let new_ts = + match String2.split_simplify line ' ' with + "#" :: "timestamp" :: "of" :: "probe:" :: new_ts :: [] -> + int_of_string new_ts + | _ -> assert false + in + + let changes = Array.create 20 [] in + begin try + while true do + let line = input_line ic in + match String2.split_simplify line '\t' with + [name; ip; ping] -> + let id = find_host name in + if id >= 0 then + let status = ping = "1" in + if peers.(id) <> status then + let n = Random.int 20 in + changes.(n) <- id :: changes.(n) + | [] -> () + | _ -> + Printf.printf "Unexpceted line [%s]\n" + (String.escaped line); + assert false + done + with + | End_of_file -> + close_in ic + end; + ts := new_ts; + + for j = 0 to 19 do + trace_output oc (Round !round); + + List.iter (fun p -> + let status = peers.(p) in + peers.(p) <- not status; + trace_output oc (if status then + Off p + else + On p) + ) changes.(j); + + for k = 0 to npeers - 1 do + if peers.(k) then + avail.(k) <- avail.(k) + 1 + done; + + incr round; + done + + +let nremoved = ref 0 + +let _ = + + if Sys.file_exists "blacklist" then + begin + let ic = open_in "blacklist" in + try + while true do + let name = input_line ic in + blacklist := StringSet.add name !blacklist; + incr nremoved + done + with End_of_file -> close_in ic + end; + + let oc = open_out "overnet" in + trace_output oc (Peers (npeers- !nremoved)); + trace_output oc (Days (7,24*60)); + for i = 1 to npeers - !nremoved do + trace_output oc (Peer (i-1, 0., "overnet")); + done; + let round = ref 0 in + f round oc 0; +(* add_hosts := false; *) + + for i = 1 to 503 do + f round oc i + done; + Printf.printf "NUMBER OF HOSTS: %d\n%!" !counter; + trace_output oc End; + + close_out oc; + + let oc = open_out "blacklist" in + StringMap.iter (fun name id -> + if avail.(id) < 1 then + Printf.fprintf oc "%s\n" name) !map; + close_out oc; diff --git a/sources/fabrice/pacemaker/pMArgs.ml b/sources/fabrice/pacemaker/pMArgs.ml new file mode 100644 index 0000000..6b0162d --- /dev/null +++ b/sources/fabrice/pacemaker/pMArgs.ml @@ -0,0 +1,87 @@ +open SafeCaml +open Pervasives + +open Checksum +open Sets +open Options + +open NetP2P + + +open PMTypes +open PMNetwork +open PMOptions + +(* +let uid = ref (Sha1.random ()) +let port = ref (1024 + Random.int 64000) +let run_as_server = ref false +let servers = ref [] +let ndegree = ref 5 + *) + + +let binary_hash = Sha1.string (File.to_string binary_filename) + +let binary_mtime = Int64.of_float (Unix.stat binary_filename).Unix.st_mtime + +let new_binary = ref false + +let arg_help = "pacemaker: run a pacemaker daemon" +let arg_list = [ + "-new_binary", Arg.Set new_binary, " : export new binary"; + "-port", Arg.Int ((=:=) my_port), " <port> : bind on port"; + "-uid", Arg.String (fun s -> + uid =:= Sha1.of_string s), " <uid> : use as uid"; + "-server", Arg.Unit (fun _ -> + run_as_server =:= true), " : run as a server"; + "-master", Arg.Unit (fun _ -> + run_as_master =:= true), " : run as a server"; + "-s", Arg.String (fun s -> + try + match String.split_simplify s ':' with + [sha1; ip; port ] -> + let x = (Sha1.of_string sha1, + Ip.of_string ip, int_of_string port) in + if not (List.mem x !!servers) then + servers =:= x :: !!servers + | _ -> assert false + with _ -> + failwith (Printf.sprintf "[-s %s] is not correctly formatted" s) + ), " <uid:ip:port> : info on server"; + ] + +let _ = + Arg.parse arg_list (fun _ -> Arg.usage arg_list arg_help) arg_help; + if Array.length Sys.argv <> 1 then must_save_options (); + + + + PMOptions.save_options () + +(* + +let nservers = ref 0 +let servers_map = ref Sha1Map.empty + +let servers_list = List.map (fun (s, sha1, ip, port) -> + let p = PaceMakerNetwork.new_peer sha1 (Some (ip, port)) in + incr nservers; + p.peer_type <- PEER_SERVER; + servers_map := Sha1Map.add sha1 p !servers_map; + s, p + ) !servers +let nservers = !nservers +let servers_map = !servers_map +let servers_tab = Array.of_list servers_list + +let ndegree = !ndegree +let parents = Array.create ndegree (None : peer_info option) +let children = Array.create ndegree (None : peer_info option) +let candidates = ref ([] : peer_info list) + +let dir = Filename.of_string "/home/irisa_pacemaker/planetlab/pacemaker" + +let heartbeats = (Hashtbl.create 2047 : (HeartBeatMsg.msg, bool) Hashtbl.t) + + *) diff --git a/sources/fabrice/pacemaker/pMConst.ml b/sources/fabrice/pacemaker/pMConst.ml new file mode 100644 index 0000000..c898bbd --- /dev/null +++ b/sources/fabrice/pacemaker/pMConst.ml @@ -0,0 +1,210 @@ +open SafeCaml +open Pervasives + +open Checksum +open Sets +open Options + + +let max_distance = 10 + +let config_dir = Filename.of_string "/home/irisa_pacemaker/pacemaker" + + +let allpeers = [| + Ip.of_string "12.108.127.137", 7000, Sha1.of_string "NSGWQIWXMWB33ZK7MK5X67ADJ4Q62FCT"; + Ip.of_string "204.85.191.10", 7000, Sha1.of_string "E2IS7NA4KMJD4VRPAWL6XWHQ4Y5OMZX7"; + Ip.of_string "128.135.11.152", 7000, Sha1.of_string "2FPG3B6KWSKWGKL5DAOR6GJ73PT4X3NS"; + Ip.of_string "169.229.50.5", 7000, Sha1.of_string "B2JR7FL6FOOXPNNYCRCQ7DJKPDXFTHH6"; + Ip.of_string "195.37.16.97", 7000, Sha1.of_string "FHGIY3HVTO3YTTJ7JEMCWB4KZ7P564LE"; + Ip.of_string "219.243.201.17", 7000, Sha1.of_string "2PT37PP6LTKKHQTAEMENJECMSDGCLFJA"; + Ip.of_string "195.83.212.155", 7001, Sha1.of_string "KLQCLYRUP3NMDOH3LNAEPX3L4QBGA6HQ"; + Ip.of_string "195.83.212.159", 7001, Sha1.of_string "JZGBBR2VOSAZFVGQGBSAQ4E6MN6QMNWQ"; + Ip.of_string "195.83.212.149", 7001, Sha1.of_string "V7T52VJ7WIQWP4T5UXH2E7XLUJXDJ6C7"; + Ip.of_string "138.232.66.194", 7000, Sha1.of_string "XCW66RLNEJLR5MX7URUV2LIXJEKGVO3N"; + Ip.of_string "143.205.172.11", 7000, Sha1.of_string "SH6RMI4K76JRYORHZTAVMPHZXBR7H2AK"; + Ip.of_string "131.130.32.152", 7000, Sha1.of_string "X7VL4KLFQIL3WEVSGTOG45E2PS4R3C4U"; + Ip.of_string "220.245.140.196", 0, Sha1.of_string "QVB26DD524S5TZGJYI2RVW6BPQWBKHZZ"; + Ip.of_string "193.191.148.227", 7000, Sha1.of_string "S5ESW43NQRXEJGYPXUP5NVMNOTD46AGQ"; + Ip.of_string "200.133.215.141", 7000, Sha1.of_string "F22Q7LQUHDFEJRMOBC4PVD2XAEZPTAZL"; + Ip.of_string "200.19.159.34", 7000, Sha1.of_string "GLWIVJOV6CKMJV7WE6ZNXVXI3XNLB3EN"; + Ip.of_string "200.132.0.70", 7000, Sha1.of_string "WXQNGCNAVOQ7KYFYB7NLA3JXPUVRPGBV"; + Ip.of_string "143.107.111.194", 7000, Sha1.of_string "2SMNW43FH3XJUAZZQTOALFZCIQ4IEGDY"; + Ip.of_string "206.12.16.154", 7000, Sha1.of_string "SYMW3EMUPXT6IEEGPE2LEFUVQ3GYGMAJ"; + Ip.of_string "198.163.152.229", 7000, Sha1.of_string "EXKG2MWZNKRVSNZEG6V4BW3JA3SD5HD7"; + Ip.of_string "205.211.183.2", 7000, Sha1.of_string "MVDJCNAKPQA6PUAMLCSSVTVG4FUOAUT6"; + Ip.of_string "128.233.252.11", 7000, Sha1.of_string "FXSJW44QXO24PU7V5HE2BLHVTZC62XV3"; + Ip.of_string "142.150.238.12", 7000, Sha1.of_string "ENMWFEDPAXV5LF24HBFLJJM2FXZYES6I"; + Ip.of_string "142.150.3.77", 7000, Sha1.of_string "GHWQKGC7E3WWOGQCR6PRZ7DEST2SELQP"; + Ip.of_string "142.104.21.241", 7000, Sha1.of_string "3KYC6PICAZ3EWAMV2RKS47XKRDUEP6DJ"; + Ip.of_string "192.33.210.16", 7000, Sha1.of_string "FMMFTYOPXF6PGLHMSM7L7Y63E4NMKTYZ"; + Ip.of_string "192.33.90.66", 7000, Sha1.of_string "7AYGTH42HNIFS2K44EXJVQISSJRSDV3B"; + Ip.of_string "130.92.70.251", 7000, Sha1.of_string "XBSITJEGFPOIFAYKGWBP2VH2YH6WDB56"; + Ip.of_string "192.42.43.22", 7000, Sha1.of_string "7UCWZIILOIWRRXB7C7L52IDRBUOENYS3"; + Ip.of_string "192.41.135.218", 7000, Sha1.of_string "H43G5MZW2FA3Y3A6KY7T6AQD33WMCW5J"; + Ip.of_string "219.243.206.36", 7000, Sha1.of_string "KXWDRWEZS4H2ZJGAHH5GFJ7VDVGRYQ4V"; + Ip.of_string "216.98.102.29", 7000, Sha1.of_string "RCZHNJUBYJRVNYJUTD7A3CI5H6RTCMVK"; + Ip.of_string "192.6.10.50", 7000, Sha1.of_string "AJDEUX57HUFG3BQQ4BR43MBL2KJPQUJ4"; + Ip.of_string "198.175.112.104", 7000, Sha1.of_string "PQQLV434OTWPM65LDLMMAA2T2KTIDUGX"; + Ip.of_string "63.64.153.82", 7000, Sha1.of_string "3T7GFCLFWYZOIAZ2F2NCT5KHHL3LEUA4"; + Ip.of_string "138.15.10.55", 7000, Sha1.of_string "TA6P3PYG3JYL2NDVRZQZV2HVL7UE7U4P"; + Ip.of_string "194.42.17.123", 7000, Sha1.of_string "YJAIZCFOM7M2UDTY2ZEZJ5VSL7RLLE6X"; + Ip.of_string "195.113.161.82", 7000, Sha1.of_string "G2EJIM7M34VKVWNKM3LA24EH4A3YR62L"; + Ip.of_string "147.229.10.250", 7000, Sha1.of_string "3FMD5HNWLMQSKVSX5MIK343PUUXTJ4ZD"; + Ip.of_string "131.246.191.42", 7000, Sha1.of_string "HQCCDIDJHNUM5ODQQ5RHEJMDIN5EBVZE"; + Ip.of_string "193.174.67.186", 7000, Sha1.of_string "JMMS2LJBXDYS7SRPB7G4U4CUI4HU7AFG"; + Ip.of_string "141.22.213.35", 7000, Sha1.of_string "LVLF7F2JXSSWNXKRDV4T4JIBRLTKCYBA"; + Ip.of_string "141.20.103.210", 7000, Sha1.of_string "Q7CAAV6A5VAIEXRMHHTTP75GNSS5CSN7"; + Ip.of_string "212.201.44.81", 7000, Sha1.of_string "2SQGMZR2WOXH7FHXT53B5HCYPEXVKNER"; + Ip.of_string "139.19.142.1", 7000, Sha1.of_string "RI6PV5M6FGGP27O3WC7OAKC6A2UZYAL6"; + Ip.of_string "137.226.138.154", 7000, Sha1.of_string "GPA454N4YE4F7UYJDYFB6ST22CGJ3O3Q"; + Ip.of_string "130.83.166.198", 7000, Sha1.of_string "3G5ZMOSM2QC6XHMPILAWPU2Y2V6SDZVK"; + Ip.of_string "141.76.45.17", 7000, Sha1.of_string "SH5B33PC7AYVX6X2235DGV7UXROWRT5K"; + Ip.of_string "141.24.249.129", 7000, Sha1.of_string "55SQEF3S5S6UH7D2FUSB24ORVTELVN32"; + Ip.of_string "141.24.33.161", 7000, Sha1.of_string "JZDFMXEZUANTTH26BUXIHQWI5SNBKEXD"; + Ip.of_string "138.246.99.249", 7000, Sha1.of_string "TEXD2OP47VVJFGWCWXS5G5GYIGU5B7QD"; + Ip.of_string "141.13.16.201", 7000, Sha1.of_string "7HCOSHF5Z7PB6E55NYAUW2MY4BBNO6HE"; + Ip.of_string "131.188.44.101", 7000, Sha1.of_string "X3BG3LCC5U52BH77NP6WAEYXMT4WEEN3"; + Ip.of_string "132.252.152.193", 7000, Sha1.of_string "6OTJGMWB3ENELUVFWI47WOCXBDRGDZKJ"; + Ip.of_string "130.75.87.83", 7000, Sha1.of_string "NOTLBXT6CWJCPMWQO3MNE63HG6SJWKPJ"; + Ip.of_string "193.196.39.9", 7000, Sha1.of_string "ZJLPBI6XUT3MEYK5QRKGRL6V6AJHPM2W"; + Ip.of_string "131.246.19.201", 7000, Sha1.of_string "373A35MFSKLYV2TBQRVKZUULWLL56ZXP"; + Ip.of_string "134.34.246.5", 7000, Sha1.of_string "PG26ZIAJFOQIUVTDXRI3ANHWR7MLBDD3"; + Ip.of_string "129.69.210.96", 7000, Sha1.of_string "H7VMU27XPXMHG3QNV3KXJOJTTJSUFOO2"; + Ip.of_string "134.2.172.253", 7000, Sha1.of_string "HW2PGBT6GFSGFW4IPI45E33BL7KMHBBZ"; + Ip.of_string "132.187.230.1", 7000, Sha1.of_string "L4CY2A7BQ23IKMU5AQTGYSIDPRZURBPQ"; + Ip.of_string "130.73.142.87", 7000, Sha1.of_string "6IFADLQG3NKMSTV5VWF73BS45ZFMBWUF"; + Ip.of_string "149.169.227.129", 7000, Sha1.of_string "M5Z2ZDQIKQSTRDA2KISLY2EJOYU4WFEF"; + Ip.of_string "198.7.242.43", 7000, Sha1.of_string "RPA3GHHEJFU3G5NSV5P24KUW5H4E62BZ"; + Ip.of_string "204.8.155.226", 7000, Sha1.of_string "UVBSZKIAYAPVTRYEQWDEYCRV5BZ3J4UN"; + Ip.of_string "128.187.223.211", 7000, Sha1.of_string "GJWQSHJJI7V2TBYJPRP6LMPLON6KYR5D"; + Ip.of_string "131.215.45.71", 7000, Sha1.of_string "ZJA556UIRAAUFG3JOPO55VS6EBX6CKPX"; + Ip.of_string "128.2.223.63", 7000, Sha1.of_string "NPPTGWL4M2WDRQRK65E4VM4M62IJHWIY"; + Ip.of_string "128.84.154.49", 7000, Sha1.of_string "ACBEXODFZXAZPM6VWK6K76BSMLOZEZF6"; + Ip.of_string "152.3.138.1", 7000, Sha1.of_string "H5V2WVFLCU2QQZKQEBKGTJQHMKRWRZ6D"; + Ip.of_string "170.140.119.69", 7000, Sha1.of_string "EED3W3446UQ7HPVY2VXJP5E3TF7NVQHM"; + Ip.of_string "141.161.20.32", 7000, Sha1.of_string "SDW4B4LWVIW2ZOROBEYM7WJGPO2W2TND"; + Ip.of_string "129.174.79.249", 7000, Sha1.of_string "3DAD4KLLQNILVMLIXNRAJDQZOEYWE5T6"; + Ip.of_string "140.247.60.123", 7000, Sha1.of_string "Z7GV5MRO27F4DHMOCIJXYTFHTD2NT55W"; + Ip.of_string "129.186.205.71", 7000, Sha1.of_string "YCHGLP3RSXUQWUBZUHP2FMTLIC5TCO4T"; + Ip.of_string "128.220.247.28", 7000, Sha1.of_string "2QJLLKYT2BJLS5FSTWDWHYW6B7OQ4YTD"; + Ip.of_string "129.130.252.141", 7000, Sha1.of_string "TGEQRTA6W2H3BH7OZSWK53HVMSKIMA6Q"; + Ip.of_string "129.237.161.193", 7000, Sha1.of_string "HDN42PP47TCOI2UQF7OQ4JOI3XLYYRFD"; + Ip.of_string "128.31.1.11", 7000, Sha1.of_string "WTLLT7EKFQXNY2GN37YQN7R4Z3ZKQN4K"; + Ip.of_string "35.9.27.26", 7000, Sha1.of_string "C3MFMD6TUZV7ELPIQBNP5CLJ6HPU22ZZ"; + Ip.of_string "141.219.252.132", 7000, Sha1.of_string "XYFKQ7S5OAUTYKUFYCETCKOSRAAGRWHJ"; + Ip.of_string "152.14.92.58", 7000, Sha1.of_string "GYEQSZH5GDPTVZ6ZUGJEIYD7X3N4UBL6"; + Ip.of_string "129.74.74.15", 7000, Sha1.of_string "PQB5ILXWMFPZZZ522NDPLZXRXGFGGNZY"; + Ip.of_string "129.10.120.193", 7000, Sha1.of_string "OOWUJIXQLSQ72A2F4BKBBI2BO2O37RON"; + Ip.of_string "216.165.109.81", 7000, Sha1.of_string "IN6Z2C7CIR4QGNVY5FECWBDQEDIIRC76"; + Ip.of_string "164.107.127.12", 7000, Sha1.of_string "D74K5YRAH4M4ZTYYWB5ON66S6O2B2YQY"; + Ip.of_string "128.193.33.7", 7000, Sha1.of_string "HLN7LWFFTHOKJTEUAD3KXTMKZ7UV4AWV"; + Ip.of_string "130.49.221.40", 7000, Sha1.of_string "3LTFOJRCJ774DBNU3T4ZFEASYKRRMBKP"; + Ip.of_string "128.112.139.80", 7000, Sha1.of_string "4XVBELRD3GVZYNODZXKXR74R6MK4VYNU"; + Ip.of_string "128.10.19.52", 7000, Sha1.of_string "VRF4WDGHK5B3U6Z4B2PQCXOMWF6DJBR6"; + Ip.of_string "128.42.6.143", 7000, Sha1.of_string "O4H4QJN644R7G6IMVRLHFEYGW4RRLUZE"; + Ip.of_string "128.151.65.101", 7000, Sha1.of_string "3UIYEKCORRCJWDOT432BYYEK5UGADZD6"; + Ip.of_string "128.113.226.235", 7000, Sha1.of_string "5S4BQ5QYJ2DQQRD54ET6ODBY5SFEUIFX"; + Ip.of_string "64.161.10.2", 7000, Sha1.of_string "BD3E44YRNGVMG7TQOHC6BX3LNGPLJHIW"; + Ip.of_string "171.66.3.181", 7000, Sha1.of_string "N22GUUPB3PCL5VSTD3I4RWVSX6BFRMJP"; + Ip.of_string "129.137.253.253", 7000, Sha1.of_string "II54XEMUDWFQAEFUVKAKQANXUSQJT4RO"; + Ip.of_string "169.237.79.210", 7000, Sha1.of_string "IKEOMWHOEBJADYJFK2CCBTJWUK63JYV7"; + Ip.of_string "132.170.3.32", 7000, Sha1.of_string "34YIASQ5UJE642T77RLAIH5XLV4O3MI6"; + Ip.of_string "128.195.54.161", 7000, Sha1.of_string "4MJQRXVMUHF5FUSG7WPT7H2PWLKIF2KF"; + Ip.of_string "131.179.50.70", 7000, Sha1.of_string "XMESSYMZLIPHT63HQJ5GMGL2GJBZXAAB"; + Ip.of_string "138.23.204.133", 7000, Sha1.of_string "B3FSK4YYB5KBFWXJA2Z7STQLCXOFLZ6M"; + Ip.of_string "128.114.63.14", 7000, Sha1.of_string "632WY6AWKZCLB6QCUMTO4NB2GZEBBU6Z"; + Ip.of_string "132.239.17.224", 7000, Sha1.of_string "RW3GG4MYZ5OIHVRFCZEOMO3RXBA67RQS"; + Ip.of_string "128.4.36.11", 7000, Sha1.of_string "S4HXULGPHIYEEX4VJKISRYOVVRIWR765"; + Ip.of_string "128.227.56.81", 7000, Sha1.of_string "MSLYOK2N3QVEVASIUM3QTJLY64O2AWW7"; + Ip.of_string "208.117.131.115", 7000, Sha1.of_string "FTASW6RQZ74ZMQCDRJDAZ7JXAANBGSPZ"; + Ip.of_string "72.36.112.71", 7000, Sha1.of_string "IQH25AIMAPHZJ4GDLOCNRSCCZ4SPNTJP"; + Ip.of_string "128.8.126.112", 7000, Sha1.of_string "PKZDYBVY5GS4BBVELRZ3CLPBUFYNSRSY"; + Ip.of_string "141.213.4.201", 7000, Sha1.of_string "ZQPXFWOTPNGX2WIU7JSHUNZJHW3BMKIV"; + Ip.of_string "204.56.0.137", 7000, Sha1.of_string "4I7DJCLADSVZBP7WOO2WAOJLZMCBARJN"; + Ip.of_string "152.15.98.226", 7000, Sha1.of_string "UN4EZM363KBWBUW4OUX4IUG2G76CRQXI"; + Ip.of_string "129.93.229.138", 7000, Sha1.of_string "LQSWZBJWNHTNBP2I44JKI7LRN5WEBAT6"; + Ip.of_string "129.24.211.25", 7000, Sha1.of_string "VHGXP3KA4B6VLOT4APLBHCHYMSOOHE37"; + Ip.of_string "128.223.8.111", 7000, Sha1.of_string "SVGRW4TSN4PL7S3WFFUV6FZQBI4JWZPW"; + Ip.of_string "158.130.6.254", 7000, Sha1.of_string "OGRVZV3BIYFPP4ARWBG25GJEVCTDPSZK"; + Ip.of_string "136.145.115.194", 7000, Sha1.of_string "U7KP2YKZP2DXNOGPX55KPJCDW3CMRS7V"; + Ip.of_string "131.247.2.241", 7000, Sha1.of_string "CFNVVEEPKWBW2D7XOAKWENOF33NPAQY5"; + Ip.of_string "155.98.35.2", 7000, Sha1.of_string "4MEBVWTXXAXS2W7WN4CVYKOL6LGNTWSC"; + Ip.of_string "129.110.125.51", 7000, Sha1.of_string "Z7DVJG3SA6FYR3L34DWS62DBH2ILSTZE"; + Ip.of_string "128.83.122.179", 7000, Sha1.of_string "QXN5OMVX4ZQR2PEPB642TBV5EB4DZQBH"; + Ip.of_string "160.36.57.172", 7000, Sha1.of_string "JCPMWMYXZY7XTUOKMCRLL7ZUQQLPTJAL"; + Ip.of_string "129.59.88.179", 7000, Sha1.of_string "KZ4P6T2ZSI3EQ4HHQSPSFKGIJJCPZE2M"; + Ip.of_string "198.82.160.221", 7001, Sha1.of_string "3GFLHJSKHJO4BUGTKRC7ZGNMV7XHOJTI"; + Ip.of_string "128.208.4.197", 7000, Sha1.of_string "J6Z2VJG4DJNQRNXXOFBOBQTRTGWWGXIL"; + Ip.of_string "137.165.1.111", 7000, Sha1.of_string "KPQ66PS3SHLW6E2SHEYWLNFOOCPUEAHN"; + Ip.of_string "198.133.224.145", 7000, Sha1.of_string "DIOFMYAYNDTUDD6SURRCDFORSTZO2AXN"; + Ip.of_string "198.133.224.147", 7000, Sha1.of_string "JC6R2DAJQ66AJJVGB7SHRNT4DBHNGHJF"; + Ip.of_string "134.121.64.4", 7000, Sha1.of_string "5ANZP6OSSTGCGQK7U6G5WIOFRHWUA6TZ"; + Ip.of_string "128.252.19.20", 7000, Sha1.of_string "BMXBX7MGLXZCWM25LTQ52HSL4HOU5U3G"; + Ip.of_string "130.206.158.138", 7000, Sha1.of_string "QRMHNZVPLLQT6DCIPG7LDJCDRIDGY5VI"; + Ip.of_string "193.147.162.166", 7000, Sha1.of_string "F6CTFI32BMQHTCTK2TJ5AEMDOKQUDLVW"; + Ip.of_string "193.167.187.187", 7000, Sha1.of_string "7ZECKF66WRHE524L66UYGUFXDYGKFKSC"; + Ip.of_string "193.167.182.130", 7000, Sha1.of_string "QQOIVZQV4DKHS42Z53JEC2EF6HOVK7TZ"; + Ip.of_string "193.55.112.41", 7000, Sha1.of_string "HNAANZ6AW3QQBJHVQEAUA7CEJ5GIQGRV"; + Ip.of_string "131.254.208.10", 7000, Sha1.of_string "GIRZBSCV5V5EPVYLFRHULPOCQGZR6UNJ"; + Ip.of_string "139.91.90.238", 7000, Sha1.of_string "ABZIAMQHWF2MSHYCRDBMDPDV2OUZ5O3U"; + Ip.of_string "147.102.3.101", 7000, Sha1.of_string "BR67N7IK62JKA7P35RH6Q4OLT2HPU3ET"; + Ip.of_string "147.102.224.228", 7000, Sha1.of_string "XD2VZ7UNZ64YXMMOYD6DODBXFXHZ7YCW"; + Ip.of_string "195.130.121.204", 7000, Sha1.of_string "VWLL47QYR4S5DRG7XRMRAXYQDSEWFHBG"; + Ip.of_string "150.140.140.91", 7000, Sha1.of_string "2TMFGHYW4Y7OGABBOPWPCKUVL5UL5MXW"; + Ip.of_string "137.189.97.17", 7000, Sha1.of_string "EOQ35KWFO6WQOCKNZYZSNRZLDCOJ5ASI"; + Ip.of_string "152.66.244.48", 7000, Sha1.of_string "QJHY6EAXZ7KH6SNZG2VKJQPXXP4NLUMT"; + Ip.of_string "193.1.170.135", 7000, Sha1.of_string "AJYX3Q5R77E2AJLRX7YZ73H3FLVDA77Y"; + Ip.of_string "132.68.237.34", 7000, Sha1.of_string "DBWHCFHNYIHT2DPRTKRQ5ELD2RZ7R2GP"; + Ip.of_string "202.141.62.34", 7000, Sha1.of_string "ZI5BKY5BNU7MWMF3OJN6POGGAOFM7KML"; + Ip.of_string "131.175.17.9", 7000, Sha1.of_string "JE5SXWKDDAHXC3Q4K5GLOLDTJD7MWJ5W"; + Ip.of_string "130.192.86.29", 7000, Sha1.of_string "GLLAHAMZKQRVHG42PIHUMYHG6OGQ4XMY"; + Ip.of_string "130.136.254.21", 7000, Sha1.of_string "GVML5IBATPOCGVTZZ5MX6C24WBGPGSMP"; + Ip.of_string "151.100.59.10", 7000, Sha1.of_string "CIAURVKZKUVP66IWIUK4MMRSU26N2NX5"; + Ip.of_string "130.192.157.131", 7000, Sha1.of_string "XHM7RZHPB7N63WWOMAJ5X6Q7XQFH7O73"; + Ip.of_string "150.65.32.66", 7000, Sha1.of_string "E5AXATEOYQULYFIZ25CZOLIF3BGESHQT"; + Ip.of_string "160.193.163.101", 7000, Sha1.of_string "C6AGGDYWUN6M5OJRO6JSZNDLX2FOFHXX"; + Ip.of_string "133.1.74.162", 7000, Sha1.of_string "OLU4PRPJ54SJ2U36NTSWUUHL3OXRMIOT"; + Ip.of_string "133.15.59.1", 7000, Sha1.of_string "FRRYCTY5G4BG53H42H5YQE6WPYJAMZGE"; + Ip.of_string "133.11.240.56", 7000, Sha1.of_string "2IU5UF2G62H35SRBTO3RWQ53HPAXE24X"; + Ip.of_string "163.221.11.71", 7000, Sha1.of_string "YEC37T3QLFT6K2UAIBZYD2DZVYBCWZ2C"; + Ip.of_string "210.125.84.15", 7000, Sha1.of_string "JDVYM5XJT3ELOP6VFV6YNJ3ZSZUTSTXB"; + Ip.of_string "210.123.39.102", 7000, Sha1.of_string "BO4N3OHLO6TVUEUN4QQMZY5MZO7PIVP4"; + Ip.of_string "206.207.248.34", 7000, Sha1.of_string "ZZ5U64PXP7HXZBMH5J5A5V72JCVYF3T6"; + Ip.of_string "87.84.153.114", 7000, Sha1.of_string "HX6XVFORH75GC4JNHIKY5KHIRUW2O4FV"; + Ip.of_string "192.42.83.251", 7000, Sha1.of_string "YQ5HTJKPWKXAZZW62U447HN4QFACXF76"; + Ip.of_string "12.46.129.14", 7000, Sha1.of_string "S7ISKO2G6NEKXDH5OETVX6QBMSAIS2HC"; + Ip.of_string "116.89.165.133", 7000, Sha1.of_string "FIXBGILJSSCRTIFXYAJNTQY3KZZ5FIP2"; + Ip.of_string "200.0.206.13", 7000, Sha1.of_string "CP3EVPHI2BBZGDGDFCXQM6QWDYE3BDGZ"; + Ip.of_string "129.242.19.196", 7000, Sha1.of_string "EOQORY4MPENPOBE34WYCUQ3QVEOVRP5N"; + Ip.of_string "213.19.160.195", 7000, Sha1.of_string "7QCNYSA4W7P3TTAJIQDA4XKARCMOOT6C"; + Ip.of_string "198.128.56.11", 7000, Sha1.of_string "DYSDU466ZB3SX33HFKF4Z6MIVFSNYYCS"; + Ip.of_string "140.112.107.82", 7000, Sha1.of_string "FINBXBKEWVP53HFZVENQ6PNVKO44WXMN"; + Ip.of_string "206.117.37.4", 7000, Sha1.of_string "HENBVYH3TG7DBIDAA762CTI4NXNF7QTJ"; + Ip.of_string "193.1.201.26", 7000, Sha1.of_string "33TYC2F2OMPZST6KZJ33A2ICWCQ4WH7V"; + Ip.of_string "150.254.212.147", 7000, Sha1.of_string "J5JABLCZUP466I36GW4PXL4MMOW5YCV2"; + Ip.of_string "156.17.10.51", 7000, Sha1.of_string "ILEA722SVWC4E5J3EY4FVJIANKUGW2PQ"; + Ip.of_string "193.136.191.25", 7000, Sha1.of_string "CLTZUSZVPMOTBV3VYKNO2LDRFAELTKC4"; + Ip.of_string "193.136.227.163", 7000, Sha1.of_string "QACXXKHISU343ABYFO33Q7DXYWROGYLN"; + Ip.of_string "194.117.20.214", 7000, Sha1.of_string "ILVVG7A73FBDWOV2ARMOUC4PQMO37LNA"; + Ip.of_string "193.136.166.54", 7000, Sha1.of_string "KAPY7DT26UCRRXFBQ4KNQRSJUOBBDOXQ"; + Ip.of_string "144.206.66.56", 7000, Sha1.of_string "N7DRHVSHAGJVLARHIJMGFMLCINEOPOBQ"; + Ip.of_string "213.131.1.101", 7000, Sha1.of_string "ENBCLF6R65IEBBY7FHXVMKOKM4IY6P4R"; + Ip.of_string "193.10.133.128", 7000, Sha1.of_string "C7ZR7H6GDATOU363UOY2DPJW3VKHN73P"; + Ip.of_string "137.132.80.106", 7000, Sha1.of_string "YSUINDE2HHPQV3JBMQUAFVBJEA6X2IOX"; + Ip.of_string "212.235.189.114", 7000, Sha1.of_string "SQ7KIVII5BRI3ZV7RKCQWP5CXZUYQVA6"; + Ip.of_string "140.119.164.84", 7000, Sha1.of_string "OPZMQJSNSYXB7V3J2FAUDLJUIV3THJL3"; + Ip.of_string "140.114.79.231", 7000, Sha1.of_string "TPK5HAUMP23GEAV5DS3TL2LXCZMLIA3N"; + Ip.of_string "140.112.42.158", 7000, Sha1.of_string "GRSH625P5OSM634QMLAQHKMIQLCHEMXH"; + Ip.of_string "140.127.208.238", 7000, Sha1.of_string "ZDA3EVRLPVLK5IWQ3ZXJ7XQKJGJCPD6M"; + Ip.of_string "140.109.17.180", 7000, Sha1.of_string "Z3UVL6D5ZA6RNVQUOYMMHUHQL5B6ZCXD"; + Ip.of_string "134.151.255.180", 7000, Sha1.of_string "P775H52X33VUQBDOO7NCK6BNBQMPQHM4"; + Ip.of_string "128.232.103.201", 7000, Sha1.of_string "HO4CH7B5RCHTF7RJJDZPDR2GZS3XWPQJ"; + Ip.of_string "193.63.75.18", 7000, Sha1.of_string "JOS2CNM4QPNOUSQCKJT6IYNOYD4U4NBE"; + Ip.of_string "129.12.3.74", 7000, Sha1.of_string "DYOTHWYUCE56BUCV6SW6FF44F4T7SX7U"; + Ip.of_string "194.36.10.156", 7000, Sha1.of_string "LQM6UL5APWYURSQSQKGOZFOB64RXI6YK"; + Ip.of_string "138.251.214.77", 7000, Sha1.of_string "TKV24JSJ24UCOSRXA2LUE4GEMW5P3EPM"; + Ip.of_string "193.63.58.70", 7000, Sha1.of_string "WJUMRWGYFJGAT7N3TNQJCPADMZSMNZ7I"; + Ip.of_string "143.215.129.115", 7000, Sha1.of_string "25UIPJBXDWDCPHHO4LGUM3T7X7SA7MXK"; + Ip.of_string "164.73.47.242", 7000, Sha1.of_string "ZE5WKLKRUNYSWDE7W6YZHK5WR7W3R5KI" + |] diff --git a/sources/fabrice/pacemaker/pMDriver.ml b/sources/fabrice/pacemaker/pMDriver.ml new file mode 100644 index 0000000..048101f --- /dev/null +++ b/sources/fabrice/pacemaker/pMDriver.ml @@ -0,0 +1,280 @@ +open SafeCaml +open Pervasives + +open Checksum +open Sets +open Options + +open NetP2P + +open PMTypes +open PMNetwork +open PMOptions +open PMGlobals +open PMHandlers + + + +let detach_daemon () = + try + let pid = Unix.unsafe_fork () in + if pid < 0 then failwith "Error in fork"; + if pid > 0 then begin + no_at_exit (); + exit 0; + end; + reset_pid (); + let _sid = Unix.setsid () in + +(* Changed in 2.5.27 *) + begin + let dev_zero = Filename.of_unix_string "/dev/zero" in + let stdin_new = Unix.openfile dev_zero [Unix.O_RDONLY] 0o444 in + Unix.dup2 stdin_new Unix.stdin; + Unix.close stdin_new; + end; + + begin + let dev_null = Filename.of_unix_string "/dev/null" in + let stdout_new = Unix.openfile dev_null [Unix.O_WRONLY] 0o666 in + Unix.dup2 stdout_new Unix.stdout; + Unix.dup2 stdout_new Unix.stderr; + Unix.close stdout_new; + end; + + with e -> + lprintf "Exception %s in detach_daemon\n" + (Printexc2.to_string e); + exit 2 + + +let check_best_binary () = + if !!auto_update + && !!best_binary_time > 0L + && !!best_binary_hash <> PMArgs.binary_hash + then + let filename = Filename.add_basename info_dir + (Sha1.to_string !!best_binary_hash) in + if Sys.file_exists filename then + let s = File.to_string filename in + let hash = Sha1.string s in + if hash = !!best_binary_hash then begin + PMLog.log (Printf.sprintf "new_binary %s" + (Sha1.to_string hash)); + Unix.chmod filename 0o755; + let mtime = Int64.to_float !!best_binary_time in + Unix.utimes filename mtime mtime; + Sys.remove binary_filename; + Unix.U.link (Filename.to_string filename) + (Filename.to_string binary_filename); + Unix.execv binary_name [| binary_name |] + end + + +let every_second _ = + if not (Fifo.empty to_ping) then begin + let (h,ip,port) = Fifo.take to_ping in + PMLog.log (Printf.sprintf "udps PING %s" (Sha1.to_string h)); + udp_send !current_ping ip port + end; + () + +(* + List.iter (fun s, p -> + if p.peer_id <> !uid then + let state = PaceMakerNetwork.peer_state p in + Printf.printf "Status of connection to %s = %s\n%!" + s (NetP2P.string_of_state state); + match state with + DISCONNECTED -> + D P "Connecting..."; + PaceMakerNetwork.connect p + | _ -> () + ) servers_list +*) + +let uptime = ref 0 +let periods = [| 10; 30; 60; 120 |] +let heartbeats = Array.map (fun n -> Random.int n) periods + + +let send_heartbeat period = + let time = Time.int64_time () in + let m = { + HeartBeatMsg.time = time; + server = my_uid; + period = period; + pubkey = sample_key_public; + privkey = sample_key_private; + signature = Rsa.sign + (Sha1.string (Printf.sprintf "%Ld-%s" time sample_key_public)) + server_key; + } in + PMHandlers.register_heartbeat m; + let send_heartbeat o = match o with + None -> () + | Some p -> send p HeartBeatMsg.msg m in + Array.iter send_heartbeat children; + Array.iter send_heartbeat parents + +let check_heartbeats () = + for i = 0 to Array.length periods - 1 do + let period = periods.(i) in + if !uptime = heartbeats.(i) then begin + send_heartbeat period; + let next_heartbeat = ((!uptime / period) + 1) * period + Random.int period in + heartbeats.(i) <- next_heartbeat + end + done + +let every_minute _ = + lprintf "every_minute"; + + if Fifo.empty to_ping then begin + List.iter (fun x -> + Fifo.put to_ping x) !!observed; + current_ping := + Printf.sprintf "PING|%Ld|%s|%d" (Time.int64_time ()) + (Sha1.to_string my_uid) !!my_port + end; + + let nchildren = ref 0 in + let nparents = ref 0 in + let ncandidates = ref 0 in + let count c = + match c with + None -> () + | Some p -> + match p.peer_status with + PEER_CANDIDATE _ -> incr ncandidates + | PEER_PARENT _ -> incr nparents + | PEER_CHILD _ -> incr nchildren + | _ -> () + in + Array.iter count parents; + Array.iter count children; + + PMLog.log (Printf.sprintf "up %d (%d) %d %d" !nparents !ncandidates !nchildren !peer_distance); + if !!run_as_server then check_heartbeats (); + if !!auto_update then check_best_binary (); + if !uptime mod 10 = 0 then begin + if not !!run_as_master then begin + lprintf "Connect to master"; + connect master + end + end; + incr uptime; (* do this after check_heartbeats *) + + if !!run_as_master then + save_nodes () + else + for i = 0 to ndegree - 1 do + match parents.(i) with + Some _ -> () + | None -> connect_candidate i + done + +let hours = ref 0 + +let log_filename = Filename.add_basename + PMConst.config_dir (Printf.sprintf "%s.log" binary_basename) +let log_filenameX = Filename.add_basename + PMConst.config_dir (Printf.sprintf "%s." binary_basename) + +let skip_first = ref true + +let rotate_logs () = + (try Sys.remove (Filename.add_suffix log_filenameX "9") with _ -> ()); + for i = 9 downto 2 do + try + Sys.rename + (Filename.add_suffix log_filenameX (string_of_int (i-1))) + (Filename.add_suffix log_filenameX (string_of_int i)) + with _ -> () + done; + (try + Sys.rename log_filename (Filename.add_suffix log_filenameX "1") + with _ -> ()); + LogPrintf.set_log_out_filename log_filename + +let every_hour _ = + lprintf "every_hour"; + PMHandlers.clean_heartbeats (); + lprintf "clean_heartbeats"; + incr hours; + if !skip_first then skip_first := false else rotate_logs () + +let _ = + assert (servers_list <> [] || !!run_as_server || !!run_as_master); + rotate_logs (); +(* if Sys.file_exists log_filename then Sys.remove log_filename; *) + set_verboses !!verbosity; + + if (not !!run_as_master) && !!observed = [] then begin + + for i = 1 to 25 do + let (x,y,z) = PMConst.allpeers.(Random.int (Array.length PMConst.allpeers)) in + observed =:= (z,x,y) :: !!observed + done; + must_save_options (); + save_options () + end; + + List.iter (fun (h,ip, port) -> + observed_by_id := Sha1Map.add h (ip,port) !observed_by_id + ) !!observed; + + if !!best_binary_hash = PMArgs.binary_hash then + lprintf "Running best binary !" + else + check_best_binary (); + + PMHandlers.main (); + set_my_id my_uid; + let rec bind_port current_port = + try + let _s = PaceMaker.bind_port current_port in + start_udp current_port; + set_my_port current_port; + if !!my_port = 0 then begin + lprintf "Setting port to %d" current_port; + my_port =:= current_port; + must_save_options (); + save_options () + end + with e -> + lprintf "Cannot bind port %d: %s" current_port + (Printexc2.to_string e); + if !!my_port <> 0 then + begin + PMLog.log "bind_failed"; + exit 2 + end + else + bind_port (current_port+1) + in + + bind_port (if !!my_port = 0 then !!min_port else !!my_port); + + PMHandlers.clean_binaries (); + + BasicSocket.add_infinite_timer 1 every_second; + BasicSocket.add_infinite_timer 60 every_minute; + BasicSocket.add_infinite_timer 3600 every_hour; + + BasicSocket.add_timer 1 every_hour; + BasicSocket.add_timer 2 every_minute; + + +(* Check if we are already running (create unix socket /tmp/pacemaker.sock) *) + + + lprintf "Pace-Maker started on %s" (Date.to_string (Date.current ())); + lprintf " UID: %s port: %d" (Sha1.to_string my_uid) !!my_port; + PMLog.log (Printf.sprintf "started %s" (Sha1.to_string PMArgs.binary_hash)); + detach_daemon (); + reset_pid (); + TestUnix.save_pid (); + NetMain.main () + + diff --git a/sources/fabrice/pacemaker/pMGlobals.ml b/sources/fabrice/pacemaker/pMGlobals.ml new file mode 100644 index 0000000..deb88f0 --- /dev/null +++ b/sources/fabrice/pacemaker/pMGlobals.ml @@ -0,0 +1,261 @@ +open SafeCaml +open Pervasives + +open Checksum +open Sets +open Options + +open NetP2P + +open PMTypes +open PMConst +open PMNetwork +open PMOptions + + +let nservers = ref 0 +let servers_map = ref Sha1Map.empty + +let servers_list = List.map (fun (sha1, ip, port) -> + let p = new_peer sha1 (Some (ip, port)) in + incr nservers; +(* p.peer_status <- PEER_SERVER; *) + servers_map := Sha1Map.add sha1 p !servers_map; + p + ) !!servers + +let to_ping = (Fifo.create () : (Sha1.t * Ip.t * int) Fifo.t) +let current_ping = ref "" + + + +let nservers = !nservers +let servers_map = !servers_map +let servers_tab = Array.of_list servers_list + +let master = + let (sha1, ip, port) = !!master in + let p = new_peer sha1 (Some (ip,port)) in + p.peer_status <- PEER_MASTER; + p + +let ndegree = !!ndegree +let my_uid = !!uid + +let parents = Array.create ndegree (None : peer_info option) +let children = Array.create ndegree (None : peer_info option) +let candidates = Array.init (max_distance+1) (fun _ -> + Fifo.create ()) + +let peer_nparents = ref 0 + +let data_dir = Filename.add_basename config_dir (Sha1.to_string my_uid) +let info_dir = Filename.add_basename config_dir "info" + + +let _ = + Unix.safe_mkdir data_dir; + Unix.safe_mkdir info_dir; + + + if !PMArgs.new_binary && + (!!best_binary_hash <> PMArgs.binary_hash || + !!best_binary_time < PMArgs.binary_mtime) then begin + lprintf "Preparing binary for exportation"; + let filename = Filename.add_basename info_dir + (Sha1.to_string PMArgs.binary_hash) in + let new_binary_ok = + if not (Sys.file_exists filename) || + Sha1.string (File.to_string filename) <> PMArgs.binary_hash then + let s = File.to_string binary_filename in + File.of_string filename s; + lprintf "Binary exported"; + Sha1.string (File.to_string filename) = PMArgs.binary_hash + else begin + lprintf "Binary already exported"; + true + end + in + + if new_binary_ok then begin + best_binary_hash =:= PMArgs.binary_hash; + best_binary_time =:= PMArgs.binary_mtime; + must_save_options (); + save_options () + end else begin + lprintf "Cannot export new binary"; + exit 2 + end + end + + +let heartbeats = (Hashtbl.create 2047 : (HeartBeatMsg.msg, bool) Hashtbl.t) + +type node = { + node_name : string; + node_ip : Ip.t option; + mutable node_port : int; + mutable node_hash : Sha1.t option; + mutable node_last : string option; + } + +let nodes_by_ip = Hashtbl.create 331 +let nodes = ref [] + +let register_node node = + nodes := node :: !nodes; + match node.node_ip with + None -> () + | Some ip -> + Hashtbl.add nodes_by_ip ip node + +let nodes_filename = Filename.add_basename config_dir "nodes.txt" + +let save_nodes () = + let b = Buffer.create 10000 in + List.iter (fun n -> + Printf.bprintf b "%s %s %d %s %s\n" n.node_name + (match n.node_ip with + None -> "---" + | Some ip -> Ip.to_string ip) + n.node_port + (match n.node_hash with + None -> "---" + | Some hash -> Sha1.to_string hash) + (match n.node_last with + None -> "---" + | Some s -> s) + ) !nodes; + File.of_string nodes_filename (Buffer.contents b) + +let _ = + if !!run_as_master then + let nodes_txt = try + File.to_string nodes_filename + with e -> + lprintf "Cannot load nodes.txt: aborting as master"; + exit 2 + in + List.iter (fun line -> + match String.split_simplify line ' ' with + [] -> () + | [ node_name ] -> + let node_ip = try + Some (Ip.from_name node_name) + with _ -> None + in + register_node { + node_name = node_name; + node_ip = node_ip; + node_port = 0; + node_hash = None; + node_last = None; + } + | [ node_name; node_ip; node_port; node_hash; node_last ] -> + let node_ip = if node_ip = "---" then None else + Some (Ip.of_string node_ip) + in + let node_hash = if node_hash = "---" then None else + Some (Sha1.of_string node_hash) + in + let node_last = if node_last = "---" then None else + Some node_last + in + register_node { + node_name = node_name; + node_ip = node_ip; + node_port = int_of_string node_port; + node_hash = node_hash; + node_last = node_last; + } + | _ -> assert false + ) (String.split nodes_txt '\n'); + nodes := List.rev !nodes; + save_nodes () + +let connected_to_node id ip port = + try + let n = Hashtbl.find nodes_by_ip ip in + n.node_hash <- Some id; + n.node_port <- port; + n.node_last <- Some (Date.DASHED.to_string (Date.current ())) + with Not_found -> + register_node { + node_name = "---"; + node_ip = Some ip; + node_port = port; + node_hash = Some id; + node_last = Some (Date.DASHED.to_string (Date.current ())); + } + +let old_binaries_map = ref StringMap.empty + +let _ = + List.iter (fun (basename, sizeL) -> + old_binaries_map := StringMap.add basename sizeL !old_binaries_map + ) !!old_binaries; + old_binaries =:= List.sort compare !!old_binaries + +let save_old_binaries () = + let binaries = ref [] in + StringMap.iter (fun basename sizeL -> + binaries := (basename, sizeL) :: !binaries) !old_binaries_map; + let binaries = List.sort compare !binaries in + if binaries <> !!old_binaries then begin + old_binaries =:= binaries; + must_save_options (); + save_options () + end + +let peer_ncandidates = ref 0 +let candidate_round = ref 1 + +let get_candidate () = + let rec iter i = + if i <= max_distance then + if Fifo.empty candidates.(i) then iter (i+1) + else begin + decr peer_ncandidates; + Some (Fifo.take candidates.(i)) + end + else + None + in + iter 0 + +let add_candidate p = + if p.peer_candidate < !candidate_round then begin + Fifo.put candidates.(p.peer_distance) p; + incr peer_ncandidates; + p.peer_candidate <- !candidate_round + end + +module Rsa = struct + + type t = unit + + let generate _ = () + let string_of_public _ = String.create 450 + let string_of_private _ = String.create 128 + let public_of_string _ = () + + let sign string () = String.create 256 + let verify string signature () = true + end + +let server_key = Rsa.generate 1024 (* this one is normally not available *) +let server_key_public = server_key + +let sample_key = Rsa.generate 1024 +let sample_key_public = Rsa.string_of_public sample_key +let sample_key_private = Rsa.string_of_private sample_key + + +let observed_by_id = ref Sha1Map.empty +let add_observed h ip port = + if not (Sha1Map.mem h !observed_by_id) then begin + observed =:= (h, ip, port) :: !!observed; + must_save_options (); + save_options () + end; + observed_by_id := Sha1Map.add h (ip,port) !observed_by_id diff --git a/sources/fabrice/pacemaker/pMHandlers.ml b/sources/fabrice/pacemaker/pMHandlers.ml new file mode 100644 index 0000000..09bd232 --- /dev/null +++ b/sources/fabrice/pacemaker/pMHandlers.ml @@ -0,0 +1,709 @@ +open SafeCaml +open Pervasives + +open Int64ops +open Checksum +open Sets +open Options + +open NetP2P + +open PMTypes +open PMNetwork +open PMConst +open PMOptions +open PMGlobals + + +let declare_handler msg f = PaceMaker.declare_handler msg (fun p m -> + PMLog.peer_log (Printf.sprintf "recv %s" msg.message_name) p; + f p m) + +let send p msg m = + PMLog.peer_log (Printf.sprintf "send %s" msg.message_name) p; + try + PaceMaker.send p msg m + with e -> + lprintf "Exception %s while sending to peer %s" + (Printexc2.to_string e) (Sha1.to_string p.peer_id) + +let connect p = + p.peer_last_try <- Time.offset_time (); + PMLog.peer_log "connect" p; + PaceMaker.connect p + +let refill_candidates _ = +(* Try to refill using the peer table: NetP2P.iter_peers *) + if !peer_ncandidates < 10 then begin + incr candidate_round; + List.iter (fun p -> + add_candidate p + ) servers_list + end + +let rec connect_candidate i = + match get_candidate () with + None -> +(* wait 30 seconds before refilling *) + BasicSocket.add_timer 30 refill_candidates + | Some p -> + + match p.peer_status with + PEER_UNKNOWN when p.peer_id <> my_uid -> + if Time.offset_time () - p.peer_last_try < 600 then +(* Don't reconnect to a peer within 5 minutes *) + connect_candidate i + else begin + try + p.peer_last_try <- Time.offset_time (); + connect p; + parents.(i) <- Some p; + p.peer_status <- PEER_CANDIDATE i; + with e -> + lprintf "Exception %s while connecting peer %s" + (Printexc2.to_string e) + (string_of_peer p) + end + + + | _ -> connect_candidate i + + +let peer_distance = ref (if !!run_as_server then 0 else max_distance) +let peer_server = ref Sha1.null + + +let distance_msg () = + { + DistanceMsg.distance = !peer_distance; + server = !peer_server; + } + + +let send_distance p msg = send p DistanceMsg.msg msg + +let broadcast_message msg m = + let send_message o = match o with + None -> () + | Some p -> + match p.peer_status with + PEER_CHILD _ | PEER_PARENT _ -> + send p msg m + | PEER_UNKNOWN -> + lprintf "WARNING: attempt to send heartbeat to unknown peer" + | PEER_CANDIDATE _ -> + lprintf "Dropping heartbeat for candidate" + | PEER_MASTER -> assert false + in + Array.iter send_message children; + Array.iter send_message parents + + +let update_distance () = + let last_distance = !peer_distance in + if !!run_as_server then begin + peer_distance := 0; + peer_server := my_uid + end else begin + peer_distance := max_distance; + peer_server := Sha1.null; + for i = 0 to ndegree - 1 do + match parents.(i) with + | Some { + peer_status = PEER_PARENT _ ; + peer_server = server; + peer_distance = distance } -> + if distance < !peer_distance then begin + peer_distance := distance; + peer_server := server; + end + | _ -> () + done; + peer_distance := min (!peer_distance+1) max_distance + end; + if !peer_distance <> last_distance then + broadcast_message DistanceMsg.msg (distance_msg ()) + + +let register_heartbeat msg = + PMLog.log (Printf.sprintf "heartbeat %s %Ld %d" + (Sha1.to_string msg.HeartBeatMsg.server) + msg.HeartBeatMsg.time msg.HeartBeatMsg.period); + Hashtbl.add heartbeats msg true + +let clean_heartbeats () = + let to_delete = ref [] in + let curtime = Time.int64_time () in + + Hashtbl.iter (fun m _ -> + if curtime -- m.HeartBeatMsg.time > 86000L then + to_delete := m :: !to_delete + ) heartbeats; + List.iter (fun m -> + Hashtbl.remove heartbeats m + ) !to_delete + +let set_longpeer p = + set_lifetime p 8640000; + set_rtimeout p 7200 + +let set_shortpeer p = + set_lifetime p 120; + set_rtimeout p 59 + +let new_sync p dir = + let s = { + directory = dir; + old_files = StringMap.empty; + new_files = []; + data_queued = 0; + } in + p.peer_sync <- Some s; + set_max_output_buffer p 400000; + s + +let chunk_sizeL = 65000L +let chunk = String.create 65000 + +let rec send_files p s = + if s.data_queued < 250000 then + match s.new_files with + [] -> + lprintf "No file to transfer"; + if !!run_as_master then set_lifetime p 120 + | (basename, new_sizeL) :: files -> + + let old_sizeL = try + StringMap.find basename s.old_files + with Not_found -> + lprintf "Filename %s not found" basename; + 0L in + + if old_sizeL < new_sizeL then begin + + lprintf "File %s : %Ld bytes remaining" basename + (new_sizeL -- old_sizeL); + let filename = Filename.add_basename s.directory basename in + let max_sizeL = new_sizeL -- old_sizeL in + let max_sizeL = min chunk_sizeL max_sizeL in + let max_size = Int64.to_int max_sizeL in + Unix.read_chunk (Unix.create_ro filename) old_sizeL + chunk 0 max_size; + + send p BlockMsg.msg { + BlockMsg.filename = Filename.to_string filename; + file_pos = old_sizeL; + file_content = String.sub chunk 0 max_size; + }; + + s.old_files <- StringMap.add basename (old_sizeL ++ max_sizeL) + s.old_files; + s.data_queued <- s.data_queued + max_size; + send_files p s + end else begin + lprintf "Finished with file %s" basename; + + begin + match p.peer_status with + PEER_MASTER -> + lprintf "\tFile uploaded to master"; + if basename <> !PMLog.current_basename then begin + lprintf "Deleting log file %s" basename; + let filename = Filename.add_basename s.directory basename in + (try Sys.remove filename with _ -> ()) + end + | PEER_PARENT _ -> lprintf "\tFile uploaded to parent" + | PEER_CHILD _ -> lprintf "\tFile uploaded to child" + | _ -> () + end; + + s.new_files <- files; + send_files p s + end + else + lprintf "Too much queued data %d" s.data_queued + +(* +let send_files p = + match p.peer_sync with + None -> () + | Some s -> send_files p s + *) + +let clean_binaries () = + let files = Unix.list_directory info_dir in + let best_binary = Sha1.to_string !!best_binary_hash in + let must_save_old_binaries = ref false in + List.iter (fun basename -> + if basename <> best_binary then begin + lprintf "Deleting old binary %s" basename; + try + let filename = Filename.add_basename info_dir basename in + let sizeL = Unix.getsize filename in + let old_sizeL = try + StringMap.find basename !old_binaries_map + with Not_found -> 0L + in + Sys.remove filename; + if sizeL > old_sizeL then begin + old_binaries_map := StringMap.add basename sizeL + !old_binaries_map; + must_save_old_binaries := true + end + with e -> + lprintf "Exception %s in clean_binaries %s" + (Printexc2.to_string e) basename + end + ) files; + if !must_save_old_binaries then save_old_binaries () + +let start_relationship p = + send_distance p (distance_msg ()); + send p InfoMsg.msg { + InfoMsg.best_binary_time = !!best_binary_time; + best_binary_hash = !!best_binary_hash; + }; + send p ListDirectoryMsg.msg { + ListDirectoryMsg.directory = Filename.to_string info_dir + } + + +let main () = + + declare_handler IdentifiedMsg.msg + (fun p msg -> + let _my_ip = msg.IdentifiedMsg.ip in + let _my_port = msg.IdentifiedMsg.port in + let other_port = msg.IdentifiedMsg.my_port in + p.peer_last_connected <- Time.offset_time (); + begin + match p.peer_addr with + None -> () + | Some (ip,port) -> + lprintf "Updating ports %s:%d to %s:%d" + (Ip.to_string ip) port (Ip.to_string ip) other_port; + p.peer_addr <- Some (ip, other_port) + end; + p.peer_sync <- None; +(* This is run when a peer as just been identified *) + lprintf "Connected to %s" (string_of_peer p); + if !!run_as_master then begin + set_rtimeout p 120; + match p.peer_addr with + None -> () + | Some (other_ip,other_port) -> + connected_to_node p.peer_id other_ip other_port + end else + match p.peer_status with + PEER_CANDIDATE i -> + set_shortpeer p; + send p AskParentMsg.msg + { AskParentMsg.distance = !peer_distance; + server = !peer_server; + nparents = !peer_nparents; + } + | PEER_MASTER -> + set_rtimeout p 120; + send p ListDirectoryMsg.msg { + ListDirectoryMsg.directory = Filename.to_string data_dir + } + | _ -> + set_shortpeer p + ); + + declare_handler ByeMsg.msg + (fun p msg -> + p.peer_sync <- None; + lprintf "Disconnecting from %s (%s)" + (string_of_peer p) + (string_of_state msg.ByeMsg.from_state); + match p.peer_status with + PEER_UNKNOWN -> () + | PEER_PARENT i -> + p.peer_status <- PEER_UNKNOWN; + PMLog.log (Printf.sprintf "lost_parent %s" + (Sha1.to_string p.peer_id)); + decr peer_nparents; + update_distance (); + parents.(i) <- None; + connect_candidate i + | PEER_CANDIDATE i -> + p.peer_status <- PEER_UNKNOWN; + parents.(i) <- None; + connect_candidate i + | PEER_CHILD i -> + PMLog.log (Printf.sprintf "lost_child %s" + (Sha1.to_string p.peer_id)); + p.peer_status <- PEER_UNKNOWN; + children.(i) <- None + | PEER_MASTER -> () + ); + + + + declare_handler AskParentMsg.msg + (fun p msg -> + + + let distance = msg.AskParentMsg.distance in + let parent_ok = +(* don't accept children if we have no parents *) + if !peer_distance = max_distance then false + else + +(* if our distance is different from the one of this peer, we should drop +any peer with the same distance as us, or, if the peer is an orphan, +any peer with a distance smaller to us. *) + let _ = + if !peer_distance <> distance then begin + let compare = + if msg.AskParentMsg.nparents = 0 then + (<=) + else + (=) + in + lprintf "Checking if some child should be dropped"; + let rec iter compare i can_drop = + if i < ndegree then + match children.(i) with + Some p -> + if p.peer_distance < max_distance && + compare p.peer_distance !peer_distance then + iter compare (i+1) (Some p) + | None -> () + else + match can_drop with + None -> + lprintf "Sorry, all children slots taken by correct peers" + | Some p -> + lprintf "Disconnecting peer with same distance"; + disconnect p + in + iter compare 0 None + end; + in + +(* check if there is an empty slot *) + let rec iter i = + if i < ndegree then + match children.(i) with + Some _ -> iter (i+1) + | None -> + p.peer_status <- PEER_CHILD i; + PMLog.log (Printf.sprintf "new_child %s" + (Sha1.to_string p.peer_id)); + children.(i) <- Some p; + set_longpeer p; + true + else false + in + iter 0 + in + + let candidates = ref [] in + let add_candidate p = + match p with + Some ({ + peer_addr = Some (ip, port); + peer_status = (PEER_CHILD _ | PEER_PARENT _); + } as p) -> + candidates := { + AskParentReplyMsg.cand_id = p.peer_id; + AskParentReplyMsg.cand_ip = ip; + cand_port = port; + cand_distance = p.peer_distance; + cand_server = p.peer_server + } :: !candidates + | _ -> () + in + for i = 0 to ndegree - 1 do + add_candidate parents.(i); + add_candidate children.(i) + done; + send p AskParentReplyMsg.msg { + AskParentReplyMsg.parent_ok = parent_ok; + candidates = !candidates; + } ; + if parent_ok then + start_relationship p; + ); + + + + declare_handler AskParentReplyMsg.msg + (fun p msg -> + + begin + match p.peer_status with + PEER_CANDIDATE i -> + if msg.AskParentReplyMsg.parent_ok then begin + p.peer_status <- PEER_PARENT i; + incr peer_nparents; + set_longpeer p; + PMLog.log (Printf.sprintf "new_parent %s" + (Sha1.to_string p.peer_id)); + start_relationship p; + end else begin + p.peer_status <- PEER_UNKNOWN; + parents.(i) <- None; + connect_candidate i + end + | _ -> + lprintf "AskParentReplyMsg from peer %s in status %s" + (string_of_peer p) (string_of_status p.peer_status) + end; + + List.iter (fun cand -> + let p = new_peer cand.AskParentReplyMsg.cand_id + (Some (cand.AskParentReplyMsg.cand_ip, + cand.AskParentReplyMsg.cand_port)) in + if p.peer_distance > cand.AskParentReplyMsg.cand_distance then begin + p.peer_distance <- cand.AskParentReplyMsg.cand_distance; + p.peer_server <- cand.AskParentReplyMsg.cand_server; + end; + add_candidate p + ) msg.AskParentReplyMsg.candidates; + ); + + + + + declare_handler DistanceMsg.msg + (fun p msg -> + p.peer_distance <- msg.DistanceMsg.distance; + p.peer_server <- msg.DistanceMsg.server; + update_distance (); + ); + + declare_handler HeartBeatMsg.msg + (fun p msg -> + + if Time.int64_time () -- msg.HeartBeatMsg.time < 86000L then + + if not (Hashtbl.mem heartbeats msg) then begin + register_heartbeat msg; + broadcast_message HeartBeatMsg.msg msg + end + ); + + + declare_handler ChallengeMsg.msg + (fun p msg -> +(* since we don't store yet pulses, we use a sample_key just to implement + the cryptography. *) + let reply = Rsa.sign + (Sha1.string (Printf.sprintf "%s-%s-%s" + msg.ChallengeMsg.nonce + (Sha1.to_string p.peer_id) + (Sha1.to_string my_uid) + )) sample_key in + +(* We sign the key instead of the server, but normally, we would +find it in the pulse. See comment above. *) + let signature = Rsa.sign + (Sha1.string (Printf.sprintf "%Ld-%s" + msg.ChallengeMsg.time + sample_key_public)) server_key in + + send p ProofMsg.msg + { + ProofMsg.time = msg.ChallengeMsg.time; + nonce = msg.ChallengeMsg.nonce; + pubkey = sample_key_public; + signature = signature; + reply = reply; + } + ); + + + declare_handler ProofMsg.msg + (fun p msg -> +(* We should first verify that, indeed, we sent the challenge ! *) + + let pubkey = Rsa.public_of_string msg.ProofMsg.pubkey in + let reply = Rsa.verify + (Sha1.string (Printf.sprintf "%s-%s-%s" + msg.ProofMsg.nonce + (Sha1.to_string my_uid) + (Sha1.to_string p.peer_id) + )) msg.ProofMsg.reply pubkey in + +(* We sign the key instead of the server, but normally, we would +find it in the pulse. See comment above. *) + let signature = Rsa.verify + (Sha1.string (Printf.sprintf "%Ld-%s" + msg.ProofMsg.time + msg.ProofMsg.pubkey)) msg.ProofMsg.signature + server_key_public in + + if reply && signature then +(* Good, this reply is correct *) + () + else +(* Bad, incorrect reply, ban this peer *) + () + ); + + + + declare_handler ListDirectoryMsg.msg + (fun p m -> + let directory = m.ListDirectoryMsg.directory in + let dir = Filename.of_string directory in + Unix.safe_mkdir dir; + let files = Unix.list_directory dir in + let old_files = ref ( + if directory = Filename.to_string info_dir then + !old_binaries_map + else + StringMap.empty) in + + let add_file basename sizeL = + try + let old_sizeL = StringMap.find basename !old_files in + if old_sizeL < sizeL then raise Not_found + with Not_found -> + old_files := StringMap.add basename sizeL !old_files + in + List.iter (fun basename -> + let filename = Filename.add_basename dir basename in + let sizeL = Unix.getsize filename in + add_file basename sizeL + ) files; + let files = ref [] in + StringMap.iter (fun basename sizeL -> + files := (basename, sizeL) :: !files + ) !old_files; + send p ListDirectoryReplyMsg.msg { + ListDirectoryReplyMsg.directory = directory; + files = !files; + } + ); + + + + declare_handler ListDirectoryReplyMsg.msg + (fun p m -> + let directory = m.ListDirectoryReplyMsg.directory in + let dir = Filename.of_string directory in + + let s = new_sync p dir in + + List.iter (fun (basename, sizeL) -> + s.old_files <- StringMap.add basename sizeL s.old_files + ) m.ListDirectoryReplyMsg.files; + + let files = Unix.list_directory dir in + let files = List.map (fun basename -> + let filename = Filename.add_basename dir basename in + let sizeL = Unix.getsize filename in + (basename, sizeL) + ) files in + s.new_files <- files; + send_files p s + ); + + + declare_handler BlockMsg.msg + (fun p m -> + + let filename = m.BlockMsg.filename in + let filenameF = Filename.of_string filename in + let file_pos = m.BlockMsg.file_pos in + let file_content = m.BlockMsg.file_content in + let file_content_size = String.length file_content in + Unix.write_chunk (Unix.create_rw filenameF) file_pos + file_content 0 file_content_size; + + send p BlockReplyMsg.msg { + BlockReplyMsg.filename = filename; + file_pos = file_pos; + file_content_size = file_content_size; + } + + ); + + + + declare_handler BlockReplyMsg.msg + (fun p m -> + + let filename = m.BlockReplyMsg.filename in + let _filenameF = Filename.of_string filename in + let _file_pos = m.BlockReplyMsg.file_pos in + let file_content_size = m.BlockReplyMsg.file_content_size in + + match p.peer_sync with + None -> () + | Some s -> + s.data_queued <- s.data_queued - file_content_size; + send_files p s + ); + + + declare_handler InfoMsg.msg + (fun p m -> + + if m.InfoMsg.best_binary_time > !!best_binary_time then begin + best_binary_time =:= m.InfoMsg.best_binary_time; + best_binary_hash =:= m.InfoMsg.best_binary_hash; + must_save_options (); + save_options (); + + clean_binaries () + end + ); + + + () + +let udp_sock = ref None + +let udp_send msg ip port = + match !udp_sock with + None -> assert false + | Some udp_sock -> + UdpSocket.write udp_sock msg ip port + + +let start_udp udp_port = + let packet_handler p = + let ip, _port = + match p.UdpSocket.udp_addr with + Unix.ADDR_INET (ip, port) -> Ip.of_inet_addr ip, port + | _ -> Ip.localhost, 0 + in + let m = p.UdpSocket.udp_content in + match String.split_simplify m '|' with + [ "PING"; time; uid; port ] -> + + PMLog.log (Printf.sprintf "udpr PING %s %s" uid time); + let uid = Sha1.of_string uid in + let port = int_of_string port in + add_observed uid ip port; + udp_send (Printf.sprintf "PONG|%s|%s|%d" time + (Sha1.to_string my_uid) !!my_port) ip port + + | [ "PONG"; time; uid; port ] -> + + PMLog.log (Printf.sprintf "udpr PONG %s %s" uid time); + let uid = Sha1.of_string uid in + let port = int_of_string port in + add_observed uid ip port + + | _ -> () + + in + let sock = + UdpSocket.create Unix.inet_addr_any udp_port (fun sock event -> + match event with + UdpSocket.READ_DONE -> + UdpSocket.read_packets sock packet_handler + | _ -> () + ) + in + udp_sock := Some sock + + + +
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/pMLog.ml b/sources/fabrice/pacemaker/pMLog.ml new file mode 100644 index 0000000..4418d35 --- /dev/null +++ b/sources/fabrice/pacemaker/pMLog.ml @@ -0,0 +1,53 @@ +open SafeCaml + +open Pervasives + +open Int64ops +open Checksum +open Sets +open Options + +open NetP2P + +open PMTypes +open PMConst +open PMNetwork +open PMGlobals + +let oc_ref = ref None + +let current_basename = ref "" + +let rec get_oc curtime = + match !oc_ref with + Some (oc, ctime) -> + if curtime -- ctime > 86400L then begin + Pervasives.OLD.close_out oc; + oc_ref := None; + get_oc curtime + end else + oc + | None -> + let basename = Printf.sprintf "%s-%Ld.txt" (Sha1.to_string my_uid) curtime + in + current_basename := basename; + let filename = Filename.add_basename data_dir basename in + let oc = open_out_gen [Open_append; Open_creat;Open_binary ] + 0o644 (Filename.to_string filename) in + Pervasives.OLD.output_char oc '\n'; + oc_ref := Some (oc, curtime); + oc + + + +let log s = + let curtime = Time.int64_time () in + let oc = get_oc curtime in + let s = Printf.sprintf "%Ld %s\n" curtime s in + lprintf "LOG: %s" s; + Pervasives.OLD.output_string oc s; + Pervasives.OLD.flush oc + +let peer_log s p = + log (Printf.sprintf "%s %s" s (Sha1.to_string p.peer_id)) + diff --git a/sources/fabrice/pacemaker/pMNetwork.ml b/sources/fabrice/pacemaker/pMNetwork.ml new file mode 100644 index 0000000..59fb618 --- /dev/null +++ b/sources/fabrice/pacemaker/pMNetwork.ml @@ -0,0 +1,435 @@ +open Checksum + +open PMTypes +open PMConst + +module PaceMaker = NetP2P.MakeNetwork (TcpSocket)(struct + type peer = peer_info + + let new_peer peer_id peer_addr = + { + peer_id = peer_id; + peer_addr = peer_addr; + peer_conn = None; + + peer_sync = None; + peer_distance = max_distance; + peer_server = Sha1.null; +(* peer_type = PEER_NORMAL; *) + peer_candidate = 0; + peer_status = PEER_UNKNOWN; + peer_last_try = - 86400; + peer_last_connected = - 86400; + } + let peer_id p = p.peer_id + let peer_address p = p.peer_addr + let peer_connection p = p.peer_conn + let set_peer_connection p c = p.peer_conn <- c + + let protocol_name = "pace-maker" + end) + +include PaceMaker + +(* these ones are redefined in PMHandlers, so prevent other modules from +using them directly *) +let send = () +let declare_handler = () +let connect = () + + +module AskParentMsg = struct + + type msg = { + distance : int; + server: Sha1.t; + nparents : int; + } + + let msg = declare_message "ASK_PARENT" + (fun b m -> + AnyEndian.buf_int8 b m.distance; + AnyEndian.buf_sha1 b m.server; + AnyEndian.buf_int8 b m.nparents + ) + (fun s pos -> + try + let distance = AnyEndian.get_uint8 s pos in + let server,pos = AnyEndian.get_sha1_pos s (pos+1) in + let nparents = try + AnyEndian.get_uint8 s pos + with _ -> 1 in + { distance = distance; + server = server; + nparents = nparents; + } + with _ -> { distance = 10; server = Sha1.null; nparents = 1; } + ) + (fun msg -> + Printf.sprintf "ASK_PARENT {\n\tdistance = %d\n\tserver = %s\n\tnparents = %d }\n" + msg.distance (Sha1.to_string msg.server) msg.nparents) + + end + +module AskParentReplyMsg = struct + + type candidate = { + cand_id : Sha1.t; + cand_ip : Ip.t; + cand_port : int; + cand_distance : int; + cand_server : Sha1.t; + } + + type msg = { + parent_ok : bool; + candidates : candidate list + } + + let msg = declare_message "ASK_PARENT_REPLY" + (fun b m -> + AnyEndian.buf_bool b m.parent_ok; + AnyEndian.buf_list8 (fun b c -> + AnyEndian.buf_sha1 b c.cand_id; + LittleEndian.buf_ip b c.cand_ip; + LittleEndian.buf_int16 b c.cand_port; + AnyEndian.buf_int8 b c.cand_distance; + AnyEndian.buf_sha1 b c.cand_server + ) b m.candidates; + ) + (fun s pos -> + let parent_ok = AnyEndian.get_bool s pos in + let candidates, pos = AnyEndian.get_list8 + (fun s pos -> + let id,pos = AnyEndian.get_sha1_pos s pos in + let ip,pos = LittleEndian.get_ip_pos s pos in + let port, pos = LittleEndian.get_int16 s pos in + let distance = AnyEndian.get_uint8 s pos in + let server,pos = AnyEndian.get_sha1_pos s (pos+1) in + { cand_id = id; + cand_ip = ip; + cand_port = port; + cand_distance = distance; + cand_server = server + }, pos + ) s (pos+1) in + { + parent_ok = parent_ok; + candidates = candidates; + } + ) + (fun m -> + let b = Buffer.create 10000 in + Printf.bprintf b "ASK_PARENT_REPLY {\n\tparent_ok = %b\n\tcandidates:\n" m.parent_ok; + List.iter (fun cand -> + Printf.bprintf b "\t\t%s %s:%d %d\n" + (Sha1.to_string cand.cand_id) + (Ip.to_string cand.cand_ip) cand.cand_port + cand.cand_distance + ) m.candidates; + Printf.bprintf b " }\n"; + Buffer.contents b) + + + end + + + +module DistanceMsg = struct + + type msg = { + distance : int; + server: Sha1.t; + } + + let msg = declare_message "DISTANCE" + (fun b m -> + AnyEndian.buf_int8 b m.distance; + AnyEndian.buf_sha1 b m.server) + (fun s pos -> + let distance = AnyEndian.get_uint8 s pos in + let server,pos = AnyEndian.get_sha1_pos s (pos+1) in + { distance = distance; server = server } + ) + (fun msg -> + Printf.sprintf "DISTANCE {\n\tdistance = %d\n\tserver = %s\n }\n" + msg.distance (Sha1.to_string msg.server)) + + end + +module InfoMsg = struct + + type msg = { + best_binary_time : int64; + best_binary_hash: Sha1.t; + } + + let msg = declare_message "INFO" + (fun b m -> + AnyEndian.buf_sha1 b m.best_binary_hash; + LittleEndian.buf_int64 b m.best_binary_time; + ) + (fun s pos -> + let best_binary_hash,pos = AnyEndian.get_sha1_pos s pos in + let best_binary_time, pos = LittleEndian.get_int64 s pos in + { best_binary_time = best_binary_time; + best_binary_hash = best_binary_hash } + ) + (fun msg -> + Printf.sprintf "INFO {\n\tbest_binary_time = %Ld\n\tbest_binary_hash = %s\n }\n" + msg.best_binary_time (Sha1.to_string msg.best_binary_hash)) + + end + + +module HeartBeatMsg = struct + + type msg = { + time : int64; + server: Sha1.t; + period : int; + pubkey : string; + privkey : string; + signature : string; + } + + let msg = declare_message "HEARTBEAT" + (fun b m -> + LittleEndian.buf_int64 b m.time; + AnyEndian.buf_sha1 b m.server; + AnyEndian.buf_int8 b m.period; + LittleEndian.buf_string31 b m.pubkey; + LittleEndian.buf_string31 b m.privkey; + LittleEndian.buf_string31 b m.signature; + ) + (fun s pos -> + let time, pos = LittleEndian.get_int64 s pos in + let server,pos = AnyEndian.get_sha1_pos s pos in + let period = AnyEndian.get_uint8 s pos in let pos = pos + 1 in + let (pubkey, privkey, signature) = + try + let pubkey, pos = LittleEndian.get_string31 s pos in + let privkey, pos = LittleEndian.get_string31 s pos in + let signature, _pos = LittleEndian.get_string31 s pos in + (pubkey, privkey, signature) + with _ -> + let payload, _pos = LittleEndian.get_string31 s pos in + "","", payload + in + { time = time; + server = server; + period = period; + pubkey = pubkey; + privkey = privkey; + signature = signature; + } + ) + (fun msg -> + Printf.sprintf "HEARTBEAT {\n\ttime = %Ld\n\tserver = %s\n\tperiod = %d\n }\n" + msg.time (Sha1.to_string msg.server) msg.period) + + end + +module AvailabilityMsg = struct + + type msg = { + time : int64; + availability : string; + signature : string; + } + + + let msg = declare_message "AVAILABILITY" + (fun b m -> + LittleEndian.buf_int64 b m.time; + LittleEndian.buf_string31 b m.availability; + LittleEndian.buf_string31 b m.signature; + ) + (fun s pos -> + let time, pos = LittleEndian.get_int64 s pos in + let availability, pos = LittleEndian.get_string31 s pos in + let signature, _pos = LittleEndian.get_string31 s pos in + { time = time; + availability = availability; + signature = signature } + ) + (fun msg -> + Printf.sprintf "AVAILABILITY {\n\ttime = %Ld\n }\n" + msg.time) + end + +module ChallengeMsg = struct + + type msg = { + time : int64; + nonce : string; + } + + let msg = declare_message "CHALLENGE" + (fun b m -> + LittleEndian.buf_int64 b m.time; + LittleEndian.buf_string31 b m.nonce; + ) + (fun s pos -> + let time, pos = LittleEndian.get_int64 s pos in + let nonce, _pos = LittleEndian.get_string31 s pos in + { time = time; + nonce = nonce; + } + ) + (fun msg -> + Printf.sprintf "CHALLENGE {\n\ttime = %Ld\n }\n" + msg.time) + end + +module ProofMsg = struct + + type msg = { + time : int64; + nonce : string; + pubkey : string; + signature : string; + reply : string; + } + + let msg = declare_message "PROOF" + (fun b m -> + LittleEndian.buf_int64 b m.time; + LittleEndian.buf_string31 b m.nonce; + LittleEndian.buf_string31 b m.pubkey; + LittleEndian.buf_string31 b m.signature; + LittleEndian.buf_string31 b m.reply; + ) + (fun s pos -> + let time, pos = LittleEndian.get_int64 s pos in + let nonce, pos = LittleEndian.get_string31 s pos in + let pubkey, pos = LittleEndian.get_string31 s pos in + let signature, pos = LittleEndian.get_string31 s pos in + let reply, _pos = LittleEndian.get_string31 s pos in + { time = time; + nonce = nonce; + pubkey = pubkey; + signature = signature; + reply = reply; + } + ) + (fun msg -> + Printf.sprintf "PROOF {\n\ttime = %Ld\n }\n" + msg.time) + end + + +module ListDirectoryMsg = struct + + type msg = { + directory : string; + } + + let msg = declare_message "LIST_DIRECTORY" + (fun b m -> + LittleEndian.buf_string31 b m.directory) + (fun s pos -> + let directory, _pos = LittleEndian.get_string31 s pos in + { directory = directory } + ) + (fun msg -> + Printf.sprintf "LIST_DIRECTORY {\n\tdirectory = %s\n }\n" + msg.directory) + + end + +module ListDirectoryReplyMsg = struct + + type msg = { + directory : string; + files : (string * int64) list; + } + + let msg = declare_message "LIST_DIRECTORY_REPLY" + (fun b m -> + LittleEndian.buf_string31 b m.directory; + LittleEndian.buf_list16 (fun b (filename, sizeL) -> + LittleEndian.buf_string31 b filename; + LittleEndian.buf_int64 b sizeL + ) b m.files + ) + (fun s pos -> + let directory, pos = LittleEndian.get_string31 s pos in + let files, pos = LittleEndian.get_list16 (fun s pos -> + let filename, pos = LittleEndian.get_string31 s pos in + let sizeL, pos = LittleEndian.get_int64 s pos in + (filename, sizeL), pos) s pos in + { directory = directory; + files = files } + ) + (fun msg -> + let b = Buffer.create 1000 in + Printf.bprintf b "LIST_DIRECTORY_REPLY {\n\tdirectory = %s\nfiles = [\n" + msg.directory; + List.iter (fun (file,size) -> + Printf.bprintf b "\t\t%s : %Ld\n" file size + ) msg.files; + Printf.bprintf b "]\n }\n"; + Buffer.contents b) + + end + +module BlockMsg = struct + + type msg = { + filename : string; + file_pos : int64; + file_content : string; + } + + let msg = declare_message "BLOCK" + (fun b m -> + LittleEndian.buf_string31 b m.filename; + LittleEndian.buf_int64 b m.file_pos; + LittleEndian.buf_string31 b m.file_content; + ) + (fun s pos -> + let filename, pos = LittleEndian.get_string31 s pos in + let file_pos, pos = LittleEndian.get_int64 s pos in + let file_content, pos = LittleEndian.get_string31 s pos in + + { filename = filename; + file_pos = file_pos; + file_content = file_content; + } + ) + (fun msg -> + Printf.sprintf "BLOCK {\n\tfilename = %s\nfile_pos = %Ld\n\tfile_content_size = %d }\n" + msg.filename msg.file_pos (String.length msg.file_content)) + + end + +module BlockReplyMsg = struct + + type msg = { + filename : string; + file_pos : int64; + file_content_size : int; + } + + + let msg = declare_message "BLOCK_REPLY" + (fun b m -> + LittleEndian.buf_string31 b m.filename; + LittleEndian.buf_int64 b m.file_pos; + LittleEndian.buf_int31 b m.file_content_size; + ) + (fun s pos -> + let filename, pos = LittleEndian.get_string31 s pos in + let file_pos, pos = LittleEndian.get_int64 s pos in + let file_content_size, pos = LittleEndian.get_int31 s pos in + { filename = filename; + file_pos = file_pos; + file_content_size = file_content_size; + } + ) + (fun msg -> + Printf.sprintf "BLOCK_REPLY {\n\tfilename = %s\nfile_pos = %Ld\n\tfile_size = %d\n }\n" + msg.filename msg.file_pos msg.file_content_size) + + end
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/pMOptions.ml b/sources/fabrice/pacemaker/pMOptions.ml new file mode 100644 index 0000000..1babbd5 --- /dev/null +++ b/sources/fabrice/pacemaker/pMOptions.ml @@ -0,0 +1,140 @@ +open SafeCaml +open Pervasives + +open Checksum +open Sets +open Options + +open NetP2P + +open PMTypes +open PMConst +open PMNetwork + + +let binary_name = Sys.argv.(0) +let _ = + if not (String.starts_with binary_name "/home/irisa_pacemaker/pacemaker/bin/") then + begin + lprintf "Bad binary location"; + exit 2 + end + +let binary_filename = Filename.of_string binary_name +let binary_basename = Filename.basename binary_filename + + +let filename = Filename.add_basename config_dir (Printf.sprintf "%s.ini" binary_basename) +let config = Options.create_options_file filename +let options = Options.file_section config ["Options"] "" + +let must_save_options = ref false + +let save_options () = + if !must_save_options then begin + Options.save_with_help config; + must_save_options := false + end + +let must_save_options () = must_save_options := true + +let master = define_option options ["master"] "" + (tuple3_option + (Sha1.option, Ip.option, int_option)) + (Sha1.of_string "F56I34NIUJEXAIMPLEHX4J3SQXBWYIMS", + Ip.of_string "195.83.212.149", 7008) + + +let version = define_option options ["version"] "" + int_option 0 + +let servers = define_option options ["server"] "" + (list_option (tuple3_option + (Sha1.option, Ip.option, int_option))) [ + +(* peerolyse *) + (Sha1.of_string "KLQCLYRUP3NMDOH3LNAEPX3L4QBGA6HQ", + Ip.of_string "195.83.212.155", 7001); + +(* peerformance *) + (Sha1.of_string "V7T52VJ7WIQWP4T5UXH2E7XLUJXDJ6C7", + Ip.of_string "195.83.212.149", 7001); + + ] + +let observed = define_option options ["observed"] "" + (list_option (tuple3_option + (Sha1.option, Ip.option, int_option))) [] + +let observers = define_option options ["observers"] "" + (list_option (tuple3_option + (Sha1.option, Ip.option, int_option))) [] + + +let old_binaries = define_option options ["old_binaries"] "" + (list_option (tuple2_option (string_option, int64_option))) [] + +let ndegree = define_option options ["ndegree"] "" + int_option 5 + +let min_port = define_option options ["min_port"] "" + int_option 7000 + +let my_port = define_option options ["port"] "" + int_option 0 + +let verbosity = define_option options ["verbosity"] "" + string_option "PPP" + +let uid = define_option options ["uid"] "" + Sha1.option (Sha1.random ()) + +let auto_update = define_option options ["auto_update"] "" + bool_option true + +let run_as_server = define_option options ["run_as_server"] "" + bool_option false + +let run_as_master = define_option options ["run_as_master"] "" + bool_option false + + +let best_binary_hash = define_option options ["best_binary_hash"] "" + Sha1.option Sha1.null + +let best_binary_time = define_option options ["best_binary_time"] "" + int64_option 0L + + + + + +let load () = + try + Options.load config + with e -> + Printf.fprintf stderr "Exception %s while loading option file\n%!" + (Printexc2.to_string e) ; + exit 2 + +let _ = + if Sys.file_exists filename then load () else must_save_options (); + + if !!version = 0 then begin + + let x = + (Sha1.of_string "V7T52VJ7WIQWP4T5UXH2E7XLUJXDJ6C7", + Ip.of_string "195.83.212.149", 7001) in + if not (List.mem x !!servers) then + servers =:= x :: !!servers; + + version =:= 1; + must_save_options () + end; + + if !!run_as_server && !!ndegree = 5 then begin + must_save_options (); + ndegree =:= 10 + end + +
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/pMTypes.ml b/sources/fabrice/pacemaker/pMTypes.ml new file mode 100644 index 0000000..a483714 --- /dev/null +++ b/sources/fabrice/pacemaker/pMTypes.ml @@ -0,0 +1,67 @@ +open SafeCaml +open Pervasives + +open Sets +open Checksum +open NetP2P + + +type peer_status = + PEER_CANDIDATE of int +| PEER_PARENT of int +| PEER_CHILD of int +| PEER_UNKNOWN +| PEER_MASTER + +(* +type peer_type = + PEER_SERVER +| PEER_MASTER +| PEER_NORMAL + *) + +type sync_dir = { + mutable directory : Filename.t; + mutable old_files : int64 StringMap.t; + mutable new_files : (string * int64) list; + mutable data_queued : int; + } + +type peer_info = { + (* These fields are for NetP2P *) + mutable peer_conn : (peer_info, TcpSocket.t) connection option; + mutable peer_id : Sha1.t; + mutable peer_addr : (Ip.t * int) option; + +(* These fields are for our personal use *) +(* mutable peer_type : peer_type; *) + +(* What can we do with this peer *) + mutable peer_status : peer_status; + + mutable peer_candidate : int; +(* never connect to the same peer in less than 10 minutes *) + mutable peer_last_try : int; + mutable peer_last_connected : int; + +(* minimal distance to server *) + mutable peer_distance : int; + mutable peer_server : Sha1.t; + + mutable peer_sync : sync_dir option; + } + +let string_of_peer p = + (Sha1.to_string p.peer_id) ^ (match p.peer_addr with + None -> "" + | Some (ip,port) -> + Printf.sprintf "(%s:%d)" (Ip.to_string ip) port) + +let string_of_status s = + match s with + PEER_CANDIDATE int -> Printf.sprintf "PEER_CANDIDATE %d" int + | PEER_PARENT int -> Printf.sprintf "PEER_PARENT %d" int + | PEER_CHILD int -> Printf.sprintf "PEER_CHILD %d" int + | PEER_UNKNOWN -> "PEER_UNKNOWN" + | PEER_MASTER -> "PEER_MASTER" +
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/pM_pl_plot.ml b/sources/fabrice/pacemaker/pM_pl_plot.ml new file mode 100644 index 0000000..b1e1e4a --- /dev/null +++ b/sources/fabrice/pacemaker/pM_pl_plot.ml @@ -0,0 +1,442 @@ +open SafeCaml +open Pervasives + +open Int64ops +open Checksum +open Sets + +type peer = { + peer_id : Sha1.t; + peer_ups : int array; + peer_heartbeats : (int * int64 *int * int) array; + peer_pongs : (int * int * string * string) ref Sha1Map.t; + } + +type observed = { + o_id : Sha1.t; + bitmap : string; + mutable observers : (Sha1.t * string) list; + } + +let peers_by_id = ref Sha1Map.empty +let server1 = "V7T52VJ7WIQWP4T5UXH2E7XLUJXDJ6C7" +let server2 = "KLQCLYRUP3NMDOH3LNAEPX3L4QBGA6HQ" +let master = "F56I34NIUJEXAIMPLEHX4J3SQXBWYIMS" + + +let min_timeL = 1223358964L +let min_time_abs = Int64.to_int (min_timeL // 60L) - 240 +let max_time_abs = min_time_abs + 1440 + 480 + +let min_timeM = Int64.to_int (min_timeL // 60L) +let max_timeM = min_timeM + 1440 +let time_rangeM = 1442 + +let server1_id = Sha1.of_string server1 +let server2_id = Sha1.of_string server2 +let master_id = Sha1.of_string master +let starters = [| []; [] |] + +let int_of_server s = + if s = server1 then 0 else + if s = server2 then 1 else + -1 + +module Sha1 = struct + + let set = ref Sha1Map.empty + + let of_string s = + let s = Sha1.of_string s in + try + Sha1Map.find s !set + with Not_found -> + set := Sha1Map.add s s !set; + s + + let to_string s = Sha1.to_string s + + end + +let sha1_len = String.length "55SQEF3S5S6UH7D2FUSB24ORVTELVN32" + +let current_directory = Filename.of_string "." + +let peers = List.sort compare (Unix.list_directory current_directory) + +let min_time = ref max_int +let max_time = ref 0 + +let logs_iter f peer_id = + let dir = Filename.add_basename current_directory + (Sha1.to_string peer_id) in + let logs = List.sort compare (Unix.list_directory dir) in + List.iter (fun log -> + let s = File.to_string (Filename.add_basename dir log) in + let lines = String.split s '\n' in + List.iter (fun line -> + f (String2.split_simplify line ' ') + ) lines + ) logs + +let analyse_peer_logs peer_id_s = + let peer_id = Sha1.of_string peer_id_s in + if peer_id <> master_id then + let ups = ref [] in + let heartbeats = ref [] in + let pongs = ref Sha1Map.empty in +(* let pongs = ref [] in + let pings = ref [] in *) + logs_iter (fun tokens -> + try + match tokens with + [] -> () + | timeS :: "up" :: args -> + let timeL = Int64.of_string timeS in + let time = Int64.to_int (Int64.div timeL 60L) in + if time < !min_time then min_time := time + else if time > !max_time then max_time := time; + if time >= min_time_abs && time <= max_time_abs then + ups := time :: !ups + | [ timeS ; "heartbeat" ; server ; ptimeS ; period ] -> + let timeL = Int64.of_string timeS in + let time = Int64.to_int (Int64.div timeL 60L) in + let ptimeL = Int64.of_string ptimeS in + let period = int_of_string period in + let server = int_of_server server in + if time >= min_time_abs && time <= max_time_abs then + heartbeats := (time, ptimeL, server,period) :: !heartbeats + | timeS :: "started" :: _ -> + let server = int_of_server peer_id_s in + if server >= 0 then + let timeL = Int64.of_string timeS in + starters.(server) <- timeL :: starters.(server) + | [ timeS ; "udpr" ; "PONG" ; hash ; timeP ] -> + let timeL = Int64.of_string timeS in + let timePL = Int64.of_string timeP in + let delay = Int64.to_int (timeL -- timePL) in + let p2 = Sha1.of_string hash in + let time = Int64.to_int (Int64.div timeL 60L) in + if time >= min_timeM && time <= max_timeM then + let time = time - min_timeM in + let x = try + Sha1Map.find p2 !pongs + with Not_found -> + let x = ref (0,0, + String.make time_rangeM '0', + String.make time_rangeM '0') in + pongs := Sha1Map.add p2 x !pongs; + x + in + let (xx,nn,pings,pongs) = !x in + pongs.[time] <- '1'; + x := (xx+delay, nn+1,pings,pongs) + + | [ timeS ; "udps" ; "PING" ; hash ] -> + let timeL = Int64.of_string timeS in + let p2 = Sha1.of_string hash in + let time = Int64.to_int (Int64.div timeL 60L) in + if time >= min_timeM && time <= max_timeM then + let time = time - min_timeM in + let x = try + Sha1Map.find p2 !pongs + with Not_found -> + let x = ref (0,0, + String.make time_rangeM '0', + String.make time_rangeM '0') in + pongs := Sha1Map.add p2 x !pongs; + x + in + let (xx,nn,pings, pongs) = !x in + pings.[time] <- '1' + + | _ -> () + with e -> + Printf.printf "Exception %s while reading log\n" + (Printexc2.to_string e) + ) peer_id; + + let p = { + peer_id = peer_id; + peer_ups = Array.of_list !ups; + peer_heartbeats = Array.of_list !heartbeats; + peer_pongs = !pongs; + } in + + if peer_id_s <> server1 && peer_id_s <> server2 then + peers_by_id := Sha1Map.add peer_id p !peers_by_id + + +let _ = + + let cache = Filename.of_string "cache.dat" in + if Sys.file_exists cache then + let ic = OLD.open_in "cache.dat" in + let (a,b,c,d,e) = input_value ic in + OLD.close_in ic; + peers_by_id := a; + min_time := b; + max_time := c; + starters.(0) <- d; + starters.(1) <- e; + else + let npeers = ref 0 in + List.iter (fun s -> + if String.length s = sha1_len then begin + incr npeers; + Printf.printf "Processing peer %s (%d)\n%!" s !npeers; + analyse_peer_logs s; + end + ) peers; + for i = 0 to 1 do + starters.(i) <- List.rev (List.sort compare starters.(i)) + done; + Printf.printf "Saving cache\n%!"; + let oc = OLD.open_out "cache.dat" in + output_value oc (!peers_by_id, !min_time, !max_time, starters.(0), starters.(1)); + OLD.close_out oc + +let _ = + let _min_time = !min_time in + let _max_time = !max_time in + + let min_time = Int64.to_int (min_timeL // 60L) in + let max_time = min_time + 1440 in + +(* let min_time = min_time + 4 * 1440 in *) + let time_range = max_time - min_time + 2 in + + Printf.printf "Min time : %d\n%!" min_time; + Printf.printf "Max time : %d (%d)\n%!" max_time ((max_time - min_time) / 1440); + let oc = OLD.open_out "trace.txt" in + + let count_bitmap bitmap = + let count = ref 0 in + for i = 0 to String.length bitmap-1 do + if bitmap.[i] = '1' then incr count + done; + !count + in + + let lines = Array.create 16 [] in + let bitmaps = ref Sha1Map.empty in + Printf.printf "Y\n%!"; + Sha1Map.iter (fun _ p -> + Printf.printf "Peer %s\n%!" (Sha1.to_string p.peer_id); + + let bitmap = String.make time_range '-' in + Array.iter (fun time -> + if time - min_time >= 0 && time < max_time then + if bitmap.[time - min_time] = '1' then + bitmap.[time - min_time + 1 ] <- '1' + else + bitmap.[time - min_time] <- '1' + ) p.peer_ups; + + bitmaps := Sha1Map.add p.peer_id bitmap !bitmaps; + let avail = count_bitmap bitmap in + + if avail > 0 then + let _ = () in + Printf.fprintf oc "%s" (Sha1.to_string p.peer_id); + Printf.fprintf oc "\t%d" avail; + + let rec find_starter list ptimeL period = + match list with + [] -> ptimeL + | startL :: tail -> + if startL <= ptimeL then + + let periodL = (Int64.of_int period) ** 60L in + startL ++ ((ptimeL -- startL) // periodL) ** periodL + + else find_starter tail ptimeL period + in + + let measures = ref 0 in + List.iter (fun period -> + + for server = 0 to 1 do +(* Printf.fprintf oc "{%d,%d} = " server period; *) + let bitmap = String.make time_range '-' in + Array.iter (fun (_, ptimeL, ss, pp) -> + if ss = server && pp = period then + let ptimeL = find_starter starters.(server) ptimeL period in + let ptime = Int64.to_int (Int64.div ptimeL 60L) in + let time = (ptime - min_time) / period in +(* Printf.fprintf oc "[%d <- %Ld,%d]" ptime ptimeL time; *) + let time = time * period in + for x = 0 to period - 1 do + if time + x >= 0 && time + x < time_range then + if bitmap.[time + x] = '1' then + +(* For each server, we need to find the starting times (log "started"), so +that we can find, for a given heartbeat the period of time to which it is +referring... *) +(* Printf.fprintf oc " XXX " *) () + else + bitmap.[time + x] <- '1' + done + ) p.peer_heartbeats; + let eval_avail = count_bitmap bitmap in + Printf.fprintf oc "\t%d %.2f" eval_avail + ((float_of_int (abs (avail - eval_avail)))/. + (float_of_int avail)) + ; + + let abs_error = float_of_int (abs (avail - eval_avail)) in + let rel_error = abs_error /. float_of_int avail in + Printf.printf "measures: %d\n%!" !measures; + lines.(!measures) <- (abs_error /. 1440.) :: lines.(!measures); + incr measures; + lines.(!measures) <- rel_error :: lines.(!measures); + incr measures; + + done; + + ) [10; 30; 60; 120]; + + Printf.fprintf oc "\n"; + ) !peers_by_id; + + + OLD.close_out oc; + + let lines = Array.map (fun list -> + Array.of_list (List.sort compare list)) lines in + let oc = OLD.open_out "error.txt" in + for i = 0 to Array.length lines.(0) - 1 do + for j = 0 to Array.length lines - 1 do + Printf.fprintf oc "%f " lines.(j).(i); + done; + Printf.fprintf oc "\n"; + done; + OLD.close_out oc; + + let merge_bitmaps b1 b2 = + let b1 = String.copy b1 in + for i = 0 to String.length b1 - 1 do + if b2.[i] <> '1' then b1.[i] <- '0' + done; + b1 + in + + let observed = ref Sha1Map.empty in + + Printf.printf "pongs now\n%!"; + let oc2 = OLD.open_out "delays.txt" in + Sha1Map.iter (fun _ p -> + let p1 = p.peer_id in + Printf.fprintf oc2 "%s:\n" (Sha1.to_string p1); + Sha1Map.iter (fun p2 x -> + if p1 <> p2 then + let (xx,nn,pings,pongs) = !x in + Printf.fprintf oc2 "\t%s %d\n" (Sha1.to_string p2) ( + if nn > 0 then xx/nn else 0); + let bitmap = try + Sha1Map.find p2 !bitmaps + with _ -> "---" in + Printf.fprintf oc2 "\t\t%s\n" bitmap; + Printf.fprintf oc2 "\t\t%s\n" pings; + Printf.fprintf oc2 "\t\t%s\n" pongs; + + let bitmap = String.sub bitmap 1 1440 in + let pings = String.sub pings 1 1440 in + let pongs = String.sub pongs 1 1440 in + + let availability = count_bitmap bitmap in + let ping_avail = merge_bitmaps bitmap pings in + let ping_avail = count_bitmap ping_avail in + begin + try + let o = Sha1Map.find p2 !observed in + o.observers <- (p1, pongs) :: o.observers + with Not_found -> + observed := Sha1Map.add p2 + { + o_id = p2; + bitmap = bitmap; + observers = [p1 ,pongs] } !observed + end; + let pongs = count_bitmap pongs in + if ping_avail > pongs then + Printf.fprintf oc2 "\t\t\tNO REPLIES: %d > %d \n" ping_avail pongs; + + if availability > 0 then +(* min: there might be more pongs that pings ? *) + let pongs = float_of_int (min availability pongs) in + let availability = float_of_int availability in + + + let availability = availability /. 1440. in + let pongs = (min 1440. pongs) /. 1440. in + + Printf.fprintf oc2 "%f %f ERROR\n" + (abs_float (availability -. pongs)) + (abs_float (availability -. pongs) /. availability); + ) p.peer_pongs; + Printf.fprintf oc2 "\n" + ) !peers_by_id; + OLD.close_out oc2; + + let oc = OLD.open_out "pings_errors.txt" in + Sha1Map.iter (fun p1 o -> + + let availability = count_bitmap o.bitmap in + if availability > 0 then + let availabilityF = float_of_int availability in + + let t = Array.of_list o.observers in + +(* shuffle it *) + let len = Array.length t in + for i = 0 to 100 do + let x1 = Random.int len in + let x2 = Random.int len in + let x = t.(x1) in + t.(x1) <- t.(x2); + t.(x2) <- x; + done; + + let observation = String.make 1440 '0' in + for i = 1 to 25 do + + begin + if i < len then + let (p2,b) = t.(i) in + for j = 0 to 1440 - 1 do + if b.[j] = '1' then observation.[j] <- '1' + done + end; + if i mod 5 = 0 then + let observed = count_bitmap observation in + let error = abs (observed - availability) in + let errorF = float_of_int error /. 1440. in + Printf.fprintf oc "%f %f " errorF (errorF /. availabilityF) + done; + Printf.fprintf oc "\n" + ) !observed; + + OLD.close_out oc; + + + let nmessages = ref 0 in + let f tokens = + match tokens with + timeS :: "recv" :: "ASK_PARENT" :: _ -> + let timeL = Int64.of_string timeS in + let time = Int64.to_int (Int64.div timeL 60L) in + if time >= min_time && time < max_time then + incr nmessages + | _ -> () + in + logs_iter f server1_id; + Printf.printf "ASK_PARENT server 1: %d (%.04f)\n" + !nmessages (float_of_int !nmessages /. float_of_int time_range); + nmessages := 0; + logs_iter f server2_id; + Printf.printf "ASK_PARENT server 2: %d (%.04f)\n" + !nmessages (float_of_int !nmessages /. float_of_int time_range); + () + +
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/pingtrace.ml b/sources/fabrice/pacemaker/pingtrace.ml new file mode 100644 index 0000000..0460994 --- /dev/null +++ b/sources/fabrice/pacemaker/pingtrace.ml @@ -0,0 +1,147 @@ +open SimulTrace +open SimulTypes +open SimulGraphes + +let day = 60 * 24 + +let degree = ref 5 +let anon_args = ref [ Sys.argv.(0) ] +let ndays = ref 0 +let subdir = ref None + +let _ = + Arg.parse [ + "-subdir", Arg.String (fun s -> + subdir := Some s), "<subdir> : set subdir for data files"; + "-ndays", Arg.Int ((:=) ndays), " <n> : number of days"; + "-dist", Arg.Set print_distribution, " : print distribution"; + "-degree", Arg.Int ((:=)degree), " <n> : peer degree"; + ] + (fun t -> anon_args := t :: !anon_args) "" + + +let subdir = + match !subdir with + None -> failwith "You must specify a subdirectory for data files" + | Some dir -> + Unix2.safe_mkdir (Filename2.of_string dir); + dir + +let degree = !degree + + +let argv = Array.of_list (List.rev !anon_args) +let trace = argv.(1) + + +let _ = + if trace = "" then + failwith "You must at least specify the name of the trace file"; + Random.self_init () + +let peers, nrounds, do_round = trace_read trace +let nrounds = + if !ndays <> 0 then + day * !ndays + else nrounds + +let npeers = Array.length peers + +type peer2 = { + mutable observers : int list; + + mutable availabilities : int array; + mutable ping : bool; + } + + +let rec find_observer i p = + let x = Random.int npeers in + if x = i || List.mem x p.observers then find_observer i p + else + p.observers <- x :: p.observers + +let nrounds = + if Array.length argv = 3 then + day * int_of_string argv.(2) + else nrounds + +let _ = + + let peers2 = Array.init npeers (fun i -> + let p = { + observers = []; + availabilities = [| 0; 0 |]; + ping = false; + } in + + for x = 1 to degree do + find_observer i p + done; + + p) + in + let rec iter_observers p list = + match list with + [] -> () + | o :: tail -> + let po = peers.(o) in + if po.state = ON then + p.availabilities.(1) <- p.availabilities.(1) + 1 + else + iter_observers p tail + in + + for round = 0 to nrounds - 1 do + do_round round; + + for i = 0 to npeers - 1 do + let p = peers.(i) in + let p2 = peers2.(i) in + if p.state = ON then begin + p2.availabilities.(0) <- p2.availabilities.(0) + 1; + iter_observers p2 p2.observers + end + done + done; + + let avail_error = + Printf.printf "availability...\n%!"; + let avail = Array.create npeers (0,0,false) in + for i = 0 to npeers - 1 do + let a = ( + peers2.(i).availabilities.(0), + peers2.(i).availabilities.(1), + false) in + avail.(i) <- a + done; + Array.sort compare avail; + let nrounds = float_of_int nrounds in + + let avail_error = ref [] in + let oc = open_out ( + Printf.sprintf "%s/ping_availability_%d.txt" subdir degree) in + for i = 0 to npeers - 1 do + let (a0,a1,selfish) = avail.(i) in + let a0 = float_of_int a0 in + let a1 = float_of_int a1 in + let a = (a0,a1,selfish) in + avail_error := (abs_float (a0 -. a1) /. nrounds) :: !avail_error; + let print oc (a0,a1,_) = + + output_string oc (Printf.sprintf "%d " i); + output_string oc (Printf.sprintf "%.3f " (a0 /. nrounds)); + output_string oc (Printf.sprintf "%.3f " (a1 /. nrounds)); + output_string oc "\n" + in + print oc a + done; + close_out oc; + !avail_error + + in + cdf_of_list string_of_float + (Printf.sprintf "%s/ping_error_avail_%d" subdir degree) avail_error + "set yrange [0:0.1]" "CDF of peers" "Error in measured availability" + " title 'error'"; + () diff --git a/sources/fabrice/pacemaker/userand.ml b/sources/fabrice/pacemaker/userand.ml new file mode 100644 index 0000000..c4e8958 --- /dev/null +++ b/sources/fabrice/pacemaker/userand.ml @@ -0,0 +1,7 @@ +open BigEndian + +let random filename = + let ic = open_in filename in + let s = String.create (4*4096) in + +
\ No newline at end of file diff --git a/sources/fabrice/pacemaker/usetrace.ml b/sources/fabrice/pacemaker/usetrace.ml new file mode 100644 index 0000000..fa88581 --- /dev/null +++ b/sources/fabrice/pacemaker/usetrace.ml @@ -0,0 +1,783 @@ +open SafeCaml +open Pervasives + +open Sets +open SimulTrace +open SimulTypes +open SimulGraphes + +let _ = + Printf.printf "VERSION 2.2\n%!" + +let day = 60 * 24 +(* Compute peers_per_round *) + +type parent_state = +| AskRoot +| Parent of int +| AskPeer of int + +type peer_com = + Idle of int +| Ticket of int +| ReceivingTicket of int + +module Bitmap : sig + + type t + + val create : unit -> t + val mem : t -> int -> bool + val add : t -> int -> unit + + end = struct + + type t = { + bitmap : string; + mutable min_time : int; + } + + let size = 100 + + let create () = { + bitmap = String.make size '0'; + min_time = 0; + } + + let mem t pos = + if pos < t.min_time then true else + if pos < t.min_time + size then t.bitmap.[ + pos mod size + ] = '1' else + false + + let rec add t pos = + if pos < t.min_time then () else + if pos < t.min_time + size then + t.bitmap.[ + pos mod size + ] <- '1' else + begin + t.min_time <- t.min_time + 1; + t.bitmap.[ + (t.min_time + size - 1) mod size + ] <- '0'; + add t pos + end + + end + + +let _ = + let t = Bitmap.create () in + Bitmap.add t 30; + assert (Bitmap.mem t 30); + assert (not (Bitmap.mem t 31)); + Bitmap.add t 150; + assert (Bitmap.mem t 150); + assert (not (Bitmap.mem t 151)); + assert (not (Bitmap.mem t 149)); + assert (Bitmap.mem t 30); + assert (Bitmap.mem t 31); + () + +type peer = { + mutable incoming : IntSet.t; + mutable tickets : IntSet.t; + bitmap : Bitmap.t; + mutable availabilities : int array; + parents : parent_state array; + children : ChildrenArray.t; + mutable rooted : (int list * int) option; + mutable distance : int; + mutable ncandidates : int; + mutable candidates : (int * peer * int) list; + mutable selfish : bool; + } + +let accuracy = ref 60 +let root_degree = ref 10 +let ndays = ref 0 +let degree = ref 5 +let nselfish = ref 0 +let subdir = ref None + +let anon_args = ref [ Sys.argv.(0) ] + +let _ = + Arg.parse [ + "-subdir", Arg.String (fun s -> + subdir := Some s), "<subdir> : set subdir for data files"; + "-ndays", Arg.Int ((:=) ndays), " <n> : number of days"; + "-accuracy", Arg.Int ((:=) accuracy), " <n>: period between heartbeats"; + "-root_degree", Arg.Int ((:=)root_degree), " <n> : root degree"; + "-degree", Arg.Int ((:=)degree), " <n> : peer degree"; + "-nselfish", Arg.Int ((:=)nselfish), " <n> : number of selfish nodes"; + ] + (fun t -> anon_args := t :: !anon_args) "" + +let subdir = + match !subdir with + None -> failwith "You must specify a subdirectory for data files" + | Some dir -> + Unix2.safe_mkdir (Filename2.of_string dir); + dir +let accuracy = !accuracy +let root_degree = !root_degree +let degree = !degree + +let argv = Array.of_list (List.rev !anon_args) +let trace = if Array.length argv > 1 then argv.(1) else "trace.dat" + + +let _ = + if trace = "" then failwith "You must at least specify the name of the trace file"; + Random.self_init () + +let peers, nrounds, do_round = trace_read trace + +let npeers = Array.length peers + +let nselfish = !nselfish * npeers / 100 + +let nrounds = + if !ndays <> 0 then + day * !ndays + else nrounds + +let peers_per_round = Array.create nrounds 0 +let sessions = ref [] +let first_connection = ref [] + +let peers2 = Array.init npeers (fun _ -> + { + incoming = IntSet.empty; + tickets = IntSet.empty; + bitmap = Bitmap.create (); + availabilities = [| 0; 0 |]; + parents = Array.create degree AskRoot; + children = ChildrenArray.create degree; + rooted = None; + distance = 10000; + candidates = []; + ncandidates = 0; + selfish = false; + }) + +let _ = + let rec iter () = + let n = Random.int npeers in + if peers2.(n).selfish then iter () else + peers2.(n).selfish <- true + in + for i = 1 to nselfish do + iter () + done + +let cursor = ref 0 +let root_nchildren = ref 0 +let root_children = Array.create root_degree None + + +let ask_peer i p p2 c x = +(* Printf.printf "ask_peer: %d -> %d\n" i x; *) +(* let px = peers.(x) in *) + let px2 = peers2.(x) in + + if ChildrenArray.length px2.children < degree then + if (ChildrenArray.mem px2.children i) then + p2.parents.(c) <- AskRoot + else begin +(* Printf.printf " Setting as parent\n"; *) + if px2.ncandidates < 100 then begin + px2.candidates <- (i, p2,c) :: px2.candidates; + px2.ncandidates <- px2.ncandidates + 1; + end + + end else begin + let rec retry () = +(* Printf.printf " Already full\n"; *) + let y = ChildrenArray.random px2.children in + if y = i then + retry () + else + p2.parents.(c) <- AskPeer y + in + retry () + end + +let max_distances = Array.create nrounds 0 +let ask_root_msgs = Array.create nrounds 0 + +let ask_root round i p p2 = + ask_root_msgs.(round) <- ask_root_msgs.(round) + 1; + let n = min !root_nchildren degree in + let rec iter n list = + if n > 0 then begin + if !cursor >= !root_nchildren then cursor := 0; + let c = match root_children.(!cursor) with + None -> assert false + | Some c -> c + in + + incr cursor; + iter (n-1) (c :: list) + end else list + in + let list = iter n [] in + if !root_nchildren < root_degree then + (-1) :: list + else list + +let ndistances = 10 +let mean_avail = Array.init (1+ndistances) (fun _ -> + Array.create nrounds 0) + +let root_ncandidates = ref 0 +let root_candidates = ref [] +let current_ticket = ref (-1) + +let print_graph round = + + Printf.printf "graph %d...\n%!" round; + let filename = Filename.of_string (Printf.sprintf "%s/graph_%06d.dot" subdir round) in + let oc = open_out filename in + output_string oc "digraph \"Network\" {\n"; + + output_string oc " root [ label = \"Root\" ];\n"; + for i = 0 to npeers - 1 do + let p = peers.(i) in + let p2 = peers2.(i) in + + if p.state = ON then + output_string oc (Printf.sprintf +(* " p%d [ label = \"%d (%d/%d)\" ];\n" i i p2.distance *) + " p%d [ label = \"%d/%d\" ];\n" i + p2.distance p.session ); + done; + + for k = 0 to !root_nchildren - 1 do + match root_children.(k) with + None -> assert false + | Some x -> + output_string oc (Printf.sprintf " root -> p%d\n" x) + done; + + for i = 0 to npeers - 1 do + let p = peers.(i) in + let p2 = peers2.(i) in + if p.state = ON then + ChildrenArray.iteri (fun _ x -> + output_string oc (Printf.sprintf " p%d -> p%d\n" i x) ) + p2.children + done; + + output_string oc "}\n"; + close_out oc + + + +let lost_tickets = Array.create (2+nrounds/accuracy) 0 + +let _ = + let hour = ref 0 in + let next_ticket = ref (Random.int accuracy) in + let peers_on = Array.create npeers 0 in + + for round = 0 to nrounds - 1 do + + do_round round; + + let rec iter_children i = + if i < !root_nchildren then + match root_children.(i) with + Some x -> + if peers.(x).state <> ON then begin + root_children.(i) <- root_children.(!root_nchildren-1); + root_nchildren := !root_nchildren - 1; + iter_children i + end else + iter_children (i+1) + | _ -> iter_children (i+1) + in + iter_children 0; + + let npeers_on = ref 0 in + for i = 0 to npeers -1 do + let p = peers.(i) in + let p2 = peers2.(i) in + + + + (* + Printf.printf "PEER: %d %d %d %d %d - %d %d %d\n" + (IntSet.cardinal p2.incoming) + (IntSet.cardinal p2.tickets) + (String.length p2.bitmap) + (Array.length p2.availabilities) + (Array.length p2.parents) + + (match p2.rooted with + None -> 0 | Some (list,_) -> List.length list) + p2.ncandidates + (List.length p2.candidates); +*) + +(* +type peer = { + mutable incoming : IntSet.t; + mutable tickets : IntSet.t; + bitmap : string; + mutable availabilities : int array; + parents : parent_state array; + children : ChildrenArray.t; + mutable rooted : (int list * int) option; + mutable distance : int; + mutable ncandidates : int; + mutable candidates : (int * peer * int) list; + mutable selfish : bool; + } +*) + + + if p.state = ON then begin + p2.availabilities.(0) <- p2.availabilities.(0) + 1; + p.session <- p.session + 1; + peers_on.(!npeers_on) <- i; + incr npeers_on; + + if p2.distance < 10000 then p2.distance <- 1000; + + for i = 0 to degree - 1 do + match p2.parents.(i) with + | Parent (-1) -> () + | Parent x | AskPeer x -> + if peers.(x).state <> ON then + p2.parents.(i) <- AskRoot + | _ -> () + done; + + ChildrenArray.iteri (fun i x -> + if peers.(x).state <> ON then + ChildrenArray.remove p2.children i) + p2.children; + + end else + if p.session > 0 then begin + sessions := p.session :: !sessions; + p.session <- 0; + for i = 0 to degree - 1 do + p2.parents.(i) <- AskRoot; + done; + p2.rooted <- None; + ChildrenArray.clear p2.children; + p2.distance <- 10000; + end; + +(* Clean the tables *) + + + done; + peers_per_round.(round) <- !npeers_on; + +(* Printf.printf "ROUND %d\n" round; *) + let to_do = Fifo.create () in + let max_distance = ref 0 in + for i = 0 to !root_nchildren - 1 do + match root_children.(i) with + None -> () + | Some x -> +(* Printf.printf "ROOT->%d\n" x; *) + if peers2.(x).distance = 10000 then + first_connection := peers.(x).session :: !first_connection; + peers2.(x).distance <- 1; + Fifo.put to_do x + done; + + let rec iter () = + if not (Fifo.empty to_do) then + let x = Fifo.take to_do in + let p2 = peers2.(x) in +(* Printf.printf "PEER %d\n" x; *) + let distance = p2.distance + 1 in + max_distance := max distance !max_distance; + ChildrenArray.iteri (fun _ x -> + let p2 = peers2.(x) in +(* Printf.printf " CHILD %d\n" x; *) + if p2.distance > distance then begin +(* Printf.printf " ->%d\n" x; *) + if peers2.(x).distance = 10000 then + first_connection := peers.(x).session :: !first_connection; + + p2.distance <- distance; + Fifo.put to_do x + end + ) p2.children; + iter () + + in + iter (); + max_distances.(round) <- !max_distance; +(* Printf.printf "Max distance: %d\n" !max_distance; *) + + + let _one_ticket = ref (-1) in + let _another_ticket = ref false in + for x = 0 to !npeers_on - 1 do + let i = peers_on.(x) in + + let p2 = peers2.(i) in + + let waiting_tickets = p2.tickets in + p2.tickets <- p2.incoming; + p2.incoming <- IntSet.empty; + + IntSet.iter (fun hour -> + if not (Bitmap.mem p2.bitmap hour) then begin + Bitmap.add p2.bitmap hour; + p2.availabilities.(1) <- p2.availabilities.(1) + accuracy; + if p2.selfish then () else begin + ChildrenArray.iteri (fun _ x -> + if x <= i then begin + if not (Bitmap.mem peers2.(x).bitmap hour) then + peers2.(x).tickets <- + IntSet.add hour peers2.(x).tickets + end else begin + if not (Bitmap.mem peers2.(x).bitmap hour) then + peers2.(x).incoming <- + IntSet.add hour peers2.(x).incoming + end + ) p2.children + end + end + ) waiting_tickets; + + (* + match p2.com with + Ticket hour -> + one_ticket := max hour !one_ticket; + p2.com <- Idle hour; + + + | ReceivingTicket hour -> + p2.com <- Ticket hour; + another_ticket := true +| _ -> () + *) + done; + +(* + if !one_ticket >= 0 && not !another_ticket then begin + for x = 0 to !npeers_on - 1 do + let i = peers_on.(x) in + let p = peers.(i) in + let p2 = peers2.(i) in + if round - p.session <= !current_ticket then + match p2.com with + Idle n when n < !one_ticket -> + lost_tickets.(!hour) <- lost_tickets.(!hour) + 1 + | _ -> () + done + end; +*) + +(* Printf.printf ".%!"; *) +(* Build the network: +- We should use Bittorrent optimistic policy: we keep 4/5*degree slots +for peers p with avail(p) > avail(me)/2, and 1/5*degree slots for other +peers. +- A first step would at least to sort connecting peers _before_ accepting +one. +*) + + root_ncandidates := 0; + root_candidates := []; + + for n = 1 to !npeers_on do + let x = Random.int !npeers_on in + let i = peers_on.(x) in + peers_on.(x) <- peers_on.(!npeers_on-1); + decr npeers_on; + + let p = peers.(i) in + let p2 = peers2.(i) in + + for c = 0 to degree-1 do + match p2.parents.(c) with + Parent _ -> () + | AskRoot -> + let rec retry () = + match p2.rooted with + None -> + let list = ask_root round i p p2 in + p2.rooted <- Some (list, round); + retry () + | Some ([], r) when r = round -> () + | Some ([],_) -> + let list = ask_root round i p p2 in + p2.rooted <- Some (list, round); + retry () + | Some (x :: tail,r) -> + p2.rooted <- Some (tail, r); + + let found = ref (x = i) in + for k = 0 to degree - 1 do + match p2.parents.(k) with + AskPeer y when y = x -> found := true + | Parent y when y = x -> found := true + | _ -> () + done; + if !found then + retry () + else + if x = -1 then begin + let found = ref false in + List.iter (fun (ii,_,_) -> + if ii = i then found := true) !root_candidates; + if not !found then begin +(* Printf.printf "adding %d\n" i; *) + if !root_ncandidates < 100 then begin + incr root_ncandidates; + root_candidates := (i,p2,c) :: !root_candidates + end; + end + end else + if r = round then + p2.parents.(c) <- AskPeer x + else + ask_peer i p p2 c x + in + retry () + | AskPeer x -> + ask_peer i p p2 c x + + done; + + ChildrenArray.iteri (fun i x -> + if peers2.(x).distance = p2.distance then begin + ChildrenArray.remove p2.children i; + for k = 0 to degree - 1 do + if peers2.(x).parents.(k) = Parent p.i then + peers2.(x).parents.(k) <- AskRoot + done + end + ) p2.children + + done; + + + root_candidates := List.sort (fun (_,p1,_) (_,p2,_) -> + p2.availabilities.(1) - p1.availabilities.(1)) !root_candidates; +(* List.iter (fun (i,p,_) -> + Printf.printf " Cand %d %d\n" i p.availabilities.(1)) !root_candidates; +*) + + let rec iter list = + if !root_nchildren < root_degree then + match list with + [] -> () + | (i1,_,_) :: ( ( (i2,_,_) :: _ ) as tail) when i1 = i2 -> + iter tail + | (i,p2,c) :: tail -> + p2.parents.(c) <- Parent (-1); + root_children.(!root_nchildren) <- Some i; + incr root_nchildren; + iter tail + in + iter !root_candidates; + + + for i = 0 to npeers - 1 do + let p = peers.(i) in + if p.state = ON then + let px2 = peers2.(i) in + if px2.candidates <> [] then + let candidates = px2.candidates in + px2.ncandidates <- 0; + px2.candidates <- []; + let candidates = List.sort (fun (_,p1,_) (_,p2,_) -> + p2.availabilities.(1) - p1.availabilities.(1)) + candidates in + + let rec iter list = + if ChildrenArray.length px2.children < degree then + match list with + [] -> () + | (i1,_,_) :: ( ( (i2,_,_) :: _ ) as tail) when i1 = i2 -> + iter tail + | (i,p2,c) :: tail -> + ChildrenArray.add px2.children i; + p2.parents.(c) <- Parent p.i; + iter tail + else + List.iter (fun (i,p2,c) -> + let rec retry () = + let y = ChildrenArray.random px2.children in + if y = i then + retry () + else + p2.parents.(c) <- AskPeer y + in + retry () + + ) list + in + iter candidates + + done; + + if round = !next_ticket then begin + current_ticket := round; + incr hour; + next_ticket := accuracy * !hour + Random.int accuracy; + + for i = 0 to !root_nchildren - 1 do + match root_children.(i) with + None -> () + | Some x -> + peers2.(x).tickets <- IntSet.add !hour peers2.(x).tickets + done; + end; + + + let avail = Array.create (ndistances + 1) 0 in + let npeers_per_dist = Array.create (ndistances + 1) 0 in + for i = 0 to npeers - 1 do + + let p = peers.(i) in + let p2 = peers2.(i) in + + if p.state = ON && p2.distance <= ndistances then begin + + avail.(p2.distance) <- avail.(p2.distance) + p2.availabilities.(0); + npeers_per_dist.(p2.distance) <- npeers_per_dist.(p2.distance) + 1; + + end + + done; + + for i = 1 to ndistances do + if npeers_per_dist.(i) <> 0 then + let x = 1000. *. float_of_int avail.(i) + /. float_of_int npeers_per_dist.(i) + /. float_of_int (1+round) in +(* Printf.printf "avail %d = %.4f\n" i x; *) + mean_avail.(i).(round) <- + + int_of_float (x); + done; +(* print_graph round *) + done + +let _ = + print_graph 0 + + +let _ = + value_per_time string_of_int + (Printf.sprintf "%s/peers_per_round" subdir) + peers_per_round "available peers"; + value_per_time string_of_int + (Printf.sprintf "%s/ask_root_msgs" subdir) + ask_root_msgs "ask root msgs"; + value_per_time string_of_int + (Printf.sprintf "%s/max_distance_per_round" subdir) + max_distances "maximal distance"; + let max_distance = ref 0 in + for i = 0 to nrounds - 1 do + max_distance := max !max_distance max_distances.(i) + done; + let max_distance = min !max_distance ndistances in + for i = 1 to max_distance do + value_per_time string_of_int (Printf.sprintf "%s/mean_avail_distance%d" subdir i) + mean_avail.(i) + (Printf.sprintf "mean availability at distance %d" i); + done; + () + + + +let avail_error = + Printf.printf "availability...\n%!"; + let avail = Array.create npeers (0,0,false) in + for i = 0 to npeers - 1 do + let a = ( + peers2.(i).availabilities.(0), + peers2.(i).availabilities.(1), + peers2.(i).selfish) in + avail.(i) <- a + done; + Array.sort compare avail; + + let avail_error = ref [] in + let filename = Filename.of_string + (Printf.sprintf "%s/availability.txt" subdir + ) in + let oc = open_out filename in +(* let oc1 = open_out "availabilityS.txt" in (* selfish *) *) +(* let oc2 = open_out "availabilityC.txt" in (* correct *) *) + for i = 0 to npeers - 1 do + let (a0,a1,selfish) = avail.(i) in + let nrounds = float_of_int nrounds in + let a0 = float_of_int a0 in + let a1 = float_of_int a1 in + let a = (a0,a1,selfish) in + avail_error := (abs_float (a0 -. a1) /. nrounds) :: !avail_error; + let print oc (a0,a1,_) = + + output_string oc (Printf.sprintf "%d " i); + output_string oc (Printf.sprintf "%.3f " (a0 /. nrounds)); + output_string oc (Printf.sprintf "%.3f " (a1 /. nrounds)); + output_string oc "\n" + in + print oc a; +(* if selfish then print oc1 a else print oc2 a *) + done; + close_out oc; +(* close_out oc1; + close_out oc2; *) + !avail_error + +let _ = + cdf_of_list string_of_int + (Printf.sprintf "%s/sessions" subdir) !sessions + "set logscale y\n" + "CDF of sessions" "Session Length (minutes)" + " title 'Sessions', 60 title '1 hour'"; + cdf_of_list string_of_int + (Printf.sprintf "%s/connections" subdir) + !first_connection "" "CDF of connections" + "Time to first connection (minutes)" + " title 'Time (minutes)'"; + +(* value_per_time "lost_tickets" lost_tickets "lost heartbeats"; *) + cdf_of_list string_of_int (Printf.sprintf "%s/lost_tickets" subdir) + (Array.to_list lost_tickets) "" "CDF of rounds" + "Number of lost heartbeats" + " title ' heartbeats'"; + cdf_of_list string_of_float + (Printf.sprintf "%s/error_avail" subdir) avail_error + "set yrange [0:0.1]" "CDF of peers" "Error in measured availability" + " title 'error'"; + + + +(* +let _ = + for i = 0 to npeers - 1 do + + let p = peers.(i) in + let p2 = peers2.(i) in + + + if p.state then begin + let nparents = ref 0 in + for i = 0 to degree - 1 do + match p2.parents.(i) with + Parent x -> incr nparents + | _ -> () + done; + Printf.printf "PEER %d %d %d %d\n" i p.session p2.distance !nparents + end + done + *) diff --git a/sources/fabrice/simulator/build.ocp b/sources/fabrice/simulator/build.ocp new file mode 100644 index 0000000..d2beede --- /dev/null +++ b/sources/fabrice/simulator/build.ocp @@ -0,0 +1,13 @@ + pp = "camlp4o.opt" + +begin "simul" + files = [ + "randomArray.ml"; + "simulTypes.ml"; + "simulGraphes.ml"; + "simulTrace.ml"; + ] + requires = [ "cdk"; "net" ] +end + + diff --git a/sources/fabrice/simulator/notes.txt b/sources/fabrice/simulator/notes.txt new file mode 100644 index 0000000..fb8bdc8 --- /dev/null +++ b/sources/fabrice/simulator/notes.txt @@ -0,0 +1,15 @@ + peerolyse:~/devel/onzego% time ./research/p2p_avail/gentrace trace_10000x1000_1 10000 1000 +./research/p2p_avail/gentrace trace_10000x1000_1 10000 1000 1183.25s user 2.83s system 99% cpu 19:46.89 total + + + + peerolyse:~/articles/p2p_avail_metro/simulation% time gentrace trace_500x365_1 500 365 +gentrace trace_500x365_1 500 365 22.19s user 0.05s system 99% cpu 22.267 total + + +In the current implementation of gentrace, all the timezones are in the +first 12 hours. + + +To obtain big graphs, don't use -Tps, but Tjpg with display + dot -Tjpg graph_000000.dot -o graph.jpg diff --git a/sources/fabrice/simulator/randomArray.ml b/sources/fabrice/simulator/randomArray.ml new file mode 100644 index 0000000..4f5ddf9 --- /dev/null +++ b/sources/fabrice/simulator/randomArray.ml @@ -0,0 +1,73 @@ + +module type INTERFACE = sig + + type 'a t + + val init : int -> (int -> 'a) -> 'a t + val length : 'a t -> int + val of_list : 'a list -> 'a t + val add : 'a t -> 'a -> unit + val random : 'a t -> 'a + val reset : 'a t -> unit + val set_state : 'a t -> Random.State.t -> unit + end + +module IMPLEMENTATION = struct + + type 'a t = { + mutable length : int; + mutable left : int; + array : 'a array; + mutable state : Random.State.t; + } + + let init len f = + let array = Array.init len f in + { + array = array; + length = len; + left = len; + state = Random.get_state (); + } + + let of_list list = + let array = Array.of_list list in + let len = Array.length array in + { + array = array; + length = len; + left = len; + state = Random.get_state (); + } + + let length t = t.length + + let add t x = + let len = t.length in + t.array.(len) <- x; + t.length <- len + 1; + if len = t.left then + t.left <- len + 1 + + let random t = + if t.left <= 0 then raise Not_found; + let pos = Random.State.int t.state t.left in + let tab = t.array in + let len = t.left-1 in +(* Printf.fprintf stderr "SWAP(%d)(%d)%!" pos len; *) + let x = tab.(pos) in + tab.(pos) <- tab.(len); + tab.(len) <- x; + t.left <- len; + x + + let reset t = + t.left <- t.length + + let set_state t state = t.state <- state + + end + +include (IMPLEMENTATION : INTERFACE) + +
\ No newline at end of file diff --git a/sources/fabrice/simulator/simulGraphes.ml b/sources/fabrice/simulator/simulGraphes.ml new file mode 100644 index 0000000..e179d48 --- /dev/null +++ b/sources/fabrice/simulator/simulGraphes.ml @@ -0,0 +1,129 @@ + +let int_of_string s = + try + int_of_string s + with e -> + failwith (Printf.sprintf "int_of_string: error with [%s]" (String.escaped s)) + +let on_file filename = + let ic = open_in filename in + let count = ref 0 in + let mins = ref [||] in + let maxs = ref [||] in + (try + let line = input_line ic in + incr count; + let line = String2.split_simplify line ' ' in + mins := Array.create (List.length line) 0.; + maxs := Array.create (List.length line) 0.; + let mins = !mins in + let maxs = !maxs in + List2.iteri (fun i x -> + let x = float_of_string x in + mins.(i) <- x; + maxs.(i) <- x) line; + while true do + let line = input_line ic in + incr count; + let line = String2.split_simplify line ' ' in + List2.iteri (fun i x -> + let x = float_of_string x in + mins.(i) <- min x mins.(i); + maxs.(i) <- max x maxs.(i)) line; + done + + with End_of_file -> ()); + !count, !mins, !maxs + + +let value_per_time x_of_y filename int_table element = + Printf.printf "%s...\n%!" filename; + let oc = open_out (Printf.sprintf "%s.txt" filename) in + let maximum = ref int_table.(0) in + let nrounds = Array.length int_table in + for round = 0 to nrounds - 1 do + maximum := max !maximum int_table.(round); + output_string oc (Printf.sprintf "%d %s\n" round + (x_of_y int_table.(round))) + done; + close_out oc; + + let oc = open_out (Printf.sprintf "%s.plot" filename) in + output_string oc (Printf.sprintf " +set out '%s.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out '%s.eps' +set yrange [0:%s+1] +set xrange [0:%d] +set ylabel 'Number of %s' +set xlabel 'Time (minutes)' + +set data style lines + +plot \"%s.txt\" using ($1):($2) title '%s' + " filename filename (x_of_y !maximum) nrounds element filename element); + close_out oc + + + + let npoints = 1000 + +let cdf_of_list x_of_y filename int_list options xlabel ylabel end_plot = + Printf.printf "%s...\n%!" filename; + match int_list with + [] -> Printf.printf " not enough data\n" + | init :: _ -> + let int_list = List.sort compare int_list in + let nints = List.length int_list in + + let oc = open_out (Printf.sprintf "%s.txt" filename) in + let maximum = ref init in + List2.iteri (fun i x -> + maximum := max !maximum x; + output_string oc (Printf.sprintf "%d %s\n" i + (x_of_y x)) + ) int_list; + close_out oc; + + let every = + if nints > npoints then + Printf.sprintf " every %d " (nints / npoints) else "" in + + let oc = open_out (Printf.sprintf "%s.plot" filename) in + output_string oc (Printf.sprintf " +set out '%s.eps' +set terminal postscript eps enhanced \"Helvetica\" 14 +set out '%s.eps' +set yrange [1:%s+1] +set xrange [0:%d] +set ylabel '%s' +set xlabel '%s' +set data style lines + +%s + +plot \"%s.txt\" %s using ($1):($2) %s + " filename filename (x_of_y !maximum) (nints+2) ylabel xlabel options filename every end_plot); + close_out oc + + +let for_every every filename = + let ic = open_in filename in + let nlines = ref 0 in + let line = ref "" in + try + while true do + line := input_line ic; + incr nlines + done + with End_of_file -> + close_in ic; + if !nlines > 0 then + let x = (!nlines - 1) mod every in + if x > 0 then + let oc = open_out_gen [Open_append] 0o644 filename in + for i = x to every-1 do + Printf.printf "adding line\n"; + Printf.fprintf oc "%s\n" !line + done; + close_out oc diff --git a/sources/fabrice/simulator/simulTrace.ml b/sources/fabrice/simulator/simulTrace.ml new file mode 100644 index 0000000..b58bf41 --- /dev/null +++ b/sources/fabrice/simulator/simulTrace.ml @@ -0,0 +1,162 @@ +open SimulTypes +open SimulGraphes + +type trace_event = + Peers of int +| Days of int * int +| Peer of int * float * string +| Round of int +| On of int +| Off of int +| Dead of int +| End +| Exponential + +let trace_output oc trace_event = + output_string oc (match trace_event with + Peers npeers -> Printf.sprintf "Peers %d\n" npeers + | Days (ndays, day) -> Printf.sprintf "Days %d %d\n" ndays day + | Peer (i,avail,s) -> + Printf.sprintf "Peer %d %.3f %s\n" i avail s + | Round round -> Printf.sprintf "Round %d\n" round + | On i -> Printf.sprintf "On %d\n" i + | Off i -> Printf.sprintf "Off %d\n" i + | Dead i -> Printf.sprintf "Dead %d\n" i + | End -> "End\n" + | Exponential -> "Exponential\n" + ) + +let trace_input ic = + let line = input_line ic in + match String2.split line ' ' with + ["Peers"; npeers] -> Peers (int_of_string npeers) + | ["Days"; ndays] -> Days (int_of_string ndays, 24 * 60) + | ["Days"; ndays; day] -> Days (int_of_string ndays, int_of_string day) + | "Peer" :: i :: avail :: tail -> + Peer (int_of_string i, float_of_string avail, String2.unsplit tail ' ') + | ["End"] -> End + | ["Exponential"] -> Exponential + | ["Round"; round] -> Round (int_of_string round) + | ["On"; i] -> On (int_of_string i) + | ["Dead"; i] -> Dead (int_of_string i) + | ["Off"; i] -> Off (int_of_string i) + + | _ -> failwith (Printf.sprintf "Bad line [%s]" (String.escaped line)) + +let print_distribution = ref false +(* gnuplot> plot exp(1-log(2+65*x)), 1.0/12 *) + +let exponential = ref false +let distribution = ref [] +let availability = ref [] + +let trace_read filename = + let ic = open_in filename in + let npeers = match trace_input ic with + Peers npeers -> npeers + | _ -> assert false + in + let (ndays, day) = match trace_input ic with + Days (ndays, day) -> ndays, day + | _ -> assert false + in + + let rec read_peer ii = + match trace_input ic with + Exponential -> exponential := true; + read_peer ii + | Peer (i, avail, s) -> + assert (i=ii); +(* + let x = float_of_int avail /. 900000. in + + let avail = (if !exponential then + max 0.02 (min 1. (exp(1. -. log(2. +. 65. *. x)))) + else + 0.02 +. 0.98 *. x + ) + in + if !print_distribution then begin + distribution := x :: !distribution; + availability := avail :: !availability; + end; + let lambda = float_of_int decs /. (60. *. 24.) in + let mu = avail *. lambda /. (1. -. avail) in + *) + let p = { + i = i; + avail = avail; + descr = s; + session = 0; + day = true; + state = OFF; + real_avail = 0; + real_decs = 0; + } in + p + | _ -> assert false + in + let peers = Array.init npeers read_peer in + let event = ref None in + let get_event () = + let ev = trace_input ic in + event := Some ev + in + + let next_day = ref 0 in + let begin_time = (Int64.of_float (Unix.gettimeofday ())) in + let rec iter_round round = + match !event with + None -> + next_event round + | Some ev -> + match ev with + Round rr -> + if rr = round then begin + if !next_day = round then begin + let time = Unix.gettimeofday () in + let time = Int64.of_float time in + Printf.printf "Day %d (%Ld)\n%!" (round / day) + (Int64.sub time begin_time); + next_day := !next_day + day + end; + next_event round + end else + assert (rr > round) + | On i -> + event := None; + let p = peers.(i) in + p.state <- ON; + next_event round + | Off i -> + event := None; + let p = peers.(i) in + p.state <- OFF; + p.real_decs <- p.real_decs + 1; + next_event round + | Dead i -> + event := None; + let p = peers.(i) in + p.state <- DEAD; + peers.(i) <- { + p with state = OFF; + }; + next_event round + | End -> () + | _ -> assert false + + and next_event round = + get_event (); + iter_round round + in + if !print_distribution then begin + cdf_of_list string_of_float "dist_random" !distribution + "set yrange [0:1]" "CDF of peers" "Distribution" + " title 'random'"; + cdf_of_list string_of_float "dist_availability" !availability + "set yrange [0:1]" "CDF of peers" "Distribution" + " title 'avail'"; + distribution := []; + availability := []; + end; + peers, ndays * day, iter_round diff --git a/sources/fabrice/simulator/simulTypes.ml b/sources/fabrice/simulator/simulTypes.ml new file mode 100644 index 0000000..7d76049 --- /dev/null +++ b/sources/fabrice/simulator/simulTypes.ml @@ -0,0 +1,91 @@ + +type state = ON | OFF | DEAD + +type peer = { + i : int; + + descr : string; + + avail : float; + mutable session : int; + mutable day : bool; + mutable state : state; + mutable real_avail : int; + mutable real_decs : int; + } + + +let _ = Random.self_init () + + +module ChildrenArray : sig + + type t + + val length : t -> int + val create : int -> t + val mem : t -> int -> bool + val add : t -> int -> unit + val iteri : (int -> int -> unit) -> t -> unit + val remove : t -> int -> unit + val random : t -> int + val clear : t -> unit + + val of_list : int list -> t + + end = struct + + type t = { + mutable length : int; + array : int array; + } + + let create n = { + length = 0; + array = Array.create n 0; + } + + let clear t = t.length <- 0 + + let add t i = + let len = t.length in + t.array.(len) <- i; + t.length <- len + 1 + + let remove t pos = + let tab = t.array in + let len = t.length-1 in + tab.(pos) <- tab.(len); + t.length <- len + + let length t = t.length + + let iteri f t = + let rec iter i t = + let len = t.length in + if i < len then begin + f i t.array.(i); + if len > t.length then iter i t else + iter (i+1) t + end + in + iter 0 t + + let mem t v = + let rec iter i t = + (i < t.length) && + (t.array.(i) = v || iter (i+1) t) + in + iter 0 t + + let random t = + t.array.(Random.int t.length) + + let of_list list = + let array = Array.of_list list in + { + array = array; + length = Array.length array; + } + + end |