/*
 * Copyright (c) 1995 Center for Advanced Computing and Communications (CACC),
 * North Carolina State University at Raleigh.
 * All rights reserved.
 *
 * -----------------------------------------------------------------------
 * Copyright (c) 1998 Lab. for Networking and Distributed Computing (LNDC)
 * Northeastern University.
 * All rights reserved.
 * 
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted, provided
 * that the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation.  The LNDC makes no representations about the
 * suitability of this software for any purpose.  It is provided "as is"
 * without express or implied warranty.
 */

/*
 * File: routQDMR.c
 * Date: August 29, 1998
 * This module will perform QoS Dependent Multicast Routing (QDMR) 
 * algorithm to find a delay-constrained minimum cost tree for
 * multicast sessions. 
 */

/*
 * How to use it?
 *
 *   o Download the MCRSIM simulator source code from North Carolina State 
 *     University's FTP site (ftp.csc.ncsu.edu/pub/rtcomm).
 *
 *   o Put this part of program under the same directory.
 *
 *   o in "node2.h", add (line 157):
 *       #define qdmr    20 // define the QDMR algorithm
 *   
 *   o also in "node2.h", add the following prototype definition to class 
 *     "TheNodeList" (line 716):
 *       double routerQDMR(int alg, Node *source, int addr, double &d,
 *          double &maxd, double &mind, double &h, double &nodes);
 *
 *   o in "rout.c", add following lines after 
 *     "else if ((alg == cdks ... return ...  h, nodes));" (line 32):
 *
 *         else if (alg == qdmr)  // call algorithm QDMR 
 *             return (routerQDMR(alg, source, addr, d, maxd, mind, h, nodes));
 *
 *   o Follow the user manual (available at the same FTP site) and README
 *     file in the package for installing and running MCRSIM
 *
 *   o Make proper modifications to the code if you got problem, or send
 *     e-mail to me (guol@ccs.neu.edu).
 *
 *   o Hope you enjoy it!
 *    
 */

#include <math.h>
#include <assert.h>

#ifndef VISITED
#define VISITED   1
#define UNVISITED 0
#endif

// Coefficients used in computing Indicator function;
#define DANGERZONE 2
#define POWERRATIO 2     

#define DBL_HALF_MAX  (DBL_MAX / 2)

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

    // Constrained Destination-Driven MultiCasting Algorithm, put as much 
    // destination nodes as possible on each branch;

    //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)  
	return(NOGROUP);

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

    NodeListEntry *tmp1, *tmp2;
    Node *bestDest;
    double bestCost;
    int bestHop, bestDestId;
    double totalCost = 0.0;
    double *costMatrix;
    double *delayMatrix, *delayVector, *delayLDMatrix;
    double maxMinDelay;       // The maximum minimum delay of all dest nodes;
    double avgLkDelay;        // The average link delay in the network;   
    double bestDelay;
    int *pieLDMatrix;
    int *from;
    int numOnTreeGroupMembers = 0;

    short *pVisited = new short[num];      // Visited Indicator;
    short *flagDestin = new short [num];   // 1 if it is a destination, 0 otherwise.
		    
    // These two matrix are used for computing Least-Delay Tree;
    pieLDMatrix = new int[num];           
    delayLDMatrix = new double[num];       

    delayMatrix = new double[num * num];
    int i,j;
    for (i = 0; i < num; i ++) {
      for (j = 0; j < num; j ++)
	*(delayMatrix + i * num + j) = DBL_HALF_MAX;
      flagDestin[i] = 0;
      pVisited[i] = UNVISITED;
      delayLDMatrix[i] = DBL_HALF_MAX;
      pieLDMatrix[i] = INT_MAX;
    }

    int nLinkCount = 0;
    avgLkDelay = 0;
    NodeListEntry *tmp = nodeListHd;
    while (tmp != NULL) {
      i = tmp->nodePtr()->name();
      AdjacencyListEntry *adj = tmp->nodePtr()->adjacentNodes();
      while (adj != NULL) {
        j = adj->nodePtr()->name();
        *(delayMatrix + (i * num) + j) = adj->delay();
	nLinkCount ++;
	avgLkDelay += adj->delay();
        adj = adj->next();
      };
      tmp = tmp->next();
    };

    assert(nLinkCount);
    avgLkDelay = (double)avgLkDelay / nLinkCount;

    tmp2 = group->headm();

    while(tmp2 != NULL) {
        flagDestin[tmp2->nodePtr()->name()] = 1;
	tmp2 = tmp2->next();
    }

    /* first compute the least delay tree from the source node */
    /* Using Dijkstra's shortest path tree algorithm.          */

    double minDelay;
    int min, u, v;
    double maxDelay = (double)(WIDTH + HEIGHT) / PROPSPEED;
    *(delayLDMatrix + source->name()) = 0;
    numOnTreeGroupMembers = 0;
    for (i = 0; i < num; i ++) {     
      // outer loop execute exactly |V| times;

      // Extract the node with the minimum delay ;
      minDelay = DBL_HALF_MAX;
      for (u = 0; u < num; u ++) {
	if (pVisited[u] == UNVISITED) {
	  if (delayLDMatrix[u] < minDelay) {
	    minDelay = delayLDMatrix[u];
	    min = u;
	  }
	}
      }

      u = min;
      pVisited[u] = VISITED;
      if (flagDestin[u] == 1)
	numOnTreeGroupMembers ++;
      if (numOnTreeGroupMembers == group->count())
	break;

      for (v = 0; v < num; v ++) {
	if (delayMatrix[u * num + v] < maxDelay) {
	  if (pVisited[v] == UNVISITED) {
	    if (delayLDMatrix[v] > delayLDMatrix[u] + delayMatrix[u * num + v]) {
	      Node *nd = nodeOf(v);
	      Node *fromNd = nodeOf(u);

	      //check the link capacity;
	      AdjacencyListEntry *adj = fromNd->adjacentNodes();
	      while (adj->nodePtr() != nd) adj = adj->next();

	      if (((fn == PEAK) && (adj->peak() <=
			((adj->linkCapacity() * ADMITRATIO) - pk))) ||
		  ((fn == AVERAGE) && (adj->average() <=
                               ((adj->linkCapacity() * ADMITRATIO) - avg)))) {
	      	
		    delayLDMatrix[v] = delayLDMatrix[u] + delayMatrix[u * num + v];
		    pieLDMatrix[v] = u;
	      }
	    }
	  }
	}
      }
    }

    // Find the maximum minimum delay of all dest nodes;
    // Important for making routing policy;
    maxMinDelay = 0;
    for (u = 0; u < num; u ++) {
      if (flagDestin[u] == 1) 
	if (delayLDMatrix[u] > maxMinDelay)
	  maxMinDelay = delayLDMatrix[u];
    }
    delete [] delayLDMatrix;
    
    if (maxMinDelay > DELAYBOUND) {
	delete [] pVisited;
	delete [] flagDestin;
	delete [] delayMatrix;
	delete [] pieLDMatrix;
        return (DBVIOL);
    }

    costMatrix = new double[num];
    delayVector = new double[num];
    from = new int[num];
    for (i = 0; i < num; i ++) {
      *(costMatrix + i) = DBL_HALF_MAX;
      *(from + i) = INT_MAX;  // point to nil;
      pVisited[i] = UNVISITED;
      delayVector[i] = DBL_HALF_MAX;   // floating point, what a mess!;
    }

    
    *(costMatrix + source->name()) = 0;
    *(delayVector + source->name()) = 0.0;

    int done = False;
    numOnTreeGroupMembers = 0;
    while (done == False) {

         bestCost = DBL_HALF_MAX;   //infinity;
	 bestDestId = INT_MAX;
	 bestDelay = DBL_HALF_MAX;

	 for (i = 0; i < num; i ++) {
	   if (pVisited[i] != VISITED) {
	      if (bestCost > *(costMatrix + i)) {
		 bestCost = *(costMatrix + i);
		 bestDestId = i;
		 bestDelay = delayVector[i];
	       }
	   }
	 }

	 if (bestDelay > DELAYBOUND) {
	   done = Incomplete;    // it could be replaced by a least delay tree;
	   break;
	 }

	 pVisited[bestDestId] = VISITED;

	 // if it is a destination node, add the counter;
	 if (flagDestin[bestDestId] == 1)
	     numOnTreeGroupMembers ++;

	 //Check if the tree contains all group members;
	 if (numOnTreeGroupMembers == group->count())
	   done = True;

	 bestDest = nodeOf(bestDestId);
	 AdjacencyListEntry *adj = bestDest->adjacentNodes();

	 while (adj != NULL) {
	   double weight, load;
	   int delayLevel;
	   
	   if (pVisited[adj->nodePtr()->name()] == VISITED) {
	       adj = adj->next();
	       continue;
	   }

	   // compute the link cost;
	   // first the actual allocated bandwidth
	   if ((fn == PEAK) && ((adj->peak() + pk) <=
				(adj->linkCapacity() * ADMITRATIO))) 
	     load = adj->peak();
	   else if ((fn == AVERAGE) && ((adj->average() +avg) <=
					(adj->linkCapacity() * ADMITRATIO)))
	     load = adj->average();
	   else load = DBL_HALF_MAX;

	   // then compute the link cost based on cost policy
	   if (load < adj->linkCapacity()) {
		if (policy == LEASTLOAD) 
		    weight = load;
		else if (policy == LEASTDLAY) 
		    weight = (double)100 / (adj->linkCapacity() * ADMITRATIO + 0.5 - load);
	   	else if (policy == MOSTLOAD)
		    weight = adj->linkCapacity() * ADMITRATIO - load;
	   }
	   else weight = DBL_HALF_MAX;

	   // convert the link delay to a integer value;
	   // delayLevel = (int)ceil(adj->delay() * DELAYLAYER / DELAYBOUND) + bestDelay;
	   
	   // if already violates delay bound;
	   if (bestDelay + adj->delay() > DELAYBOUND) {
	       adj = adj->next();
	       continue;
	   }

	   // relax the cost (weight) of this neighbor node at the computed delay level;
	   // Cost[v, d+d(u,v)] = IdFunc() * Cost[u, d] + weight(u, v);
	   // where IdFunc() is the indicator function;
	   int nodeId = adj->nodePtr()->name();
	   double coeff = IdFunction(alg, flagDestin[bestDestId], bestDelay, DELAYBOUND, maxMinDelay, avgLkDelay);

	   if (*(costMatrix + nodeId) >
	       coeff * *(costMatrix + bestDestId) + weight) {
	     *(costMatrix + nodeId) =
	       coeff * *(costMatrix + bestDestId) + weight;
	     *(from + nodeId) = bestDestId;
	     *(delayVector + nodeId) = 
		*(delayVector + bestDestId) + adj->delay();
	   }

	   adj = adj->next();
	 }


    }; //end done;

    if ((done == Incomplete) &&(flagReplaceLDTree == False)) {
      delete [] costMatrix;
      delete [] pieLDMatrix;
      delete [] pVisited;
      delete [] flagDestin;
      delete [] delayMatrix;
      delete [] delayVector;
      delete [] from;
      return (DBVIOL);
    }

    // Merging process, use least-delay path to connect those
    // receivers that are still not connected to the tree yet.
    if (done == Incomplete) {  
        int p;

        // replace some path by least-delay path;
	for (u = 0; u < num; u ++) {
	    // if there are some unvisited destination nodes;
	    if ((flagDestin[u] == 1) && (pVisited[u] == UNVISITED)) {
		v = u;
		p = pieLDMatrix[u];
		pVisited[v] = VISITED;
		// scan through the least delay path, compare it with the tree;
		double cummDelay = 0;
		do {
			// if come across with some nodes in the tree;
			from[v] = p;
			cummDelay += delayMatrix[p * num + v];
			if (pVisited[p] == VISITED) {
			    if (delayVector[p] + cummDelay <= DELAYBOUND) {
				break;
			    }
			}
			pVisited[p] = VISITED;
			v = p;
			p = pieLDMatrix[v];
		} while ((p!= source->name()) && (p != INT_MAX));
		if (p == INT_MAX) {
			// not possible to reach here;
			assert(0);
		}
		if (p == source->name()) 
			from[v] = p;
	    }
	}
			
    }
	    

    //prune nonmember leaves
    pruneLeaves(&from, flagDestin, source->name());

    delete [] costMatrix;
    delete [] pieLDMatrix;
    delete [] pVisited;
    delete [] flagDestin;
    delete [] delayMatrix;
    delete [] delayVector;


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

    //Now construct the tree;
    for (i = 0; i < num; i++) {
      if (*(from + i) != INT_MAX) {

        Node *nd = nodeOf(i);
        Node *fromNd = nodeOf(*(from + i));

        //Add that node to the tree
        tmp1 = new NodeListEntry;
        tmp1->nodePtr(nd);
        tmp1->next(pTree);
        pTree = tmp1;
        nd->addRoutingEntry(addr, source);

        //update the link cost
        AdjacencyListEntry *adj = fromNd->adjacentNodes();
        while (adj->nodePtr() != nd) adj = adj->next();
	if (adj == NULL)
		assert(0);
        double wght = adj->peak() + pk;
        adj->peak(wght);
        double average = adj->average() + avg;
        adj->average(average);

        //and add it to the routing table
        fromNd->addChild(addr, source, nd);
      };
    };
    delete [] from;

    //prune nonmember leaves
    //prune(group, &pTree, 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
    totalCost = 0;
    nodes = 0;
    tmp1 = pTree;
    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);
};

double TheNodeList::IdFunction(int algorithm, short bIsDestin, double crtDelay, double upperBound, double maxMinDelay, double avgLkDelay)
{
    if (bIsDestin == 1)  {
      switch (algorithm) {
	case qdmr:
	     return ((double)crtDelay / upperBound);
	     break;

	// other possible definitions could be added here 
        default:
	     assert(0);
      }
    }
    else {
	return 1;
    }
}

void TheNodeList::pruneLeaves(int **fromMatrix, short *flagDestin, int srcId)
{
    register int i, j;
    unsigned int u;
    int flag = 0;

    do {
      flag = 0;
      for (u = 0; u < num; u ++) {

        /* If u is not on the tree, why bother care about it? */
        if ( *(*fromMatrix + u) > num)
            continue;

        if ( (*(flagDestin + u) != 1) && (u != srcId)) {
            /* if it is not, check whether it is a leaf node */
            /*  if ((i == pMGroup->nDestin) && (u != srcNode)) { */
            for (j = 0; j < num; j ++) {
                if (u == *(*fromMatrix + j))
                    break;
            }

            /* If it is, prune it off */
            if (j == num) {
                *(*fromMatrix + u) = INT_MAX;
                flag = 1;
            }
        }
      }
    } while (flag == 1);
}