/*---------------------------------------------
                    C
       Shortest Path Packet Routing 
        Copyright 1992, Hyun Park
---------------------------------------------*/

#include "../queuing/queuing.h"

#define NODES 20
#define MESSAGES 1000
#define TRANSCEIVERS 200
#define MAX_MSG_LENGTH 20
#define NUM_DSTTYPES 5
#define INFINITY 1000
#define perm 1
#define tent 0

#define GEN 0
#define LINK 1
#define REQUEST 2
#define RELEASE 3

int num_nodes,message_length[MESSAGES],event,message_id,inter_arrival_type;
int length,message[MESSAGES][MAX_MSG_LENGTH],transceiver[TRANSCEIVERS][3];
int trans_count,facility_id,messages_routed,message_ptr[MESSAGES];
int event,token,num_transceivers,num_messages,message_tr[MESSAGES];
int slow,shigh,dlow,dhigh;
float graph[NODES][NODES],node_time,stime;
float param1, param2;
char dist_types[NUM_DSTTYPES][20] = {"exponential","uniform","erlang","normal"};
char inter_arrival[20];
TOKEN a_token;

main()
{
  int i,j;

  init_simpack(LINKED);

  /* read in the network topology and message parameters */
  scanf("%f",&stime);
  scanf("%d",&num_nodes);
  scanf("%f",&node_time);

  for (i=0;i<num_nodes;i++) 
    for (j=0;j<num_nodes;j++) 
     scanf("%f",&graph[i][j]);

  scanf("%s",inter_arrival);
  scanf("%f",&param1);
  if (strcmp(inter_arrival,"exponential") == 0) {
	inter_arrival_type = 0;
  } else if (strcmp(inter_arrival,"uniform") == 0) {
	scanf("%f",&param2);
   	inter_arrival_type = 1;
  } else if (strcmp(inter_arrival,"erlang") == 0) {
	inter_arrival_type = 2;
	scanf("%f",&param2);
  } else if (strcmp(inter_arrival,"normal") == 0) {
	inter_arrival_type = 3;
	scanf("%f",&param2);
  } else {
    	printf("\nType correct distribution type\n");
  }

  /* the range of source and destination nodes */
  slow = 0; shigh = num_nodes - 1;
  dlow = 0; dhigh = num_nodes - 1;

  /* specify all transceivers as facilities */
  trans_count=0;
  for(i=0;i<num_nodes;i++)
    for (j=0;j<num_nodes;j++)
      if (graph[i][j] != 0.0) {
        transceiver[trans_count][0] = i;
        transceiver[trans_count][1] = j;
        facility_id = create_facility("tr",1);
        transceiver[trans_count][2] = facility_id;
        trans_count++;
      } /* end if */
  num_transceivers = trans_count;
  

  /* For each message, reset the pointer inside message path */
  for (i=0;i<MESSAGES;i++)
	message_ptr[i] = 0;

  /* initialize the packet generator */
  message_id = 0;
  a_token.attr[0] = (float)message_id;
  schedule(GEN,0.0,a_token);

  messages_routed = 0;

  while (sim_time() < stime) { 
    next_event(&event,&a_token);
    proc_event(event);
  } /* end while */

  report_stats();
  report_nodes();

} /* end main() */


/************************************************
  Find the shortest path for given source and
  destination pair
 ************************************************/
ShortestPath(s,d,id)
int s,d,id;
{
    struct NodeLabel {
	int predecessor;
	float length;
	int labl;
    };

    struct NodeLabel state[NODES];
    int i,k,min; 

    /* initialize the node state */
    for (i=0; i < num_nodes; i++) {
	state[i].predecessor = 0;
	state[i].length = INFINITY;
	state[i].labl = tent;
    }
    state[d].length = 0;
    state[d].labl = perm;
    k = d;		/* k is the initial working node */

    do {		/* is there better path from k? */
	for (i=0; i < num_nodes; i++) {
	    if ((graph[k][i] != 0.0) && (state[i].labl == tent)) {
		if (state[k].length + graph[k][i] < state[i].length) {
		    state[i].predecessor = k;
		    state[i].length = state[k].length + graph[k][i];
		}
	    }
	}
 	/* find the tentatively labled node with the smallest label */
	min = INFINITY; k = 0;
	for (i=0; i < num_nodes; i++) {
	    if ((state[i].labl == tent) && (state[i].length < min)) {
		min = state[i].length;
		k = i;	/* unless superseded, k will be next working node */
	    }
	}
	state[k].labl = perm;
    } while (k != s);	/* repeat until we reach the source */

    /* copy the path into the message array */
    k = s; i = 0;
    do {
	message[id][i] = k;
	k = state[k].predecessor;
	i++;
    } while (k != 0);
    message_length[id] = i;
} /* shortest path */



/********************************************
   Process the first event in the future
   event list
 ********************************************/
proc_event(event)
int event;
{
    int i,j,source,dest,trans_num,row,col;
    float interval,link_time;

    i = (int)a_token.attr[0];
    switch (event) {

    case GEN: /* generate message */
     message_id++;
     source = random(slow, shigh);	/* source address */
     dest = random(dlow, dhigh);	/* destination address */
     if (source == dest)
	dest = (dest + 1) % num_nodes;  /* do not allow self-looping */ 
     a_token.attr[0] = (float)message_id;
     a_token.attr[1] = (float)source;	/* we don't have to do this */
     a_token.attr[2] = (float)dest;	/* but for future use       */
     ShortestPath(source,dest,message_id); /* find and store the shortest */
					   /* path between source and dest*/

  /* for debuggin purpose you can print out the messages
  printf("\n Msg No. = %d  Source = %d  Dest = %d\n",message_id,source,dest);
  for (j=0;j<message_length[message_id];j++) {
    printf("   %d",message[message_id][j]);
  }
  printf("\n");
  */
     update_arrivals();
     schedule(LINK,0.0,a_token);	/* schedule newly created packet  */

     switch(inter_arrival_type) {
	case 0: interval = expntl(param1); break;
	case 1: interval = uniform(param1, param2); break;
	case 2: interval = erlang(param1, param2); break;
	case 3: interval = normal(param1, param2); break;
     }
     schedule(GEN,interval,a_token);	/* schedule next packet generation */
     break;

    case LINK: /* message traveling along a link */
     /* determine which transceiver is being requested */
     for (j=0;j<num_transceivers;j++)
      if ((message_ptr[i] < (message_length[i]-1)) &&
         (message[i][message_ptr[i]] == transceiver[j][0]) &&
         (message[i][message_ptr[i]+1] == transceiver[j][1]))
       trans_num = j;
     row = transceiver[trans_num][0];
     col = transceiver[trans_num][1];
     link_time = graph[row][col];
     a_token.attr[0] = (float) i;
     schedule(REQUEST,link_time,a_token);
     break;
  
    case REQUEST: /* message requesting a facility */
     /* determine which transceiver is being requested -
        then obtain facility or queue for it */
     for (j=0;j<num_transceivers;j++)
      if ((message_ptr[i] < (message_length[i]-1)) &&
         (message[i][message_ptr[i]] == transceiver[j][0]) &&
         (message[i][message_ptr[i]+1] == transceiver[j][1]))
       trans_num = j;
     if(message_ptr[i] < (message_length[i]-1)) {
       a_token.attr[0] = (float) i;
       if (request(transceiver[trans_num][2],a_token,0) == FREE) {
          /* total_time = graph[transceiver[trans_num][0],
                                transceiver[trans_num][1]] + 1.0; */
           message_tr[i] = trans_num;
           a_token.attr[0] = (float) i;
           schedule(RELEASE,node_time,a_token);
       } /* end if */
     } /* end if */
     break;

    case RELEASE:  /* message releasing a facility */
     /* release a facility. first find out which transceiver
        has this message token  */
       j = message_tr[i];
       a_token.attr[0] = (float) i;
       release(transceiver[j][2],a_token);
       /* update the message pointer */
       if(message_ptr[i] < (message_length[i]-2)) {
          message_ptr[i] += 1;
          a_token.attr[0] = (float) i;
          schedule(LINK,0.0,a_token);
       }
       else {
          messages_routed++;
	  update_completions();
       }
       break;
    } /* end switch */
} /* end proc_event */ 

/**************************************************
  Report the statistics related to each node
 **************************************************/
report_nodes()
{ 
  int trans_count,i,j,transceivers_in_node;
  float node_busy_time[NODES],utilization,avg_busy_time;
 
  printf("\n");
  printf("----------------\n");
  printf("NODE Utilization\n");
  printf("----------------\n\n");
  /* loop through all transceivers to obtain node statistics */
  trans_count=0;
  for(i=0;i<num_nodes;i++)
    node_busy_time[i] = 0.0;
  for(i=0;i<num_nodes;i++) {
    transceivers_in_node = 0;
    for (j=0;j<num_nodes;j++)
      if (graph[i][j] != 0.0) {
        node_busy_time[i] += busy_time(transceiver[trans_count][2]);
        trans_count++;
        transceivers_in_node++;
      } /* end if */
  } /* end for */
  for(i=0;i<num_nodes;i++) {
    avg_busy_time = node_busy_time[i]/(float) transceivers_in_node;
    utilization = 100.0 * avg_busy_time/sim_time();
    printf("Node %d Utilization is %.1f%%\n",i,utilization);
  } /* end for */
} /* end report_nodes() */

