Christensen Tools Page
Department of Computer Science and Engineering
This page contains software tools related to performance evaluation and TCP/IP sockets programming. These tools are intended for use as teaching and research aids and therefore include very well documented source code, build and execution instructions, and sample input and output. With few exceptions (that are clearly noted - see the author listed in the program header), the tools have been developed by Ken Christensen at the University of South Florida. If you find a bug, please send me email.
Solving for the steady state probabilities of sparse P and Q matrices
Solving for the steady state probabilities of a probability (P) or rate
transition (Q) matrix is difficult if the matrix is large and sparse. The
program iter.c solves P and Q matrices using iterative
methods. Only non-zero matrix values are stored and operated on.
- An example Q matrix (for an M/M/1/K queue) in iter.c column format is mm1k.dat.
- A program to check the validity of P and Q matrices in iter.c column format is check.c.
- A program to convert a text matrix to iter.c column format is mat2iter.c.
- A program to convert a Q text matrix to a P text matrix is qmat2pmat.c.
Mean Value Analysis for a closed queueing network
Mean Value Analysis (MVA) is a method of solving for mean queue lengths and
delays in a closed queueing network. The program mva.c
implements MVA for a simple tandem (all queues have a visit ratio of 1.0)
closed queueing network.
Computing the Erlang-B and Erlang-C probabilities
The Erlang B and C formulas are the classic way to compute the blocking
and queueing probabilities for voice teletraffic systems. The program
erlang.c uses a recursive approach to insure
numerical stability to compute both Erlang-B and Erlang-C probabilities.
Computing Poisson probabilities
The program poisson.c uses an iterative approach to
insure numerical stability to compute the Poisson probability.
Iterative solution for M/M/1/K
The following are implementations of an iterative solution method for the
M/M/1/K queue. The program chain1.c assumes integer
valued arrival and service rates. The program chain2.c
does not make this integer assumption. The program
chain3.c uses state dependent arrival and service rates.
|Statistics and measurement tools|
Studying the properties of a time series
Analysis of a time series is integral to traffic analysis. Here are
some tools for computing various population statistics:
- summary1.c - Min, max, sum, mean, var, std dev, and CoV
- summary2.c - Median, 1%, 5%, 25%, 75%, 95%, and 99% values
- moments.c - Moments (raw and central)
- hist.c - Frequency count (histogram)
- runlen.c - Run length counts
- count01.c - 0 and 1 burst counts
- peakmean.c - Peak-mean ratios
- autoc.c - Autocorrelation
- rs.c - R/S analysis for Hurst parameter estimation
- sort.c - Sort values
- sortdouble.c - Sort a series of doubles
- sortint.c - Sort a series of integers
- dup.c - Test for duplicate values
- filter1.c - Filter "out"
- filter2.c - Filter "in"
- busyhour.c - Extract busy hour values
- scale.c - Scale
- spread.c - Spread-out values
- shape1.c - Shape to deterministic
- shape2.c - Shape to exponential
- count2exp.c - Counts to exponential interarrivals
- block.c - Aggregate into block means
- interval.c - Aggregate into interval means
- shuffle.c - Simple shuffle
- shuffle1.c - External block shuffle
- shuffle2.c - Internal block shuffle
- delta.c - Output deltas between values
- ttoc1.c - Convert cumulative times to counts
- ttoc2.c - Convert delta time to counts
- dtoclk.c - Convert delta time to cumulative time
- clktod.c - Convert cumulative time to delta time
- clktosec.c - Convert clock values to seconds
Generating a time series with a known distribution
The following programs generate a times series with a given probability
distribution. A summary of the properties of key distributions is
- gendet.c - Deterministic
- genunifc.c - Uniform (continuous)
- genunifd.c - Uniform (discrete)
- genpeak.c - Peaked
- gennorm.c - Normal
- genexp.c - Exponential
- gengeo.c - Geometric
- genpois.c - Poisson
- genbin.c - Binomial
- generl.c - Erlang
- genhyp1.c - Hyperexponential for lambdas and p1
- genhyp2.c - Hyperexponential for mean lambda and CoV
- genipp.c - Interrupted Poisson Process (IPP)
- genpar1.c - Pareto
- genpar2.c - Bounded Pareto
- genzipf.c - Zipf
- genemp.c - Empirical
- genuniq.c - Unique random integers
Generating synthetic packet traffic
The following programs generate synthetic trace files with entries of
Tools for working with a time series of paired data
Some tools to operate on a series of tuples of
<delta_time_stamp, num_bytes> are:
- rate.c - Convert byte counts to a rate
- count1.c - Tabulate byte counts for a time interval
- count2.c - Tabulate time for a byte count block size
Fitting a line to <x, y> data with linear regression
Here is a tool for computing the linear regression line and coefficient
of determination for paired data, lr.c.
Computing the correlation coefficient of <x, y> data
Here is a tool for computing the correlation coefficient of paired data,
Exponential smoothing to forecast the next value in a series
Here is a tool to implement exponential smoothing,
Computing confidence intervals and doing a hypothesis test
A tool for computing the 90%, 95%, and 99% confidence interval using a
simple Z-test is ztest.c (need at least 30 samples).
A tool for computing the 95% confidence interval using a simple T-test is
ttest.c (can have less than 30 samples). A tool for
performing a one-tailed T-test for 90% and 95% confidence for two groups is
Computing positive tail values for a normal distribution
A tool to compute positive tail values assuming a normal distribution
Note that all programs with "_csim.c" in their file name require the
commercial CSIM libraries available only from
Mesquite Software, Inc..
Source files for SMPL event-based simulation modeling
SMPL is a set of C functions for building event-based, discrete-event
simulation models. SMPL was written by M. H. MacDougall and is described
in his book, Simulating Computer Systems, Techniques and Tools,
The MIT Press, 1987. Here is the original "package" for the book
including sample files, smpl_org.zip. Here is
an updated version that eliminates some of the warning messages from the
original, smpl_new.zip (sample programs not
included). The original archive of SMPL at the University of Florida is,
Generating uniform random numbers
To generate uniform(0, 1) random numbers use unif.c
(from, R. Jain, "The Art of Computer Systems Performance Analysis,"
John Wiley & Sons, 1991 - page 443, figure 26.2).
Generating normal random numbers
To compute normal(0, 1) random numbers use normal.c
(uses the polar method to generate normal(0,1) random variables).
Monte Carlo simulations to estimate pi and integrate f(x)
Classic Monte Carlo simulation to estimate the value of pi is
findPi.c. A Monte Carlo simulation to integrate
f(x) from 0 to x_max is integrate.c.
Simulation of a fluid-flow, single-server, finite-buffer queue
A program to model a fluid-flow, single-server, finite-buffer queue is
Simulation of the M/M/1 queue
The M/M/1 is the classic queueing system. The program
mm1.c is a discrete event simulation of the M/M/1 that can easily be
modified for different arrival and service distributions and for finite
capacity. An event-based SMPL M/M/1 model is
mm1_smpl.c (SMPL is available below). A process-based CSIM M/M/1 model
is mm1_csim.c (CSIM is available from
Mesquite Software, Inc.). A CSIM
M/M/1 model demonstrating automatic run-length control is
Simulation of the M/D/1 queue
A process-based CSIM M/D/1 model is mm1_csim.c.
Simulation of the H2/D/1 queue
The H2/D/1 queue allows for experimentation with burstiness of arrivals.
The program h2d1.c is a derivative of the program
mm1.c which allows for the Coefficient of Variation
(CoV) of the arrival process to be changed.
Simulation of the IBP/D/1 queue
The IBP/D/1 queue allows for experimentation with the Interrupted
Bernoulli Arrival process - ibp_csim.c.
Simulation of the N independent M/M/1 queues
CSIM18 supports process-oriented simulation. Here is an example of N
independent M/M/1 queues using the so-called "station centric" approach for
CSIM models (which uses function pointers) - n_mm1.c.
Simulation of a trace-driven single-server queue
A program to use packet trace data to drive a single-server queue simulation
with finite capacity is tracesim.c. Deterministic
service time is assumed (this is then a "trace/D/1/K" queue). Two more
general trace-driven models are tr_csim.c which models
a "trace/trace/1/K" queue (using CSIM libraries) and
tr_smpl.c which models a "trace/trace/1" queue (using SMPL libraries).
Simulation of a trace-driven leaky bucket
A program to run packet trace data through a leaky bucket smoother is
lb_csim.c. An improved version that allows for
policing is lb1_csim.c.
Simulating the effectiveness of parity for error detection
Parity can detect an odd number of bit errors. The program
parity.c is a simulation of parity and also
can model simple bit correlation.
Simulating bit errors to determine burst sizes
Given a bit error probability of p, what lengths of error bursts
will occur? The progam burst.c is a
simulation of bit errors and can model simple bit correlation.
Simulation of machine failures
A program to simulate N machines, each with probability p of failing, over M
intervals is fail.c.
Simulation of node discovery in a passive network
A program to simulate node discovery in a passive network using a
randomized delay method is disc_sim.c.
Some CSIM models of interesting systems
Here are CSIM simulation models of a call center (
callcenter.c), a thin-client plus server system (
thinclient.c), and a disk drive (diskdrive.c).
|Data communications tools|
Computing link utilization for DLC stop-and-wait and sliding window
Here is a tool that computes link utilization given link length, link data
rate, frame size, and Pr[bit error] for DLC stop-and-wait and sliding window
(with both selective reject and go-back-N ARQ) - dlc.c.
Computing link utilization for Token Ring and Ethernet LANs
Here are tools for computing link utilization on a Token Ring and Ethernet
(assuming saturated sending stations) given medium length, medium data rate,
frame size, and number of stations - token.c and
Generating CRC and checksum error detection codes
Here are programs to generate standard CRC32 and TCP 16-bit checksum -
crc32.c and checksum.c. A
32-bit checksum is check32.c.
|TCP/IP sockets programs|
Demonstration of basic TCP/IP client/server model
The programs tcpServer.c and
tcpClient.c implement a simple TCP client/server model using sockets.
A text message is transferred from server to client and then from client to
server. Programs conditionally compile for Winsock or BSD sockets.
Demonstration of basic UDP/IP client/server model
The programs udpServer.c and
udpClient.c implement a UDP client/server model similar to the above
TCP model. Programs conditionally compile for Winsock or BSD sockets.
Demonstration of basic raw socket client/server model
The programs rawServer.c and
rawClient.c implement a raw socket client/server model similar to the
above TCP and UDP models. Programs compile only for Winsock.
Demonstration of raw sockets packet send
A program to demonstrate a send with raw sockets is
rawsend.c. Program compiles only for Winsock.
Demonstration of broadcast of UDP datagrams
Demonstration of non-blocking sockets and use of select for time-out
The program udpClientNonblock.c modifies
the above udpClient.c to use non-blocking sockets.
The program udpClientSelect.c uses select()
to implement a time-out for recvfrom().
A UDP "blaster" program to measure transmission data rate
The program blast.c is a UDP packet blaster
with built-in timing to measure transmission data rate.
The "world's smallest" web server
A very simple web server for Windows and Unix that serves HTML, text, and GIF
images is weblite.c (conditionally compiles to use
Windows or POSIX threads).
Demonstration of HTTP GET and HTTP response
The program httpget1.c executes an HTTP GET to a Web
server. The programs httpget2.c and
httpget3.c do serial and threaded parallel HTTP GETs.
The program httpresp.c accepts a connect
from a web browser (i.e., it acts as an HTTP server) and responds with an
HTML message. The program http302.c redirects all
GET requests from a browser to http://www.csee.usf.edu/~christen
using an HTTP 302 response message to the browser. Programs compile
conditionally for Winsock or BSD sockets. An
Analyzer trace of
an HTTP GET with a return HTTP 302 is here.
Programs for timing of serial and parallel HTTP GETs
Demonstration of gethostbyname() and gethostbyaddr()
A sockets program to get a host IP address for a given host name is
getaddr.c. And, to get a host name for a given
IP address is getname.c. Programs conditionally
compile for Winsock or BSD sockets.
Demonstration of getsockname()
A sockets program to get a the local IP address for a given host name is
getmyip.c. Program conditionally compiles for
Winsock or BSD sockets.
Demonstration of htonl()
A sockets program to demonstate htonl() and other similar sockets functions is
htonl.c. Program conditionally compiles for Winsock or
A simple UDP datagram reflector/relay program
A sockets program to reflect or relay UDP datagrams is
Demonstration of IP multicast send and receive
The programs mserver.c and
mclient.c implement an IP multicast sender and receiver. Programs
conditionally compile for Winsock or BSD sockets.
Program to send a Magic Packet to wake-up a target host
A program to send a Magic Packet is magicSend.c.
The target host must be enabled to wake-up on a Magic Packet, see
here for screen shots showing a Windows PC enabled for wake-up.
Raw send and receive using WinPcap interface
A toolkit for totally raw (MAC level and with no TCP/IP installed) send and
receive on Windows is rawStuff.zip (updated on
January 29, 2009). This toolkit includes software developed by the Politecnico
di Torino, and its contributors
Utility for remote execution of a Windows console application
Two sockets programs, a local.c and
remote.c to transfer a Windows console
application (an "exe" file) from the local host to the remote host,
execute the program on the remote host, and then return stdout to the
local host. This program compiles only for Winsock.
|Bloom filter and related|
Implementing a Bloom filter
A simple program for a 256-bit Bloom filter is bloom1.c.
A general implementation of a Bloom filter is bloom2.c.
Simulation of a Bloom filter to determine probability of false postive
A simulation of a Bloom filter to determine probability of false positive
Simulation of "balls and bins" to determine bin probabilities
A simulation of "balls and bins" to determine probability of non-empty bins
|Miscellaneous tools and programs|
Demonstration of threads and processes
Threads and processes can enable one to build multitasking program.
A bare-bones example of threads is thread.c
(this example is for both Windows and POSIX threads - conditionally compiled).
An example of processes using Win32 API function calls is
process.c (this program needs a compiled
hello.c to be in the same directory).
Demonstration of Windows semaphore and threads
A semaphore can be used to make a thread wait for work (and not just spin).
Two examples are semaphore1.c and
semaphore2.c. A thread can also be directly suspended
and resumed, an example is suspendThread.c.
Demonstration of the system() function
The system() function can be used to execute command-line
commands. An example is system.c (this program needs
a compiled hello.c to be in the same directory).
Demonstration of how to time program execution
Timing program execution is possible using standard timeb.h library
functions (portable for Windows and Unix), an example is,
timeit.c. For greater precision on Windows the
precision timer can be used, an example is
Program to get the current time
A program to get the current time is gettime.c
Utility to suspend a process for a user specified number of seconds
A sleep program for Windows and Unix is sleep.c.
Program to generate files of a specified size
Program to compute probabilities for the birthday paradox
A birthday paradox program is birthday.c.
Program to BUSY, IDLE, and SLEEP data from a Windows PC
A program to collect BUSY, IDLE, and SLEEP data on a per minutes basis
from a Windows PC is idleCollect.c.
Program to determine sleep time given BUSY and IDLE data
A program to model inactivity time out for a time series of
BUSY and IDLE data is sleepSim.c. A
program to convert interval times to vectors (of 0 and 1) is
Programs to put to sleep and wake-up a Windows PC
A program to immediately put to sleep a Windows PC is
putSleep.c. And, a program to implement a
timed wake-up is wakeup.c.
Programs to get battery lifetime of Windows laptop
A program to get battery lifetime (as a percentage) of a Windows
laptop is getBattery.c.