--- /dev/null
+#!/usr/bin/perl -w
+use strict;
+
+use AlvinMisc;
+use graph_viz;
+use graph_tbx;
+use tiers;
+
+my (%machine);
+$machine{"canaria.ens-lyon.fr"}{"CPU_clock"} = "347.669";
+$machine{"canaria.ens-lyon.fr"}{"CPU_Mflops"} = "34.333";
+$machine{"canaria.ens-lyon.fr"}{"CPU_model"} = "Pentium II (Deschutes)";
+$machine{"canaria.ens-lyon.fr"}{"CPU_num"} = "2";
+$machine{"canaria.ens-lyon.fr"}{"Machine_type"} = "i686";
+$machine{"canaria.ens-lyon.fr"}{"OS_version"} = "Linux 2.2.19pre17";
+
+$machine{"moby.ens-lyon.fr"}{"CPU_clock"} = "996.698";
+$machine{"moby.ens-lyon.fr"}{"CPU_Mflops"} = "114.444";
+$machine{"moby.ens-lyon.fr"}{"CPU_model"} = "Intel(R) Pentium(R) III Mobile CPU 1000MHz";
+$machine{"moby.ens-lyon.fr"}{"CPU_num"} = "1";
+$machine{"moby.ens-lyon.fr"}{"Machine_type"} = "i686";
+$machine{"moby.ens-lyon.fr"}{"OS_version"} = "Linux 2.4.18-accelerated";
+
+$machine{"popc0.ens-lyon.fr"}{"CPU_clock"} = "199.095";
+$machine{"popc0.ens-lyon.fr"}{"CPU_Mflops"} = "22.151";
+$machine{"popc0.ens-lyon.fr"}{"CPU_model"} = "Pentium Pro";
+$machine{"popc0.ens-lyon.fr"}{"CPU_num"} = "1";
+$machine{"popc0.ens-lyon.fr"}{"Machine_type"} = "i686";
+$machine{"popc0.ens-lyon.fr"}{"OS_version"} = "Linux 2.2.19";
+
+$machine{"sci0.ens-lyon.fr"}{"CPU_clock"} = "451.032446";
+$machine{"sci0.ens-lyon.fr"}{"CPU_Mflops"} = "48.492";
+$machine{"sci0.ens-lyon.fr"}{"CPU_model"} = "Pentium II (Deschutes)";
+$machine{"sci0.ens-lyon.fr"}{"CPU_num"} = "2";
+$machine{"sci0.ens-lyon.fr"}{"Machine_type"} = "i686";
+$machine{"sci0.ens-lyon.fr"}{"OS_version"} = "Linux 2.2.13";
+
+$machine{"lancelot.u-strasbg.fr"}{"OS_version"} = "Linux 2.2.17-21mdk";
+$machine{"lancelot.u-strasbg.fr"}{"CPU_clock"} = "400.916";
+$machine{"lancelot.u-strasbg.fr"}{"CPU_model"} = "Celeron (Mendocino)";
+$machine{"lancelot.u-strasbg.fr"}{"CPU_Mflops"} = "42.917000000000002";
+$machine{"lancelot.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"lancelot.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"caseb.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.8-26mdk";
+$machine{"caseb.u-strasbg.fr"}{"CPU_clock"} = "1399.763";
+$machine{"caseb.u-strasbg.fr"}{"CPU_model"} = "AMD Athlon(tm) 4 Processor";
+$machine{"caseb.u-strasbg.fr"}{"CPU_Mflops"} = "137.333";
+$machine{"caseb.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"caseb.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"pellinore.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.18-6mdksmp";
+$machine{"pellinore.u-strasbg.fr"}{"CPU_clock"} = "802.922";
+$machine{"pellinore.u-strasbg.fr"}{"CPU_model"} = "Pentium III (Coppermine)";
+$machine{"pellinore.u-strasbg.fr"}{"CPU_Mflops"} = "68.667000000000002";
+$machine{"pellinore.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"pellinore.u-strasbg.fr"}{"CPU_num"} = "2";
+
+$machine{"dinadan.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.19-686";
+$machine{"dinadan.u-strasbg.fr"}{"CPU_clock"} = "933.375";
+$machine{"dinadan.u-strasbg.fr"}{"CPU_model"} = "Pentium III (Coppermine)";
+$machine{"dinadan.u-strasbg.fr"}{"CPU_Mflops"} = "85.832999999999998";
+$machine{"dinadan.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"dinadan.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"darjeeling.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.18-5";
+$machine{"darjeeling.u-strasbg.fr"}{"CPU_clock"} = "1793.371";
+$machine{"darjeeling.u-strasbg.fr"}{"CPU_model"} = "Intel(R) Pentium(R) 4 CPU 1.80GHz";
+$machine{"darjeeling.u-strasbg.fr"}{"CPU_Mflops"} = "98.094999999999999";
+$machine{"darjeeling.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"darjeeling.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"gauvain.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.17";
+$machine{"gauvain.u-strasbg.fr"}{"CPU_clock"} = "1050.034";
+$machine{"gauvain.u-strasbg.fr"}{"CPU_model"} = "AMD Athlon(tm) Processor";
+$machine{"gauvain.u-strasbg.fr"}{"CPU_Mflops"} = "114.444";
+$machine{"gauvain.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"gauvain.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"sekhmet.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.18-k7";
+$machine{"sekhmet.u-strasbg.fr"}{"CPU_clock"} = "1399.803";
+$machine{"sekhmet.u-strasbg.fr"}{"CPU_model"} = "AMD Athlon(tm) 4 Processor";
+$machine{"sekhmet.u-strasbg.fr"}{"CPU_Mflops"} = "171.667";
+$machine{"sekhmet.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"sekhmet.u-strasbg.fr"}{"CPU_num"} = "1";
+
+$machine{"shaitan.u-strasbg.fr"}{"OS_version"} = "Linux 2.4.18-6mdk";
+$machine{"shaitan.u-strasbg.fr"}{"CPU_clock"} = "800.030";
+$machine{"shaitan.u-strasbg.fr"}{"CPU_model"} = "Pentium III (Coppermine)";
+$machine{"shaitan.u-strasbg.fr"}{"CPU_Mflops"} = "76.296000000000006";
+$machine{"shaitan.u-strasbg.fr"}{"Machine_type"} = "i686";
+$machine{"shaitan.u-strasbg.fr"}{"CPU_num"} = "1";
+
+my (%network);
+#0.587500,0.655,0.681
+
+$network{"bw"}{10} = [ [274285,0.514433], [330233,0.059904],
+ [949460,0.136931], [1063823,0.131098],
+ [2041829,7.413073] ];
+
+$network{"bw"}{100} = [ [64121,35.076518], [65264,0.270544],
+ [67418,0.156056], [80797,0.479780], [82517,6.932556],
+ [92951,0.189980], [94763,0.370788],
+ [123015,35.083019], [171318,295.890617],
+ [223570,0.278066], [274285,0.514433],
+ [330233,0.059904] ];
+
+$network{"bw"}{1000} = [ [937,53.930106], [2013,4.455826],
+ [2022,5.704550], [2025,5.652577], [2073,4.460898],
+ [2179,5.922616], [2195,4.669142], [2321,4.522355],
+ [2327,4.477270], [2427,4.062241], [2539,4.583831],
+ [3777,5.161451], [4448,3.101854], [4629,5.473705],
+ [4840,87.981858], [5773,0.006406], [6150,8.762440],
+ [7413,0.601375], [7837,0.424305], [7867,2.885584],
+ [7924,1.742977], [8394,9.647856], [9015,0.287840],
+ [9612,0.468130], [9842,1.502106], [10069,1.340162],
+ [10255,6.104672], [10609,1.402769], [11014,0.449267],
+ [11724,0.863872], [11741,0.869727], [11753,1.114548],
+ [12100,1.200141], [12122,0.844683], [12513,0.788956],
+ [13022,0.278175], [14341,7.877863], [14864,0.820952],
+ [15084,0.950938], [15111,1.081287], [15141,0.162735],
+ [15449,0.951830], [15797,0.380044], [15868,0.848211],
+ [17433,0.320114], [17819,0.907120], [17906,1.043314],
+ [18382,1.087968], [18788,0.259761], [18944,9.547561],
+ [20667,0.410463], [20864,0.637001], [22546,0.247605],
+ [24227,0.677908], [24547,0.040300], [25404,0.472524],
+ [26205,0.658142], [26382,0.595883], [26970,0.666676],
+ [27441,0.536941], [28416,3.870785], [29714,3.866813],
+ [31020,0.863123], [31452,1.913591], [31964,0.678645],
+ [33067,9.693542], [33378,0.728103], [34162,0.672289],
+ [34363,0.539000], [35178,0.677601], [35333,0.019773],
+ [35689,0.106949], [35881,0.126045], [37202,0.705967],
+ [37438,0.848712], [38536,0.117352], [38723,0.751810],
+ [39826,7.164412], [41518,0.630529], [41827,0.039417],
+ [42392,0.520693], [43729,0.272268], [44597,0.227430],
+ [45776,0.789218], [46068,4.760145], [46531,0.164758],
+ [52408,0.522878], [54216,0.533340], [57678,1.461517],
+ [60272,0.125428] ];
+
+sub assign_host_speed{
+ my($nodes,$edges) = @_;
+
+ my($u);
+
+ my(@label_list) = keys %machine;
+ foreach $u (keys %$nodes) {
+ my($mach_type_nb) = scalar(@label_list);
+ my($mach_type) = int rand($mach_type_nb);
+ $$nodes{$u}{Mflops} = $machine{$label_list[$mach_type]}{CPU_Mflops};
+ }
+}
+
+sub assign_host_names{
+ my($nodes,$edges) = @_;
+
+ my(@name_list) = qw(Abbott Adoncourt Aikin Alain Alfred Amadeus
+ Angie Anjou Anne_Marie Apple April Archibald
+ Aubertin Auclair Audy AutoCAD Barry BASIC
+ Beaudoin Beaulac Bellemarre Bellevue
+ Bell_Northern Benoit Bentz Bernard Bescherelle
+ Blais Boily Boivin Borduas Boston Boucherville
+ Bourassa Bousquet Boyer Brian Brosseau Brown
+ Browne Cadieux Cambridge Canada Carole
+ Casavant Chambly Charles Charron Christian
+ Claude Cloutier Colin Comeau Corp Coulombe
+ Cousineau Croteau Daniel Decelles Denis Denise
+ Desjardins Dick Dionne Disney Dodge Domey
+ Dominique Doris Dorval Doyon Drouin Dumoulin
+ EDF Emacs Ethernet Europe Fafard Fernand
+ Fernet Flamand Florient Foisy Forget Fourier
+ FrameMaker France Francine Frank Fraser
+ Freedman Gagnon Gaston Gatien Gaudreault
+ Gauthier Gavrel Gendron Gentilly Geoff
+ Geoffray George Georges Gilles Ginette Girard
+ Goodwin Gordon Gosselin Gratton Greg Gregory
+ Guy Harry Harwell Hayward Hollerbach Horne
+ Houde Hubert Hz Inc Inmos Intel Interleaf
+ Internet iRMX iRMXII iRMXIII Isabelle ISPELL
+ Jackson Jacobsen Jacquelin Jacques
+ Jacques_Cartier Jamie Jean Jean_Claude
+ Jean_Louis Jean_Maurice Jeannine Jean_Paul
+ Jean_Pierre Jean_Yves Jill Jobin Jocelyne John
+ Jones Joynes Jude Julian Julien Juneau Jupiter
+ Kansas Kent Khan King Kuenning kV Lachapelle
+ Laflamme Lafontaine Lamothe Lapointe Laroche
+ LaSalle LaTeX Laugier Laurendeau Laval Lavoie
+ Leblanc Lecavalier Leclerc Lepage Lessard
+ Letarte Linda LISP Longueuil Louis Louise
+ Louis_Marc Ltd Lucie Mahoney Maltais Manseau
+ Marc Marcel Marcoux Marie Marielle Mark
+ Marseille Martin Masson Mathematica Matlab
+ McGee McGill Messier METAFONT Michel Mike
+ Minneapolis Mireille Mongenot Monique
+ Mont_Tremblant Morin Morissette Moshe Mulhouse
+ mW Nagle Nelligan Nestor Nicole OHara Olivier
+ Ontario Ottawa Ouellet Owen Ozias Papineau
+ Paul Pellan Pelletier PERL Phaneuf Phil Pierre
+ Pierrefonds Plante Pointe_Claire PostScript
+ Poussart Pronovost Provost Raymond Re README
+ Renato Ricard Richard Ringuet Riopelle Rioux
+ Roberge Robert Rochefort Roger Romano Ronald
+ Roy Rubin Sacramento Saint_Amand Sainte_Foy
+ Sainte_Julie Saint_Marc_sur_Richelieu Seattle
+ Shawinigan Sherbrooke Sirois Smith Sorel Soucy
+ SPARC SPARCs SPICE St_Antoine St_Bruno
+ Ste_Anne Steele Ste_Julie Stephen St_Jacques
+ St_Jean St_Paul Strasbourg Sun SunOS Suzanne
+ Tanguay Tessier TeX Texas Thibault Thierry
+ Todd Tokyo Toronto Toulouse Tremblay Turcotte
+ Uintas UniPress Unix UNIX Utah Vancouver
+ Varennes Verville Victoria Victoriaville Viger
+ Vincent VxWorks Wilfrid William Williams
+ Wright Yolande Yvan Yves Zawinski);
+
+ AlvinMisc::melange(\@name_list);
+
+ my($u);
+ foreach $u (keys %$nodes) {
+ if($$nodes{$u}{host}==1) {
+ $$nodes{$u}{name} = shift @name_list;
+ }
+ }
+}
+
+sub assign_link_speed{
+ my($nodes,$edges) = @_;
+
+ my($e);
+
+ foreach $e (keys %$edges) {
+ my($bw) = $$edges{$e}{bw};
+
+ my(@choice) = @{$network{"bw"}{$bw}};
+ my($choice_nb) = scalar(@choice);
+ my($chosen_link) = $choice[(int rand($choice_nb))];
+ $$edges{$e}{bw} = $$chosen_link[0]/8000;
+ $$edges{$e}{delay} = $$chosen_link[1];
+ }
+}
+
+
+sub affiche_graph{
+ my($nodes,$edges,$filename) = @_;
+ my($u,$v,$w,$e);
+
+ my(%node_to_export);
+ my(%edge_to_export);
+
+ my(@host_list,@routeur_list,@link_list);
+
+ foreach $u (keys %{$nodes}) {
+ if (!((defined($$nodes{$u}{host}))&&($$nodes{$u}{host}==1))) { next; }
+ if (!((defined($$nodes{$u}{Mflops}))&&($$nodes{$u}{host}==1))) {
+ die "Lacking Mflops for $u\n";
+ }
+ push @host_list,$u;
+ $node_to_export{$u}=$#host_list;
+ }
+
+ foreach $u (@host_list){
+ foreach $v (@host_list){
+ if($u ne $v) {
+ $w = $u;
+ if(!defined($node_to_export{$w})) {
+ push @routeur_list,$w;
+ $node_to_export{$w}=$#host_list + $#routeur_list + 1;
+ }
+ while ($w ne $v) {
+ my($next) = $$nodes{$w}{shortest_route}{$v};
+ my($e) = $$nodes{$w}{out}{$next};
+ if(!defined($edge_to_export{$e})) {
+ push @link_list,$e;
+ $edge_to_export{$e}=$#link_list;
+ }
+ $w = $next;
+ if(!defined($node_to_export{$w})) {
+ push @routeur_list,$w;
+ $node_to_export{$w}=$#host_list + $#routeur_list + 1;
+ }
+ }
+ }
+ }
+ }
+
+ open VIZ, "> $filename.dot";
+ print VIZ "graph essai { \n";
+ print VIZ " graph [overlap=scale]\n";
+ #print VIZ " graph [overlap=false spline=true]\n";
+ print VIZ " node [shape=box, style=filled]\n";
+ print VIZ " node [width=.3, height=.3, style=filled]\n";
+
+ foreach $u (@host_list) {
+ print VIZ " \"$u\" [label=\"$$nodes{$u}{name}\",color=red,shape=box];\n";
+ }
+ foreach $u (@routeur_list) {
+ print VIZ " \"$u\" [label=\"$$nodes{$u}{name}\",fontsize=2,color=skyblue,shape=circle];\n";
+ }
+ foreach $e (@link_list) {
+ my($src)=$$edges{$e}{src};
+ my($dst)=$$edges{$e}{dst};
+ (defined($$edges{$e}{bw})) or die "Lacking bw for $u\n";
+ (defined($$edges{$e}{delay})) or die "Lacking bw for $u\n";
+ print VIZ " \"$src\" -- \"$dst\";\n";
+ }
+
+ print VIZ "}\n";
+ close VIZ;
+
+ system("neato -Tps $filename.dot > $filename.ps");
+# system("gv $filename.ps");
+ system("pstoedit -f fig $filename.ps $filename.fig 2>/dev/null");
+# system("xfig -startg 0 $filename.fig ");
+}
+
+sub build_lat_matrix {
+ my($nodes,$edges) = @_;
+ my($u,$v,$w,$e);
+ my(@host_list)=();
+ my($matrix);
+ foreach $u (keys %{$nodes}) {
+ if (!((defined($$nodes{$u}{host}))&&($$nodes{$u}{host}==1))) { next; }
+ push @host_list,$u;
+ }
+
+ foreach $u (@host_list){
+ foreach $v (@host_list){
+ $$matrix{$$nodes{$u}{name}}{$$nodes{$v}{name}}=0;
+ if($u ne $v) {
+ $w = $u;
+ while ($w ne $v) {
+ my($next) = $$nodes{$w}{shortest_route}{$v};
+ $e = $$nodes{$w}{out}{$next};
+ $$matrix{$$nodes{$u}{name}}{$$nodes{$v}{name}}+=$$edges{$e}{delay};
+ $w = $next;
+ }
+ }
+ print STDERR "$$nodes{$u}{name} -> $$nodes{$v}{name} : $$matrix{$$nodes{$u}{name}}{$$nodes{$v}{name}}\n";
+ }
+ }
+ return $matrix;
+}
+
+sub cluster_matrix {
+ my($matrix)=@_;
+ my($nodes,$edges) = G_new_graph();
+
+ my(@host_list)=keys %$matrix;
+
+ my($root);
+ my($u,$v);
+ my($min,$min_u,$min_v);
+ my(%taken);
+ foreach $u (@host_list){
+ G_new_node($nodes,$edges,$u);
+ }
+
+ $root=$host_list[0];
+ $taken{$root} = 1;
+
+ while(scalar(keys %taken) != scalar(@host_list)) {
+ $min = 10000000000000;
+ foreach $u (keys %taken) {
+ foreach $v (@host_list) {
+ if(!$taken{$v}) {
+ if($u ne $v) {
+ if($$matrix{$u}{$v}<$min) {
+ $min=$$matrix{$u}{$v};
+ $min_u=$u;
+ $min_v=$v;
+ }
+ }
+ }
+ }
+ }
+ $taken{$min_u} = $taken{$min_v} = 1;
+ G_connect($nodes,$edges,$min_u,$min_v);
+ print STDERR "Connecting $min_u and $min_v\n"
+ }
+ return ($nodes,$edges,$root);
+}
+
+sub PP {
+ my($nodes, $edges, $taken, $root) = @_;
+ my($u);
+ my(@tab) = ();
+ push @tab, $root;
+ foreach $u (keys (%{$$nodes{$root}{out}})) {
+ if($$taken{$u}) { next;}
+ $$taken{$u}=1;
+ push(@tab,PP($nodes,$edges, $taken, $u));
+ }
+ return \@tab;
+}
+
+sub create_orientation {
+ my($nodes,$edges,$root) = @_;
+ my(%taken);
+
+ $taken{$root} = 1;
+
+ return PP($nodes,$edges, \%taken,$root);
+}
+
+sub dump_orientation {
+ my($nodes,$edges, $tab) = @_;
+ my($u,$father);
+ my($root) = shift @$tab;
+
+ print DEPLOYMENT ' <process host="'.$$nodes{$root}{name}.'" function="msma_agent">'."\n";
+ print DEPLOYMENT ' <argument value="blabla"/> <!-- policy -->'."\n";
+
+ { # Need to find my father...
+ my(@sons) = ();
+ my(@neighboors) = keys %{$$nodes{$root}{in}};
+
+ $father = -1;
+
+ foreach $u (@$tab) {
+ push @sons,$$u[0];
+ }
+ @sons = sort @sons;
+ @neighboors = sort @neighboors;
+
+ if($#sons != $#neighboors) {
+ $u = 0;
+ while(defined($sons[$u])&&($sons[$u] eq $neighboors[$u])) {
+ $u++;
+ }
+ $father = $neighboors[$u];
+ }
+ }
+
+ if($father ne -1) {
+ print DEPLOYMENT " <argument value=\"$$nodes{$root}{name}\"/> <!-- father -->\n";
+ } else {
+ print DEPLOYMENT ' <argument value=""/> <!-- father -->'." <!-- I am the master -->\n";
+ }
+
+
+ foreach $u (@$tab) {
+ print DEPLOYMENT " <argument value=\"$$nodes{$$u[0]}{name}\"/>\n";
+ }
+ print DEPLOYMENT " </process>\n";
+ foreach $u (@$tab) {
+ dump_orientation($nodes, $edges, $u);
+ }
+
+ unshift @$tab, $root;
+}
+
+sub main {
+ my($nodes,$edges,$interferences,$host_list,$count_interferences);
+
+ $#ARGV>=0 or die "Need a tiers file!";
+ my($filename)=$ARGV[0];
+ $filename =~ s/\.[^\.]*$//g;
+ if(1) {
+ print STDERR "Reading graph\n";
+ ($nodes,$edges) = parse_tiers_file $ARGV[0];
+
+ print STDERR "Generating host list\n";
+ $host_list = generate_host_list($nodes,$edges,.7);
+ assign_host_speed($nodes,$edges);
+ assign_link_speed($nodes,$edges);
+ assign_host_names($nodes,$edges);
+ print STDERR "Computing Shortest Paths \n";
+ shortest_paths($nodes,$edges);
+ print STDERR "Exporting to surfxml\n";
+ G_surfxml_export($nodes,$edges,"$filename.xml");
+ print STDERR "Calling graphviz\n";
+ affiche_graph($nodes,$edges,"$filename");
+ print STDERR "Getting Latency Matrix\n";
+ my($matrix)=build_lat_matrix($nodes,$edges);
+ print STDERR "Clustering on Latency\n";
+ my($n_nodes,$n_edges,$root)=cluster_matrix($matrix);
+ print STDERR "Creating Orientation\n";
+ my($orientation) = create_orientation($n_nodes,$n_edges,$root);
+ print STDERR "Exporting deployment\n";
+ open DEPLOYMENT, "> $ARGV[0]_deployment.xml";
+ dump_orientation($n_nodes,$n_edges, $orientation);
+ close DEPLOYMENT;
+ }
+}
+
+main;
