routcao.c

一个linux下的各种组播路由算法编程

	   j++;
	 };
       };
     };
	 
     //Create a routing table entry for each group member
     tmp = group->headm();
     while (tmp != NULL) {
       tmp->nodePtr()->addRoutingEntry(addr, source);
       tmp = tmp->next();
     };

     //Create the physical paths and merge them
     NodeListEntry *tree = NULL;
     double *delay; 
     int *waiting;
     delay = new double[gCount];
     waiting = new int[gCount];
     for (i = 0; i < gCount; i++) {
       *(delay + i) = 0;
       pth = (*(mPath + i))->pred;
       j = 0;
       while (*(pth + j) != INT_MAX) j++;
       j--;
       *(waiting + i) = *(pth + j);
       *(encountered + *(pth + j)) += 1;
       if ((i == (gCount - 2)) && (srceMember == True)) i++;
     };

     int stop, from, to;
     Node *ndFrom, *ndTo;
     AdjacencyListEntry *adj;
     double wght, average;
     int change = False;
     done = False;
     i = 0;
     while (done == False) {
       if (i == gCount) {
	 if (change == False) { 
//printf("sev\n");
	   if (severeConflict(gCount, member, occur, encountered, delay, 
			      d_matrix, waiting, mPath, srce) == False) {
	     delete [] d_matrix;
	     delete [] member;
	     delete [] delay;
	     delete [] waiting;
	     delete [] occur;
	     delete [] encountered;
	     for (i = 0; i < gCount; i++) delete (*(mPath + i));
	     delete [] mPath;
	     NodeListEntry *tmp1 = tree;
	     NodeListEntry *tmp2 = NULL;
	     while (tmp1 != NULL) {
	       tmp2 = tmp1->next();
	       delete tmp1;
	       tmp1 = tmp2;
	     };
	     tmp1 = nodeListHd;
	     while (tmp1 != NULL) {
	       RoutingTableEntry *rout = tmp1->nodePtr()->routingTable();
	       int found = False;
	       while ((rout != NULL) && (found == False)) {
		 if ((rout->address() == addr) && (rout->source() == source)) 
		 found = True;
		 else rout = rout->next();
	       };
	       if (found == True) {
		 NodeListEntry *tmp = rout->children();
		 while (tmp != NULL) {
		   AdjacencyListEntry *adj = tmp1->nodePtr()->adjacentNodes();
		   int found2 = False;
		   while ((adj != NULL) && (found2 == False)) {
		     if (adj->nodePtr() == tmp->nodePtr()) found2 = True;
		     else adj = adj->next();
		   };
		   if (adj != NULL) {
		     wght = adj->peak() - pk;
		     adj->peak(wght);
		     average = adj->average() - avg;
		     adj->average(average);
		   };
		   tmp = tmp->next();
		 };
		 tmp1->nodePtr()->removeRoutingEntry(addr, source);
	       };
	       tmp1 = tmp1->next();
	     };
	     return(CONFLICT);
	   };
	 };
	 change = False;
	 i = 0;
       };
       if ((*(member + i) != INT_MAX) && 
	   (*(encountered + *(waiting + i)) == *(occur + *(waiting + i)))) {
	 change = True;
	 pth = (*(mPath + i))->pred;
	 j = 0;
	 while (*(pth + j) != *(waiting + i)) j++;
	 to = *(pth + j);
	 from = *(pth + j - 1);
	 ndFrom = nodeOf(from);
	 ndTo = nodeOf(to);
	 ndFrom->addChild(addr, source, ndTo);
//printf("connecting from %d to %d\n", from, to);
	 //update the link cost
	 adj = ndFrom->adjacentNodes();
	 while (adj->nodePtr() != ndTo) adj = adj->next();
	 wght = adj->peak() + pk;
	 adj->peak(wght);
	 average = adj->average() + avg;
	 adj->average(average);
	 *(delay + i) += *(d_matrix + (from * num) + to);
	 //add to the tree
	 tmp = new NodeListEntry;
	 tmp->nodePtr(ndTo);
	 tmp->next(tree);
	 tree = tmp;
	 j--;
	 stop = False;
	 while (stop == False) {
	   to = *(pth + j);
	   *(encountered + to) += 1;
	   if (*(occur + to) == 1) {
	     if (to != srce) {
	       from = *(pth + j - 1);
	       ndFrom = nodeOf(from);
	       ndTo = nodeOf(to);
	       ndFrom->addChild(addr, source, ndTo);
	       //update the link cost
	       adj = ndFrom->adjacentNodes();
	       while (adj->nodePtr() != ndTo) adj = adj->next();
	       wght = adj->peak() + pk;
	       adj->peak(wght);
	       average = adj->average() + avg;
	       adj->average(average);

	       *(delay + i) += *(d_matrix + (from * num) + to);
	       
	       //add to the tree
	       tmp = new NodeListEntry;
	       tmp->nodePtr(ndTo);
	       tmp->next(tree);
	       tree = tmp;
	       
	       j--;
	     }
	     else {
	       stop = True;
	       done = True;
	     };
	   }
	   else if ((*(encountered + to) == *(occur + to)) &&
		    (to != srce)) {
	     *(waiting + i) = to; 
	     stop = True; 
	     resolveConflict(gCount, to, member, occur, encountered, 
			     delay, waiting, mPath);
	   }
	   else {
	     if (to == srce) *(member + i) = INT_MAX;
	     *(waiting + i) = to; 
	     stop = True; 
	   };
	 };
       };
       i++;
       if (*(encountered + srce) == *(occur + srce)) {
	 //add to the tree
	 tmp = new NodeListEntry;
	 tmp->nodePtr(source);
	 tmp->next(tree);
	 tree = tmp;
	 done = True;
       };
     };
     delete [] d_matrix;
     delete [] member;
     delete [] delay;
     delete [] waiting;
     delete [] occur;
     delete [] encountered;
     for (i = 0; i < gCount; i++) delete (*(mPath + i));
     delete [] mPath; 
     
     //Statistics and cleanup
      int dbViolation = False;
      maxd = 0;
      mind = DBL_MAX;
      //calculate the expected end-to-end delay and the average number of hops
      //and the cost per destination
      NodeListEntry *tmp2 = group->headm();
      double avgDelay = 0;
      double avgHops = 0;
      while (tmp2 != NULL) {
         int gotit = False;
         int hops = 0;
         double delay = 0;
         if (source != tmp2->nodePtr()) 
         results(source, addr, source, tmp2->nodePtr(), delay, hops, gotit);   
         if (delay >= DELAYBOUND) dbViolation = True;
//if (delay >= DELAYBOUND) printf("%d  delay %.3e\n", tmp2->nodePtr()->name(), delay);
         if (delay > maxd) maxd = delay;
         if (delay < mind) mind = delay;
         avgDelay += delay;
         avgHops += hops;
         tmp2 = tmp2->next();
      };
      avgDelay /= group->count();
      avgHops /= group->count();
      d = avgDelay;
      h = avgHops;

      //Calculate the total cost of the tree and delete the temp. tree
      double totalCost = 0;
      nodes = 0;
      NodeListEntry *tmp1 = tree;
      while (tmp1 != NULL) {
	 nodes++;
         RoutingTableEntry *rout = tmp1->nodePtr()->routingTable();
         int found = False;
         while ((rout != NULL) && (found == False)) {
           if ((rout->address() == addr) && (rout->source() == source)) 
                                                          found = True;
           else rout = rout->next();
         };
         NodeListEntry *tmp = rout->children();
         while (tmp != NULL) {
             AdjacencyListEntry *adj = tmp1->nodePtr()->adjacentNodes();
             int found2 = False;
             while ((adj != NULL) && (found2 == False)) {
                if (adj->nodePtr() == tmp->nodePtr()) found2 = True;
                else adj = adj->next();
             };
             if (adj != NULL) {
                if (fn == PEAK) totalCost += (adj->peak() - pk);
                else totalCost += (adj->average() - avg);
             };
             tmp = tmp->next();
         };
         tmp2 = tmp1->next();
         delete tmp1;
         tmp1 = tmp2;
      };

      if ((DBV == True) && (dbViolation == True)) {
         removeTree(source, addr);
         return(DBVIOL);
      }
      else return(totalCost);
   }
   else return(NOGROUP);
};

void TheNodeList::resolveConflict(int gCount, int nd, int *member, int *occur,
				  int *encountered, double *delay, 
				  int *waiting, path **mPath) {
  
  //I will resolve the conflicts only for the case when the Delay bound is
  //constant for all destinations.
  int i, j, k;
  int choose;
  double maxD = 0; 
  for (i = 0; i < gCount; i++) {
    if ((*(member + i) != INT_MAX) &&  (*(waiting + i) == nd)) {
      if (*(delay + i) > maxD) {
	choose = *(member + i);
	maxD = *(delay + i);
      };
    };
  };

  int *p;
  for (i = 0; i < gCount; i++) {
    if ((*(member + i) != INT_MAX) &&  (*(member + i) != choose) &&
	(*(waiting + i) == nd)) {
      p = (*(mPath + i))->pred;
      j = 0;
      while (*(p +j) != nd) j++;
      j--;
      while (j >= 0) {
	k = *(p + j);
	*(occur + k) -= 1;
	if ((j > 0) && (*(occur + k) > 1) && 
	    (*(occur + k) == *(encountered + k))) 
	  resolveConflict(gCount, k, member, occur, encountered, delay,
			  waiting, mPath);
	j--;
      };
      *(member + i) = INT_MAX;
    };
  };
};
     

int TheNodeList::severeConflict(int gCount, int *member, int *occur,
		 int *encountered, double *delay, double *d_matrix, 
		 int *waiting, path **mPath, int srce) {

  //printf("severe conflict\n");
  //I will resolve the conflicts only for the case when the Delay bound is
  //constant for all destinations.

  int i, j, k, l;
  int nd1, nd2;
  int *p1, *p2;
  double d1, d2;
  double minD = 0;

  int found = False;
  i = 0;
  while  ((found == False) && (i < gCount)) {
    if (*(member + i) != INT_MAX) {
      nd1 = *(waiting + i);
     p1 = (*(mPath + i))->pred;
      j = 1;
      d1 = 0;
      while ((*(p1 + j) != nd1) && (found == False)) {
	d1 += *(d_matrix + (*(p1 + j - 1) * num) + *(p1 + j));
	k = 0;
	while ((k < gCount) && (found == False)) {
	  if ((*(member + k) != INT_MAX) && (*(member + k) != *(member + i))
	      && (*(waiting + k) == *(p1 + j))) {
	    nd2 = *(waiting + k);
	    p2 = (*(mPath + k))->pred;
	    l = 1;
	    d2 = 0;
	    while ((*(p2 + l) != nd2) && (found == False)) {
	      d2 += *(d_matrix + (*(p2 + l - 1) * num) + *(p2 + l));
	      if (*(p2 + l) == nd1) found = True;
	      l++;
	    };
	  };
	  if (found == False) k++;
	};
        j++;
      };
      if (found == False) i++;
    }
    else i++;
  };

if (i < gCount) {
 //printf("member i %d member k %d\n", *(member +i), *(member + k));
 //printf("waiting i %d waiting  k %d\n", *(waiting +i), *(waiting + k));
 //printf("delay i %.3e delay  k %.3e\n", d1, d2);
};
  if (found == True) {
    if (d1 < d2) {
      p1 = (*(mPath + k))->pred;
      p2 = (*(mPath + i))->pred;
      nd1 = nd2;
      // *(member + k) = INT_MAX;
    }
    else {
      p1 = (*(mPath + i))->pred;
      p2 = (*(mPath + k))->pred;
      // *(member + i) = INT_MAX;
    };
    
    j = 0;
    while (*(p1 +j) != nd1) j++;
    j--;
    while (j >= 0) {
      l = *(p1 + j);
      *(occur + l) -= 1;
      j--;
    };
    l = 0;
    while (*(p2 + l) != nd1) {
      *(p1 + l)  = *(p2 + l);
      *(occur + *(p2 + l)) += 1;
      l++;
    };
    *(p1 + l) = nd1;
    *(p1 + l + 1) = INT_MAX;
    for (l = 0; l < num; l++) {
      if ((*(occur + l) > 1) && ( l != srce) && 
	  (*(occur + l) == *(encountered + l))) 
	resolveConflict(gCount, l, member, occur, encountered, delay,
			waiting, mPath);
    };
    return(True);
  }
  else return(False);
};