Christensen Tools Page Department of Computer Science and Engineering

Analytical tools

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.

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.

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%, 95%, and 99% values
• moments.c - Moments (raw and central)
• 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
• qsort.c - Sort a series of floating point numbers
Here are some tools to manipulate, convert, and otherwise "morph" time series data sets :
• dup.c - Test for duplicate values
• sort.c - Sort
• hist.c - Frequency count (histogram)
• filter1.c - Filter "out"
• filter2.c - Filter "in"
• scale.c - Scale
• spread.c - Spread-out values
• shape1.c - Shape to deterministic
• shape2.c - Shape to exponential
• 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
• 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
Using the above simple tools, a reproduction of some of the key results in the famous Leland et al. Bellcore traffic study was completed (see Bellcore reproduction).

Generating a time series with a known distribution

The following programs generate a times series with a given probability distribution.
• gendet.c - Deterministic
• genunifc.c - Uniform (continuous)
• genunifd.c - Uniform (discrete)
• genpeak.c - Peaked
• gennorm.c - Normal
• genexp.c - Exponential
• 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
To merge two files containing <interarrival_time_delta> entries (e.g., as generated by the above programs), use merge.c.

Generating synthetic packet traffic

The following programs generate synthetic trace files with entries of <interarrival_time, packet_size>.
• syntraf1.c - Bounded Pareto burst size and exponential interburst time
• syntraf1a.c - Version of above syntraf1.c with target utilization

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
Some tools to operate on a series of tuples of <boolean, boolean> are:
• corr1.c - Correlate "anomalies" with "glitches"
• corr2.c - Correlate "glitches" with "anomalies"

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, correl.c.

Exponential smoothing to forecast the next value in a series

Here is a tool to implement exponential smoothing, smooth1.c

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 hypo1.c.

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, here.

Generating uniform and normal 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). To compute normal(0, 1) random numbers use normal.c (using the polar method).

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 stop_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 - 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 a fluid-flow, single-server, finite-buffer queue

A program to model a fluid-flow, single-server, finite-buffer queue is fluid1.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.

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 ether.c.

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.

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.

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.

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

The program timeget1.c time serial GETs to a web server and timeget2.c times parallel 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.

A simple UDP datagram reflector/relay program

A sockets program to reflect or relay UDP datagrams is udprelay.c.

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.

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.

Demonstration of raw sockets

A program to demonstrate a send with raw sockets (for Winsock only) is rawsend.c.

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. This product includes software developed by the Politecnico di Torino, and its contributors (found here).

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). An example is semaphore.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.

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 a binary file of a specified size

A binary file generator program is genfile.c.

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.

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.