# Copyright (c) 2004-2005, 2007-2008
#      Satish Raghunath (rsatish@alum.rpi.edu).  All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
# 4. The name of the author may not be used to endorse or
#    promote products derived from this software without specific
#    prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND
# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE
# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
# OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
# OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
# SUCH DAMAGE.

#
# Perl routines for simulation study to validate traffic matrices obtained by 
# solving optimization described in the following paper:
# ``Measurement-based Characterization of IP VPNs'', 
#       S. Raghunath, K.K. Ramakrishnan, S. Kalyanaraman,
#       IEEE/ACM Transactions on Networking, 15(6), pp 1428-1441,
#       Dec 2007
#
# For extended version see
# http://rsatish.net/ton-vpn_tm-post_review.pdf 
#
#
# To generate synthetic VPNs to test the traffic matrix
# estimation procedure. 

# 04/19/04 Satish rsatish@alum.rpi.edu
#
# 05/24/05 Minor changes to run it locally (out directory made relative)
#
$DATA="../out";

sub gen_pure_hs {

    my $vpnsize = shift;
    my $spread = shift;

    # Generate total in and out for hub
    $hub_in = int(1+rand(10))*100000000;
    $hub_out = int(1+rand(10))*100000000;
    
    $total = 0;
    for($spoke = 1; $spoke <= $vpnsize-1; $spoke++) {
	$share[$spoke] = rand($spread);
	$total += $share[$spoke];
    }

    for($spoke = 1; $spoke <= $vpnsize-1; $spoke++) {
	$total_in[$spoke] = int(($share[$spoke]/$total)*$hub_out);
	$total_out[$spoke] = int(($share[$spoke]/$total)*$hub_in);
    }

    $total_in[$vpnsize] = $hub_in;
    $total_out[$vpnsize] = $hub_out;

    open f1, "> $DATA/"."total_inoutbytes_9999_synth";

    print f1 "9999 0 ";
    for ($spoke = 1; $spoke <= $vpnsize; $spoke++) {
	print f1 $total_out[$spoke]," ",$total_in[$spoke]," ";
    }
    print f1 "\n";

    print f1 "9999 0 ";
    $numpes = $vpnsize;
    open f2, "> $DATA/"."pepe_linkdata_9999_synth.dat";
    $tmp = $numpes*($numpes-1);
    print f2 "9999 $vpnsize\n9999 $tmp\n";
    $count=1;
    for($i=1; $i <= $numpes; $i++) {
	for($j=1; $j <= $numpes; $j++) {
	    next if($i==$j);
	    if($total_out[$i] < $total_in[$j]) {
		$min = $total_out[$i];
	    } else {
		$min = $total_in[$j];
	    }
	    print f1 $min," ";
	    $var_id = ($i-1)*$vpnsize+$j;
	    print f2 "9999 $count $var_id\n";
	    $count = $count+1;
	}
    }
    print f1 "\n";
    close(f1);
    close(f2);

    # Write the correct traffic matrix 
    open f1, ">$DATA/"."correct_tm.dat";
    for($i=1;$i<=$vpnsize-1; $i++) {
	$var_id = ($i-1)*($vpnsize-1)+$vpnsize-1;
	print f1 "$var_id $total_out[$i] ";
	$var_id = ($vpnsize-1)*($vpnsize-1)+$i;
	print f1 "$var_id $total_in[$i] ";
    }
    print f1 "\n";
    close(f1);
}

# Have multiple CEs per PE
sub gen_hs_clustered {

    my $maxclust = shift;
    my $vpnsize = shift;
    my $spread = shift;

    # Generate total in and out for hub
    $hub_in = int(1+rand(10))*100000000;
    $hub_out = int(1+rand(10))*100000000;
    
    $total = 0;
    for($spoke = 1; $spoke <= $vpnsize-1; $spoke++) {
	$share[$spoke] = rand($spread);
	$total += $share[$spoke];
    }

    for($spoke = 1; $spoke <= $vpnsize-1; $spoke++) {
	$total_in[$spoke] = int(($share[$spoke]/$total)*$hub_out);
	$total_out[$spoke] = int(($share[$spoke]/$total)*$hub_in);
    }

    $total_in[$vpnsize] = $hub_in;
    $total_out[$vpnsize] = $hub_out;

    # Assign CEs to PEs
    $num = 0; $peid = 1;
    while($num < $vpnsize) {
	$numces[$peid] = int(rand($maxclust))+1;
	print "\nnumces[$peid] = $numces[$peid]\n";
	$num += $numces[$peid];
	$peid++;
    }
    print "\n num = $num\n";
    $numces[$peid-1] = $numces[$peid-1] - ($num - $vpnsize);
    
    $numpes = $peid-1; $ceid = 1;
    # We have number of CEs per PE, now actually assign
    for($i=1; $i <= $numpes; $i++) {
	for($j=1; $j <= $numces[$i]; $j++) {
	    $ces_on_pe{$i}->{$ceid}=1;
	    $ceid++;
	}
    }

    open f1, "> $DATA/"."total_inoutbytes_9999_synth";

    print f1 "9999 0 ";
    for ($spoke = 1; $spoke <= $vpnsize; $spoke++) {
	print f1 $total_out[$spoke]," ",$total_in[$spoke]," ";
    }
    print f1 "\n";

    print f1 "9999 0 ";
    open f2, "> $DATA/"."pepe_linkdata_9999_synth.dat";
    $tmp = $numpes*($numpes-1);
    print f2 "9999 $vpnsize\n9999 $tmp\n";
    $count=1;
    for($i=1; $i <= $numpes; $i++) {
	for($j=1; $j <= $numpes; $j++) {
	    next if($i==$j);
	    $bytes_in = 0; $bytes_out = 0;
	    print f2 "9999 $count ";
	    foreach $ce1 (sort {$a <=> $b} (keys %{$ces_on_pe{$i}})) {
		foreach $ce2 (sort {$a <=> $b} (keys %{$ces_on_pe{$j}})) {
		    $bytes_out += $total_out[$ce1];
		    $bytes_in += $total_in[$ce2];

		    $var_id = ($ce1-1)*$vpnsize+$ce2;
		    print f2 " $var_id";
		}
	    }
	    print f2 "\n";
	    if($bytes_out < $bytes_in) {
		$min = $bytes_out;
	    } else {
		$min = $bytes_in;
	    }
	    print f1 $min," ";
	    $count = $count+1;
	}
    }
    print f1 "\n";
    close(f1);
    close(f2);

    # Write the correct traffic matrix 
    open f1, ">$DATA/"."correct_tm.dat";
    for($i=1;$i<=$vpnsize-1; $i++) {
	$var_id = ($i-1)*($vpnsize-1)+$vpnsize-1;
	print f1 "$var_id $total_out[$i] ";
	$var_id = ($vpnsize-1)*($vpnsize-1)+$i;
	print f1 "$var_id $total_in[$i] ";
    }
    print f1 "\n";
    close(f1);
}

# From perlmonks.thepen.com, google cache:
# http://216.239.51.104/search?q=cache:cOmfJ5Yo5DQJ:perlmonks.thepen.com/26889.html+perl+snippet+random+number+rands&hl=en
# Serch query "perl snipptet random number rands"
#
# Call rands(1,5) to get normal (0,1). For more precision increase second
# param
sub rands{
    my $t=0;
    $t = 0;
    $t+= ( rand()* ($_[0]/$_[1]) ) for(1..$_[1]);
    return $t;
}

# Generate a multi-hub/spoke VPN using deviation as input.
sub gen_multi_hs {
    my $numhubs = shift;
    my $maxclust = shift;
    my $vpnsize = shift;
    my $spread = shift;

    # Generate total in and out for a dummy spoke and
    # use that as mean and spread as sigma to randomly 
    # derive others.
    $mean_in = int(1+rand(10))*1000000;
    $mean_out = int(1+rand(10))*1000000;
    $std_in = $mean_in*$spread;
    $std_out = $mean_out*$spread;

    for($spoke = 1; $spoke <= $vpnsize-$numhubs; $spoke++) {
	$total_in[$spoke] = int($mean_in + $std_in * (rands(2,5)-1));
	$total_out[$spoke] = int($mean_in + $std_in * (rands(2,5)-1));
	$total_in[$spoke] = 0 if($total_in[$spoke] < 0);
	$total_out[$spoke] = 0 if($total_out[$spoke] < 0);
    }

    # Now decide which spokes talk to which hubs; Divvy up the
    # spokes among the hubs and calculate hub traffic as sum of
    # these spokes.
    $overlap = 1;
    $total = 0;
    for($i =1; $i <= $numhubs; $i++) {
	$numspokes[$i] = int(($vpnsize - $numhubs)*$overlap/$numhubs);
	$total += $numspokes[$i];
    }
    # Assign whatever remains to the last hub
    $numspokes[$numhubs] += ($vpnsize - $numhubs) - $total;

    # Now compute the total_in/out for the hubs
    $spoke=1;
    for($i=$vpnsize-$numhubs+1; $i<=$vpnsize; $i++) {
	$hub = $i - ($vpnsize - $numhubs);
	for($j = $spoke; $j <= $spoke+$numspokes[$hub]-1; $j++) {
	    $total_in[$i] += $total_in[$j];
	    $total_out[$i] += $total_out[$j];
	    $tm{$i}{$j} = $total_in[$j];
	    $tm{$j}{$i} = $total_out[$j];
	}
	$spoke = $spoke+$numspokes[$hub];
    }

    # Now add inter-hub traffic. Choose a hub-of-hub
    # kind of a model. One hub talks to the other hubs.
    $inter_hub_traffic = 1;
    if($numhubs > 1 && $inter_hub_traffic == 1) {
	$hub_of_hubs = $vpnsize-$numhums+1;
	for($i=$hub_of_hubs+1; $i <= $vpnsize; $i++) {
	    $extra_in = int($mean_in + $std_in * (rands(2,5)-1));
	    $extra_out = int($mean_out + $std_out * (rands(2,5)-1));
	    $extra_in = 0 if($extra_in < 0);
	    $extra_out = 0 if($extra_out < 0);
	    
	    #Add to the total_in/out of this hub
	    $total_in[$i] += $extra_in;
	    $total_out[$hub_of_hubs] += $extra_in;
	    $tm{$hub_of_hubs}{$i} += $extra_in;

	    $total_out[$i] += $extra_out;
	    $total_in[$hub_of_hubs] += $extra_out;
	    $tm{$i}{$hub_of_hubs} += $extra_out;
	}
    }

    # Assign CEs to PEs
    $num = 0; $peid = 1;
    while($num < $vpnsize) {
	$numces[$peid] = int(rand($maxclust))+1;
	print "\nnumces[$peid] = $numces[$peid]\n";
	$num += $numces[$peid];
	$peid++;
    }
    print "\n num = $num\n";
    $numces[$peid-1] = $numces[$peid-1] - ($num - $vpnsize);
    
    $numpes = $peid-1; $ceid = 1;
    # We have number of CEs per PE, now actually assign
    for($i=1; $i <= $numpes; $i++) {
	for($j=1; $j <= $numces[$i]; $j++) {
	    $ces_on_pe{$i}->{$ceid}=1;
	    $ceid++;
	}
    }

    open f1, "> $DATA/"."total_inoutbytes_9999_synth";

    print f1 "9999 0 ";
    for ($spoke = 1; $spoke <= $vpnsize; $spoke++) {
	print f1 $total_out[$spoke]," ",$total_in[$spoke]," ";
    }
    print f1 "\n";

    print f1 "9999 0 ";
    open f2, "> $DATA/"."pepe_linkdata_9999_synth.dat";
    $tmp = $numpes*($numpes-1);
    print f2 "9999 $vpnsize\n9999 $tmp\n";
    $count=1;
    for($i=1; $i <= $numpes; $i++) {
	for($j=1; $j <= $numpes; $j++) {
	    next if($i==$j);
	    $bytes_in = 0; $bytes_out = 0;
	    print f2 "9999 $count ";
	    foreach $ce1 (sort {$a <=> $b} (keys %{$ces_on_pe{$i}})) {
		foreach $ce2 (sort {$a <=> $b} (keys %{$ces_on_pe{$j}})) {
		    $bytes_out += $total_out[$ce1];
		    $bytes_in += $total_in[$ce2];

		    $var_id = ($ce1-1)*$vpnsize+$ce2;
		    print f2 " $var_id";
		}
	    }
	    print f2 "\n";
	    if($bytes_out < $bytes_in) {
		$min = $bytes_out;
	    } else {
		$min = $bytes_in;
	    }
	    print f1 $min," ";
	    $count = $count+1;
	}
    }
    print f1 "\n";
    close(f1);
    close(f2);

    # Write the correct traffic matrix 
    open f1, ">$DATA/"."correct_tm.dat";
    for($i=1;$i<=$vpnsize-$numhubs; $i++) {
	for($j = $vpnsize-$numhubs+1; $j <= $vpnsize; $j++) {
	    $var_id = ($i-1)*($vpnsize-1)+$j-1;
	    if(defined($tm{$i}{$j})) {
		print f1 "$var_id $total_out[$i] ";
	    } else {
		print f1 "$var_id 0 ";
	    }
	    
	    $var_id = ($j-1)*($vpnsize-1)+$i;
	    
	    if(defined($tm{$j}{$i})) {
		print f1 "$var_id $total_in[$i] ";
	    } else {
		print f1 "$var_id 0 ";
	    }
	}
    }
    print f1 "\n";
    close(f1);

}

$numargs = scalar(@ARGV);
if($ARGV[0] == 0) {
    print "\n Calling Pure H/S proc\n";
    gen_pure_hs($ARGV[1],$ARGV[2]);
} elsif($numargs == 3) {
    print "\n Calling H/S proc with cluster size $ARGV[0]\n";
    gen_hs_clustered($ARGV[0],$ARGV[1],$ARGV[2]);
} elsif($numargs == 4) {
    print "\n Calling Multi H/S proc with numhubs $ARGV[0]\n";
    gen_multi_hs($ARGV[0],$ARGV[1],$ARGV[2], $ARGV[3]);
} else {
    die("Wrong number of arguments: $numargs, see code to figure out\n");
}