Open University of Sudan

Computer Science & Information

Technology Program

Computer Science & Software

Engineering M.Sc Program
Computer Science & Information
Technology Program

Computer Science & Software

Engineering M.Sc Course
 .

Analytic Models and Simulation of

Computer Systems
 Unit 1

• Introduction
 Introduction

• Simulation:
A simulation is the imitation of the
operation of a real process or system
over time.
 Continue
• Simulation involves:
1/ The generation of an artificial history of
a system.
2/ The observation of that history.
3/ The Drawing of inferences concerning
the operating characteristics of the real
system.
 Continue

• A simulation Model is utilized to study the

behavior of the desired system as it
evolves over time.
• This model usually rely on some
assumptions concerning the operation of
the system.
 Continue

• These assumptions are expressed in

mathematical, logical and symbolic
relationships between the objects of
interest
 Continue

• It is worth mentioning that, system analysis

and Operation Research Applications
consider Simulation as the appropriate tool.
 Continue

• This is true since Simulation techniques

are characterized by the following
features:
 Unit 2

• Characteristics and
Advantages of Simulation
Characteristics and Advantages
of Simulation

1- The availability of special-purpose

simulation languages.
2- The availability of massive computing
capabilities at a decreasing cost per
operation.
 Continue

3- The availability of advanced simulation

methodologies.
4- Simulation enables the study of, and
experimentation with, the internal
interactions of complex systems.
 Continue

5- Expected changes in the system can

be simulated to observe consequent
alterations in model behavior.
 Continue

6- Experience and knowledge gained in

designing a simulation model may play a
role in the improvement of the system
under investigation.
 Continue

7- The possibility of monitoring the impact

of input changes on outputs.
8- Simulation may play an important role in
the reinforcement of Analytic Solution
Methodologies.
 Continue

9- Simulation is a powerful tool for both

design purposes and pre-implementation
stages assessment.
10- Simulation techniques can be utilized
in the verification of analytic solutions.
 Continue

11- Many System features can be

explored without disturbing ongoing
operations of the real system. These
include:
 Continue

a/ New Policies.
b/ New Procedures.
c/ New Decision rules.
d/ New information flow scenarios.
 Continue

12- The possibility of testing new

hardware designs or physical layouts
without being physically implemented.
13- The possibility of testing hypotheses
about how and why certain phenomena
occur.
 Continue

14- The possibility of controlling the

investigation duration for a given
phenomena.
15- The Possibility of studying the
contribution of different variables in
deciding system performance.
 Continue

16- The Possibility of determining delay

sources according to performance
analysis.
 Continue

17- The Possibility of understanding how the

system operates.
18- The Possibility of answering “ What if “
questions.
 Assignment NO. 1
• Characteristics and Advantages of
Simulation include:
- Simulation is a powerful tool for both
design purposes and pre-implementation
stages assessment.
- Many System features can be explored
without disturbing ongoing operations of
the real system.
 Continue:
- The possibility of controlling the
investigation duration for a given
phenomena.
With the aid of suitable examples, discuss
the above mentioned points.
 Unit 3

• Disadvantages of Simulation
 Disadvantages of Simulation

• Model building requires training and

experience. This leads to the fact that,
models developed by two different
individuals may differ.
 Continue
• Simulation is expensive and time
consuming. Without the availability of
necessary resources, Simulation may
result in poor and insufficient outputs for
the desired task.
 Continue

• Sometimes, Simulation techniques are

used where analytical solutions are
possible or even preferable.
 Areas of Application

• Computer Systems Performance.

• Communication Networks Performance
Analysis.
• Manufacturing Systems.
• Public Systems (Health care, Military,
Natural Resources).
 Continue
• Transportation Systems.
• Construction Systems.
• Business Process Engineering.
• Food Processing.
• Traffic Engineering Analysis.
 Unit 4

• Some Important Concepts

 Some Important Concepts

• System and System Environment.

• Components of a System.
 System

• A system is defined as a group of objects

that are joined together in some regular
interaction or interdependence in order to
achieve some purpose.
 System Environment

• A system is often affected by changes

occurring outside the system. Such
changes are said to occur in the system
environment.
 Components of a System
- An entity.
- An attribute.
- An activity.
- The state of a system.
- An event.
- Endogenous & Exogenous.
 Continue

• An entity is an object of interest in the

system.
• An attribute is a property of an entity.
 Continue

• An activity represents a time period of

specified length during which some task
or process is performed.
 Continue

• The state of a system is defined to be

that collection of variables necessary to
describe the system at any time, relative
to the objectives of the study.
 Continue

• An event is defined as an instantaneous

occurrence that may change the state of
a system
 Continue

• The term endogenous is used to describe

activities and events occurring within a
system.
 Continue

• While the term exogenous is used to

describe activities and events in the
environment that affect the system.
 Unit 5

• Models
Discrete and Continuous Systems

• Systems are categorized as:

- Discrete systems.
- Continuous systems
 Discrete Systems

• A discrete system is one in which the

state variables change only at a discrete
set of points in time.
 Continue

• A continuous system is one in which the

state variables change continuously over
time
 Model of a System

• A model is defined as a representation of a

system for the purpose of studying the
system.
• The model should be sufficiently detailed to
represent the real system.
 Types of Models
• Models can be classified as:
- Mathematical models.
- Physical models.
• Models may be further classified as:
- Static models.
- Dynamic models.
 Continue

• A mathematical model uses symbolic

notation and mathematical equations to
represent a system. A simulation model is a
particular type of mathematical model of a
system.
 Monte Carlo Simulation

• Monte Carlo Simulation, sometimes

called a static simulation model,
represents a system at a particular point
in time.
 Dynamic Simulation Models

• Dynamic Simulation Models represent

systems as they change over time. The
simulation of a Bookshop from 8:00 A.M.
to 3:00 P.M. is An example of dynamic
Simulation.
 Unit 6

• Simulation Steps
 Simulation Steps

• The flow chart shown below illustrates a

set of steps to guide a model builder in a
simulation study. These steps include:
Simulation Steps Flow Chart (1/2)
 Simulation Steps Flow Chart (2/2)

.
 Simulation Steps

• 1/ Problem Formulation:
The analyst must ensure that the problem
being described is clearly understood.
 Continue

• 2/ Setting of objectives and project plan:

The objectives indicate the questions to
be answered by simulation. The plan
should include:
 Continue
1- A statement of alternatives.
2- A method for evaluating the
effectiveness of these alternatives.
3- The plans in terms of number of people
involved.
4- The cost of the study.
5- The time table of the study.
 Continue
• 3/ Model conceptualization:
The art of modeling is enhanced by the
ability to abstract the essential features of a
problem, to select and modify basic
assumptions that characterize the system
and then to enrich and elaborate the model
until useful approximation results.
 Continue

• 4/ Data Collection:
There is a strong relation between the
construction of the model and the
collection of the needed input data.
 Continue

• 5/ Model Translation:
The model must be entered into a computer
recognizable format using some
programming language or special-purpose
simulation software.
 Continue

• 6/ Verification:
In verification step we answer the
following question:
Is the computer program performing
properly?
 Continue

• 7/ Validation:
Validation is the determination that a
model is an accurate representation of
the real system.
 Continue

• 8/ Experimental Design:
In experimental design, the following
points should be determined:
- Alternatives to be simulated.
- Initialization period length.
- NO. of run replications.
 Continue

• 9/ Production runs and analysis:

Production run results are utilized to
estimate system designs performance.
 Continue

• 10/ More runs:

According to runs analysis results, the
analyst should decide whether more runs
are needed or not.
 Continue

• 11/ Documentation and Reporting:

There are two types of documentation
1- Program Documentation.
2- Progress Documentation.
 Continue

• Program Documentation is necessary for

many reasons. Documentation makes
the program easy:
- To understand.
- To modify.
- To change model parameters
 Continue

• Progress Documentation provides the

important written history of a simulation
project. Projects reports show the work
done and decisions made.
 Continue

• 12/ Implementation:
The success of implementation phase
depends on how well the previous 11
steps have been performed.
 Unit 7

• Simulation Example


Poisson Distribution

• A stochastic process taking non-negative

values is said to be a Poisson process
with rate if:
 Continue

• 1- A(t) is a counting process that

represents the total number of arrivals that
have occurred from 0 to time t (A(0)=0)
and for S<t, A(t) –A(S) equals the number
of arrivals in the interval (S,t).
 Continue
• 2- The number of arrivals that occur in
disjoint time intervals are independent.
• 3- The number of arrivals in any interval of
length is Poisson distributed with
parameter for,t >0.
P At     At  n  
   
n

n! e
n=0,1,2,..
 Continue
• The average number of arrivals within an
interval of length is (According to the
calculated mean in a Poisson distributed
system). Hence, can be considered as
arrival rate (average number of arriving
customers per unit time).
 Continue

• The following properties of the Poisson

process are worth mentioning
 Continue
• 1/ Inter-arrival times are
independent and exponentially
distributed with parameter . That is if
denotes the time of the nth arrival, the
intervals
have the probability distribution

P n S  1 
 S
e 0
s
 Continue
• The probability density function is

P  n   e
  n

The mean and variance of are 

1 / and 1/ 
2

respectively.
 Continue
• 2- For every t 0 and  0

P At     At  0 1    0 

P At     At  1   0 

P At    At  2 0 

 Continue
• The proof of the above stated property can
be illustrated by substituting the value of n
by 0,1,2,…
in the following equation:

P At     At  n e

    n

n!
 Continue

• If two or more Poisson processes

A= A1, A2,… ,Ak
are merged into a single process
A= A1+ A2+… +Ak , then, this
resulting process is Poisson with rate
equal to the sum of rates of its
components.
 Assignment
• Prove this property.

Hint:
Assume that, two disjoint time intervals are
independent and Poisson distributed with
parameters ,  1  2
 Continue
• , then the probability that the total number
of arrivals is N=N1+N2 is given by

N
PN1  N 2  N   PN1 k PN 2  N  k 
k 0
 Exponential Distribution
• A given process (e.g. customers service
times ) is said to have an exponential
distribution with parameter  . I.e., if S n is
the service time for the nth customer, then
 Continue

P S n S  1  e  S
S 0

• The corresponding probability density

function is
P S n  e  S n
 Continue
• The service times S n are mutually
independent and also independent of all
inter-arrival times. The parameter 
is called the service rate.
 Continue

• It represents the number of customers

served per unit time at which the server
operates when busy.
 Computer & Communication
Networks Performance Analysis

• For Design Purposes.

• For Quality Assurance Purposes.
• For Congestion Prevention Purposes.
• For the Continuation of Normal
Operation.
• For Future Planning Purposes.
 For Design Purposes:

• Traffic Engineering Analysis offers a

powerful forecasting tool for the expected
system performance level.
 For Quality Assurance Purposes:

• Traffic Engineering Analysis results

constitute powerful monitoring means
that help a lot in achieving Quality
Assurance Goals.
 For Congestion Prevention
Purposes

• Some Traffic Engineering Analysis results

constitute a powerful congestion indicators.
Thus, these results are utilized in taking
congestion prevention decisions.
 For the Continuation of Normal
Operation:

• Traffic Engineering Analysis results are

key factors in the normal operation of
Routing Algorithms.
 For Future Planning Purposes:

• Future system expansions should rely on

reasonable projections and estimates. This
is possible under the light of the present
working conditions expressed in terms of
Traffic Analysis results.
 Simulation example
• M/M/1 Queuing Systems:
The M/M/1 Queuing system consists of a
single queuing station with a single server
(a single transmission line).
 Continue
Customers arrive according to a Poisson
process with rate . The probability
distribution of the service time is
exponential with mean equals (1/  ) sec.
 Continue

• 1 M/M/1 Arrival Statistics:

Referring to Poisson process properties
mentioned earlier, the following relations
(these relations represent the probabilities
of 0, 1 and 2 arrivals) hold:
 Continue

P At    At  0 1    0 

P At    At  0 1    0 

P At    At  1   0 
P At    At  2 0 
 Continue

• The above shown expressions show that

the summation of probabilities associated
with n=0, 1 and 2 is one. This dictates
that all probabilities associated with n>2
are zeros.
 Continue

• M/M/1 Service Statistics:

Since service times are exponentially
distributed, the departure probability of
zero customers and 1 customer can be
expressed as follows:
 Continue

 
PD0 e
 
PD1 1  e
 Continue

• According to arrival and departure

probabilities mentioned earlier, the
probabilities of 0 arrival 0 departure, 0
arrival 1 departure and 1 arrival 0
departure are expressed as follows:
 Continue

P00 1      0 
Pi ,i 1   0 
Pi ,i  1    0 
 Continue
• These probabilities add up to 1. . This
implies that, the probability of ( I
customers arrive and I customers
depart), for i,1 equals 0. That is to
say, Pi ,i 0 for i 1
 Continue
• The figure below shows the transition
diagram based on Markov chains. It is
clear that, the total number of transitions
from state n to state n+1 must differ from
the total number of transitions from state
n+1 to state n by at most 1.
 Markov Chain for the M/M/1 System

.
 Continue
• Accordingly, the transition frequency from
n to n+1 is equal to that from n+1 to n.

Pi ,i 1   0 
Pi ,i  1    0 
 Continue
• So

Pn    Pn 1  
Pn 1 Pn

  / 
n 1
Pn 1   P0
 Continue

• Starting from the last equation and using

Little’s Theorem (N= T ), we can derive
so many parameters. These include:
 Continue
- Average number of customers in the
system N.
- Average number of queued customers
Nq.
- Average queuing (waiting) time in the
queue W.
- Average total time T.
 Assignment NO. 2

1/ Derive expressions for:

a- Average number of customers in the
system (N).
b- Average total time (T).
2/ Write a simple program to compute the
above mentioned parameters.
 Continue

3/ Use these programs to plot N as a

function of utilization factor   / and
 T
as a function of arrival rate .
 References:

Bossel H., Modeling & Simulation, A. K.

Peters Pub., 1994.
Delaney W., and E. Vaccari, Dynamic
Models and Discrete Event Simulation,
Dekker, 1989.
 References
• Fishman G., Discrete-Event Simulation:
Modeling, Programming and Analysis,
Springer-Verlag, Berlin, 2001.
 References
• Fishwick P., Simulation Model Design and
Execution: Building Digital Worlds,
Prentice-Hall, Englewood Cliffs, 1995.
 References
• Ghosh S., and T. Lee, Modeling &
Asynchronous Distributed Simulation:
Analyzing Complex Systems, IEEE
Publications, 2000.
 References

• Gimblett R., Integrating Geographic

Information Systems and Agent-Based
Modeling: Techniques for Simulating
Social and Ecological Processes, Oxford
University Press, 2002.
‫و نسأل الله التوفيق والسداد لنا ولكم‬

‫د‪ /‬أمين بابكر عبد النبي مصطفى‬

‫يوليو ‪2008‬‬