routld.c

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

double TheNodeList::leastDelay(Node *source, int addr, MCGroup **group,
			       NodeListEntry **tree, double &pk, double &avg) {

   //The basic part of Dijkstra's least-delay routing algorithm

   NodeListEntry *tmp1, *tmp2;
   Node   *bestDest;
   RoutingTableEntry *bestRout;
   AdjacencyListEntry *bestAdj;
   double bestCost;
   int bestHop;
   double *cost_matrix;
   int *hop_matrix;

   //First delete any previous routing for the this group and source set.
   removeTree(source, addr);

   //Locate the source to get the peak rate
   SourceList *ss = source->sourceList();
   int found = False;
   while ((ss != NULL) && (found == False)) {
       if ((ss->source()->type() != Background) &&
           (ss->source()->address() == addr)) found = True;
       else ss = ss->next();
   };
   pk = ss->source()->peak();
   avg = ss->source()->average();

   //Locate the MC group that contains the destination set
   *group = groupsHd;
   while ((*group !=  NULL) && ((*group)->address() != addr))   
      *group = (*group)->next();

   if (*group != NULL)  {

      cost_matrix = new double[num];
      int i;
      for (i = 0; i < num; i++) *(cost_matrix + i) = DBL_MAX;
      hop_matrix = new int[num];

      if (((*group)->count() == 1) && 
          ((*group)->headm()->nodePtr()->name() == source->name())) {
            source->addRoutingEntry(addr, source);
	    delete [] cost_matrix;
            delete [] hop_matrix;
            return(GOOD);
      };

      //The source is the first member in the tree
      *tree = new NodeListEntry;
      (*tree)->nodePtr(source);
      *(cost_matrix + source->name()) = 0;
      *(hop_matrix + source->name()) = 0;
      source->addRoutingEntry(addr, source);
      
      int done = False;
      while (done == False) {

         tmp1 = *tree;          //for each node already in the tree
         bestCost = DBL_MAX;   //infinity
         bestAdj = NULL;
         while (tmp1 != NULL) {

            //find the routing table entry for the given group & source
            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();
            };

            //scan the adjacency list for the least cost (weight) link
            AdjacencyListEntry *adj = tmp1->nodePtr()->adjacentNodes();
            while (adj != NULL) {
               int better = False;
	       double weight;
	       if ((fn == PEAK) && ((adj->peak() + pk) <= 
                   (adj->linkCapacity() * ADMITRATIO)))
                  weight = adj->delay();
	       else if ((fn == AVERAGE) && 
                        ((adj->average() + avg) <= 
                         (adj->linkCapacity() * ADMITRATIO))) 
                  weight = adj->delay();
               else weight = DBL_MAX;
               switch (obj) {
               case PLAIN:
                 if ((*(cost_matrix + tmp1->nodePtr()->name()) + weight) < 
	              bestCost) better = True;
                 break;
               case MULT:
                 if ((*(cost_matrix + tmp1->nodePtr()->name()) 
                      + weight * (*(hop_matrix + tmp1->nodePtr()->name()) + 1))
                      < bestCost) better = True;
                 break;
               case ADD:
                 if ((*(cost_matrix + tmp1->nodePtr()->name()) 
                   + weight + *(hop_matrix + tmp1->nodePtr()->name()) * ALPHA) 
                   < bestCost) better = True;
                 break;
               };

               //if the cost of that adjacent node is less than the best 
               //cost so far
               if (better == True) {
                   tmp2 = *tree;
                   found = False;
                   while ((tmp2 != NULL) && (found == False)) {
                   //check if that adjacent node is already in the tree
                        if (tmp2->nodePtr() == adj->nodePtr()) found = True;
                        else tmp2 = tmp2->next();
                   };
                   if (found == False) {
                   //if not update the bestCost ...etc.
                     switch (obj) {
                     case PLAIN:   
		       bestCost = 
			  *(cost_matrix + tmp1->nodePtr()->name()) + weight;
                       break;
                     case MULT:
		       bestCost = 
		       *(cost_matrix + tmp1->nodePtr()->name()) + 
                       weight * (*(hop_matrix + tmp1->nodePtr()->name()) + 1);
                       break;
                     case ADD:
		       bestCost = 
		       *(cost_matrix + tmp1->nodePtr()->name()) + 
                       weight + *(hop_matrix + tmp1->nodePtr()->name()) * ALPHA;
                       break;
                     };
		     bestDest = adj->nodePtr();
		     bestRout = rout;
		     bestAdj = adj;
                     bestHop = *(hop_matrix + tmp1->nodePtr()->name()) + 1;
                   };
               };
               adj = adj->next(); //repeat for all nodes adjacent to tmp1
            };
            tmp1 = tmp1->next(); //repeat for all nodes already in the tree
         };

	 if (bestAdj == NULL) {
            removeTree(source, addr);
            tmp1 = *tree;
            while (tmp1 != NULL) {
              tmp2 = tmp1->next();
              delete tmp1;
              tmp1 = tmp2;
           };
	   delete [] cost_matrix;
	   delete [] hop_matrix;
           return(LINKSAT);
	 }
         else {
            //Add the least cost node to the tree
            tmp1 = new NodeListEntry;
            tmp1->nodePtr(bestDest);
            tmp1->next(*tree);
            *tree = tmp1;

	    //update the link cost
	    double wght = bestAdj->peak() + pk; //link costs are proportional
                                                 //to the peak rates of the 
                                                 //traffic crossing these
                                                 //links.
             bestAdj->peak(wght);
             double average = bestAdj->average() + avg;
             bestAdj->average(average);

            //and add it to the routing table of the best connection node
            bestRout->addDestination(bestDest);

            //create a new routing table entry for that node
	      bestDest->addRoutingEntry(addr, source);
	      *(cost_matrix + bestDest->name()) = bestCost;
              *(hop_matrix + bestDest->name()) = bestHop;      
            //Check if the tree contains all group members
            tmp2 = (*group)->headm();
            int quit = False;
            while ((tmp2 != NULL) && (quit == False)) {
               int found = False;
               tmp1 = *tree;
               while ((tmp1 != NULL) && (found == False)) {
                  if (tmp1->nodePtr() == tmp2->nodePtr()) found = True;
                  else tmp1 = tmp1->next();
               };
               if (tmp1 == NULL) quit = True; //if the tree doesn't include all
                                              //group members yet.
               tmp2 = tmp2->next();
            };
            if (quit == False) done = True;
         }; //end bestCost >= 
      }; //end done

      //prune nonmember leaves
      prune(*group, tree, source, source, addr, NULL, pk, avg);
      delete [] cost_matrix;
      delete [] hop_matrix;
      return(GOOD);      
   }
   else return(NOGROUP);
};

double TheNodeList::routerLD(Node *source, int addr,  double &d, 
			     double &maxd, double &mind, 
			     double &h, double &nodes) {

   //The complete Dijkstra's least-delay routing algorithm, including
   //all statistics

   MCGroup *group;
   NodeListEntry *tree;
   double pk, avg;
   double status = leastDelay(source, addr, &group, &tree, pk, avg);
   if (status == GOOD) {
      int dbViolation = False;
      maxd = mind = 0;
      //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;

      //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(status);
};