routcst.c

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

		    (*(hops + current) + 1);
		  bestFrom = current;
		  bestChoice = j;
		  bestHop = *(hops + current) + 1;
		  bestI = i;
		};
		break;
	      case ADD:
		if ((*(cost_matrix + (current * num) + j) +
		     *(hops + current) * ALPHA) < minCost) {
		  minCost = (*(cost_matrix + (current * num) + j)) + 
		    *(hops + current) * ALPHA;
		  bestFrom = current;
		  bestChoice = j;
		  bestHop = *(hops + current) + 1;
		  bestI = i;
		};
		break;
	      };
	    }
	    else if (alg == cstcd) {
	      switch (obj) {
	      case PLAIN:
		if (((*(cost_matrix + (current * num) + j)) /
		     (DELAYBOUND - ((*(delay + i)) + 
		     (*(delay_matrix + (current * num) + j))))) <
		    minCost) {
		  minCost = ((*(cost_matrix + (current * num) + j)) /
			     (DELAYBOUND - ((*(delay + i)) + 
			     (*(delay_matrix + (current * num) + j)))));
		  bestFrom = current;
		  bestChoice = j;
		  bestHop = *(hops + current) + 1;
		  bestI = i;
		};
		break;
	      case MULT:
		if (((*(cost_matrix + (current * num) + j) *
		      (*(hops + current) + 1)) /
		     (DELAYBOUND - ((*(delay + i)) + 
		      (*(delay_matrix + (current * num) + j))))) <
		    minCost) {
		  minCost = ((*(cost_matrix + (current * num) + j) *
			      (*(hops + current) + 1)) /
			     (DELAYBOUND - ((*(delay + i)) + 
			     (*(delay_matrix + (current * num) + j)))));
		  bestFrom = current;
		  bestChoice = j;
		  bestHop = *(hops + current) + 1;
		  bestI = i;
		};
		break;
	      case ADD:
		if (((*(cost_matrix + (current * num) + j) + 
		      *(hops + current) * ALPHA) /
		     (DELAYBOUND - ((*(delay + i)) + 
		     (*(delay_matrix + (current * num) + j))))) <
		    minCost) {
		  minCost = ((*(cost_matrix + (current * num) + j) + 
			      *(hops + current) * ALPHA) /
			     (DELAYBOUND - ((*(delay + i)) + 
			     (*(delay_matrix + (current * num) + j)))));
		  bestFrom = current;
		  bestChoice = j;
		  bestHop = *(hops + current) + 1;
		  bestI = i;
		};
		break;
	      };
	    };
	  };
	};
	i++;
	if (((*(member + i)) == INT_MAX)) quit = True;
	else current = (*(member + i));
      };
      if (minCost == DBL_MAX) { /*if the alg. can't create a tree spanning all
				  group members*/	
	delete [] cost_matrix;
	delete [] delay_matrix;
	for (i = 0; i < num; i++) {
	  for (j = 0; j < num; j++) 
	    if (*(via_matrix + (i*num) + j) != NULL)
	      delete [] *(via_matrix + (i*num) + j);
	};
	delete [] via_matrix;
	delete [] member;
	delete [] delay;
	delete [] from;
	delete [] hops;
	return(SATORDB);
      };
      
      /*add the minimum cost link to the tree and check if minimum
	spanning tree is complete*/
      *(member + i) = bestChoice;
      *(from + i) = bestFrom;
      *(delay + i) = *(delay + bestI) +
	             *(delay_matrix + (bestFrom * num) + bestChoice);
      *(hops + bestChoice) = bestHop;
      for (j = 0; j < num; j++) { /*to reduce the amount of work*/
	*(delay_matrix + (j * num) + bestChoice) = DBL_MAX;
	*(cost_matrix + (j * num) + bestChoice) = DBL_MAX;
      };

      if (i == (group->count() - 1)) {
	tmp = group->headm();
	while ((tmp != NULL) && (tmp->nodePtr() != source)) tmp = tmp->next();
	if (tmp != NULL) done = True;
      }
      else if (i == group->count()) done = True;
    };
    delete [] hops;
    delete [] cost_matrix;
    delete [] delay_matrix;
  
    /*Expand the links of the constrained spanning tree into the constrained 
      cheapest paths they represent*/

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

    int *in = new int[num];
    int *fr = new int[num];
    double *del = new double[num];
    for (i = 0; i < num; i++) *(in + i) = False;
    *(in + source->name()) = True;
    *(fr + source->name()) = INT_MAX;
    *(del + source->name()) = 0;
    i = 1;
    while ((i < (group->count() + 1)) && ((*(member + i)) != INT_MAX)) {

      Node *tmpn = nodeOf(*(member + i));
      NodeListEntry *tmp3 = tree;
      int found = False;
      while ((tmp3 != NULL) && (found == False)) {
	if (tmp3->nodePtr() == tmpn) found = True;
	else tmp3 = tmp3->next();
      };
      if (found == False) {
//printf("expanding from %d to %d of delay %.3e\n", *(from + i), *(member + i),
//*(delay + i));
	expand2(*(from + i), *(member + i), 
	        *(via_matrix + (*(from + i)*num) + *(member + i)), &tree,
		source, addr, pk, avg, in, fr, del, d_matrix,
		*(delay + i));
      };
      i++;
    };
    delete [] in;
    delete [] fr;
    delete [] delay;
    delete [] from;
    delete [] member;
    for (i = 0; i < num; i++) {
      for (j = 0; j < num; j++) 
        if (*(via_matrix + (i*num) + j) != NULL) 
          delete [] *(via_matrix + (i*num) + j);
    };
    delete [] via_matrix;
    delete [] d_matrix;

    //prune the tree
    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*/
    tmp = group->headm();
    double avgDelay = 0;
    double avgHops = 0;
    while (tmp != NULL) {
      int gotit = False;
      int hops = 0;
      double delay = 0;
      if (source != tmp->nodePtr()) 
	results(source, addr, source, tmp->nodePtr(), delay, hops,
		gotit);     
      if (delay >= DELAYBOUND) dbViolation = True;
      if (delay > maxd) maxd = delay;
      if (delay < mind) mind = delay;
      avgDelay += delay;
      avgHops += hops;
      tmp = tmp->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;
    tmp = tree;
    while (tmp != NULL) {
      nodes++;
      RoutingTableEntry *rout = tmp->nodePtr()->routingTable();
      int found = False;
      while ((rout != NULL) && (found == False)) {
	if ((rout->address() == addr) && (rout->source() == source)) 
	  found = True;
	else rout = rout->next();
      };
      NodeListEntry *tmp2 = rout->children();
      while (tmp2 != NULL) {
	AdjacencyListEntry *adj = tmp->nodePtr()->adjacentNodes();
	int found2 = False;
	while ((adj != NULL) && (found2 == False)) {
	  if (adj->nodePtr() == tmp2->nodePtr()) found2 = True;
	  else adj = adj->next();
	};
	if (adj != NULL) {
	  if (fn == PEAK) totalCost += (adj->peak() - pk);
	  else totalCost += (adj->average() - avg);
	};
	tmp2 = tmp2->next();
      };
      NodeListEntry *tmp3 = tmp->next();
      delete tmp;
      tmp = tmp3;
    };

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

void TheNodeList::expand2(int from, int member, int *via_matrix, 
			  NodeListEntry **tree, Node *source, int addr,
			  double peak, double avg, int *in, int *fr,
			  double *del, double *d_matrix, double d) {

  int i = 0;
  int found = False;
  int via1, via2, preVia;
  int inTree = False;
  do {
    via1 = *(via_matrix + i);
    if (via1 == member) found = True;
    else i++;
  } while (found == False);

  if (i > 0) {
    i--;
    via2 =  *(via_matrix + i);
    do {
//printf("connecting from %d to %d\n", via2, via1);
      nodeOf(via2)->addChild(addr, source, nodeOf(via1));
      nodeOf(via1)->addRoutingEntry(addr, source);	
      *(in + via1) = True;
      *(fr + via1) = via2;
      if (via1 == member) *(del + via1) = d;
      else *(del + via1) = *(del + preVia) - *(d_matrix + (via1*num) + preVia);
    
      NodeListEntry *tmp = new NodeListEntry;
      tmp->nodePtr(nodeOf(via1));
      tmp->next(*tree);
      *tree = tmp;

      AdjacencyListEntry *bestAdj = nodeOf(via2)->adjacentNodes();
      while (bestAdj->nodePtr() != nodeOf(via1)) 
	bestAdj = bestAdj->next();
      /*update the link cost*/
      double wght = bestAdj->peak() + peak; /*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);

      if (*(in + via2) == True) {
	if (*(del + via2) > 
	    (*(del + via1) - *(d_matrix + (via2*num) + via1))) {
//printf("in here parent %d\n", *(fr + via2));
	  nodeOf(*(fr + via2))->removeChild(addr, source, nodeOf(via2));
	  *(in + via2) = False;
	  bestAdj = nodeOf(*(fr + via2))->adjacentNodes();
	  while (bestAdj->nodePtr()->name() != via2) bestAdj = bestAdj->next();
	  wght = bestAdj->peak() - peak; 
	  bestAdj->peak(wght);
	  average = bestAdj->average() - avg;
	  bestAdj->average(average);
	  NodeListEntry *tr = *tree;
	  NodeListEntry *prtr = NULL;
	  while (tr->nodePtr()->name() != via2) {
	    prtr = tr;
	    tr = tr->next();
	  };
	  if (tr == *tree) *tree = tr->next();
	  else prtr->next(tr->next());
	  delete tr;
	}
	else inTree = True;
      };
//printf("out here\n");

      if (inTree == False) {
	preVia = via1;
	via1 = via2;
	i--;
	if (i >= 0)
	  via2 =  *(via_matrix + i);
      };
    } while ((inTree == False) && (i >= 0));
  };
  
  if (inTree == False) {
//printf("connecting from %d to %d\n", from, via1);
    nodeOf(from)->addChild(addr, source, nodeOf(via1));
    nodeOf(via1)->addRoutingEntry(addr, source);	
    *(in + via1) = True;
    *(fr + via1) = from;
    if (via1 == member) *(del + via1) = d;
    else *(del + via1) = *(del + preVia) - *(d_matrix + (via1*num) + preVia);

     NodeListEntry *tmp = new NodeListEntry;
     tmp->nodePtr(nodeOf(via1));
     tmp->next(*tree);
     *tree = tmp;

    AdjacencyListEntry *bestAdj = nodeOf(from)->adjacentNodes();
    while (bestAdj->nodePtr() != nodeOf(via1)) 
      bestAdj = bestAdj->next();
    /*update the link cost*/
    double wght = bestAdj->peak() + peak; /*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);
  };
};