routatm.c

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

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

   double totalCost = 0;

   //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();
   };
   double pk = ss->source()->peak();
   double avg = ss->source()->average();

   //Locate the MC group that contains the destination set
   MCGroup *group = groupsHd;
   while ((group !=  NULL) && (group->address() != addr))   
      group = group->next();
   
   if (group != NULL) {
      //Find the bound on the delay (the maximum shortest delay to any node in
      //the network) using Dijkstra's algorithm

      if ((group->count() == 1) && 
          (group->headm()->nodePtr()->name() == source->name())) {
            source->addRoutingEntry(addr, source);
            h = d = maxd = mind = 0;
            nodes = 1;
            return(0);
      };

      double *delay_matrix;
      delay_matrix = new double[num*num];
      double *cost_matrix;
      cost_matrix = new double[num*num];
      double *dbv;
      dbv = new double[num];
      double dbB = 0.0;
      int i, j;
      for (i = 0; i < num; i++) {
         for (j = 0; j < num; j++) {
           (*(delay_matrix + (i * num) + j)) = DBL_MAX;
           (*(cost_matrix + (i * num) + j)) = DBL_MAX;
         };
         *(dbv + i) = DBL_MAX;         
      };
      (*(delay_matrix + (source->name() * num) + source->name())) = 0;
      (*(cost_matrix + (source->name() * num) + source->name())) = 0;
      *(dbv + source->name()) = 0;

      dijkstra(alg, fn, source, delay_matrix, cost_matrix, dbv, pk, avg);

      for (i = 0; i < num; i++) {
         if (dbB < (*(dbv + i))) dbB = (*(dbv + i));
         if ((*(dbv + i)) == DBL_MAX) {
            delete [] delay_matrix;
            delete [] dbv;
            delete [] cost_matrix;
            return(LINKSAT);
         };
      };

      for (i = 0; i < num; i++) {
         for (j = 0; j < num; j++) {
            if ((*(delay_matrix + (i * num) + j)) > dbB) {
               (*(delay_matrix + (i * num) + j)) = DBL_MAX;
               (*(cost_matrix + (i * num) + j)) = DBL_MAX;
            };
         };
      };

      //sort the nodes in discending order of dbv
      int *o;
      o = new int[num];
      for (i = 0; i < num; i++) o[i] = i;
      for (i = 0; i < (num - 1); i++) {
         for (j = 0; j < (num - i - 1); j++) {
            if ((*(dbv + o[j])) < (*(dbv + o[j+1]))) {
               int swap = o[j+1];
               o[j+1] = o[j];
               o[j] = swap;
            };
         };
      };

      //The source is the first member in the tree
      NodeListEntry *tree = new NodeListEntry;
      tree->nodePtr(source);
      source->addRoutingEntry(addr, source);

      //For each node, if it is not already in the
      //tree, then find the shortest path from that member to any node already
      //in the tree
      int k;
      for (k = 0; k < num; k++) {
         Node *tmp1 = nodeOf(o[k]);     
         //check if already in the tree
         NodeListEntry *tmp2 = tree;
         int inTree = False;
         while ((tmp2 != NULL) && (inTree == False)) {
            if (tmp2->nodePtr() == tmp1) inTree = True;
            else tmp2 = tmp2->next();
         };

         if (inTree == False) {  //if not already in tree

            //create a new routing table entry for tmp1
            tmp1->addRoutingEntry(addr, source);

            NodeListEntry *path = NULL;
            pathWaters(source, addr, o[k], delay_matrix, cost_matrix, 
                dbB, &tree, pk, avg, &path);
            NodeListEntry *tmp3, *tmp4;
            tmp3 = path;
            tmp4 = NULL;
            while (tmp3 != NULL) {
               tmp4 = tmp3->next();
               delete tmp3;
               tmp3 = tmp4;
            };
         };      
      };

      //prune nonmember leaves
      prune(group, &tree, source, source, addr, NULL, pk, avg);

      maxd = 0;
      mind = DBL_MAX;
      int dbViolation = False;
      //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 tree
      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;
      };
      delete [] delay_matrix;
      delete [] dbv;
      delete [] cost_matrix;
      delete [] o;
      if ((DBV == True) && (dbViolation == True)) {
         removeTree(source, addr);
         return(DBVIOL);
      }
      else return(totalCost);
   }
   else return(NOGROUP);
};

void TheNodeList::dijkstra(int alg, int fn, Node *source,
                           double *delay_matrix, double *cost_matrix, 
                           double *dbv, double peak, double average) {

  double *cost;
  cost = new double[num];
  *(cost + source->name()) = 0;
  int *hops;
  hops = new int[num];
  *(hops + source->name()) = 0;

  //The source is the first member in the tree
  int *tree, i, k, found;
  tree = new int[num+1];
  *tree = source->name();
  for (i = 1; i <= num; i++) *(tree + i) = INT_MAX;

  AdjacencyListEntry *adj = source->adjacentNodes();
  while (adj != NULL) {
     double weight;
     if ((fn == PEAK) && ((adj->peak() + peak) <= 
                          (adj->linkCapacity() * ADMITRATIO))) 
       weight = adj->peak();
     else if ((adj->average() + average) <= (adj->linkCapacity() * ADMITRATIO))
       weight = adj->average();
     else weight = DBL_MAX;
     if (weight != DBL_MAX) {
       *(cost_matrix + (adj->nodePtr()->name() * num) + source->name()) 
         = weight;
       *(delay_matrix + (adj->nodePtr()->name() * num) + source->name())
         = adj->delay();
     };
     adj = adj->next();
   };

   for (k = 0; k < (num-1); k++) {
         double bestCost = DBL_MAX;   //infinity
         int bestHop;
         int bestFrom;
         double bestDel = DBL_MAX;
         int bestDest = INT_MAX;
         Node *nd;
         i = 0;
         int tmp = *tree;
         while (tmp != INT_MAX) {