I have a graph with 14 nodes and 21 links. This graph shows an optical network. The links are bidirectional and there are some resources on each link. Assume there is a working path from a source to a destination which carry a packet containing data and uses some resources(some amount of bandwidth of the link that it is traversed by). for each source and destination, I must establish a working and a protection path simultaneously in advance in case of a link failure but they muse be link disjoint.(they cannot traverse any common link)
For example I send a packet from node1 to node4 through route<1,2,3,4> as the working path. If link 1-2 fails, I have to send the packet through a protection path that has been established in advance and is disjoint with the working path. for example my protection path may be <1,9,3,4>.
The purpose is write a code in C/C++ to find the protection path which is link disjoint with the working path. Actualy I couldn't get an idea for doing that. Any help would be greatly appreciated.
This is a piece of my code where I have allocate resources to working paths, I don't know how I can do the same for establishing protection path under condition that it must be disjoint with the working path.
int required_fs;
int des;
int idpk;
double holding;
int src;
//get the information about the packet that is sent from source to destination.
Packet *pkptr;
pkptr = op_pk_get (0);
op_pk_nfd_get(pkptr,"bw_fs",&required_fs);
op_pk_nfd_get(pkptr,"des",&des);
op_pk_nfd_get(pkptr,"src",&src);
op_pk_nfd_get(pkptr,"id",&idpk);
op_pk_nfd_get(pkptr,"ht",&holding);
bw_req=bw_req + required_fs;
number_of_req=number_of_req+1;
if (number_of_req > 1000000)
{
FILE* file1=fopen("C:/400f_rsa.txt","a+");
fprintf(file1,"\n");
fprintf(file1,"number_of_req ,number_of_nack,number_of_ack , bw_req , bw_nack , bw_ack " );
fprintf(file1,"\n");
fprintf(file1," %d , %d , %d , %d , %d , %d ", number_of_req, number_of_nack ,number_of_ack,bw_req,bw_nack,bw_ack );
fprintf(file1,"\n");
fprintf(file1,"------------------------------- ");
fclose (file1);
op_sim_end("1000000 paket","","","");
}
// Allocate the resources on each link to the working path, This part must be the same for the protection path too.
int determined_t=0;
int determined_r=0;
int determined_p_f=0;
int determined_p_e=0;
int determined_k=0;
for ( int i=1; i<=10; i++)
{
if (transmitter[src][i]==0)
{
determined_t=i;
break;
}
}
if (determined_t!=0)
{
for ( int i=1; i<=10; i++)
{
if (reciever[des][i]==0)
{
determined_r=i;
break;
}
}
if (determined_r!=0)
{
for ( int k=1; k<=2 ; k++)
{
determined_p_f=0;
determined_p_e=0;
int count = paths_node[src][des][k][2][14];
zero_array();
for (int i=1; i<=count; i++)
{
finding_fs( k, i, des, src );
}
if ( ff_rr==0)
{//ff
////checking gap
determined_p_f=find_first_free_gap(required_fs);
if (determined_p_f!=0)
{
determined_p_e=determined_p_f+required_fs-1;
if (determined_p_e != 1000)
{
determined_p_e=determined_p_e+1;
}
determined_k=k;
break;
}
}
else if (ff_rr==1)
{//rr
clear_rr_gap();
find_rr_gap(required_fs);
int index=rr_spectrum();
determined_p_f=ary_rr[index].first;
if (determined_p_f!=0)
{
determined_p_e=ary_rr[index].last;
determined_k=k;
break;
}
}
}
if (determined_p_f!=0)
{
//add to ls , applying
int count_link = paths_node[src][des][determined_k][2][14];
for ( int i=1; i<=count_link ; i++)
{
int num_link_p=paths_node[src][des][determined_k][2][i];
for ( int j=determined_p_f ; j<=determined_p_e; j++)
{
links_fs[num_link_p][j]=1;
}
}
reciever[des][determined_r]=1;
transmitter[src][determined_t]=1;
ls(determined_p_f,determined_p_e,determined_r,determined_t,determined_k,src,des,idpk);
number_of_ack= number_of_ack +1 ;
bw_ack= bw_ack + required_fs;
op_intrpt_schedule_self(op_sim_time ()+ holding,idpk);
op_pk_destroy(pkptr);
}
else
{
number_of_nack=number_of_nack+1;
bw_nack= bw_nack + required_fs;
op_pk_destroy(pkptr);
}
}
else
{
number_of_nack=number_of_nack+1;
bw_nack= bw_nack + required_fs;
op_pk_destroy(pkptr);
}
}
else
{
number_of_nack=number_of_nack+1;
bw_nack= bw_nack + required_fs;
op_pk_destroy(pkptr);
}
