/*
** 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
header(void);
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
header();
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);
}
/*************************************************************************************/
/*********** Function (definintion): header
***************************************/
/*************************************************************************************/
void
header (void)
{
/** Print header on output**/
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 **/