routdcdimst.c

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

/*****************************************************************************
***                      Author: Hussein F. Salama                         ***
***                       Date: March 20, 1995                             ***
***                            File: routDCDIMST.c                             ***
***                        Routing Algorithms                              *** 
*****************************************************************************/

//ASSUMPTION: For this algorithm to work correctly, the delay along a direct link from the source s to a node x is always less that the delay along any possible path from s to x in the give network.


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


  //An Near-Optimal Delay-Constrained (and unconstrained) Minimum Spanning 
  //Tree Algorithm for 
  //Directed Graphs (Networks with asymmetric link loads)

  //Note: This algorithm can not be used with additive nor multiplicative 
  //penalties;

  //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)  {
    
    if ((group->count() == 1) && 
	(group->headm()->nodePtr()->name() == source->name())) {
      source->addRoutingEntry(addr, source);
      h = d = maxd = mind = 0;
      nodes = 1;
      return(0);
    };

    double *cost_matrix = new double[num];
    double *actual_delay_matrix = new double[num];
    double *max_delay_matrix = new double[num];
    int *from_matrix = new int[num];
    int *blacklist_matrix = new int[num*num];
    int *branch_matrix = new int[num];

    int i, j;
    for (i = 0; i < num; i++) {
      *(from_matrix + i) = INT_MAX;
      *(branch_matrix + i) = INT_MAX;
      for (j = 0; j < num; j++) *(blacklist_matrix + i*num + j) = False;
    };

    //The source is the first member in the tree
    int srce = source->name();
    *(cost_matrix + srce) = 0;
    *(actual_delay_matrix + srce) = 0;
    *(max_delay_matrix + srce) = 0;
    *(from_matrix + srce) = srce;
    *(branch_matrix + srce) = 0;
    
    int done = False;
    int relaxDelays = False;
    int inTree = 1;
    int blacklistEmpty = True;
    while (done == False) {

      double bestCost = DBL_MAX;   //infinity
      int bestDest = INT_MAX;
      int bestSrce = INT_MAX;
      double delay_relaxation = 0;
      AdjacencyListEntry *bestAdj = NULL;
      for (i = 0; i < num; i++) {    //for each node already in the tree:
	if (*(from_matrix + i) != INT_MAX) {
//printf("i = %d\n", i);
	  //scan the adjacency list for the least cost (weight) link
	  AdjacencyListEntry *adj = nodeOf(i)->adjacentNodes();
	  while (adj != NULL) {
	    int nme = adj->nodePtr()->name();
	    if ((nme != srce) && (*(blacklist_matrix + i*num+nme) == False)) {
	      int better = False;
	      double weight;
	      if ((fn == PEAK) && ((adj->peak() + pk) <= 
				   (adj->linkCapacity() * ADMITRATIO)))
		weight = adj->peak();
	      else if ((fn == AVERAGE) && 
		       ((adj->average() + avg) <= 
			(adj->linkCapacity() * ADMITRATIO))) 
		weight = adj->average();
	      else weight = DBL_MAX;
	      if ((weight < bestCost) || (relaxDelays == True)) better = True;
	      
	      //if the cost of that adjacent node is less than the best 
	      //cost so far;
	      if (better == True) {
		int found = False;
		
		//check if that adjacent node is already in the tree
		if (*(from_matrix + nme) != INT_MAX) {
//printf("in\n");
		  //check if that node is on the path from the srce to the
		  //potential bestSrce node
		  if (i == *(from_matrix + nme)) found = True;
		  j = i;
		  while ((j != srce) && (found == False)) {
		    if (*(from_matrix + j) == nme) found = True;
		    else j = *(from_matrix + j);
		  };

		  //if not check if the potential link is cheaper than the 
		  //link already used for connecting the potential 
		  //destination and that using that link will not lead to 
		  //delay bound violations;
//printf("in path = %d\n", found);
		  if (found == False) {
//printf("in2\n");
		    if (alg == dimst) { 
		      if (weight >= *(cost_matrix + nme)) found = True;
		    }
		    else {
//printf("1\n");
		      if (relaxDelays == False) {
//printf("2\n");
			if  (weight >= *(cost_matrix + nme)) found = True;
			else {
//printf("3\n");
			  if (inTree == num) {
			    if ((*(max_delay_matrix + nme) -
				 *(actual_delay_matrix + nme) + 
				 *(actual_delay_matrix + i) + adj->delay()) >
				DELAYBOUND) found = True;
			  }
			  else {
//printf("4\n");
			    if ((*(actual_delay_matrix + i) + adj->delay()) >=
				(*(actual_delay_matrix + nme))) found = True;
			  };
			};
		      }
		      else {
			if ((*(actual_delay_matrix + nme) -
			     (*(actual_delay_matrix + i) + adj->delay()))
			    > delay_relaxation) delay_relaxation =
			      *(actual_delay_matrix + nme) -
				(*(actual_delay_matrix + i)+adj->delay());
			else found = True;
		      };
		    };
		  };
		}
		else if ((alg == dcdimst) && ((*(actual_delay_matrix + i) + 
			 adj->delay()) > DELAYBOUND)) found = True;

//printf("found = %d\n", found);

		if (found == False) {
		  //if the potential link passes all tests:
//printf("NOT NULL\n");

		  bestCost = weight;
		  bestDest = nme;
		  bestSrce = i;
		  bestAdj = adj;
		};
	      };
	    };
	    adj = adj->next(); //repeat for all nodes adjacent to i;
	  };
	};
      }; //repeat for all i;

      if (bestAdj == NULL) {
//printf("NULL\n");
	//may be we are done? check if the tree already contains all nodes
	if (inTree == num) done = True;
	//if not:
	if (done == False) {
	  if ((alg == dimst) || (relaxDelays == True)) {
	    //if no more link replacements are possible fail and quit;
	    delete [] cost_matrix;
	    delete [] max_delay_matrix;
	    delete [] actual_delay_matrix;
	    delete [] from_matrix;
	    delete [] branch_matrix;
	    delete [] blacklist_matrix;
	    return(SATORDB);
	  }
	  else {
	    relaxDelays = True;
//printf("relax delays\n");
	  };
	};
      }
      else {
	//Add the least cost node to the tree
	
	//update all matrices, updating the maximum delay matrices is 
	//tricky;
	if (*(from_matrix + bestDest) == INT_MAX) {
//printf("add link from %d to %d act del %.2e max del %.2e\n", bestSrce, bestDest, *(actual_delay_matrix + bestSrce) + bestAdj->delay(), *(actual_delay_matrix + bestSrce) + bestAdj->delay());
	  inTree++;
	  *(branch_matrix + bestDest) = 0;
	  *(actual_delay_matrix + bestDest) = 
	    *(actual_delay_matrix + bestSrce) + bestAdj->delay();
	  *(max_delay_matrix + bestDest) = *(actual_delay_matrix + bestDest);
        }
	else {
//printf("replace link from %d to %d with link from %d to %d act del %.2e max del %.2e cost %.3e\n", *(from_matrix + bestDest), bestDest, bestSrce, bestDest, *(actual_delay_matrix + bestSrce) + bestAdj->delay(), *(max_delay_matrix + bestDest) - *(actual_delay_matrix + bestDest) + *(actual_delay_matrix + bestSrce) + bestAdj->delay(), bestCost);
	  if (relaxDelays == True) { 
//printf("relax\n");
	    relaxDelays = False;
	    *(blacklist_matrix + *(from_matrix + bestDest) * num + bestDest) 
	      = True;
	    for (i = 0; i < num; i++) {
	      if ((i!=bestSrce) && (i != *(from_matrix + bestDest)))
		*(blacklist_matrix+bestDest * num + i) = False;
	    };
	    blacklistEmpty = False;
	  };
          *(branch_matrix + *(from_matrix + bestDest)) -= 1;
	  double tmpd = *(actual_delay_matrix + bestSrce) + bestAdj->delay();

          //Set the maximum delays for the (old path to bestDest) = 0,temporarily;
          int bd = bestDest;
          do {
	    bd = *(from_matrix + bd);
	    *(max_delay_matrix + bd) = 0;
	  } while (bd != srce);


	  *(max_delay_matrix + bestDest) = *(max_delay_matrix + bestDest)
	    - *(actual_delay_matrix + bestDest) + tmpd;
	  updateSubtreeDelays(bestDest, 
			      tmpd - *(actual_delay_matrix + bestDest),
			      from_matrix, actual_delay_matrix,
			      max_delay_matrix);
	  *(actual_delay_matrix + bestDest) = tmpd;
	};

	*(from_matrix + bestDest) = bestSrce;
	*(cost_matrix + bestDest) = bestCost;
	*(branch_matrix + bestSrce) += 1;

	//Update the maximum delays for all nodes;
	int stop, bd, bs;
	for (i =0; i < num; i++) {
	  if ((i != srce) && (*(from_matrix + i) != INT_MAX)) {
	    if (*(max_delay_matrix + i) == 0)
	      *(max_delay_matrix + i) = *(actual_delay_matrix + i);
	    bd = i;
	    bs = *(from_matrix + bd);
	    stop = False;
	    while (stop == False) {
	      if (*(max_delay_matrix + bd) > *(max_delay_matrix + bs)) {
		*(max_delay_matrix + bs) = *(max_delay_matrix + bd);
//printf("max del of %d = %.3e\n", bs, *(max_delay_matrix + bs));
		if (bs == srce) stop = True;
		else {
		  bd = bs;
		  bs = *(from_matrix + bs);
		};
	      }
	      else stop = True;
	    };
	  };
	};

	if ((inTree == num) && (blacklistEmpty == False)) {
	  for (i = 0; i < num; i++) {
	    for (j = 0; j < num; j++) 
	      *(blacklist_matrix + i*num + j) = False;
	  };
	  blacklistEmpty = True;
	};
      }; //end if bestAdj else;
    }; //end done

    //Create the actual tree and then delete all the matrices:
    NodeListEntry *tree, *tmp1, *tmp2;
    tree = NULL;
    AdjacencyListEntry *adj;
    double wght, average;
    for (i = 0; i < num; i++) {
      tmp1 = new NodeListEntry;
      tmp1->nodePtr(nodeOf(i));
      tmp1->next(tree);
      tree = tmp1;
      if (i != srce) {
	nodeOf(*(from_matrix + i))->addChild(addr, source, nodeOf(i));
	//update the link cost
	adj = nodeOf(*(from_matrix + i))->adjacentNodes();
	while (adj->nodePtr()->name() != i) adj = adj->next(); 
	wght = adj->peak() + pk;
	adj->peak(wght);
	average = adj->average() + avg;
	adj->average(average);
      };
      nodeOf(i)->addRoutingEntry(addr, source);
    };
    delete [] cost_matrix;
    delete [] max_delay_matrix;
    delete [] actual_delay_matrix;
    delete [] from_matrix;
    delete [] branch_matrix;
    delete [] blacklist_matrix;
    
    //prune nonmember leaves;        
    prune(group, &tree, source, source, addr, NULL, pk, avg);
    
    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
    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
    nodes = 0;
    double totalCost = 0;
    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::updateSubtreeDelays(int node, double diff, 
                  int *from_m, double *actual_delay_m,
                  double *max_delay_m) {
  int i, j;
  for (i = 0; i < num; i++) {
    if (*(from_m + i) == node) {
      *(actual_delay_m + i) += diff;
      *(max_delay_m + i) += diff;
//printf("act del of %d = %.3e\t max del of %d = %.3e\n", i, *(actual_delay_m + i), i, *(max_delay_m + i));
      updateSubtreeDelays(i, diff, from_m, actual_delay_m, max_delay_m);
    };
  };
};