/*

**  Craig Worley

**  University of New Haven

**  CS642

**  02-13-01

**  Homework Assignment 5

**  Problem 2.42 and 2.43 in PD Edition 2, page 166

** .

**  filename HW5.c

**

**   Synopsis  -  Provides simulation of effect of multiple CSMA/CD stations with random

**                exponential backoff algorithm.

**

**                Simulates for NUM_STATIONS stations, running MAX_PASS times, and computes

**                the average time elapsed (quantum time intervals of 51.2 us) from initial

**                collision (at time 0) before the first successful retransmission by any.

**                station.

**/

/* Include Files */

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <float.h>

#include <math.h>

#include <ctype.h>

#include <time.h>

/** Global Constant Declarations  **/

#define MAX_PASS    1000

#define NUM_STATIONS 200

/** Global Variable Declarations   **/

int      total_time  = 0;      /* Total time of all passes (cumulative )                 */

int ave_time      = 0;

/** Global Type Declarations (Descriptions) **/

struct Tx_Station

{

int coll_cnt;      /* Number of collisions since last Tx */

int next_tx;      /* Next time (T) to transmit          */

};

/** Global Function Declarations (Prototypes)    **/

void introduction(void);

void init_array(struct Tx_Station *);

int Tx_Loop(struct Tx_Station *);

int Get_K (int);

int Two_to_the_nth(int);

int Rand_Gen (int, int);

int Complete (int, int, int);

/******************** Main Program Function ************************/

void main( void )

{

struct Tx_Station station[NUM_STATIONS];

int pass_number = 1;

int tx_time           = 0;

/** comment out following lines for brevity of output

introduction();

**/

/*****  Top Loop: Makes MAX_PASS number of passes      **/

/*****  Each pass runs until sucessful Tx (Tx_Loop)      **/

for (pass_number=1;pass_number<=MAX_PASS;pass_number++)

{

init_array(station);                      /** initialize stations each pass      **/

tx_time = Tx_Loop(station);           /** execute a simulation                  **/

total_time = total_time + tx_time;  /** cumulative total for averaging      **/

/** comment out following line for brevity of output

printf("\tPass Number: %d\t\tTime: %d\n", (pass_number),tx_time);

**/

}

/**  Run  completed, print results      **/

ave_time = (total_time/MAX_PASS);

printf( "\n\tNumber of passes run: %d", MAX_PASS);

printf( "\n\tNumber of stations: %d", NUM_STATIONS);

printf( "\n\tAverage Time to 1st sucessful transmit:  %d\n", ave_time);

}

/*************************************************************************************/

/*********************  Init_array()   ***********************************************/

/*************************************************************************************/

/** Initializes array values to 0 **/

void init_array(struct Tx_Station *station_ptr)

{

int j;

for (j=0;j<NUM_STATIONS;j++)

{

station_ptr[j].next_tx = 0;

station_ptr[j].coll_cnt = 0;

}

}

/*************************************************************************************/

/*********************    Tx_Loop()    ***********************************************/

/*************************************************************************************/

/** Initializes number of stations attempting to transmit (TX_NUM) to 0             **/

/**                                                                                 **/

/** Walks thru array of stations; test each one for Tx attempt (next_tx = timeslot) **/

/** If a station attempts Tx, increments TX_NUM and that station's collision count  **/

/** Calls backoff timer function and updates that stations next_tx time             **/

/** Resets timer (time_slot) to 0 and repeats until exactly 1 station attempts Tx   **/

/** Returns value of time_slot to calling function                                  **/

/**                                                                                 **/

/** Note: While the exponential backoff algorithm actually calls for a value of     **/

/**       K between 0 and 2^n-1, to get this result, this simulation must add 1     **/

/**       to the value returned for K. Otherwise, setting the next_tx time to a     **/

/**       value equal to (current time + 0), and then incrementing the current      **/

/**       time value before entering the next iteration would result in the next_tx **/

/**       time being less than the current time, and thus would never attempt tx.   **/

int Tx_Loop(struct Tx_Station *station_ptr)

{

int      time_slot   = 0;      /* Quantum time in 51.2 us increments (time slot)      */

int      tx_num            = 0;      /* Number of stations attempting TX this time_slot      */

int      K                 = 0;      /* Backoff timer value                                           */

int N             = 0;      /* Array index                                      */

test_next_time_slot:

for (N=0;N<NUM_STATIONS;N++)

{

if (station_ptr[N].next_tx == time_slot)        /** if Tx attempt              **/

{

tx_num = tx_num + 1;                            /** incr number attempting        **/

if (station_ptr[N].coll_cnt < 10 )            /** backoff algorithm limits "n"**/

station_ptr[N].coll_cnt = station_ptr[N].coll_cnt +1;

K = Get_K(station_ptr[N].coll_cnt);                             /** backoff value **/

station_ptr[N].next_tx = 1 + time_slot + K;                /** update next_tx      **/

}

}

if (tx_num == 1)

return(time_slot);

else

{

tx_num = 0;

time_slot = time_slot + 1;

goto test_next_time_slot;

}

}

/*************************************************************************************/

/*********************   Get_K  ******************************************************/

/*************************************************************************************/

/** Get backoff time value K = random value between 0 and (2^n - 1)                 **/

int Get_K ( int nth )

{

int k = 0;

int U = 0;

U = ( Two_to_the_nth(nth) ) - 1;

k = Rand_Gen(0,U);

return(k);

}

/*************************************************************************************/

/***********              Two_to_the_nth       ***************************************/

/*************************************************************************************/

/**                 Calculates 2 to the nth power, maximum of 2 ^16                       **/

/**                                                                                                                           **/

int Two_to_the_nth(int nth)

{

int value = 1;

int i = 1;

if (nth > 16)

nth = 16;

if (nth > 0)

{

for (i=1; (i <= nth); i++)

{

value *= 2;

}

}

;

return(value);

}

/*************************************************************************************/

/*********************   Rand_Gen()   ************************************************/

/*************************************************************************************/

/** Generate random integer between values L (lower) & U (upper) using mod operator      **/

/**         general case:                                                                                               **/

/**                                 x  = ( rand() % (  (U-L)  + 1) ) + L                               **/

/**                                                                                                                           **/

/**         specific case:  15 <= x <= 40                                                                    **/

/**                     x  = ( rand() % ( (40-15) + 1) ) + 15 = ( 0 to 25 ) + 15      **/

int Rand_Gen ( int L, int U )

{

int x;

static int y = 0;   /** First pass indicator for time-based seed                          **/

/** Initialize random number generator with time based seed, requires using       **/

/** preprocessor directive  #include <time.h>                                                          **/

if ( y == 0 )

srand( (unsigned)time((time_t *) NULL ) );

y = 1;

x  = ( rand() % (  (U-L)  + 1) ) + L;

return(x);

}

/*************************************************************************************/

/*************************************************************************************/

{

printf("\n Worley, Craig\n CS642\n 02/13/01");

printf("\n Homework 5 \n Problem 2.42 and 2.43 in PD Edition 2, page 166:\n");

}

/*************************************************************************************/

/************  Function (definintion): introduction   ********************************/

/*************************************************************************************/

void introduction (void)

{

/** Print introduction  to screen. **/

printf("\n This program simulates a CSMA/CD network of %d stations.\n", NUM_STATIONS);

printf(" Following collision of all stations, the simulation uses an exponential\n");

printf(" backoff algorithm to schedule retransmission. The simulation continues\n");

printf(" until any station successfully retransmits, and the total time from\n");

printf(" initial collision to successful retransmission is output.\n\n");

printf(" This simulation is for %d stations.\n", NUM_STATIONS);

printf(" The simulation is repeated for %d passes, and the average time\n", MAX_PASS);

printf(" of all passes is calculated and output.\n\n");

}

/**  End of file   **/