Added sources of simulator and emulator

git-svn-id: https://scm.gforge.inria.fr/svn/pacemaker@2 30fcff6e-8de6-41c7-acce-77ff6d1dd07b

6 files changed, 483 insertions, 0 deletions

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