routkmb.c

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

double TheNodeList::routerKMB(Node *source, int addr, double &d,
			      double &maxd, double &mind, double &h, 
			      double &nodes) {
  
  /*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;
    cost_matrix = new double[num*num];
    int *via_matrix;
    via_matrix = new int[num*num*num];

    /*initialize the matrices*/
    int i, j, k;
    for (i = 0; i < num; i++) {
      for (j = 0; j < num; j++) {
	(*(cost_matrix + (i * num) + j)) = DBL_MAX;
	(*(via_matrix + (i * num * num) + (j * num))) = INT_MAX;
      };
      (*(cost_matrix + (i * num) + i)) = 0;
    };
    
    /*initially the via matrix contains only information about directly 
      connected nodes*/
    NodeListEntry *tmp = nodeListHd;
    while (tmp != NULL) {
      i = tmp->nodePtr()->name();
      AdjacencyListEntry *adj = tmp->nodePtr()->adjacentNodes();
      while (adj != NULL) {
	j = adj->nodePtr()->name();

	if ((fn == PEAK) && (adj->peak() <= 
			     ((adj->linkCapacity() * ADMITRATIO) - pk))) { 
	                                            /*in order to eliminate
						      links saturated links*/
	  (*(cost_matrix  + (i * num) + j)) = adj->peak();
	  (*(via_matrix + (i * num * num) + (j * num))) = j;
	  (*(via_matrix + (i * num * num) + (j * num) + 1)) = INT_MAX;
	}
	else if ((fn == AVERAGE) && (adj->average() <= 
				((adj->linkCapacity() * ADMITRATIO) - avg))) {
 	                                            /*in order to eliminate
						      links saturated links*/
	  (*(cost_matrix  + (i * num) + j)) = adj->average();
	  (*(via_matrix + (i * num * num) + (j * num))) = j;
	  (*(via_matrix + (i * num * num) + (j * num) + 1)) = INT_MAX;
	};
	adj = adj->next();
      };
      tmp = tmp->next();
    };

    /*Now find the all-pairs constrained cheapest paths using a dynamic 
      programming approach*/
    for (k = 0; k < num; k++) {
      for (i = 0; i < num; i++) {
	for (j = 0; j < num; j++) {
	    if (((*(cost_matrix + (i * num) + k)) +
		(*(cost_matrix + (k * num) + j))) < 
		(*(cost_matrix + (i * num) + j))) {
	      (*(cost_matrix + (i * num) + j)) = 
		(*(cost_matrix + (i * num) + k)) +
		  (*(cost_matrix + (k * num) + j));
	      int l = 0;
	      while ((*(via_matrix + (i * num * num) + (k * num) + l)) 
		     != INT_MAX) {
		(*(via_matrix + (i * num * num) + (j * num) + l)) = 
		  (*(via_matrix + (i * num * num) + (k * num) + l));
		l++;
	      };
	      int m = 0;
	      while ((*(via_matrix + (k * num * num) + (j * num) + m)) 
		     != INT_MAX) {
		(*(via_matrix + (i * num * num) + (j * num) + l + m)) = 
		  (*(via_matrix + (k * num * num) + (j * num) + m));
		m++;
	      };
	      (*(via_matrix + (i * num * num) + (j * num) + l + m)) = INT_MAX;
	    };
	};
      };
    };

    /*delete entries not corresponding to the source or one of the group 
      members*/
    for (i = 0; i < num; i++) {
      tmp = group->headm();
      while ((tmp != NULL) && (tmp->nodePtr()->name() != i)) tmp = tmp->next();
      if ((tmp == NULL) && (source->name() != i)) {
	for (j = 0; j < num; j++) {
	  (*(cost_matrix + (i * num) + j)) = DBL_MAX;
	  (*(cost_matrix + (j * num) + i)) = DBL_MAX;
	};
      };
      (*(cost_matrix + (i * num) + i)) = DBL_MAX;
    };

    /*The above matrices describe a complete (may not be complete if some 
      links are saturated)directed graph that includes
      the multicast group members and the source only.
      The next step is to create a minimum spanning tree on that graph
      using a greedy approach, and starting at the source*/
    int *member = new int[group->count() + 1];
    int *hops = new int[num];
    int *from = new int[group->count() + 1];
    for (i = 1; i < (group->count() + 1); i++) {
      *(member + i) = INT_MAX;
      *(from + i) = INT_MAX;
    };

    *member = source->name();
    *(hops + source->name()) = 0;
    for (i = 0; i < num; i++)
      (*(cost_matrix + (i * num) + *member)) = DBL_MAX;

    int done = False;
    while (done == False) {
      
      double minCost = DBL_MAX;
      int bestFrom = INT_MAX;
      int bestChoice = INT_MAX;
      int bestHop;
      int quit = False;
      int current = *member;
      i = 0;
      while (quit == False) {
	for (j = 0; j < num; j++) {
	  switch (obj) {
	  case PLAIN:
	      if ((*(cost_matrix + (current * num) + j)) < minCost) {
		minCost = (*(cost_matrix + (current * num) + j));
		bestFrom = current;
		bestChoice = j;
		bestHop = *(hops + current) + 1;
	      };
	      break;
	  case MULT:
	      if ((*(cost_matrix + (current * num) + j) *
		  (*(hops + current) + 1)) < minCost) {
		minCost = (*(cost_matrix + (current * num) + j)) * 
		  (*(hops + current) + 1);
		bestFrom = current;
		bestChoice = j;
		bestHop = *(hops + current) + 1;
	      };
	      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;
	      };
	      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 [] via_matrix;
	delete [] member;
	delete [] hops;
	delete [] from;
	return(LINKSAT);
      };
      
      /*add the minimum cost link to the tree and check if minimum
	spanning tree is complete*/
      *(member + i) = bestChoice;
      *(from + i) = bestFrom;
      *(hops + bestChoice) = bestHop;
      for (j = 0; j < num; j++)  /*to reduce the amount of work*/
	*(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;

    /*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);

    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)
	expand(*(from + i), *(member + i), via_matrix, &tree,
		   source, addr, pk, avg);
      i++;
    };
    delete [] cost_matrix;
    delete [] via_matrix;
    delete [] member;
    delete [] from;


    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::expand(int from, int member, int *via_matrix, 
			     NodeListEntry **tree, Node *source, int addr,
			     double peak, double avg) {

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

  if (i > 0) {
    i--;
    via2 =  *(via_matrix + (from * num * num) + (member * num) + i);
    do {
//printf("connecting from %d to %d\n", via2, via1);
      nodeOf(via2)->addChild(addr, source, nodeOf(via1));
      nodeOf(via1)->addRoutingEntry(addr, source);	
    
      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);

      Node *tmpn = nodeOf(via2);
      NodeListEntry *tmp3 = *tree;
      while ((tmp3 != NULL) && (inTree == False)) {
	if (tmp3->nodePtr() == tmpn) inTree = True;
	else tmp3 = tmp3->next();
      };

      if (inTree == False) {
	via1 = via2;
	i--;
	if (i >= 0)
	  via2 =  *(via_matrix + (from * num * num) + (member * num) + 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);	

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