An Architecture for Network Simulation
A flexible system based on a blocks language
Peter D. Varhol
Peter is chair of the graduate computer science and mathematics department at Rivier College in New Hampshire. He can be contacted at [email protected].
My need to simulate computer networks arose out of research on intelligent architectures for evaluating network traffic and routing packets along the most-efficient path. Without a large-scale computer network with which to experiment, I could not prototype and test different types of architectures, nor show with any certainty that they would actually work as planned. Before proceeding with this research, I needed to find a way to demonstrate its effectiveness; a simulation seemed in order. Of course, commercial network-simulation software is available--NetMaker (Make Systems), Bones PlanNet (Comdisco Systems), L-Net (CACI), and SES (Scientific and Engineering Software) spring to mind--but none of these completely satisfied my needs. Consequently, I developed my own simulation package as a visual blocks language.
A blocks language is composed of graphical blocks representing, in this case, simulation or networking concepts. With blocks languages, you write a program by positioning blocks on the screen, connecting them with wires, and adding any necessary parameters. In the case of my blocks language, a simulation might look like the diagram in Figure 1.
Writing a block is a multiple-step process. For the block itself, you can assume an array of inputs and outputs corresponding to the number of inputs into the block and outputs from the block. Parameters for individual blocks are entered in a dialog box and are available to the block as an array of variables.
The block itself is a procedure or function that takes the data, manipulates it according to the specification for that block, and outputs the result. For example, the create-packet block might look like Listing One.
In addition, several optional functions are associated with each block. These functions perform operations such as creating the dialog box, labeling dialog-box inputs, allocating memory for parameters, and initializing variables at the start of a simulation run. Some associated functions are shown in Listing Two.
As I began developing a language for simulating computer networks, I discovered that many people I talked to were interested in network simulation as an end unto itself. Many researchers, network managers, and information-system planners are looking for ways to experiment with different network configurations for both abstract and practical purposes. This description of a network-simulation system represents one possible approach to doing just that.
Queuing and Computer Networks
A packet network is, in effect, a queuing system. Packets are generated by a source system and passed to a server. The server evaluates the destination address of the packet, wraps it in a different protocol if necessary, and sends it on its way. Most networks are simply a sequence of these structures operating in a serial fashion.
The server, hub, or router (or internetworking host) is a finite resource that all packets must use. The packets may come into that servicing agent from multiple sources, and may have to be routed to multiple destinations, according to their destination address. If multiple packets arrive too quickly for the server to process them all at once, they have to queue up and wait for service. These intermediate servers may also wrap the packet in another protocol, requiring more processing time.
Granted, more than this basic activity goes on in computer networks; in fact, many types of computer networks do not even use this transmission paradigm. The Token Ring, for example, is literally a ring that continuously runs a token, much as a race car runs on a racetrack. When some data has to be transmitted from a system on the network, the token picks it up and deposits it at the destination system. I wanted to be able to model these different types of networks also.
Therefore, my simulation-blocks language became a general queuing language geared toward simulating bus-oriented packet networks, since these networks were easiest to visualize as a queuing system. In fact, the queue/server concept can serve as the basis for simulating other types of networks (such as Token Ring) and even nonnetworking applications. (I've been asked about the possibility of using it to simulate computer I/O subsystems and even to simulate riverboat traffic on the Mississippi River.)
Written in Borland Pascal and sitting on top of the VisSim simulation engine from Visual Solutions (Westford, MA), my blocks language includes blocks for creating, queuing, servicing, and passing a packet on to its destination. The packet can be destroyed, or it can be passed on to as many servers as necessary to reach its destination. (For more information on VisSim, see my article, "Extending a Visual Language for Simulation," DDJ, June 1993, which describes how you can enable discrete-event simulation via DLLs.)
The Language Internals
The base unit of management is the packet--a Pascal record that carries all of the information that you may need to know about individual packets. It has fields for a packet ID number, priority, destination, waiting time, service time, and number of "servers," or routing gateways. User-defined fields let the user specify things like packet size or protocol type. While it doesn't contain nearly all of the information contained in a TCP/IP packet, for example, it can be configured with most of the information that could possibly influence a simulation.
Example 1 is the packet's structure. Queues are arrays of linked lists, with the linked list representing the actual queuing of packets. This lets me consecutively number packets and reference them by array element. The linked list can be ordered in a variety of different scheduling disciplines, including FIFO, LIFO, and priority orders, with FIFO as the default. Implementing the alternative scheduling disciplines is a simple matter of ordering the linked list every time a new packet enters the queue.
The server is also an array, but one whose elements can contain only a single packet structure. The server element simply holds onto a packet until the service time expires.
In between the queue and the server is a block called a "transaction manager," a structure that accepts packets from any number of different queues and parcels them out among any number of different servers. It is a traffic manager, so to speak. While there is no analogous construct in a computer network, the transaction manager gives a queue/server combination the flexibility to simulate many different combinations of networks. The transaction managers are also implemented in arrays, so that it is possible to develop a simulation with multiple queue-server combinations.
The transaction manager also provides for the implementation of several different service disciplines across multiple queues and servers. It can select packets for service according to their arrival time in the queue, irrespective of which queue they join. For multiple-queue systems, it offers several different service protocols, including packet or queue priority and priority preemption with or without saving the processing state.
In addition to these basic simulation constructs, I collect the data from packets as they are created and use it to produce statistics on packet-creation rate, average service time, average waiting time, number of packets created and processed, and server-utilization rate. As a result, you can monitor the progress of individual packets and also locate bottlenecks in individual servers, routers, or hubs.
How It Works
The entire simulation process is event driven. Each event represents either one or more packets being created, or one or more packets leaving one or more of the service elements. (If the queue has more packets, this also represents a dequeue.) All packets are created with a random number that designates the time required to service that packet (this number can also be constant and deterministic). At the same time, another random number is generated to designate the time until the next transaction is created.
At an event, if a packet is created, it is assigned a service time, an ID number, a destination address, a priority (if desired), and any user-defined data you want to include. It is queued, and the queue is ordered if necessary. If both the queue and an available server are idle, the packet goes directly to the server.
At the next event, if the service time completes before the next packet is created, the server releases the packet. If that server is its destination, it is destroyed; if it was an intermediate processing location, it is passed on. If the next packet is created first, it waits in the queue until the next event occurs. If service is completed at that time, that packet is released and the next waiting packet enters the queue. If, instead, it's time to create yet another packet, the new packet will also be queued up.
For multiple-queue/multiple-server configurations, the transaction manager comes into play. It effectively manages the flow of packets from multiple queues and parcels them out to one or more servers. It can service multiple queues in round-robin ordering, or it can service queues either by queue priority or by individual-packet priority, regardless of queue. If you service by packet priority, you can choose to preempt service for packets with a higher priority. The service protocol can be specified from a pop-up menu.
Random numbers play an important part in this architecture. They represent the time between packets and the time required to service a packet. I developed random-number generators that follow the uniform, normal, poisson, and exponential distributions. The user has full control over the means of the random number created by the random-number generator and can even insert the mean values on a slider control and change them during a simulation run.
Building a Network Simulation
The VisSim blocks editor lets you select blocks from the menu and place them on the workspace, then connect them with wire lines to signify the flow of control. It also lets you define your own menu selections through a C-language interface. These menus are mounted in the editor's blocks menu during load time. For flexibility (and to let me work in Pascal), my menu selections use the C-language interface (see Listing Three), which subsequently calls a DLL with my Pascal functions.
Creating a network simulation is a simple matter of loading the correct menus during application launch, then placing the blocks on the display and connecting them. The VisSim blocks editor also lets you collect individual blocks together and create compound blocks so that you can abstract details and create large network simulations. The level of abstraction is effectively unlimited, so you can create a hierarchy of components and collect statistics that examine the behavior at each level.
It would be relatively easy to add other constructs to this simulation language. The block-programming interfaces are limited, and there is little dependency between blocks that would limit the ways in which the constructs can be assembled. Each block places a packet in a memory location identified by a pointer. The next block in the sequence checks to see if there is a packet in the previous block; if there is, it simply assigns a pointer variable to that packet and continues processing from that point.
As a result, knowing the data interface and the conventions for developing user-defined components for the VisSim simulation engine, it is possible to develop additional blocks to interact with the existing ones. They can even be added to the VisSim menu and completely integrated with existing blocks.
An Environment for Network Planning
There are many directions to take from here. I intend to build neural-network and fuzzy-logic controls for an intelligent feedback architecture that monitors network performance and changes the routing scheme in response to faults and bottlenecks. Imagine an unsupervised neural net that categorizes network traffic by traffic intensity or by projected time to destination. These categories are, in effect, fuzzy and can be used to construct likelihood distributions of the relevant variable. The likelihood distributions can then be defined as inputs to a supervised neural net, which will develop the routing algorithm. In Figure 2, the unsupervised neural net establishes fuzzy categories of network traffic, the backpropagation neural net develops the algorithm and feeds data back to refine fuzzy categories, and the network traffic is routed across multiple pathways.
Eventually, this type of simulation approach can also become a more complete environment for network planning and implementation. For many network managers, the implementation and maintenance of a large network can be a matter of hit or miss. Imagine the possibility of amassing and codifying expertise on network types, configurations, implementations, and management; in other words, an expert system (or combination of cooperating expert systems) for networking. Such an expert system could evaluate the data created by a network simulation and recommend improvements to the configuration. This is, of course, much more difficult to do than to describe, but it is a worthy effort and certainly a needed tool to deal with the growing size and complexity of today's internetworks.
Figure 1: A multiple-queue, single-server configuration that simulates the behavior of a networking bridge.
Figure 2: Routing algorithm.
Example 1: Packet structure.
Copyright © 1995, Dr. Dobb's Journal
packetptr = ^packet;
packet = record
packet_number : double;
priority : double;
wait_time : double;
serve_time : double;
preempt_time : double;
destination : double;
t_mgr : double;
servers : double;
use : user;
link : packetptr
end;
Listing One
procedure create(var param, inV,outV:VisSimArg);
export;
var i: integer;
begin
if param[0] <> 0 then
q_number := trunc(param[0])
else
begin
q_number := 1;
param[0] := q_number
end;
c[q_number] := false;
if {(inV[0] > 0) and} q_remaining[q_number] <= 0 then
begin
new(next[q_number]);
created[q_number] := true;
q_remaining[q_number] := InV[0];
packet_created[q_number] := cust_created[q_number] + 1;
packet_id[q_number] := customer_id[q_number] + 1;
next[q_number]^.customer_number := customer_id[q_number];
next[q_number]^.destination := q_number;
next[q_number]^.priority := inV[1];
next[q_number]^.wait_time := 0;
next[q_number]^.serve_time := 0;
next[q_number]^.preempt_time := 0;
next[q_number]^.link := nil;
next[q_number]^.use[1] := InV[2];
if inV[3] <> 0 then
if first[q_number,1] = 0 then
next[q_number]^.use[1] := InV[2]
else
for i := 1 to max_data do
next[q_number]^.use[i] := first[q_number,i];
end;
if created[q_number] = false then
outV[0] := 0
else
outV[0] := q_number;
end;
Listing Two
procedure createSS(var param : VisSimArg; var runCount : shortint);
export;
var i : integer;
begin
for q_number := 1 to maxqueues do
begin
created[q_number] := false;
packet_id[q_number] := 0;
q_remaining[q_number] := 0;
arrive_sum[q_number] := 0;
packet_created[q_number] := 0;
q_time[q_number] := 0;
for i := 1 to max_data do
first[q_number,i] := 0;
end
end;
function createPA(var ppCount : shortint) : longint;
export;
var paramalloc : byteptr;
begin
ppCount := 1;
createPA := GetMem(paramalloc,16);
end;
function createPC(var param : VisSimArg) : PChar;
export;
begin
createPC := 'Queue #'
end;
Listing Three
#include "windows.h"
#include "vsuser.h"
int DLLInst;
USER_MENU_ITEM trans[] = {
{"Discrete Event", "tran2", -1,-1,0, "Discrete event simulation building blocks"},
{"createTransaction", "create", 3,1,48, "Creates new transactions"},
{"queue", "queue_block", 1,1,184, "First-in, first-out queue"},
{"transactionManager", "t_manager", 1,1,32, "Manages transaction flow between queues and servers"},
{"server", "server", 2,1,32, "Services a transaction"},
{"departSystem", "depart", 1,0,16, "Removes a transaction at the end of a system"},
{0}
};
USER_MENU_ITEM stats[] = {
{"Discrete Statistics", "tran2", -1,-1,0, "Collects statistical data on simulation"},
{"utilizationRate", "utilization", 1,1,16, "Cumulatively computes utilization rate"},
{"queueLength", "queue_length", 1,1,16, "Computes the length of the queue"},
{"waitingTime", "waiting_time", 1,1,16, "Cumulatively computes time waiting in queue"},
{"timeInSystem", "system_time", 1,1,16, "Cumulatively computes waiting and service times combined"},
{"transactionsGenerated", "transactions_generated", 1,1,16, "Computes number of transactions produced in a simulation run"},
{"transactionsServed", "transactions_served", 1,1,16, "Computes number of transactions served in a simulation run"},
{"transactionsLost", "transactions_lost", 1,1,16, "Cumulatively computes proportion of transactions lost in a finite queue"},
{"transactionTime", "trans_time", 1,1,16, "Foobar"},
{0}
};
USER_MENU_ITEM utils[] = {
{"Discrete Utilities", "tran2", -1,-1,0, "Utilities from manipulating a simulation"},
{"poissonRandomNumbers", "poisson", 1,1,16, "Produces a stream of Poisson-distributed random numbers"},
{"exponentialRandomNumbers", "exponential", 1,1,16, "Produces a stream of exponentially-distributed random numbers"}, {"generatePriorities", "generate_priority", 1,1,16, "Randomly generates priority levels for the priority queue"},
{"readTransactionID", "read_transaction", 1,1,16, "Reads the unique ID number of a transaction"},
{"insertData", "insert_data", 1,1,160, "Writes user-defined data into a transaction"},
{"retrieveData", "retrieve_data", 1,1,160, "Reads user-defined data from a transaction"},
{"fork", "fork", 1,2,8, "Causes a branching of a random number stream"},
{"delayTransaction", "delay", 2,1,16, "Delays a transaction passing from a server to a serial queue"},
{"simulationTime", "sim_time", 1,1,16, "Computes the internal simulation running time"},
{0}
};
void EXPORT PASCAL vsmInit()
{
setUserBlockMenu(trans);
setUserBlockMenu(stats);
setUserBlockMenu(utils);
}
