#!  /usr/local/bin/perl
#
# copyright 2010 The Regents of the University of California All Rights
# Reserved
#
# Permission to copy, modify and distribute any part of this AS ASSIGNMENT
# SUPPLEMENTAL MATERIAL for educational, research and non-profit purposes,
# without fee, and without a written agreement is hereby granted, provided
# that the above copyright notice, this paragraph and the following three
# paragraphs appear in all copies.
#
# Those desiring to incorporate this AS ASSIGNMENT SUPPLEMENTAL PATERIAL
# into commercial products or use for commercial purposes should contact
# the Technology Transfer Office, University of California, San Diego, 9500
# Gilman Drive, Mail Code 0910, La Jolla, CA 92093-0910, Ph: (858)
# 534-5815, FAX: (858) 534-7345, E-MAIL:invent@ucsd.edu.
#
# IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
# DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES,
# INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS AS ASSIGNMENT
# PAPER SUPPLEMENTAL MATERIAL, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS
# BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
# THE AS ASSIGNMENT SUPPLEMENTAL MATERIAL PROVIDED HEREIN IS ON AN "AS IS"
# BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
# MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.  THE
# UNIVERSITY OF CALIFORNIA MAKES NO REPRESENTATIONS AND EXTENDS NO
# WARRANTIES OF ANY KIND, EITHER IMPLIED OR EXPRESS, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
# PARTICULAR PURPOSE, OR THAT THE USE OF THE AS ASSIGNMENT SUPPLEMENTAL
# MATERIAL WILL NOT INFRINGE ANY PATENT, TRADEMARK OR OTHER RIGHTS.
#
use strict;

# This needs to be the path to ASFinder
# http://www.caida.org/tools/measurement/coralreef/status.xml
use lib '/usr/local/pkg/caida_coral-3.8.4/Coral/lib/';
use CAIDA::ASFinder;

my %valid_options = %{{
    "prefix2as" => ["p",
       "ASFinder friendly \"prefix\\tlength\\tAS\" (prefix2as.2010.04.19.txt)"],
    "routers" => ["r","kapar router file (midar-iffinder-kapar.nodes)"],
    "links" => ["l","kapar links file (midar-iffinder-kapar.links)"]
    }};

use Getopt::Std;
use FindBin qw($Bin);
use Socket;
my ($exe) = ($0 =~ /([^\/]+)$/);
my $usage = "usage:$exe [-p prefix2as] [-r routers] [-l link] [config]\n".
	    "      $exe -c > sample-config-file";
sub Help() {
    print <<EOP;
$usage
    This program assigns AS to each of the routers It first uses AS degree
    (as calculated by assuming direct connection beween AS in the same
    router) then falls back on election.
    h - this message
    c - prints sample configuration file to STDOUT
EOP
    foreach my $keyword (keys %valid_options) {
	my ($key, $description) = @{$valid_options{$keyword}};
	print "    $key - $description\n";
    }
}

my %opts;
unless (getopts("hcp:r:l:",\%opts) ) {
    print STDERR $usage,"\n";
    exit -1;
}
if (defined $opts{h}) {
    Help();
    exit(0);
}
if (defined $opts{c}) {
    PrintSampleConfig();
    exit(0);
}

my $config_file = $ARGV[0];
if (defined $config_file) {
    ParseConfig($config_file, \%opts);
} else {
    die "You need config file\n";
}

#######################
# Order matters.  Becareful changing order
#######################
my @keyword_order = qw( prefix2as routers links );

my @missing;
my @permission;
foreach my $keyword (@keyword_order) {
    my ($key, $description) = @{$valid_options{$keyword}};
    my $file = $opts{$key};
    unless (defined $file) {
	push @missing, $keyword;
    } elsif (!-r $file) {
	push @permission, $file;
    }
}

my $error_message;
if ($#missing >= 0) {
    $error_message = "no file for :".join(",",@missing)."\n";
}
if ($#permission >= 0) {
    $error_message = "no read permission for :".join(",",@permission)."\n";
}

my $asfinder = new CAIDA::ASFinder();
my %total;
my @routers;
my %file2linenum;
foreach my $keyword (@keyword_order) {
    my ($key, $description) = @{$valid_options{$keyword}};
    my $file = $opts{$key};
    if (-r $file) {
	PrintStatus("$keyword Loading");

	if ($keyword eq "prefix2as") {
	    $asfinder->load_file_text($file);
	} elsif ($keyword eq "routers") {
	    LoadRoutersLinks($file);
	} elsif ($keyword eq "links") {
	    LoadRoutersLinks($file);
	} else {
	    die("Unknown keyword:$keyword");
	}
    } else {
	die "missing $keyword";
    }
}

my %as2degree;
CountAsDegree();
my @rids = (0..$#routers);
my $rids_second = AssignAs("election", \@rids);

my ($key, $description) = @{$valid_options{"links"}};
my $link_file = $opts{$key};
LoadRoutersLinks($link_file,"second pass");
AssignAs("election+degree", $rids_second);
ResolveSets(\@rids);
PrintAsAssignment();

##################################################################

sub LoadRoutersLinks {
    my ($file, $second_pass) = @_;
    my $linenum_total = CountFileSize($file);
    $file2linenum{$file} = $linenum_total;
    if ($file =~ /gz$/) {
	open (IN, "gunzip -c $file|") || die("Unable to open $file:$!");
    } else {
	open(IN, "<$file") || die("Unable to open $file:$!");
    }
    my $linenum = 0;
    while(<IN>) {
	CheckStatus("$file $second_pass",$linenum++,$linenum_total);
	s/#.*//;
	next unless (/[^\s]/);
	if (/^node N(\d+):\s+(.*)/) {
	    my ($rid, $ips) = ($1, $2);
	    my @ips = split /\s+/, $ips;
	    my $placeholder_counted;
	    $total{routers}{seen}++;
            foreach my $ip (@ips) {
		if ($ip =~ /\d/) {
		    unless ($ip =~ /^0\./) {
			my ($as, $prefix, $len) = GetAs($ip);
			if ($len > 7) {
			    $routers[$rid]{ases}{$as}++;
			}
		    } elsif (!defined $placeholder_counted) {
			$placeholder_counted = 1;
		    }
		}
            }
	    unless (defined $routers[$rid]{has_ip}){ 
		$total{routers}{"no ip"}++;
	    }
	} elsif (/^link L(\d+):\s+(.*)/) {
	    my ($lid, $rid_ips) = ($1, $2);
	    my %as;
	    my @rid;
	    my $num_routers;
	    my $link_has_ip;
	    unless (defined $second_pass) {
		$total{links}{seen}++;
	    }
	    foreach my $rid_ip (split /\s+/ , $rid_ips) {
		my ($rid, $ip) = ($rid_ip =~ /^N([^\:]+):?(.*)/);
		push @rid, $rid;
		
		unless (defined $second_pass) {
		    if ($ip =~ /\d/ && !$ip =~ /^0\./) {
			$link_has_ip = 1;
			my ($as, $prefix, $len) = GetAs($ip);
			if ($len > 7) {
			    $as{$as} = 1;
			}
		    }
		} else {
		    my $as = $routers[$rid]{as};
		    if (defined $as) {
			$as{$as} = 1;
		    }
		}
	    }
	    my @as = keys %as;
	    if ($#as >= 0) {
		foreach my $rid (@rid) {
		    foreach my $as (@as) {
			$routers[$rid]{ases}{$as}++;
		    }
		}
	    } elsif (!defined $second_pass) {
		$total{links}{skipped}++;
	    }
	} else {
	    print STDERR "$file\[$linenum\] failed to parse:$_";
	}
    }
    close IN;
}

sub GetAs {
    my ($ip) = @_;
#    my ($as, $prefix, $len) = GetAs($ip);
    return $asfinder->get_as($ip);
}

##################################################################

sub CountAsDegree {
    my %as_as;
    foreach my $rid (0..$#routers) {
	next unless (defined $routers[$rid]);
	
	my @as = keys %{$routers[$rid]{ases}};
	next if ($#as < 1);

	foreach my $i (0..($#as-1)) {
	    foreach my $j (($i+1)..$#as) {
		$as_as{$as[$i]}{$as[$j]} = 1;
		$as_as{$as[$j]}{$as[$i]} = 1;
	    }
	}
    }

    foreach my $as (keys %as_as) {
	my $degree = keys %{$as_as{$as}};
	$as2degree{$as} = $degree;
    }
}

##################################################################

sub AssignAs {
    my ($method_label, $rids) = @_;
    PrintStatus("Assigning AS $method_label");
    my ($method) = ($method_label =~ /([^\+]+)$/);

    my @as_second_pass;
    my $total_routers = @$rids;
    my $num_routers = 0;
    foreach my $rid (@$rids) {

	CheckStatus("Assigning AS $method", $num_routers++, $total_routers);
	my @as;
	my $as2value;
	if ($method eq "degree") {
	    @as = keys %{$routers[$rid]{ases}};
	    $as2value = \%as2degree;
	} elsif ($method eq "election") {
	    $as2value = $routers[$rid]{ases};
	    @as = keys %$as2value;
	} else {
	    die("Unknown method:$method");
	}
	@as = sort {$as2value->{$a}<=>$as2value->{$b}} @as;
	delete $routers[$rid]{ases};
	if ($#as == 0) {
	    $routers[$rid]{as} = $as[0];
	    $routers[$rid]{method} = "single";
	    undef $routers[$rid]{ases};
	} elsif ($#as > 0) {
	    if ($as2value->{$as[0]} != $as2value->{$as[1]}) {
		$routers[$rid]{as} = $as[0];
		$routers[$rid]{method} = $method_label;
	    } else {
		push @as_second_pass, $rid;
	    }
	} else {
	    push @as_second_pass, $rid;
	}
    }
    return \@as_second_pass;
}

##################################################################

sub ResolveSets {
    my ($rids) = @_;
    PrintStatus("Resolve Sets");

    my @as_second_pass;
    my $total_routers = @$rids;
    my $num_routers = 0;
    foreach my $rid (@$rids) {
	CheckStatus("Resolving Sets", $num_routers++, $total_routers);
	my $as_set = $routers[$rid]{as};
	next if (!defined $as_set || ($as_set =~ /^\d+$/));

	my $as;
	my @as = split /[^\d]/, $as_set;
	if ($#as == 0) {
	    $as = $as[0];
	} else {
	    if (defined $routers[$rid]{ases}) {
		my $as2value = $routers[$rid]{ases};
		@as = sort {$as2value->{$a}<=>$as2value->{$b}} @as;
		if ($as2value->{$as[0]} != $as2value->{$as[1]}) {
		    $as = $as[0];
		}
	    } 

	    unless (defined $as) {
		@as = sort {$as2degree{$a}<=>$as2degree{$b}} @as;
		if ($as2degree{$as[0]} != $as2degree{$as[1]}) {
		    $as = $as[0];
		}
	    }
	}
	unless (defined $as) {
	    @as = reverse sort {$a<=>$b} @as;
	    $as = $as[0];
	}
	if (defined $as) {
	    $routers[$rid]{as} = $as;
	}
    }
    
}

##################################################################

sub PrintAsAssignment {
    PrintStatus("Printing AS");

    my $total_routers = @routers;
    my $num_routers = 0;
    print "#node.AS rid AS method\n";
    foreach my $rid (0..$#routers) {
	CheckStatus("Assigning AS (pass one)", $num_routers++, $total_routers);
	next unless (defined $routers[$rid]);
	next unless (defined $routers[$rid]{as});

	my $as = $routers[$rid]{as};
	my $method = $routers[$rid]{method};
	print "node.AS N$rid $as $method\n";
    }
}

##################################################################
sub PrintStatus {
    my ($message) = @_;
    my ($sec, $min, $hour, $day, $mon, $year) = localtime(time);
    $mon++;
    foreach my $value ($sec, $min, $hour, $day, $mon) {
	$value = "0".$value if ($value < 10);
    }
    $year += 1900;
    print STDERR "    $year/$mon/$day $hour:$min:$sec $message\n";
}

{
my %file2start;
my $check_last_time;
sub CheckStatus {
    my ($file, $linenum, $linenum_total) = @_;
    my $check_window = 5;
    my $time = time;
    unless (defined $file2start{$file}) {
	$file2start{$file} = $time;
	$check_last_time = $time;
    } elsif ($time-$check_last_time >= $check_window) {
	my $prec = sprintf("%.2f", 100*($linenum/$linenum_total));

	my $start_time = $file2start{$file};
	my $estimate_time = ($linenum_total-$linenum)
	    *(($time-$start_time)/$linenum);
	$estimate_time = sprintf("%.3f",$estimate_time/(60*60));

	PrintStatus("$file $prec\% $estimate_time hours");
        $check_last_time = $time;
    }
}
}

sub CountFileSize {
    my ($file) = @_;
    if ($file =~ /gz$/) {
        open (COUNT, "gunzip -c $file |") || die("Unable to open $file:$!");
    } else {
        open (COUNT, "<$file") || die("Unable to open $file:$!");
    }

    my $linenum = 0;
    while (<COUNT>) {
        $linenum++;
    }
    close COUNT;
    return $linenum;
}

##################################################################
sub PrintSampleConfig {
    print "# This file tells $exe where the following data files are\n";
    foreach my $keyword (sort keys %valid_options) {
	my ($key, $description) = @{$valid_options{$keyword}};
	print "# $description\n";
	print "$keyword:\n";
    }
}
sub ParseConfig {
    my ($filename, $opts) = @_;
    my $dir = $filename;
    $dir =~ s/\/?[^\/]+$//;

    open (IN,"<$filename") || die ("Unable to open config file $filename:$!");
    my $linenum = 0;
    my ($continue_next, $key);
    while (<IN>) {
        $linenum++;
        s/#.*//;
        next unless (/[^\s]/);
	chop;
	my $continue;
	if (defined $continue_next) {
	    $continue = 1;
	}
	undef $continue_next;
	if (/\\$/) {
	    chop;
	    $continue_next = 1;
	}

	if (defined $continue) {
	    $opts->{$key} .= " ".AddPath($key, $dir, $_);
	} elsif  (/([^\:]+)\:\s*(.*)/) {
            my ($keyword , $value) = ($1, $2);
            my $key_description = $valid_options{$keyword};
	    if (defined $key_description) {
		my ($key, $description) = @$key_description;
		unless (defined $opts->{$key}) {
		    $opts->{$key} = AddPath($key, $dir,$value);
		}
	    }
	} else {
	    print STDERR "$filename\[$linenum\] failed to parse $_";
        }
    }
    close IN;
}

sub AddPath {
    my ($key, $dir, $file) = @_;
    if (($dir =~ /[^\s]/) && ($key ne "D")) {
	$file =~ s/^\s*//;
	unless ($file =~ /^\//) {
	    return "$dir/$file";
	}
    }
    return $file;
}

1;