ns-2.29 » indep-utils » dosreduce

dosreduce.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

Include dependency graph for dosreduce.c:

Go to the source code of this file.

Data Structures

struct  ATlinks
struct  CTinfo
struct  node
struct  QueueItem

Defines

#define INC   0
#define INFINITY   -1;

Functions

void cleanq (void)
node * dequeue (void)
void enqueue (struct node *vertex)
int main (int argc, char **argv)

Variables

ATlinks * AThead
ATlinks * ATtail
int debug = 0
QueueItem * head
QueueItem * tail

Define Documentation

#define INC   0
 

Definition at line 6 of file dosreduce.c.

#define INFINITY   -1;
 

Definition at line 5 of file dosreduce.c.

Function Documentation

void cleanq (  void   ) 
 

Definition at line 476 of file dosreduce.c.

References dequeue(), head, and node::p.

00477 {
00478   struct node *p;
00479   while(head)
00480     p = dequeue();
00481 }

Here is the call graph for this function:

struct node * dequeue (  void   ) 
 

Definition at line 503 of file dosreduce.c.

References head, QueueItem::next, node::p, tail, and QueueItem::u.

Referenced by cleanq().

00504 {
00505   struct node *retvertex;
00506   QueueItem *p = (struct QueueItem *) malloc (sizeof(QueueItem));
00507 
00508   if (head == tail) {
00509     retvertex = head->u;
00510     head = tail = NULL;
00511   } else {
00512     p = head;
00513     retvertex=head->u;
00514     head = head->next;
00515     free(p);
00516   }
00517   return retvertex;
00518 }

void enqueue (  struct node *  vertex  ) 
 

Definition at line 483 of file dosreduce.c.

References head, QueueItem::next, node::p, tail, and QueueItem::u.

00484 {
00485   QueueItem *p = (struct QueueItem *) malloc (sizeof(QueueItem));
00486   if ( p == NULL){
00487     printf("Error here");
00488     exit(0);
00489   }
00490   p->u = vertex;
00491   p->next = NULL;
00492 
00493   if(head==NULL){
00494     head = p;
00495     tail = p;
00496   }
00497   else {
00498     tail->next= p;
00499     tail = p;
00500   }
00501 }

int main (  int  argc,
char **  argv
) 
 

Definition at line 43 of file dosreduce.c.

00044 {
00045   int i,j,k, maxd,id1,id2,noattackers,wt;
00046   int node_count,edges,victim;
00047   FILE *fp;
00048   struct node **V, *u;
00049   struct ATlinks *newlink;
00050   struct ATlinks *p;
00051   struct CTinfo **CrossTraffic;
00052   int **matrix;
00053   char temp[30];
00054   int pn1,pn2,*attackers;
00055   int found,activeconn,pathlen;
00056   int tempi;
00057   int *FT,lc,nc;
00058 
00059 
00060   if (argc < 3 ){
00061     printf("Usage: %s inet_topology #attackers #activeconnections\n",argv[0]);
00062     exit(0);
00063   }
00064 
00065   noattackers = atoi(argv[2]);
00066   activeconn = atoi(argv[3]);
00067   
00068   /* Read the node_count and edges for topo file */ 
00069   if ( (fp = fopen(argv[1],"r")) == NULL ){
00070     printf(" Error openning the adjanceny file\n");
00071     exit(1);
00072   }
00073 
00074   fscanf(fp,"%d %d",&node_count,&edges);
00075   /* Ignore location infomation */
00076   for(i=0;i<=node_count;i++){
00077     fgets(temp,30,fp);
00078   }
00079 
00080   /* Randomly choose victim node */
00081   victim = (int)((float)node_count*rand()/(RAND_MAX+1.0));
00082   if(debug){
00083     printf("node_count= %d edges %d victim=%d\n",node_count,edges,victim);
00084   }
00085 
00086   /* Initialise all remaining vertices 
00087    */
00088   V = (struct node **)malloc(node_count*sizeof(node));
00089   for(i=0;i<node_count;i++){
00090     V[i] = (struct node *) malloc (sizeof(node));
00091     V[i]->id=i;
00092     V[i]->c=0;
00093     V[i]->d=INFINITY;
00094     V[i]->p=INFINITY;
00095   }
00096   
00097   /* Initialise queue */
00098   head = tail = NULL;
00099   
00100   /* Initialise the root of bfs tree 
00101    * rootid can be the id of any node. like node 0 or leaf */
00102   V[victim]->c = 1;
00103   V[victim]->d = 0;
00104   V[victim]->p = INFINITY;
00105 
00106   enqueue(V[victim]);
00107   
00108   /* open file with adjaceny information */
00109   matrix = (int**)malloc(node_count*sizeof(int*));
00110   for(i=0;i<node_count;i++){
00111     matrix[i] = (int*)malloc(node_count*sizeof(int));
00112     for(j=0;j<node_count;j++){
00113       matrix[i][j]=0;
00114     }
00115   }
00116 
00117   for(i=0;i<edges;i++){
00118     fscanf(fp,"%d %d %d",&id1,&id2,&wt);
00119     matrix[id1][id2]=1;
00120     matrix[id2][id1]=1;
00121   }
00122 
00123   close(fp);
00124 
00125   
00126   while(head){
00127     u = (struct node *) malloc (sizeof(node));
00128     if(u== NULL){
00129       printf("Error allocationg u\n");
00130       exit(1);
00131     }
00132     u=dequeue();
00133     id1= u->id;
00134     for(i=0;i<node_count;i++){
00135       /* refer to adj matrix */
00136       if(matrix[id1][i] == 1 ){
00137     if (V[i]->c == 0){
00138       V[i]->c =1;
00139       V[i]->d = u->d + 1;
00140       V[i]->p = u->id;
00141       enqueue(V[i]);
00142     } 
00143       }
00144     }
00145 
00146       V[id1]->c = 2;
00147       V[id1]->p = u->p;
00148       V[id1]->d = u->d;
00149   }
00150 
00151   maxd =0;
00152   /* print out all the information */
00153   for (i=0;i<node_count;i++){
00154     /* printf("id: %d c=%d d=%d p=%d\n",V[i]->id,V[i]->c,V[i]->d,V[i]->p);  */
00155      if(maxd < V[i]->d)
00156        maxd = V[i]->d;
00157 
00158   }    
00159   if (debug) printf(" Max depth %d\n",maxd);
00160   
00161   /* Choose the attackers randomly in the topology  */
00162   attackers = (int*)malloc(noattackers*sizeof(int));
00163   for(i=0;i<noattackers;i++){
00164     attackers[i] = victim;
00165     /* Ensure the victim and attackers are distinct */
00166     while(attackers[i] == victim){
00167       attackers[i]= (int)((float)node_count*rand()/(RAND_MAX+1.0));
00168     }
00169     if(debug)
00170       printf("attacker[%d] = %d\n",i,attackers[i]);
00171   }
00172 
00173   /* Record the attack tree links */
00174   AThead = ATtail = NULL;
00175   for(i=0;i<noattackers;i++){
00176     pn1 = V[attackers[i]]->id;
00177     pn2 = V[attackers[i]]->p;
00178     while(pn2 != victim) {
00179 
00180       if(AThead == NULL){
00181     if ( (newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
00182       printf("Error allocationg space for new ATlink\n");
00183       exit(1);
00184     }
00185     newlink->n1=pn1;
00186     newlink->n2=pn2;
00187     AThead = newlink;
00188     ATtail = newlink;
00189     newlink->next = NULL;
00190       } else {
00191     /* insert only if not already present */
00192     ATlinks *p = AThead;
00193     while (p){
00194       if( (p->n1 != pn1) || (p->n2 != pn2) )
00195         p = p->next; 
00196       else 
00197         break;
00198     }
00199     /* link not found */ 
00200     if(p==NULL){
00201         if ( (newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
00202           printf("Error allocationg space for new ATlink\n");
00203           exit(1);
00204         }
00205         newlink->n1=pn1;
00206         newlink->n2=pn2;
00207         newlink->next = NULL;
00208         ATtail->next = newlink;
00209         ATtail = newlink;
00210     } else {
00211       /* reached common attack tree. Break from while */
00212       break; 
00213     }
00214 
00215       }
00216       pn1 = pn2;
00217       pn2 = V[pn1]->p;
00218     }
00219     /* Insert the last link before victim */ 
00220     if(pn2 == victim){
00221        if(AThead == NULL){
00222     if ( (newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
00223       printf("Error allocationg space for new ATlink\n");
00224       exit(1);
00225     }
00226     newlink->n1=pn1;
00227     newlink->n2=pn2;
00228     AThead = newlink;
00229     ATtail = newlink;
00230     newlink->next = NULL;
00231       } else {
00232       /* insert only if not already present */
00233     ATlinks *p = AThead;
00234     while (p){
00235       if( (p->n1 != pn1) || (p->n2 != pn2) )
00236         p = p->next;
00237       else 
00238         break;
00239     }
00240         /* link not found */ 
00241     if(p==NULL){
00242         if((newlink = (struct ATlinks *)malloc(sizeof(ATlinks))) == NULL){
00243           printf("Error allocationg space for new ATlink\n");
00244           exit(1);
00245         }
00246         newlink->n1=pn1;
00247         newlink->n2=pn2;
00248         newlink->next = NULL;
00249         ATtail->next = newlink;
00250         ATtail = newlink;
00251     }
00252       } /* end else */
00253     }
00254     
00255   }
00256     
00257   
00258   /* print the attack tree  and encode into matrix */
00259   i=0;
00260   p = AThead;
00261   while(p){
00262      if(debug) printf("%d n1= %d n2= %d\n",i++,p->n1,p->n2);
00263       matrix[p->n1][p->n2] = 2;
00264       p = p->next;
00265   }
00266 
00267   /* Now randomly choose the cross traffic source and sinks */
00268   CrossTraffic = (struct CTinfo **)malloc(activeconn*sizeof(CTinfo));
00269   for(k=0;k<activeconn;k++){
00270     if ((CrossTraffic[k] = (struct CTinfo *)malloc(sizeof(CTinfo))) == NULL){
00271       printf("%d:Error allocation Crosstraffic structure\n",errno);
00272       exit(1);
00273     }
00274     CrossTraffic[k]->src =(int)((float)node_count*rand()/(RAND_MAX+ 1.0));
00275     CrossTraffic[k]->dst =(int)((float)node_count*rand()/(RAND_MAX+ 1.0));
00276     if(CrossTraffic[k]->src == CrossTraffic[k]->dst){
00277       while(CrossTraffic[k]->dst == CrossTraffic[k]->src)
00278     CrossTraffic[k]->dst =(int)((float)node_count*rand()/(RAND_MAX+ 1.0));
00279     }
00280     CrossTraffic[k]->flag = 0; /* Usable */
00281     /* printf("src %d dst %d\n",CrossTraffic[k]->src, CrossTraffic[k]->dst);
00282        fflush(NULL); */
00283     
00284     /* fill path after bfs */
00285     /* Initialise the V matrix */
00286     for(i=0;i<node_count;i++){
00287       V[i]->id=i;
00288       V[i]->c=0;
00289       V[i]->d=INFINITY;
00290       V[i]->p=INFINITY;
00291     }
00292   
00293     /* Initialise queue */
00294     head = tail = NULL;
00295     tempi = CrossTraffic[k]->src;
00296 
00297     /* Initialise the root of bfs tree 
00298      * rootid can be the id of any node. like node 0 or leaf */
00299     V[tempi]->c = 1;
00300     V[tempi]->d = 0;
00301     V[tempi]->p = INFINITY;
00302 
00303     enqueue(V[tempi]);
00304     found=0;
00305     while(head){
00306       if((u = (struct node *)malloc(sizeof(node))) == NULL){
00307     printf("out of memory for u %d\n",errno);
00308     exit(1);
00309       }
00310     
00311       u=dequeue();
00312       id1= u->id;
00313       for(i=0;i<node_count;i++){
00314     /* refer to adj matrix */
00315     if(matrix[id1][i] != 0 ){
00316       if (V[i]->c == 0){
00317         V[i]->c =1;
00318         V[i]->d = u->d + 1;
00319         V[i]->p = u->id;
00320         if (V[i]->id == CrossTraffic[k]->dst){
00321           found = 1;
00322           pathlen = V[i]->d;
00323           break; 
00324         }
00325         enqueue(V[i]);
00326       } 
00327     }
00328       }
00329       if(found == 1){ 
00330     cleanq();
00331     break;
00332       }
00333       V[id1]->c = 2;
00334       V[id1]->p = u->p;
00335       V[id1]->d = u->d;
00336     }
00337 
00338     /* print the information */
00339     if(debug)
00340       printf("%d Src %d Dst %d Path ",k,CrossTraffic[k]->src,CrossTraffic[k]->dst);
00341 
00342     /* Find the path from src to dst */
00343     /* Stored dst, dst-1...src */ 
00344 
00345     CrossTraffic[k]->path = (int*)malloc(sizeof(pathlen));
00346     for(j=pathlen;j>=0;j--){
00347       if(j==pathlen)
00348     CrossTraffic[k]->path[j] = CrossTraffic[k]->dst;
00349       else {
00350     tempi = CrossTraffic[k]->path[j+1];
00351     CrossTraffic[k]->path[j] = V[tempi]->p;
00352       }
00353       if(debug)
00354     printf("%d ",CrossTraffic[k]->path[j]);
00355 
00356     }
00357   
00358     /* Matrix encoding 
00359      * 0 = no link 
00360      * 1 = link ( no traffic )
00361      * 2 = attack link only 
00362      * 3 = attack + cross traffic link 
00363      * 4 = cross traffic link only but path on AT  
00364      * 5 = only one flow of cross traffic 
00365      * 6 = more than one flow of cross traffic on link 
00366      *
00367 
00368      * Flag encoding 
00369      * 0 : discard 
00370      * 1 : shared attack tree 
00371      * 2 : shared cross traffic links 
00372      **** */ 
00373     /* Check is flag should change */ 
00374     for(j=0;j<pathlen;j++){
00375       if((matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]] == 2) \
00376       || (matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]] == 3)){
00377     CrossTraffic[k]->flag = 1;
00378       }
00379     }
00380 
00381     for(j=0;j<pathlen;j++){
00382       switch(matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]]){
00383       case 1:
00384     if(CrossTraffic[k]->flag == 1)
00385       tempi=4;
00386     else 
00387       tempi=5;
00388     break;
00389       case 2:
00390     if(CrossTraffic[k]->flag == 0){
00391       printf("Flag has to be 1 or 2 for %d\n",k);
00392       printf("info: link %d %d, matrix = %d\n",\
00393          CrossTraffic[k]->path[j],CrossTraffic[k]->path[j+1], matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]]); 
00394       exit(1);
00395     }
00396     tempi=3;
00397     break;
00398       case 3:
00399     if(CrossTraffic[k]->flag == 0){
00400       printf("Flag has to be 1 or 2 for %d\n",k);
00401       printf("info: link %d %d, matrix = %d\n",\
00402          CrossTraffic[k]->path[j],CrossTraffic[k]->path[j+1], matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]]); 
00403 
00404       exit(1);
00405     }
00406     tempi=3;
00407     break;
00408     /*
00409        //case 4:
00410     //if(CrossTraffic[k]->flag == 1)
00411      // tempi=4;
00412     //else {
00413     //  tempi=6;
00414     //  CrossTraffic[k]->flag = 2;
00415     //}
00416     //break;
00417       //case 5:
00418 //  if (CrossTraffic[k]->flag == 0)
00419 //    tempi = 5;
00420 //  else {
00421 //    CrossTraffic[k]->flag =2;
00422 //    tempi = 6;
00423 //  }
00424 //  break; 
00425     */
00426     
00427 }
00428       matrix[CrossTraffic[k]->path[j]][CrossTraffic[k]->path[j+1]] = tempi;
00429     } /* for the switch */ 
00430 
00431     if(debug) printf("Flag %d\n",CrossTraffic[k]->flag);
00432   } /* Close for number of active connections  */
00433 
00434   /* Get number of nodes and links in reducted topology */ 
00435   FT = (int *)malloc(node_count*sizeof(int));
00436   if ( FT == NULL){
00437     printf("out of memory\n");
00438     exit(0);
00439   }
00440   for(i=0;i<node_count;i++)
00441     FT[i] =0;
00442   lc=0;
00443   nc=0;
00444 
00445   for(i=0;i<node_count;i++){
00446     for(j=0;j<node_count;j++){
00447       // printf("[%d][%d]= %d\n",i,j,matrix[i][j]);
00448       if((matrix[i][j] == 2) || (matrix[i][j] == 3) || (matrix[i][j] == 4) || (matrix[i][j] == 6)){
00449     if(FT[i]==0){
00450       FT[i] = 1;
00451       printf("node %d\n",i);
00452       nc++;
00453     }
00454     if(FT[j] == 0){
00455       FT[j]=1;
00456       printf("node %d\n",j);
00457       nc++;
00458     }
00459     printf("link %d %d\n",i,j);
00460     lc++;
00461       } 
00462     }
00463   }
00464   printf("\nSummary\n");
00465   printf("Total: Nodes %d Links %d\n",nc,lc);
00466   printf("Victim: %d\n",victim);
00467   printf("Attackers:");
00468   for(i=0;i<noattackers;i++) printf(" %d",attackers[i]);
00469   printf("\n");
00470   
00471   return 0; 
00472 }

Variable Documentation

ATlinks* AThead
 

Definition at line 36 of file dosreduce.c.

ATlinks * ATtail
 

Definition at line 36 of file dosreduce.c.

int debug = 0
 

Definition at line 8 of file dosreduce.c.

QueueItem* head
 

Definition at line 35 of file dosreduce.c.

Referenced by JoBS::adjustRatesRDC(), JoBS::assignRateDropsADC(), cleanq(), JoBS::deque(), dequeue(), JoBS::dropFront(), JoBS::enforceWC(), enqueue(), HttpHbData::extract(), InvalidationRec::insert(), JoBS::minRatesNeeded(), JoBS::pickDroppedRLC(), PrintEntry_Squid(), PrintEntry_Text(), JoBS::projDelay(), ReadEntryV1(), HttpMInvalCache::recv_inv(), EWdetectorB::sortAList(), ToOtherEndian(), and JoBS::updateError().

QueueItem * tail
 

Definition at line 35 of file dosreduce.c.

Referenced by dequeue(), JoBS::dropTail(), enqueue(), PrintEntry_Squid(), PrintEntry_Text(), ReadEntryV1(), CalendarScheduler::resize(), EWdetectorB::sortAList(), and ToOtherEndian().

Generated on Tue Mar 6 16:52:11 2007 for ns2 Network Simulator 2.29 by  doxygen 1.4.6