| Line 1571... |
Line 1571... |
my ($self)=@_;
|
my ($self)=@_;
|
my %R_num;
|
my %R_num;
|
my %L_num;
|
my %L_num;
|
my @all_endpoints=get_list_of_all_endpoints($self);
|
my @all_endpoints=get_list_of_all_endpoints($self);
|
foreach my $r (@all_endpoints ){
|
foreach my $r (@all_endpoints ){
|
$R_num{$r} =0;
|
#$R_num{$r} =0;
|
}
|
}
|
my @nodes=get_list_of_all_routers($self);
|
my @nodes=get_list_of_all_routers($self);
|
foreach my $p (@nodes){
|
foreach my $p (@nodes){
|
$R_num{$p} =0;
|
$R_num{$p} =0;
|
}
|
}
|
| Line 1583... |
Line 1583... |
foreach my $dst (@all_endpoints ){
|
foreach my $dst (@all_endpoints ){
|
my $path = $self->object_get_attribute('Route',"${src}::$dst");
|
my $path = $self->object_get_attribute('Route',"${src}::$dst");
|
if (defined $path){
|
if (defined $path){
|
#router counting
|
#router counting
|
my @p=@{$path};
|
my @p=@{$path};
|
|
shift @p; #remove source node from the path
|
|
pop @p; #remove the destination node from the path
|
foreach my $r (@p){
|
foreach my $r (@p){
|
$R_num{$r} ++;
|
$R_num{$r} ++;
|
}
|
}
|
#path counting
|
#path counting
|
@p= get_adjacent_router_in_a_path($path);
|
@p= get_adjacent_router_in_a_path($path);
|
| Line 2576... |
Line 2578... |
} else {
|
} else {
|
add_info($info,"Use $alg_name algorithm for obtaing acyclic paths\n");
|
add_info($info,"Use $alg_name algorithm for obtaing acyclic paths\n");
|
}
|
}
|
|
|
my @acyclic_turns = @{$pp};
|
my @acyclic_turns = @{$pp};
|
|
my %rusage = get_router_usage ($self,\@acyclic_turns);
|
|
|
|
|
#step 1: calculate all minimal paths between all source and destination pairs
|
#step 1: calculate all minimal paths between all source and destination pairs
|
add_info($info,"Calculate all paths between all source and destination pairs\n");
|
add_info($info,"Calculate all paths between all source and destination pairs\n");
|
my @all_endpoints=get_list_of_all_endpoints($self);
|
my @all_endpoints=get_list_of_all_endpoints($self);
|
| Line 2611... |
Line 2613... |
# print "($key)->($Psize{$key})\n";
|
# print "($key)->($Psize{$key})\n";
|
my ($src , $dst)=split ('::',$key);
|
my ($src , $dst)=split ('::',$key);
|
my ($paths_to_dst,$ports_to_dst) = get_all_paths_between_two_endps_using_accyclic_turn($self,$src, $dst,\@acyclic_turns);
|
my ($paths_to_dst,$ports_to_dst) = get_all_paths_between_two_endps_using_accyclic_turn($self,$src, $dst,\@acyclic_turns);
|
#my @cyle_free_paths=remove_cycle_paths($self,$info,$paths_to_dst, \@forbiden_turn);
|
#my @cyle_free_paths=remove_cycle_paths($self,$info,$paths_to_dst, \@forbiden_turn);
|
my @cyle_free_paths= @{$paths_to_dst} if (defined $paths_to_dst);
|
my @cyle_free_paths= @{$paths_to_dst} if (defined $paths_to_dst);
|
my @sort_paths=sort_paths_based_on_link_usage($self,\@cyle_free_paths);
|
my @sort_paths=sort_paths_based_on_router_usage($self,\@cyle_free_paths,\%rusage);
|
|
|
|
# my @sort_paths=sort_paths_based_on_link_usage($self,\@cyle_free_paths);
|
|
|
|
|
|
|
my $path;
|
my $path;
|
my $n=0;
|
my $n=0;
|
foreach my $p (@sort_paths ){
|
foreach my $p (@sort_paths ){
|
if(check_cyclick_loop($self,$p)==0){
|
if(check_cyclick_loop($self,$p)==0){
|
$path=$p;
|
$path=$p;
|
| Line 2699... |
Line 2706... |
if (defined $hash{$p}){ $copy{$p} = $hash{$p};}
|
if (defined $hash{$p}){ $copy{$p} = $hash{$p};}
|
}
|
}
|
return %copy;
|
return %copy;
|
}
|
}
|
|
|
|
|
|
sub sort_paths_based_on_router_usage{
|
|
my ($self,$paths_to_dst,$usage)=@_;
|
|
my %scored;
|
|
my %usage_r= %{$usage};
|
|
#get list of 30% high congested ruters
|
|
my @A = sort { $usage_r{$b} <=> $usage_r{$a} } keys %usage_r;
|
|
#my $t = (scalar @A)*.3; # %30
|
|
my %congested;
|
|
foreach my $a ( @A){
|
|
$congested{$a}=$usage_r{$a};# if(scalar(keys %congested)<$t);
|
|
}
|
|
|
|
my $i=0;
|
|
foreach my $path (@{$paths_to_dst}) {
|
|
my $val = 0;
|
|
my $num=0;
|
|
for my $r (@{$path}){
|
|
if(defined $congested{$r}){
|
|
$val+=$congested{$r}**1.5;# pow of 3/2 to give higher weight to more congested routers
|
|
$num++;
|
|
}
|
|
}
|
|
$scored{$i}=($num==0)? 0 : $val/$num; #average weight of congested routers
|
|
$i++;
|
|
}
|
|
|
|
my @order = sort { $scored{$a} <=> $scored{$b} } keys %scored;
|
|
my @sorted;
|
|
|
|
|
|
|
|
$i=0;
|
|
foreach my $a ( @order){
|
|
$sorted[$i]=${$paths_to_dst}[$a];
|
|
$i++;
|
|
#print "\$max{$a}=$max{$a},"
|
|
}
|
|
|
|
#print "\n";
|
|
|
|
return @sorted;
|
|
}
|
|
|
|
|
sub sort_paths_based_on_link_usage{
|
sub sort_paths_based_on_link_usage{
|
my ($self,$paths_to_dst)=@_;
|
my ($self,$paths_to_dst)=@_;
|
|
|
my %L_num;
|
my %L_num;
|
my %max;
|
my %max;
|
| Line 2712... |
Line 2764... |
foreach my $dst (@all_endpoints ){
|
foreach my $dst (@all_endpoints ){
|
my $path = $self->object_get_attribute('Route',"${src}::$dst");
|
my $path = $self->object_get_attribute('Route',"${src}::$dst");
|
if (defined $path){
|
if (defined $path){
|
#path counting
|
#path counting
|
my @p= get_adjacent_router_in_a_path($path);
|
my @p= get_adjacent_router_in_a_path($path);
|
|
|
foreach my $r (@p){
|
foreach my $r (@p){
|
$L_num{$r} ++;
|
$L_num{$r} ++;
|
}
|
}
|
|
|
}
|
}
|
| Line 2752... |
Line 2805... |
return @sorted;
|
return @sorted;
|
|
|
|
|
}
|
}
|
|
|
|
|
|
sub get_router_usage{
|
|
my ($self,$acycle_turn_ref)=@_;
|
|
|
|
my @all_endpoints=get_list_of_all_endpoints($self);
|
|
my %router_cnt;
|
|
#get router counts
|
|
foreach my $src (@all_endpoints ){
|
|
foreach my $dst (@all_endpoints ){
|
|
#get list of all path between a source and destination nodes
|
|
my ($paths_to_dst,$ports_to_dst)= get_all_paths_between_two_endps_using_accyclic_turn($self,$src, $dst,$acycle_turn_ref);
|
|
|
|
my @paths = @{$paths_to_dst};
|
|
foreach my $path (@paths){
|
|
shift @{$path}; #remove source node from the path
|
|
pop @{$path}; #remove the destination node from the path
|
|
foreach my $q ( @{$path}){
|
|
$router_cnt{"$q"} = ( defined $router_cnt{"$q"})? $router_cnt{"$q"}+1 : 1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return %router_cnt;
|
|
|
|
}
|
|
|
|
|
sub check_cyclick_loop{
|
sub check_cyclick_loop{
|
my ($self,$paths_to_dst)=@_;
|
my ($self,$paths_to_dst)=@_;
|
|
|
|
|
my %graph;
|
my %graph;
|
