rout.c

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

			     + 1;; 
			   bestAdj = adj2;
                         };
			 break;
		       case ADD:
			 if ((*(cost_matrix + tmp2->nodePtr()->name()) + 
			      weight + (*(hop_matrix + tmp2->nodePtr()->name())
					  * ALPHA)) < bestCost) {
                           bestCost =  *(cost_matrix + tmp2->nodePtr()->name())
                                       + weight + 
				       (*(hop_matrix + tmp2->nodePtr()->name())
				       * ALPHA);
                           bestDest = adj->nodePtr();
                           bestSource = tmp2->nodePtr();
			   bestHop = *(hop_matrix + tmp2->nodePtr()->name())
			     + 1;; 
			   bestAdj = adj2;
                         };
			 break;
		       };
		     };
                     adj = adj->next();
                  };
                  tmp2 = tmp2->next();
               };

               if (bestCost < DBL_MAX) {
		 //Check if bestDest is already in the tree
		   tmp2 = tree;
		 while ((tmp2 != NULL) && (done == False)) {
		   if (tmp2->nodePtr() == bestDest) {
		     done = True;
		     bestConn = bestDest; //this is the best connection 
		                          //point to the tree
		   }
		   else tmp2 = tmp2->next();
		 };
	       }
               else {
                     removeTree(source, addr);
                     int path = False;
                     prunePIM(fn, tmp1->nodePtr(), NULL, NULL, 
                              &tree2, path, addr, source, pk, avg, totalCost);

                     //delete the temp tree
                     tmp1 = tree;
                     NodeListEntry *tmp3;
                     while (tmp1 != NULL) {
                       tmp3 = tmp1->next();
                       delete tmp1;
                       tmp1 = tmp3;
                     };
                     //delete the temp tree2
                     tmp1 = tree2;
                     while (tmp1 != NULL) {
                         tmp3 = tmp1->next();
                         delete tmp1;
                         tmp1 = tmp3;
                     };
                     delete [] cost_matrix;
		     delete [] hop_matrix;
                     return(LINKSAT);
               };
               if (done == False) { //if not already in the tree

                  //Add the least cost node to the tree
                  tmp2 = new NodeListEntry;
                  tmp2->nodePtr(bestDest);
                  tmp2->next(tree2);
                  tree2 = tmp2;
                  bestDest->addChild(addr, source, bestSource);
                  bestSource->addChild(0, NULL, bestDest);  //for pruning
                  *(cost_matrix + bestDest->name()) = bestCost;
		  *(hop_matrix + bestDest->name()) = bestHop;
                  lastNode = bestDest;   
                  if (fn == PEAK) totalCost += bestAdj->peak();
                  else totalCost += bestAdj->average();
                  double wght = bestAdj->peak() + pk;
                  bestAdj->peak(wght);
                  double average = bestAdj->average() + avg;
                  bestAdj->average(average);
               }
               else { //if already in the tree

                   bestDest->addChild(addr, source, bestSource);
                   AdjacencyListEntry *adj = bestDest->adjacentNodes();
                   //update  the link cost at this best connection point
                   int found2 = False;
                   while ((adj != NULL) && (found2 == False)) {
                      if (adj->nodePtr() == bestSource) found2 = True;
                      else adj = adj->next();
                   };
                   if (adj != NULL) {
                       if (fn == PEAK) totalCost += bestAdj->peak();
                       else totalCost += bestAdj->average();
                       double wght = adj->peak() + pk;
                       adj->peak(wght);
                       double average = adj->average() + avg;
                       adj->average(average);
		  };
		  bestSource->addChild(0, NULL, bestDest);  //for pruning   

                  //prune nonmember leaves
                  int path = False;
                  prunePIM(fn, tmp1->nodePtr(), NULL, bestConn, 
                           &tree2, path, addr, source, pk,
                           avg, totalCost);  

                  //Join the pruned tree2 to the tree
                  tmp2 = tree2;
                  while (tmp2->next() != NULL) {
                      tmp2 = tmp2->next();
                  };
                  tmp2->next(tree);
                  tree = tree2;

                  for (i = 0; i < num; i++) *(cost_matrix + i) = DBL_MAX;
               };
            };
         };
         tmp1 =tmp1->next(); //repeat for all group members
      };
      delete [] cost_matrix;
      delete [] hop_matrix;


      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 > 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;

      //Now delete the temp tree
      tmp1 = tree;
      NodeListEntry *tmp3;
      while (tmp1 != NULL) {
	 nodes++;
         tmp3 = tmp1->next();
         delete tmp1;
         tmp1 = tmp3;
      };
      if ((DBV == True) && (dbViolation == True)) {
         removeTree(source, addr);
         return(DBVIOL);
      }
      else return(totalCost);
   }
   else return(NOGROUP);
};

void TheNodeList::prunePIM(int fn, Node *current, Node *dest, 
                           Node *bestConn, NodeListEntry **tree, int &path, 
                           int addr, Node *source, double peak, double avg,
                           double &cost) {

   //First locate the routing table entry corresponding to group address 0 and 
   //source NULL
   RoutingTableEntry *rout = current->routingTable();
   RoutingTableEntry *prout = NULL;
   int found = False;
   while ((rout != NULL) && (found == False)) {
      if ((rout->address() == 0) && (rout->source() == NULL)) found = True;
      else {
          prout = rout;
          rout = rout->next();
      };
   };

   if (found == True) { //if current is not a leaf

      //prune tree recursively
      NodeListEntry *tmp = rout->children();
      NodeListEntry *prev = NULL;
      int tmpPath;
      while (tmp != NULL) {
          tmpPath = False;
          prunePIM(fn, tmp->nodePtr(), current, 
                   bestConn, tree, tmpPath, addr, source, peak,
                   avg, cost);
          path = path | tmpPath;
          if (tmp == rout->children()) {
              rout->removeDestination(tmp->nodePtr());
              tmp = rout->children();
          }
          else {
              NodeListEntry *tmp2 = tmp->next();
              rout->removeDestination(tmp->nodePtr());
              tmp = tmp2;
          };
      };

      // At the end if path = False remove Entry for (addr, Source, dest);
      if ((path == False) && (dest != NULL)) {
          AdjacencyListEntry *adj = current->adjacentNodes();
          while (adj->nodePtr() != dest) adj = adj->next();
          if (adj != NULL) {
             double wght = adj->peak() - peak;
             adj->peak(wght);
             double average = adj->average() - avg;
             adj->average(average);
             if (fn == PEAK) cost -= adj->peak();
             else cost -= adj->average();
             current->removeChild(addr, source, dest);
         };
      };

      //delete the temporary routing entry which was created for pruning
      //purposes only.
      if (prout != NULL) prout->next(rout->next());
      else current->routingTable(rout->next());
      delete rout;
   }
   else { // if current is a leaf
      // check if this is the bestConn  then path = True else path = False
      // if path = False remove routingEntry (addr, source, dest??);
      if (current == bestConn) path = True;
      else {
          AdjacencyListEntry *adj = current->adjacentNodes();
          while ((adj != NULL) && (adj->nodePtr() != dest)) adj = adj->next();
          if (adj != NULL) {
             double wght = adj->peak() - peak;
             adj->peak(wght);
             double average = adj->average() - avg;
             adj->average(average);
             if (fn == PEAK) cost -= adj->peak();
             else cost -= adj->average();
             current->removeChild(addr, source, dest);
         };
      };
   };
    
   //if the node is not in the path
   if (path == False) {

      //delete the created routing entry.
      RoutingTableEntry *rout1 = current->routingTable();
      RoutingTableEntry *prout1 = NULL;
      int found1 = False;
      while ((rout1 != NULL) && (found1 == False)) {
         if ((rout1->address() == addr) && (rout1->source() == source))
            found1 = True;
         else {
            prout1 = rout1;
            rout1 = rout1->next();
         };
      };

      if (rout1->children() == NULL) { //It should always be NULL
        if (prout1 == NULL) current->routingTable(rout1->next());
        else prout1->next(rout1->next()); 
        delete rout1;
      };

      //delete it from the tree
      NodeListEntry *tmp = *tree;
      NodeListEntry *tmp2 = NULL;
      found = False;
      while ((tmp != NULL) && (found == False)) {
         if (tmp->nodePtr() == current) found = True;
         else {
            tmp2 = tmp;
            tmp = tmp->next();
         };
      };
      if (found == True) {
         if (tmp == *tree) *tree = tmp->next();
         else tmp2->next(tmp->next());
         delete tmp;
      };
   };
};