

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

#include "queuing.h"
#include <stdio.h>

#define NODES 20
//#define MESSAGES 1000
#define MESSAGES 100
#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

// fn prototype declarations:
void proc_event (int event);
void report_nodes (void);
void ShortestPath (int s, int d, int id);

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

  cout << "about to call init_simpack()\n";
  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();

return 0;
} /* end main() */


/************************************************
  Find the shortest path for given source and
  destination pair
 ************************************************/
void ShortestPath (int s, int d, int 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 = int (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
 ********************************************/
void proc_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
 **************************************************/
void 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() */


