NONOVERLAPPING QUEUEING MODELS
by
Jeffrey Scott Meis
B.S., Colorado School of Mines, 1986
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Master of Science
Department of Electrical Engineering
and Computer Science
1991
This thesis for the Master of Science
degree by
Jeffrey Scott Meis
has been approved for the
Department of Electrical Engineering
and Computer Science
by
ii
Meis, Jeffrey Scott (M.S., Electrical Engineering)
Nonoverlapping Queueing Models
Thesis directed by Associate Professor Douglas A. Ross
Queueing models must accurately predict physical
system behaviors in order to be used for determination of
network capabilities and sizing.
The M/M/l model is based on Poisson packet arrival
and service processes and therefore the arrival and
service rates have the same mean and variance. The
packets in this models can theoretically overlap which
causes the prediction for the arrival rate and number of
packets in a queue to be over emphasized. Most models
such as the M/M/l and the M/G/l model do not consider the
packet lengths as well as the gap lengths between
subsequent packets arriving into a queue. In order to
have an accurate prediction of the queue's behavior both
the packet and gap lengths must be considered.
The M/G/l queueing model shows that for all queueing
models with general service distributions, the mean queue
occupancy can be determined if only the queue utilization
and variance of packets arrivals is known. Therefore, in
iii
order to derive an accurate model the arrival process for
realistic packets must be determined.
When the variance of a nonoverlapping packet arrival
process is known, the G/G/l model can be derived. This
model can then be truncated to a finite model, G/G/.1/N,
in order to accurately predict the mean queue occupancy
and thus the average time delay for a queueing system.
The form and content of this abstract are approved.
I recommend its publication.
Signed_
iv
ACKNOWLEDGMENTS
I would like to express my appreciation to Dr.
Douglas A. Ross for his support and for the use of his
mind at times. I would also like to thank the people at
BDM International in Boulder for their help in preparing
this thesis.
Special thanks is given to my wife Audrey and Jim
Conrad for their support and constant encouragement to
finish.
v
TABLE OF CONTENTS
CHAPTER
1. INTRODUCTION.......................................1
2. BASIC QUEUEING THEORY AND MODELS...................4
Queueing Systems.................................4
Packet Arrival Process...........................7
Service Time Distributions......................10
M/M/l Queue.....................................11
State Dependent Queues..........................18
M/G/l Queue.....................................25
3. NONOVERLAP PING PACKET ARRIVALS..................32
Theory Development..............................32
Variable Length Packets.........................38
Fixed Length Packets............................41
4. G/G/l QUEUEING MODEL..............................45
Variable Length Packet Model....................4 6
Fixed Length Packet Model.......................50
5. G/G/l/N QUEUEING SIMULATION.......................55
Ethernet Network Simulation.....................58
6. DISCUSSION AND CONCLUSION.........................62
APPENDIX
A. PROOFS AND DERIVATIONS............................67
B. COMPUTER PROGRAMS.................................7 9
vi
FIGURES
Figure Page
2.1. Queueing System.....................................5
2.2. State Diagram......................................12
2.3. Blocking Probability...............................16
2.4. Throughputload Characteristic.....................16
2.5. Performance Characteristics........................21
2.6. M/M/N/N Queueing System............................24
2.7. Timing Diagram.....................................28
3.1. Probability of n Arrivals,
Variable Length Packets...........................41
3.2. Probability of n Arrivals,
Fixed Length Packets..............................44
4.1. Mean Queue Occupancy, Variable Length Packets......4 8
4.2. Mean Queue Occupancy, Fixed Length Packets.........51
4.3. Average Time Delay.................................52
5.1. Average Time Delay for Network Simulation
(100 msec)........................................59
5.2. Average Time Delay for Network Simulation
(200 msec)........................................60
vii
CHAPTER 1.
INTRODUCTION
Queueing model performance is based on how well the
model matches a system's true behavior. In most
practical systems, packets must be guaranteed to arrive
without damage. These systems are governed by protocols
such as IEEE 802.3, which do not allow for packet
collisions. Since these protocols protect against packet
damage due to the existence of multiple packets on the
same part of the transmission facility at the same time,
packets cannot overlap. However, all queueing models
based on Poisson arrivals allow for overlapping packets.
The unrealistic result of these models is derived from
the fact that the variance of a Poisson distributed
random variable is equal to its mean. Theoretically
then, the packets can overlap as much as 50 percent.
Chapter II develops the basic queueing model concept and
the M/M/l model based on the Poisson process. The M/G/l
model is also developed which leads to an important
derivation for the mean queue occupancy of a system for
any arrival process.
Since packets are not allowed to overlap in a
physical system, an arrival process based on non
overlapping packets must be developed. Packets have a
certain length or range of lengths and a time gap between
successive arrivals. Therefore, both the packet sizes
and the gaps must be taken into account when a model is
developed. Chapter III develops the statistics for the
nonoverlapping packet arrival process for both fixed and
variable length packets. These statistics are used to
determine the probability of arrivals into a queue during
a service time and more importantly the variance of the
number of packets arriving.
A queueing model that more accurately predicts
important behavior, such as average queue occupancy and
mean time delay, of actual systems is needed. In chapter
IV a generalized model called a G/G/l queueing model is
developed. It can be derived from the variance of the
packet arrivals and is comparable with existing models
such as the M/M/l and the M/G/l.
Packet networks deal primarily with fixed packet
lengths for transmission. If fixed packet sizes are used
and the gaps are still allowed to vary, the model that is
created will best fit physical message buffering systems.
Chapter V compares a finite queue model, G/G/l/N, with a
simulation run on a physical system where the mean time
2
delay was measured. A simplistic result is developed
when actual network behavior is introduced to the model.
A discussion and conclusions of this thesis is given
in chapter VI.
3
CHAPTER 2.
BASIC QUEUEING THEORY AND MODELS
21 Queueing Systems
A queueing system is a set of separate, yet sometimes
interrelated, processes that perform the function of
receiving input and ultimately supplying output. This
system can be divided into six essential parts. Each
part has its own unique set of rules and operations that,
when accumulated, make up the queue's behavior. The
following is a list and brief definition of each part,
corresponding with figure 2.1:
Population The source of customers that can
either be described as finite or infinite. An
infinite source is mathematically easier to use
since it is independent of the arrival rate.
Arrival Rate The rate at which customers
arrive at the queue. The arrival rate is a mean
value of a random variable with a given
distribution. Arrival rate is usually noted as
X packets/second.
Service Rate The rate at which customers are
served and sent on their way. The service rate
is also a mean value of a random variable with a
given distribution. Service rate is usually
noted as 1 packets/second.
Queueing Capacity Maximum number of customers
allowed to wait for service. At maximum,
customers are either blocked and returned or
dropped. The queue is sometimes referred to as
a buffer with either a finite or an infinite
size.
Number of Servers Number of identical servers
available to service incoming customers.
Queue Discipline The rules used at input to
determine which customer is to be served.
Number of
Queue Servers c
5
In order to analyze a queueing system's performance,
certain parameters must be measured or calculated. The
following is a brief discussion of these performance
parameters and how they relate to specific system parts.
Link capacity C The digital rate of data
transmission in data units per unit time.
Average packet length 1/1' Average size of
packets being serviced in bits per packet.
These two values are related to the service rate by (i =
Cl' packets/second.
Average holding time l/l seconds/packet, or the
expected service time.
Link utilization or traffic intensity p The
measure of how busy the queue is or at what
ratio traffic is entering to traffic leaving.
p= ^./cl c number of servers.
Other parameters that will be defined later include:
Estimated number of packets in the queueing
system.
Probability of a given number of packets in the
queueing system.
6
Wait times for queue, server, and system.
These other parameters are functions of the packet
arrival process, service time distribution, and service
discipline. To calculate the performance of a queueing
system, these processes must be thoroughly defined. A
common way to label a particular queueing system is to
use the Kendal notation A/B/C. The A represents the
arrival distribution, the B represents the service
distribution, and the C represents the number of servers.
22 Packet Arrival Process
Arrival processes are defined as random with a given
distribution, mean, and variance. The most common
arrival process is the Poisson Process. The Poisson
Process has the following defined characteristics.
1) The probability of one arrival in an interval At
is:
XAt + o(At)*
AAt 1
o(At)* higher order terms.
X proportionality constant.
AAt > 0  so only one packet arrives in
each At.
7
2) The probability of zero arrivals
1 XAt + o (At) *
3) Independent arrival events.
4) Special Markov Process where the probability t +
At depends only on t (memoryless).
For a finite time T, the probability of k events
occurring is defined as:
(A.T) ke^T
p(k) = k! k = O'1/2 2. i
The mean and variance of the Poisson Process are:
oo
E [k] = Â£ k p (k) = XT [A.1.1]
k=0
OO
var[k] = Â£ k2 p(k) = ?tT [A. 1.2]
k=0
The mean E[k] is the average number of packets that
arrive at the queue in a time interval T. For the
Poisson process the variance is equal to the mean,
therefore the number of packets arriving at the queue can
vary as much as *\/E [k] The average arrival rate X is:
X = E[k]/T
Another useful value is the normalized standard
deviation:
8
Gk = >/var [k] /e [k] = yjxt/A,T = l/'N^T
Since this trends to zero as X,T increases, at a large X.T
the distribution is tightly packed around the average X.T.
If X.T 1 then X = n/T (n is the number of arrivals in
T) is a good estimate of the arrival rate. In other
words, over a large time interval the arrival rate can be
assumed to be the number of packets arriving at the queue
per the time interval. Also, since p(0) = e^T, as
increases the probability of no arrivals approaches zero.
Consider a large time interval with Poisson arrivals.
The time between successive events, x, is a continuously
distributed positive random variable with the following
exponential distribution:
f^ (x) = Xe~^ x >= 0 [Derivation appendix A]
This is expected since X is in arrivals/second. Then 1/X
is in seconds/arrival or the average time between
arrivals. The Poisson process has another property that
makes it a widely used arrival process for queueing
models. If m independent streams of rates ^1, X% > are
merged, then the composite stream is Poisson with rate 1:
OO
The mean E [x]
0
The variance o2% = 1/X2
2.2
9
m
* = 2>
i=l
Therefore, regardless of how many nodes are on the
network, the combined arrivals will always behave as a
single source exponential arrival process.
23 Service Time Distributions
The service time distribution shows how the service
of a customer is distributed over a given time and at a
given rate. The Poisson distributed arrival times
development in the previous section leads us directly to
an exponential service distribution. Assume the queue
system is servicing data and then transmitting it at a
rate of (1, and the time between transmissions is an
exponentially distributed random variable r. The mean
and distribution are represented as follows:
E[r] = 1/1
fr (r) = ie^r r >= 0 [A. 2]
If the time between completions is exponential, then
the completion times must represent a Poisson Process.
So the probability of a completion in the interval (t,
t+At) is iAt + o(At). The probability of no completions
in the same interval is then 1 lAt + o(At) While
10
there are a number of other service distributions, they
will not be mentioned here. However, they will be used
in deriving the results for different queueing models.
24 M/M/l Queue
In the Kendal notation, the first M is Poisson
arrivals, the second M is exponential service time, and
the 1 is a single server. The first parameter to
calculate for any queue is the probability p(n) that the
queue is nonempty. Assuming that the queue is in steady
state (the probabilities do not change with time), the
probability of n customers in the queue at time t + At
can be determined. The state, or buffer occupancy, is
either n, n1, or n+1 at time t providing n > 0. The
probability of the queue being in state n at time t + At
is the sum of the mutually exclusive probabilities that
the queue was in states n, n1, or n+1 at time t, each
multiplied by the probability of arriving at state n in
the intervening At unit of time.
pn(t + At) = pn(t) [ (1XAt) (liAt) + (p.At) (XAt) +
o(At)]
+ Pni(t) [ (AAt) (l[iAt) + o (At) ]
+ Pn+I
o(At) higher order terms.
11
Use this equation to study the timedependent (transient)
behavior of the M/M/l queue given that t = 0 is the
starting time and the queue is in a known state or set of
states. The transient analysis can be written by the
following differential equation:
pn (t+At) = pn(t) +
dpn(t)
dt
At
dPn(t)
dt
(^+(J.)pn(t) + ^Pn! (t) + lpn+;L(t)
This yields the differential difference equation to be
solved to find the time variation of pn(t). Assume that
pn(t) approaches the constant pn. For the case of
stationary, nontime varying probabilities:
(^+l)Pn = ^Pn1 + W?n+1 n >= 1 2.3
This equation, called a balance equation, makes physical
sense if the state diagram is observed.
AO M
0
4^"
kn+1
n+1
Hi fl2 /in /in+1
Figure 2.2. State Diagram
Figure 2.2 shows a series of events needed to create a
state of n packets in the queue. This is related to the
12
previous equation if it is examined in parts. The left
side, (A,+l)pn, is the rate of departure from a queue of
state n, where Apn is the arrival rate to n+1 and Jipn is
the departure from state n. The right side is the
arrival rate to state n, where Apn_]_ is the arrival rate
to n and ppn+1 is the departure rate from n+1. Keeping in
mind the rates to and from a state, a solution to the
balance equation would be:
^Pn = M'Pn+l
If this solution is repeated for n states:
Pn = PnPo p = A,/(i 2.4
oo
To find p0 use the probability condition ^pn = 1.
0
For the case of an infinite M/M/l queue:
Po = dp)
pn = (lp)pn p = k/l <1 2.5
In an infinite queue, p< 1 is necessary to maintain
equilibrium. This is required for the convergence of the
infinite sum.
Consider a finite queue with at most N packets. The
normalized condition must consider the finite number of
states.
N
JPn = 1
n=0
13
Therefore, the probabilities of empty and nonempty
queues become:
(1P)
p0 (1pN+l)
2.6
(l~p)pn
Pn (1pN+1)
2.7
So the probability that the queue is full, or the
probability of blocking, becomes:
(1~P)PN
PN =
2.8
(1pN+l)
The probability of blocking becomes an important
parameter when dealing with actual systems. This
probability determines at what utilization p, given a
queue size of N packets, the queue will block subsequent
arrivals. The determination of blocking probability is
used when queue sizing and number of server
determinations are needed.
If a load X is introduced to a queue with blocking
probability of PN, the arrival rate is X provided that
the queue is not full. The actual arrival rate is then
the product of the arrival rate and the probability that
the queue is not full. This is the throughput, y, of the
queue, or the number of packets served per second.
y = X(1 pN) 2.9
14
Another way to define the throughput is to examine the
service time. The throughput is the average service time
provided that the queue is non empty. If the finite
probability of zero arrivals is known, the throughput can
be defined as:
7 = i(l p0) 2.10
The zero probability can be related to the blocking
probability if equations 2.9 and 2.10 are equated.
p0 = 1 pd PN)
In the finite M/M/l queue, the condition p < 1 is no
longer necessary for the equilibrium probabilities to
exist. As X increases with respect to l, p approaches
infinity, and the probability of blocking becomes 1. The
region where p > 1 is said to be congested. The
probability of blocking as p approaches 1 is PN =
1/(N+1). This expression can be used to obtain an
estimate of the blocking probability if an infinite queue
model is used.
The queue's throughput closely equals the load for
small p. As p increases, the throughput approaches the
service capacity p. The expression for the normalized
throughput 7/(1 as a function of the normalized load p = X
/lis:
2 = P(1~PN)
p (lpN+1)
15
At p = 1 the normalized throughput is N/(N+1). Once
again this can be used for calculations when an infinite
queue is used. Figures 2.3 and 2.4 show these
approximations.
PN = 0.1666 N = 5
Figure 2.3. Blocking Probability
y/\L = 0.8333 N = 5
Y/i
Figure 2.4. Throughputload Characteristic
16
The throughput of a queue is dependent on the number
of packets in the queue. This was shown in the
determination of equation 2.9 since the probability of
blocking increases as the number of packets in a queue
increases. The mean number of packets in a queue, or
mean queue occupancy, is also directly related to the
wait time for a packet to be serviced. The infinite
buffer is more convenient to use in the uncongested
region (p < 1) to determine the average number of packets
in a queue. Using the discrete formula for a mean:
E[n]
XnPn = Â£n(lp)pn
CO oo
= X npn X nPn+1
n=l n=l
= Xpn = p/(lp> 2.11
n=l
The average time delay is proportional to the
number of packets in the queue. If the number of packets
that are in line for service increases, the time for a
single packet to be served also increase. The average
time delay can be calculated by using Little's formula 2.
E[n] = Ae [T] E[T] mean time delay.
17
E[T]
2.12
E fn] 1/1
X (1p)
E [T] = 1/JLL pl
For a single server, the relation between the average
wait time E[W] and the average delay through the queue
is:
E[T] = E[W] + l/i
Therefore, the average number of customers E[q] waiting
only in the queue is:
E[q] = Ae [W] = XE[T] X/\l = E[n] p
The previous results show that there is a tradeoff in
the queue's performance. As the load increases, the
throughput increases. However, more packets are blocked
and the average number of packets in the queue increases
rapidly, which increases time delay. If a system is
being modeled it is therefore important to keep in mind
the load that will be applied to that system in order to
fully understand the performance characteristics that are
expected.
2.5 State Dependent Queues
State Dependent Queues, also known as BirthDeath
Processes, are single queue systems in which arrival and
18
departure rates are dependent on the system's state. A
"Birth", one arrival or no arrivals in (t,t+At), is A^At
+ o(At), or (1A^At) + o(At) respectively. A "Death",
one departure or no departures in (t,t+At), is inAt +
o(At), or (l~nnAt) + o(At) respectively. So the
equilibrium equation for this queue is:
(X,n + Hn) pn = ^nlPnl + Mn+lPn+1
Solving the equilibrium equation in the same manner as
the balance equation:
^nPn = l^n+lPn+1
This solution differs from the stateindependent
queue in the state dependent arrival and service rates.
If the solution is again carried to n states the
probability pn is:
Pn
Po
n **
i=0
n >*i
i=0
2.13
This result can be altered to include other queueing
systems, such as the M/M/2 system. This system has two
identical servers, each with the same probability of
receiving a client. The probability of either server
completing service in the interval (t+At) is lAt. The
19
probability of one completion in the same interval is
2iAt. This system is exactly a "BirthDeath" Process
with the following constants:
In =X  independent of n.
Mn M' n=l.
ln = 2\i  n>=2.
Pn nl [1
Po l2pj W
= 2pn
n>=l
p = X / 2\l
oo
With an infinite queue ^ pn = 1 :
p0 = (lp)/(l+p)
Pn =
2 (1p)
(1+p)
Pn
E[n]
2P
(1p2)
E[T]
1
l(lp2)
0
[A.3.1]
n >= 1
p = X / 2p 2.14
[A.3.2]
E[T] average time delay
E2[T] < EJT]
1
P < 1p)
The mean time delay for the two server case is of course
less than the single server, however it does not differ
by 1/2. The M/M/2 queue instead differs by the square of
the utilization. This is caused by the fact that the
service time is doubled instead of the mean queue
20
occupancy being halved. The average throughput of the 2
server case is not 2(1 because for p0 the queue is empty
and for px only one server is being used, therefore the
throughput is:
Y = HPi + 2(1 (lp0_Pl)
For the infinite M/M/2 queue with no blocking, this
should be the average arrival rate of load A, [A. 3.3].
The performance characteristic, 1E[T], measures the
normalized number of packets waiting in the system. For
the M/M/2 queue, the performance characteristic is
significantly better than that of the M/M/l queue and
approaches that of the M/M/l queue with twice the service
rate as seen in Figure 2.5.
1E[T]
21
If a server has a fixed maximum service time, a queueing
system with two servers can approximate a server with
twice the speed.
The next example is that of the M/M/<*> where every
customer is serviced. The probability of n packets can
be easily found from equation 2.13:
Pn = q/)l)n
PO n!
PO = e_P
The probability of n packets in a queue is therefore
given by the Poisson distribution.
(X.T) ne~^T
pn n!
Since the model has an infinite number of servers the
mean time delay is the average service time with a wait
time of zero. The throughput is the arrival rate since
the probability of blocking is also zero.
E[T] = 1/n
y = X
The third example is "queue with discouragement".
This models a system with customer flow control at the
input. The arrival rate is normalized by the state of
22
the queue, since flow will decreased as the state
increases.
(n+1)
Pn = P
Pn = (X / p)n
PO n!
PO = e_P
E[n] = p = X / \l
The throughput is found by averaging the arrival rate
over all states.
Y = H(leP) p = (X / p)
The throughput is therefore an exponential rise from zero
to the average service time as the utilization increases
from zero.
E[T]
____e____
P (lep)
The mean time delay is therefore utilization normalized
by the throughput.
The fourth example is a special case of the M/M/
queue with a finite number of servers and no waiting
23
room, usually referred to as an M/M/N/N or a pure loss
system.
n
rO
*
Figure 2.6. M/M/N/N Queueing System
The service rate is a function of the number of packets
being serviced. The arrival rate is a constant, however,
all arrivals will be blocked at n = N.
Mn =
= A,
Again using equation 2.13 pn can be found:
Pn =
Po n!
1
PO = "i
1 PVI!
1=0
pn/n!
Pn = n
I pVl!
1=0
24
Blocking occurs at n = N so if N is substituted in the
previous expression
_ Pn/NI
~ N
X PVl!
1=0
The mean queue occupancy is therefore the product of the
utilization and the probability of the queue not being
full.
E[n] = p(lPN) [A.3.4]
y = X(1PN) = fiE [n]
The throughput is the average over the state dependent
service rate at the system's output. As the traffic
builds up, the throughput approaches its maximum value of
Ni. This corresponds to the case where p = (^ / l) N.
Since most arriving customers are being blocked, the
probability of blocking approaches 1. The average delay
is then 1/p, the holding or service time.
2.5 M/G/l Queue
In the previous section, the M/M/l queue was
discussed with both a finite and an infinite buffer size.
The "BirthDeath" process was also discussed. While
25
these basic models are useful and are very often used (as
seen in the brief examples given), they rely on the fact
that both the arrival process and the service
distribution are Markov processes. This section will
discuss the case of general service time distribution.
The general distribution may have an arbitrary but known
packet length and service distribution. The model is
assumed to be a single server infinite queue with Poisson
arrivals. The most important aspects of a queueing
system are the mean queue occupancy and the average time
delay through the system. These two values are defined
by the following expressions:
E[n]
E[T]
_2_
UPJ
[lf(lp2o2) ]
E rn]
X
1 / M
UPJ
[lf (lli2a2) ]
2.15
2.16
a2 the variance of the servicetime distribution.
These two expressions are called the PollaczekKhinchine
formulas 3. The leading terms of these two equations are
the same as those of the M/M/l queue. The variance of an
exponential distribution is then a2 = l/l2. The result
for an exponential distribution is exactly that described
in the M/M/l model. If G2 > l/l2 both E[T] and E[n]
26
increase, however, if c2 < 1/I2 then E[n] and E[T]
decrease relative to the M/M/l result.
For a special case of this model, let all packets
have the same service length 1/(0., so for o2 = 0
E[n]
_e_
p
Â£
2)
E[T]
'
Â£
2)
This queue is called the M/D/l queue, where the D
represents a deterministic servicetime distribution.
The mean occupancy and time delay for the general
form of the M/G/l queue is dominated by the (1p) of
these equations. This shows that all infinite buffer
queues exhibit the same queuecongestion behavior as p >
1. Those with larger variance in their service
distribution produce larger mean queue occupancy and time
delay. The mean wait time E[W] can be determined by
using equation 2.16 and the relationship of the time
delay and wait time.
E [W] = E[T] 1/(1 2.17
Substituting 2.16 int 2.17 yields:
E [W]
A.E [ X2 ]
2(1p)
2.18
27
where E[T2] is the mean square of the service time.
E[t2] = a2 + l/\i2
The derivation of the mean queue occupancy for the
M/G/l queue differs from that of the M/M/l queue by the
service process. The general service distribution is not
a Markov process, therefore the memoryless property can
not be used. The derivation is shown here in order to
point out a very important intermediate result. The
focus of the derivation is no longer on the state of the
queue as used previously, but upon the change of state at
the end of a service time. A timing diagram, figure 2.7,
shows the relation of the state to arriving packets.
jn:l r 1"
1 r 1 r i
i+1
Jl j j+1
Figure 2.7. Timing Diagram
Time
The customer service time j is known and the arriving
packets during a service time is assumed to be Vj. The
number of packets in the state after service time j is nj
and before the completed service is nj_x. They are
related by:
28
2.19
nj =
Equation 2.19 can be rewritten to incorporate only the
states and change in states.
nj = nj.j^ u(nj_x) + Vj 2.20
u(x) unit step
Let the time approach infinity where the
probabilities are stable. Noting that in a stable state
E[n.j] = Etnj.jJ, the mean number of arrivals in a service
interval j is:
E [v] = E [u (n) ]
o
E [u (n) ] = ^pn = P (n>0) = p
n=l
Therefore p0 = (1 p)
In order to solve for the mean queue occupancy,
square both sides of equation 2.20. Take the mean of
both sides, and assuming Vj and nj^ are independent,
solve for E[nu(n)] = E[n].
2E [nu (n) ] + 2E[v]E[u(n)] = E[u2(n)] + 2E[n]E[v] +
E [ v2 ]
2E[n] (1E [ v] ) = E [v2] 2E [v] 2 + E[v]
E [v] = p
29
E[n]
2.21
_ Â£ + gv2
2 2(1p)
Gv2 = E [v2] E [v] 2
It is important to understand what equation 2.21
represents. The mean queue occupancy is shown as a
function of the utilization, as expected, but also as a
function of the variance of packet arrivals. This result
is very important in queue modeling. It states that for
any queueing model, with the above characteristics and
general service distribution, the mean queue occupancy
can be calculated by using the variance of the packet
arrival process. This also shows that reqardless of the
properties of the arrival function, the queue occupancy
is attainable if the variance is available in either
closed form or as a sample variance for data. This
equation will be used in the following sections to
determine the mean queue occupancy of the G/G/l model.
The variance of the packet arrivals in the case can
be found by determining the mean number of arrivals. Use
the fact that the arrivals are Poisson and the mean is
equal to the variance. Solving for the mean arrivals
leads to the solution:
Gv2 = p + 12<52
30
Substituting this into equation 2.21 yields equation
2.15.
1 M. Schwartz, Telecommunication Networks: Protocols.
Modeling and Analysis. AddisonWesley, 1987, pp 30.
2 Ibid, pp 41.
3 Ibid, pp 57.
31
CHAPTER 3
NONOVERLAPPING PACKET ARRIVALS
3.1 Theory Development
Existing models of queueing systems rely on the
assumption that the packets arrive in a Poisson
distributed pattern and that the departure times are
independent of the arrivals. Since the Poisson arrivals
do not consider the packet length, these models may allow
packets to overlap. In a physical system, providing the
protocol does not allow for collisions, packets do not
overlap. The Poisson based queueing models thus may
overemphasize the number of packets actually in the
queue and may therefore also overestimate the total
system time delay.
The mathematical approach and methodology in the
following sections of this chapter were taken from 4.
Therefore, most of the steps used in the derivations will
not be noted. Direct quotes of significantly large
portions, however, will be referenced.
The packet arrival process can be divided into two
essential parts. These parts are the interarrival
process, the time between packets and its associated
distribution, and the packet lengths with its own
distribution. The arrivals are modeled as a series of
times tlft2,.., with interarrival times T that are
identically independently distributed (i.i.d.). The
arrival process parts are related by T = xp + Tg, where xp
is the packet length and Tg is the random gap between
packets. In order to analyze the properties of packet
arrivals, the following theorem is used.
Theorem: Consider a sequence of arrivals at times
...t0,t1, ... where t0<0 and t1>0. If the
interarrival time % is i.i.d the
probability density of the arrival time tl
is:
ftl(x) = X[lFt(x) ] 3.1
X average arrival rate.
Fx(x) distribution of interarrival
times.
The probability of n packets arriving in the interval
(0,t) is given by:
pn(t) = P{tn <= t, tn+1 > t}
Pn(t) = f J*fn (x) ft (y) dxdy
xt
x > n packets arriving in (0,t)
x+y > n+1 packets arriving in (t,t+T)
33
oo
t
Pntt) = /dx fn(x) J*dy fT(y) 3.2
0 tx
fn(x) is the probability density of tn.
t
Since fn+i(t) = J*fn(x) fT(t_x) dx
0
Differentiating 3.2 leads to the following differential
equation:
dpn(t)
dt = fn(t) fn+l(t) 3.3
Characteristic functions are often used to determine
certain properties of random variables when little is
known. In order to examine these properties, the Laplace
transform is used. Transform equation 3.3 in order to
place the random variable in terms of its characteristic
function.
OO
Pn(s) = / e St pn(t) dt = L{}
0
sPn(s) pn(0) = L{fn(t) L{fn+1(t)}
sPn(s) pn(0) = On(s) On+1(s)
On(s) characteristic function of tn.
pn (0) = 0 n = 1,2,...
P0<0) = 1
Assuming tl and all other arrival times are independent
34
n(s) = 0tl(s)0Tn 1 (s)
X distribution
tl event
sPn(s) = Otl(s) [1Ot(s) ]Otn_1(s)
Oti(s) =[1Ot(s)]
The Laplace domain probability of n events is:
Pn(s) = p[l0T(s) ]20Tn 1(s) 3.4
1 X
P0(s) =  2 [1<>T(S) ] [A.4.1]
^ b
t
pO (t) = (1 A.t)u(t) + XjFT(x)dx 3.5
0
The next step is to develop a general expression for
the average number of packets arriving in the same
interval (0,t). First use the discrete definition of a
mean:
CO
E [n] = Â£ npn (t)
n=l
Use the Laplace transform to put the summation in a known
form.
OO
L{E[n] } = Â£ nPn (s)
n=l
35
L{E[n] }
_ A
s2
E[n] = Xt
The mean square number of packets arriving in (0,t) is:
E
[n2] = Â£ n2pn(t)
n=l
L{E[n2] } = n2pn(s)
n=l
X [1+Ot (s) ]
5  [A.4.2]
s2 [1Ot(s) ]
Taking the inverse transform, using the integral law
t x
E[n2] = A,Jdx Jdy g(y)
o o
g(t) = l
l
[1+$T(S) ]
[!<Â£>; (S) ]
The variance of packet arrivals in (0,t) is:
Cn2(t) = E [n2 ] (fa:)2
Using the initial and final value theorems for Laplace
transforms, the following limit variance values can be
found:
Initial value theorem:
lim f (t) = lim sF(s)
t>0 s>
Evaluating the variance yields an unbounded solution,
so the theorem is applied to the derivative of the
36
variance. The initial value of the derivative is a
constant A,, therefore the initial value of the variance
is :
Gn2 (t) > At
t>0
Final value theorem:
lim f (t) = lim sF(s)
t> s>0
Again the solution is unbounded so the final value
must be applied to the derivative. As in the previous
case this yields a constant value of A3oT2.
an2(t) > At X2gx2
t>
Ot2 variance of inter arrival times
In the case of Poisson arrivals
A2o^2 = 1 on2(t) = At
For nonoverlapping arrivals
A2^2 < 1 on2(t) < At
Therefore, in general, the variance of packets arriving
in an interval (0,t) is smaller than that predicted by
the model of Poisson arrivals.
37
3.2 Variable Length Packets
The inter arrival time random variable x is a function
of the packet length and the gap between packets. In
order to have a direct comparison with the Poisson
models, the packet length and gaps are assumed to have
exponential distributions and are independent. If the
packet length is a random variable xp with a mean Tp, its
exponential distribution is:
Xp1
(x) = ^ exp(Â£;) u (x)
fT(x) =
exp(TÂ§)exp(TÂ§]
TgTp
U(x)
, Tg t Tp
= 7j^ exp(^J u (x) , Tg = Tp
The characteristic function of X = Xp + xg
x(s) = ^Tp (S) ^Xg (S) = (1+STp) (1+STg) 3 6
Substituting equation 3.6 into equation 3.4 gives the
Laplace domain equation for the probability of n packets
arriving at a queue.
Tp+Tg 2
____X____ _____( s + TpTg )______
Pn^S^ (TpTg) n1 (S + 1/Tp) n+1 (S + 1/Tg) n+1
38
Taking the inverse transform using the convolution
integral finds the probability for the time domain.
A r
pn(t) =J f (tx) g(x) dx
(TpTg)n 1 J
3.7
f(t) = L
1
s +
0
Tp+Tq
TpTg
(S + l/Tp)
n+1
f(t) = 1 +
nTg.
n1
(^D i gxp(tf) u(t) [A. 4.3]
g(t) = l
l
s +
Tp+Tq
TpTg
(S+1/Tg)
n+1
g(t) =
nl
l1 + Hi?) (nl) !
Inserting f(t) and g(t) into equation 3.7 obtains the
form for a confluent hypergeometric function integral
solution.
2nl
pn (t) = ^ I exp(t/Tg) { M(n,2n,p) +
(TpTg) n
2^p M(nf2n+l,P) + 2^ M (n+1,2n+l, P) +
TpTg (2n+l) 2n M(n+l,2n+2, p) }
3.8
[A.4.4]
Po (t)
TgTp [T9 exp( Tg]
Tp exp
3.9
39
M(a,b,z) confluent hypergeometric function.
P = ^Tg Tp]
In the special case where the packet length equals
the gap, Tp = Tg, equation 3.8 and 3.9 simplify using
M (a, b, 0) = 1:
Pn(t)
XTp
m2n 1 exp (t/Tp)
iTpJ (2nl) !
1 +
t'
nTP (2n+l) (2n)TP2
Po (t)
As the previous section showed, the variance of
packet arrivals is needed to model the mean queue
occupancy of a given queue. If equation 3.6 is used and
the inverse laplace transform is taken, the closed form
solution of the variance in the time (0,t) becomes:
= A/t
2 2
Tp Tg
(Tp+Tg)
+ 2 ( ArTpTg)
1 exp
t
ArpTg.
[A.4.5]
Figure 3.1 shows the probability of n arrivals into a
queue, given that nonoverlapping packets with
exponentially distributed packet length and gaps arrive
into the queue with a utilization of 50 percent (Tp = Tg)
and an average arrival rate of one per second.
40
Pn(t)
Figure 3.1. Probability of n Arrivals,
Variable.Length Packets
3.3 Fixed Length Packets
The development of the fixed length arrival process
is much the same as the variable length with Tp = Tp. The
gap is again assumed to be exponentially distributed.
The interarrival density is:
fT(x) = ^ exp( u (xTp)
Converting the arrival density into the distribution and
solving equation 3.5 produces the probability of zero
arrivals in the cases of 0 < t < Tp and Tp < t.
Po (t)
l Xt
A/Ig exp (
, 0 < t < Tp
, Tp < t
41
To solve the general expression for the probability
of n arrivals, pn(t), equation 3.4 must be evaluated
using the characteristic equation of the interarrival
time based on a fixed packet length.
T
exp ( sTp)
1 + STg
Pn(t) = A,J*dx Jdy gn(y)
o o
gn(y) = L1[ (1Ot(s) )2Ox(s)n X]
, x _ 1 fy (n1) Tp] n~2 .
Tggn (y) (n2) I Tg J
exp( y Tp)u (y(n1) Tp)
" (n1) [ZTÂ§TE] exp(~ Z7Â§lE)u(ynTp)
+ Â£ [y7(nT+g1)TP']nexp[ y(nT+g1)Tp]u(y(n+l)TP)
/gn(y)dy = p(n_1 ; x (lig1)Tp)u(x (nl)Tp)
0
 2p(n ; ^"Â£]u (x~nTp)
+ p(n+l ; X Tp]u (x(n+1) Tp)
[A.4.6]
P(n,z) incomplete gamma function 5 with properties.
42
P(l,z) = 1 exp(z)
.n
P(n+l,z) = P(n,z) exp(z)
P(n,z) > 1
z>
Integrate over the second variable using:
f P(n,z)dz = aP(n,a) nP(n+l,a)
pn(t) = 7lTg(B (n1) P (n1 ^g1 Tp)) u (t (n1) Tp)
 ?iTg[ (n1) p[n;^ Tp)]u (t (n1) Tp)
 2^Tg[b (n)p[nl;~ ~TgTp] nP (n+1;) u (tnTp)
+ A,Tg(B (n+1) p(n+l;~^g^ Tp>]]u (t (n+1) Tp)
 ^Tg[ (n+1) P [n+2;~ ~ ^g1} Tp)) u (t (n+l)Tp) 3.10
B (x) =
_ t~ (x) Tp
Tg
In the special case of 1 arrival, the probability is:
Pi(t) = Xt 2krg[B(l)P(l,B(0) ) P (2,B(0) ) ]u(tTp)
+ tog[B(2)P(2,B(2) ) 2P (3,B (2) ) ]u (t2TP) 2.11
If the service interval can be assumed to be very
small so that no more than one arrival can occur in time
(0,t), then equation 3.11 can be used to predict the
43
probability of a packet arriving. This is very
beneficial considering the complexity of equation 2.10.
Using the probability of n arrivals, the variance can
be determined by applying following expression:
oo
tfn2(t) = X n2Pn(t) (^t)2
n=l
Figure 3.2 shows the probability of n arrivals into a
queue, given that nonoverlapping packets with fixed
packet lengths and exponentially distributed gaps arrive
into the queue with a utilization of 50 percent (Tp = Tg)
and an average arrival rate of one per second.
Pn(t)
Figure 3.2. Probability of n Arrivals,
Fixed Length Packets
4 Douglas A. Ross, Theory of nonoverlapping packet
arrivalsr Computer Society Press, 1989, pp 242246.
5 M. Abramowitz, I.E. Stegun, Handbook of Mathematical
Functionsf Dover Publications, 1965, pp 262.
44
CHAPTER 4
G/G/l QUEUEING MODEL
The basis for deriving a G/G/l model is to determine
the behavior of a system when the arrival and departure
statistics are considered to be general. General, in
this usage, represents packets and their statistics which
are based on their mean and variance with any associated
distribution. In this chapter, the arrival statistics
are based on those derived for nonoverlapping packets.
The important aspect of the arrival statistics is that
they are based on both the packet length and the gap
between subsequent packets. The distribution of the
packet length and the gap is assumed to be exponential.
Two different arrival patterns will also be considered.
These are the cases of variable and fixed packet lengths.
The departure statistics will be based on those derived
for the M/G/l queue in section 2.5. The most important
parameter of a queue's performance is the mean queue
occupancy. This directly affects the service
distribution time and the system wait time. The general
expression for E[n] is:
E[n]
4.1
2 + 2 (1p)
on2 variance of packet arrivals.
p utilization.
Equation 4.1 was derived in section 2.5. It was
shown that for any arrival process, if the service time
was considered general, the mean queue occupancy was a
function of the arrival variance and the utilization.
The mean queue occupancy of a G/G/l queue can be found if
the variance and utilization are determined. The
variance of the variable and fixed length packet arrivals
were derived in Chapter 3.
4.1 Variable Length Packet Model
The variance of the variable length packet arrivals
is:
Gn2 = Xt
2 2
Tp Ter
.(Tp+Tg) .
+ 2 ( ArTpTg)
1 exp
t
A,TpTg
4.2
The mean queue occupancy is found when equation 4.2
is substituted into 4.1.
E [n] = Â§ +
^,t
2 2
Tp Tg
,(Tp+Tg) ,
2(1p)
2 ( A,2 TpTg)
2(1p)
1 exp
^TpTg,
4.3
46
In order to simplify this expression to obtain a
comparison with the M/M/l and M/G/l models, certain
assumptions and substitutions will be made. The average
service time is Tp (average packet length) This can be
seen if the servers are assumed to be incoming packet
distributors. The service time is then the time needed
to read in a complete packet. The utilization is the
ratio of the arrival time to the service rate. Since Tp
is the average service time, 1/Tp is the average service
rate. The utilization p is then A/rp. The average time
between arrivals is the sum of the packet length and gap
(Tp + Tg). The average arrival rate is the inverse of the
average arrival time and therefore is X = 1/ (Tp + Tg) .
The A,Tg term is thus 1p. The variance of arrivals in an
average service time Tp then becomes:
n2 = P (Tp2 + Tg)z = P[p2 + (1"P)2] 44
Recalling the final value theorem application in
chapter 3 for the derivation of the variance, as the time
approaches infinity the variance approaches Xt X2oxz.
Since the packet lengths and gap size are both
exponential the variance of T = Tp + Tg is Tp2 + Tg2.
Substituting equation 4.4 into 4.1 gives the mean queue
47
occupancy for the G/G/l model using nonoverlapping
packet arrivals with variable packet lengths.
E[n] = Â§ + f (1p) + ^1 4.5
In comparison, the mean queue occupancy for the M/M/l
model is:
E [n]
Â£ + 2
2 2(1p)
Figure 4.1 shows the comparison.
E[n]
Figure 4.1. Mean Queue Occupancy,
Variable Length Packets
Figure 4.1 shows that at high utilization the
variable length packet model approaches that of the
Poisson model. At high utilization the gaps between
packets shrink to zero, however, the packet sizes still
48
vary. Since the packet lengths are considered to be
exponentially distributed, this model is actually the
Poisson model providing the gap lengths are approximately
zero. This model as well as the Poisson model is not a
very realistic model at high utilization unless the
traffic rate that produces it is very unlikely. If a
communication or computer network ran at this rate the
packets would be designed to be fixed length. The
reasons for this will be shown in the next section.
In addition to the variance and mean queue occupancy,
the average time delay through the system demonstrates
the queues performance.
E[T]
E[n1
X
(Tp + Tg)
Â£
2
f dp)
+
2(lp)J
4.6
The average wait time E[W] is related to the mean time
delay by the following expression:
E [W] = E[T]  = (Tp + Tg)
M'
2 + 2(1~P> +
2(1p)
 Tp
4.7
This equation is only valid providing that the gap
size is larger than the packet length and a non zero
utilization. In most physical system, this requirement
is realistic.
49
Fixed Length Packet Model
The variance of the fixed length packet model using
the same substitutions as in the previous model yields an
even further simplified expression.
Further simplifying gives the variance as only a function
of the utilization.
Substituting equation 4.9 into equation 4.1 gives the
expression for the mean queue occupancy for non
overlapping packet arrivals with fixed length packets.
Figure 4.2 shows that at high utilization the mean
number of packets in the queue is 0.5. Physically this
means that as one packet leaves the queue another is
entering. At high utilization the packet arrivals is a
continuous process. Provided the server has no delay
between server functions, this becomes a very predictable
and accurate model. Delay is caused when a single server
4.8
an2 = p(lp)2
4.9
E[n] = f + \ (1P)
4.10
50
must service several communication ports at the same
time. If a single server is dedicated to one port, as is
most often the case, then no delay will occur. This
means that as soon as a packet is serviced another will
be read in from the same queue. Therefore most
commercial systems use fixed length packets in order to
achieve the lowest possible mean queue occupancy.
E[n]
Figure 4.2. Mean Queue Occupancy,
Fixed Length Packets
The average time delay and wait time are then
expressed by:
E [T] = = (Tp + Tg)
Â£ + f (1P)
12
E [W] = E [T]  = (Tp + Tg)
2
.2 + 2 (1P}
 Tp
51
The same limitation as in the variable length model
applies to the fixed length when modeling the wait time.
A comparison of the average time delay can give more
insight into the performance of a queueing model and its
relationship to physical systems.
E[T]
Figure 4.3. Average Time Delay
The average time delays are based on a constant
service time of 1 /\l. In order to realistically compare
the time delays of different models, a constant service
time equal to the average arrival time of 1/1 = Tp was
chosen. The plot of the M/M/l queue shows the expected
behavior of rapidly becoming unbounded. This M/G/l queue
is some times referred to as an M/D/l queue due to the
deterministic nature of service process. This queue
52
model is said to have "...the smallest possible queue
occupancy and delay" 6. This may be true of traditional
queueing models, however, figure 4.3 shows that either
G/G/l model has better results. The variable packet
length model again shows the behavior of the M/M/l queue
at high utilization but a slower rise in time delay.
This model, however, does degrade quicker at high p than
the M/G/l model. This result is caused by the variance
in the packet length. As the utilization increases the
packet length has a greater effect on the arrival time as
well as the service time. The packet length actually
becomes the arrival time and therefore the service time.
This again models the M/M/l queue. The G/G/l Model, then
crosses over the M/G/l queue because the service time
becomes exponential rather than deterministic as in the
M/D/l. At small utilization, however, the G/G/l variable
length packets is more reliable than the M/G/l model.
The fixed packet length model display a very unique
property. As the utilization increases the time delay
levels to a fixed time. This result will be further
explored in chapter 5 by measuring an actual computer
message buffering system. In either G/G/l queueing model
a large increase in performance is seen at lower
utilization. This makes the G/G/l queueing model very
53
attractive regardless of the packet traffic for a given
network.
6 M. Schwartz, Telecommunication Networks: Protocols,
Modeling and Analysis. AddisonWesley, 1987, pp 57.
54
CHAPTER 5
G/G/l/N QUEUEING SIMULATION
All physical message buffering systems are of finite
length. They also rely on fixed packet lengths for speed
of processing and network efficiency. While different
sizes of message information may be sent the carrier
packet length is fixed. Packets on a network are usually
processed by a main cpu and then distributed. Different
servers are used depending on their function in the
network. Some servers simply read in packets and send
them to the appropriate process while others process the
network instructions which are present in the packets.
Therefore two separate server models can be used. The
first is a fixed time server which is used to read in
data and pass it to other systems. The second is a
random time server that deals with the network
instructions. In order to obtain comparable results, the
service time and gaps between arriving packets will be
modeled as variable with means 1/1 and Tg respectively
and each having an exponential distribution.
As was shown earlier the G/G/l model equation for
mean queue occupancy is a function of the utilization and
variance of arrivals only. For a finite queue the
normalization of the probabilities is calculated over a
fixed length N. This normalization will effect the
probability of state zero only, and is used to calculate
the probability of blocking at a given utilization. The
probability of blocking can be calculated by truncating
the infinite queue model at n = N, if the queue is
significantly large. The requirement is that pN 1.
While complete modeling of physical systems is important,
the only measurable parameters are the average time delay
and the average wait time. The G/G/l/N model has the
exact equations for these two parameters as the G/G/l
model.
E[n]
2(1p)
an2 = ?it X2gt2
5.1
5.2
Since the variance of the packet arrivals approaches
equation 5.2 asymptotically it can be used as a
conservative value.
(y 2 (y 2i (t 2
The variance of the packet length is zero since it is a
constant, therefore the variance of the packet arrivals
can be simplified to:
56
Cn2 = A,t A,2Tg2
If an ethernet is considered to be a normal network, then
a data rate of approximately 10 Mbits per second is
typical. An NFS packet is 1024 bytes long and therefore
the packet length in time is 800 (isec. Since most
machine internal clocks can only measure time to 10 msec,
this length is essentially zero. In this case the packet
length can be considered as the average service time
instead of the packet length transmission time. This is
done by considering that there is no difference to the
queue if the service time is spent reading in a packet or
servicing it some other way. The mean queue occupancy
can then be modeled exactly the same as in chapter 4.
E[n]
+
fapi
5.3
Since the utilization is equal to the arrival rate
multiplied by the average service time, the time delay is
simply the mean queue occupancy multiplied by the service
time normalized by the utilization.
E [T]
5.4
1 Tp
X p
57
If p <= 1, the maximum probability of blocking occurs
at p = 1. Therefore for calculation purposes the
simplification from chapter 2 can be used to calculate
the probability of blocking.
p _1_
 n+1
5.1 Ethernet Network Simulation
The simulation was implemented using an ethernet with
NFS as the server. The network is connected to multiple
Sun 4 330 machines and a Sequent parallel processor.
Communication was established between two processes on
the net using Berkley sockets implemented using TCP/IP
protocols on the system level and IEEE 802.3 packet level
protocols. 802.3 has collision detection and is
therefore an appropriate protocol to use when modeling
nonoverlapping queueing models. The communication
sockets can be established using two different protocols
for transmission. These two are either blocking or non
blocking sockets. The blocking sockets will wait on a
write to the message buffer until the queue is no longer
full. The nonblocking socket returns a system signal
when the queue is full and then allows for retransmission
of the data. Blocking sockets are used in this
58
simulation in order to get a true measure of the time
delay. The arrival and service processes use the
resident random number generator on the Sun 4 330
machines to model the random distributions. Since the
random number generator simulates uniformly distributed
numbers the values were mapped to be exponentially
distributed. The simulation was run during normal
operation of the network and therefore exhibits the
stochastic behavior that is expected. Figure 5.1 is a
comparison of the actual data, the G/G/l model and the
M/G/l model at a utilization range of 0 to 1.
E[T]
P
Figure 5.1. Average Time Delay
for Network Simulation (100 msec)
59
The average service time was chosen to be 100 msec.
Since the average time delay is a function of only the
service time and utilization, the result is easily
checked. The average wait time is not graphed here since
it is only a constant shift and would therefore yield the
same results. Figure 5.2 ran with an average service
time of 200 msec. The time delay was averaged over 2000
packets for both figure 5.1 and 5.2.
E[T]
Figure 5.2. Average Time Delay
for Network Simulation (200 msec)
Both Simulations and models show the same downward
trend. This trend is caused by the fact that the mean
time delay is inversely proportional to the arrival rate.
As the arrival rate increases, the utilization increases.
The factor of (1p) decreases as well as 1/X and
60
therefore the mean time delay decreases. The model
predicts the physical system well in this case since the
server and queue can handle the faster arrival rate
without approaching the queue occupancy.
61
CHAPTER 6
DISCUSSION AND CONCLUSION
Existing queueing models such as the M/M/l model
described in chapter 2 do not take into account certain
physical characteristics of a communication network.
Among these characteristics is the fact that network
protocols do not allow packets to overlap. Another
aspect of physical systems is that the arrival process
must not only consider the time between packet arrivals
but the packet lengths as well. When the arrival process
is assumed to be Poisson, the packets can theoretically
overlap. This can lead to an overemphasized variance of
packet arrivals as well as an unrealistic behavior of the
mean queue occupancy at high utilization. If the service
time is considered to be general, as in the M/G/l model,
a simplified expression of the mean queue occupancy can
be used. This expression, derived in section 2.5, is a
function only of the system utilization and the variance
of the packet arrivals. Therefore, in order to develop a
model based on nonoverlapping packet arrivals, the
variance of the arrivals over a given time interval must
be determined.
During the development of the nonoverlapping packet
arrival process in chapter 3, it was advantageous to
transform the properties into the Laplace domain. This
transformation lead to a unique solution to the
probability of arrivals using the average arrival rate
and the characteristic function that describes the random
variable. Using this solution it becomes possible to
solve for the probabilities of arrival for any process
that has reasonably defined statistics. Another very
important result can be obtained by taking advantage of
the Initial and Final Value theorems of the Laplace
transform. This result is the asymptotic limits of the
variance for the packet arrival process. It was shown
that the variance of the Poisson arrivals is ^t while the
variance of other processes is Xt A,2at2 which is less than
that of the Poisson arrivals. The probability of
arrivals in a service interval was then developed based
on both the variable and fixed length packet
possibilities given an exponential distribution of packet
size and separation gaps. The fixed length packet
arrival probability can be further simplified if the
service time is assumed small enough to allow only one
arrival.
Once the arrival probabilities, including the
variance, was developed a queueing model could then be
63
developed. Chapter 4 developed the G/G/l model for both
packet cases based on the mean queue occupancy result for
the M/G/l model. The variable and fixed packet length
G/G/l models were compared to the M/M/l and M/G/l models.
The variable length model shows lower queue occupancy
than the models developed in chapter 2 at low
utilization, however at high utilization it becomes the
Poisson model. At high utilization this characteristic
is caused by the gaps shrinking to zero and therefore the
exponentially distributed packets fully describe the
arrival process. The fixed length packet model, however,
yields a completely different result. As the utilization
approaches one the mean queue occupancy approaches one
half. This is seen as one packet entering the queue as
one leaves. This result is expected if the queue is
large enough and the service process can handle the
increase in arrival rate.
All physical systems are of finite size and most use
fixed length packets for data transmission. The reason
for this was shown in chapter 4. In a commercial
networking system the most important parameters of
queueing performance are the probability of blocking and
the average time delay through the system. Chapter 5
develops the G/G/l/N finite queueing model based on
certain physical network characteristics. In a network
64
such as ethernet, where coaxial cable is used, the actual
transmission time of the packet becomes negligible. The
packet length can then be assumed to be the same as the
average service time. Since the average time delay is
measured through the entire system, the average service
time is the time for a packet to be read in from the
queue and transmitted through the service process. When
this assumption is made the mean queue occupancy
expression can be simplified to a function of only the
utilization. The mean time delay is then a function of
the utilization and the average service time. The mean
time delay is modeled to decrease from the service time
to one half the service time as the utilization
approaches one. A simulation was ran on an ethernet
network to measure the mean time delay as a function of
the utilization and average service time. The results
were nearly identical to the predicted model with a
slight stochastic behavior caused by other network
traffic.
The use of an infinite queueing model to predict the
performance of a finite queue is very beneficial. Not
only is the infinite model easier mathematically but it
allows for further simplification of complex concepts.
This simplification is valid if the utilization is not
allowed to exceed one and that the utilization raised to
65
the power of the queue size is much less than one. If
this requirement is met, the probability of blocking is
easily calculated. Since the maximum probability of
blocking occurs at the utilization equal to one, the
Poisson model calculation described in chapter 2 can be
used.
The G/G/l queueing model is thus shown to be a very
good queueing model for a physical network when fixed
packet sizes are used. Since an infinite model can also
be used the calculation of important queueing parameters
becomes less cumbersome than in other models. Fixed
packet protocols are therefore designed to incorporate
the idea of nonoverlapping packet arrival process in
order to obtain lower blocking probabilities and average
time delay.
66
APPENDIX A
A. 1 Mean and Variance of a Poisson
Distributed Random Variable
A.1.1 Mean
E[k] = X kP(k) = A,T
k=0
X
k(AT) e
k!
k=0
Let a = ^,T
X
k=0
i / k a
k (a) e
k!
= 1
a
e =
X
k=0
k (a)
k!
r >
oo
* Jf(x)dx = 1
>. oo
Differentiate with respect to a
a
e
V Mai*"1
Zf k!
1 k(a)k
a k!
k=0
k=0
CO
, k a
k (a) e
k!
k=0
a
A.1,2 Variance
Gy.2 = E [k2]  E [k]2 = A,T
Proceed as above but take the second derivative
oo a \' k (k1) ak 2 e Za k! OO 1 V (k2k) ak a2 k!
k=0 k=0
oo a 1 V1 k2ak e a2 Za k! OO 1 "V kak a2 Zrf k!
k=0 k=0
OO V1 2 k a 2 X k a e a Zu k! OO v k a \ ka e Z^ k!
k=0 k=0
E [k] 2 = E [k2] E [k]
E [k] = E [k2] E [k] 2 = a
68
A,2 Exponential distribution
Consider a time diagram:
+
x is the time of first arrival, therefore no arrivals
will occur from 0x if x > x.
p(x>x) = p (arrivals in 0x) = 0
(A,T) e_^T
P() = o! = e
p (x <= x) = 1 e = Ft(x)
dF^(X) .JLI
ft(x) =
dx
= Ae"
A.3 StateDependent Queue Parameters
A.3.1 Probability of State for M/M/2
Â£Pn = 1
n=0
P0 + Â£Pn = 1
n=l
69
Pn = 2pnp0
Po + Po2 Â£pn = 1
n=l
Po
1 +
JR.
ipj
= 1
Po
Pn
izÂ£
1+P
2pnP0
2(1P) n
(1+p) P
A.3.2 Mean Queue Occupancy for M/M/2
E[n] =
Z nPn
n=0
I
n=0
n2(l~p) n
d+p) P
2(l~p)
(1+P} nto
Z nPn
X (n) = Z Pn
n=0
dX (n)
dp
(1p)
12 = p^111 = I npn
UP)2 dP nt0
2p
E[n] = *2
1P
70
A.3.3 Throughput for M/M/2
= fi.2 (1p) p
1 1+P
2(1
1P 2 (lp)p
1+P 1+P .
X(lp)
1+p
+ 2(1
r
2SL
U+pJ
p =
X.+pA. ^
l+P
A.3.4 Mean Queue Occupancy M/M/N/N
N i w
E[n] = ^ npn = jj E pn/(nl)!
n=0 Â£ pl/1! n=0
1=0
I
_e____
p1/!!
1=0
N1
X Pn/n!
n=0
____B____
N
X P1/!!
1=0
' N
X pn/n!
.n=0
pN/N!
E [n] = [1 PN]
A.4 NonOverlappina Packet arrivals
A.4.T Zero Probability of Arrivals
X Pn(t) = 1
n=0
71
c^l CO
( 1 <&j(s)) 2 Â£ 0Tn 1 (S) + Pq (S) = J
n=l
n=l
1
1 T(s)
Po(s)
1.
s
s2 ^
1 Ot(s))
t(s)  < 1
A.4.2 Mean Square Value
E[n2] = ^n2pn(t)
n=l
L{E[n] } = Â£n2Pn(s)
n=l
A, _ v 2 V1 2 n1 .
^2 ( 1 0<((S) ) 2wn (S)
n=l
E2. n1 v
n Ot (s)
n=l
?
^n
n=l
_______1________
[1 0>T(s) ]2
Take the derivative of both sides.
72
v 2_ n2, 2jn (S)  2 (s)
n=l n=l
OO CO
v 2a n1 , 2^n (S)  ^n<_1(s) :
n=l n=l
OO V 2, n1 4 > n (s) 20^(s) 3
n=l [1 Ot(s) ]
1 + T(s)
[1 T(s) ]
L{E[n2]} = A [1 Ot(s) ]2 
[1 +
s2 [1 Ot(s)]
[1 T(s) ]
20>t(s)
[1
+
1 + Ot(s)
[1 " <&r(S) ]
A.4.3 Inverse Laplace Transform for Variable Length
Packet
f(t) = L
l
Tp+Tg
& f TpTg
' 11 n+1
.s TpJ
= L
1
f 11 n+l + f 1 "I n+1 + f 11 n+1
[s + ^pj Ms + TpJ TPls + TpJ
73
= L
1
.(S + Tp] T^(S + Tp)
n+1
1
1
n
l(s + a)
=>
^nl at
t e
(n1)!
f(t) =
nl t 1 n t
t exp (ip) ig t exp ( ip)
^TTi u(fc) +  u(t)
(nl)
L 11 t"1 f t ]
1 + nTg. (nl) ! exp[TpJ
u (t)
A.4.4 Confluent Hypergeometric Function
Pn(t)
X
(TpTg)n 1
exp
J((i
+
x
nTp.
(tx)
nl
nl
x
exp 
f 11
iTp TgJ
dx
Substitute x =
Pn(t)
X
(TgTp)
nl
yt, dx = tdy;
exP (Tp] 2nl
2 t
[ (nl) ]
J
1
t(ly)
nTg
+
nTp
+
t2 (1v) y~
n2TpTg .
(ly)
nl nl
y
exp (yt (iAf)) dy
74
Pn(t)
exp
(Â£)
2nl
(TgTp)
n1
[(n1)!]
J
1 +
tflzY+JL
nl Tp +Tg.
:J + n2
y(1~v)
TpTg
n1 n1
(ly) y
exp(yt(^^))dy
Let P =
This integral fits the confluent hypergeometric function
integral form where M(a,b,z) is defined as:
M (a, b, z) =
r (b)
r (ba) r (a)
I
zt a1
e t
(1+t)
ba1
dt
First term: Second term
CO. ii n z = P
a = n a = n
b = 2n b = 2n+l
f t)
X exP l_TgJ
t'n (L) n1 , , 2
(TpTg) [ (n1) ]
Third term Fourth term
z = P z = P
a = n+1 a = n+1
b = 2n+l b = 2n+2
1
r (n1) M2
(2nl)!
M(n,2n,P) +
t f (n1) 11 2
Tp(2n) !
M (n, 2n+l
P)
tr (n1) 1 2
Tg (2n) !
M (n+1, 2n+l,P)
+
t2r(n1)!12
TpTg (2n+l) !
M(n+1,2n+2,P)
75
1
(2nl) yields the
2
Dividing out [(n1)!] and factoring
the final result.
A.4.5 Variance of Variable Length Packet Arrivals
t x
E [n2] = ?ijdxjdy g(y)
0 0
g(t) = l
1 + PT(s) 1
1 Ot(s)
t
g(t) = l
l
l +
2/TpTq
(S+^)
l =
Tp+Tg
x
Jg(t)dt = u(x) + 2Xj
1 exp
t '
X,TpTg.
dt
1 2X2TpTg + 2A,x + 2A,2TpTg
r r
exp
x
^TpTg.
76
E[n2]
t
Tp2+Tq2
(Tp+Tg)2
+ 2Xx + 2X2TpTg
' r x "i'll
exp . ATpTgJ J
dx
A/t
Tp2+Tq2
(Tp+Tg)2
+ ?l2t2 + 2^4Tp2Tg2
1 exp
^TpTg.
an2 = E [n2] (kt)2
A.4.6 Fixed Length Packet Arrivals
gn(y) = L
1
exp (s [n1 ] Tp) 2exp (snTp) exp (s [n+1 ] Tp)'
nl 1 nl n , 1 n + n+1 1 n+1
Tg (S+Tg) Tg (S+ifg) Tg (S+^)
1
exp (s [nl ] Tp)'
nl . 1 nl
Tg (S+^)
=> e bSf(s)
b = [nl]Tp
f(s) =
(s+4)"'1
Tgn (t) = (n^) i
Divide through by Tg112:
Tgf(t) = (n2) ^ CJTg1]TP) exP
exp(t TP']u (t [nl] Tp)
(~t [nTg1]~Â£)u (t~ [nl] Tp)
Repeat steps for n and n+1.
77
Incomplete gamma function P(a,x):
P (a,x)
1
r (a)
al
dt
Ha) = (al) !
Term 1
Term 2
Term 3
a n1
a = n
a = n+l
t
y(n1)Tp
Tg
t
ynTp
Tg
y (n+l) Tp
Tg
78
APPENDIX B
Computer Programs
B. 1 Probability of Blocking
/* Probability of blocking in the M/M/l/N queue
finclude
finclude
#include
#define QUEUE_SIZE 5.0
double Prob[201];
FILE *fp;
main ()
{
int Gd, Gm;
fp = fopen("block.dat","w");
getProbBlocking();
Gd = DETECT;
initgraph(&Gd,&Gm,"");
drawplot();
closegraph();
}
getProbBlocking()
{
int n;
double rho;
double power,power2;
for (n=l; n <= 200 ; n++) {
rho = (double)n 0.021;
power = exp(log(rho)*QUEUE_SIZE);
power2 = exp(log(rho)*(QUEUE_SIZE+1));
Prob[n] = (1.0rho)*power/(1.0power2);
fprintf(fp,"%lf %lf\n",rho,Prob[n]);
}
}
drawplot ()
{
int i;
int rho;
char ret;
moveto(0,300) ;
linerel(200,0) ;
moveto(0,300) ;
linerel (0,100);
moveto(0,300);
for (i=l; i <= 200; i++) {
rho = (int) (i*1.05);
lineto(rho,(300(int)(Prob[i]*100.0)));
}
scant("%c",&ret);
}
B.2 ThroughputLoad Characteristic
/* Normalized Throughput in the M/M/l/N queue */
finclude
#include
finclude
#define QUEUE_SIZE 5.0
double Through[201];
FILE *fp;
main ()
{
int Gd, Gm;
fp = fopen("block.dat","w");
getThroughput();
Gd = DETECT;
initgraph(&Gd,&Gm,"");
drawplot () ;
closegraph () ;
}
80
getThroughPut()
{
int re
double rho;
double power,power2;
for (n=l; n <= 200 ; n++) {
rho = (double)n 0.021;
power = exp(log(rho)*QUEUE_SIZE);
power2 = exp(log(rho)*(QUEUE_SIZE+1));
Through[n] = rho*(1.0power)/(1.0power2);
fprintf(fp,"%lf %lf\n",rho,Through[n]);
}
}
drawplot()
{
int i ;
int rho;
char ret;
moveto(0,300);
linerel(200,0);
moveto(0,300);
linerel(0,100);
moveto(0,300);
for (i=l; i <= 200; i++) {
rho = (int) (i*1.05);
lineto(rho, (300 (int) (Through[i]*100.0)));
}
scanf("%c",&ret);
}
B.3 Performance Characteristics
/* Performance Characteristics */
#include
#include
finclude
double PI [158];
double P2[126];
double P3[162];
81
FILE *fp;
void getPerformance();
int Gd, Gm;
main ()
{
fp = fopen("perf.txt","w");
getPerformance();
drawplot();
closegraph () ;
void getPerformance()
{
int n;
double rho;
double power,power2;
for (n=0; n <= 157 ; n++) {
rho = (double)n 0.0051;
PI[n] = 1.0/(1.0rho*rho);
}
for (n=157; n >= 0 ; n) {
rho = (double)n 0.0051;
fprintf(fp,"%lf %lf\n",rho,PI[n]);
}
for (n=0; n <= 125 ; n++) {
rho = (double)n 0.0051;
P2[n] = 1.0/(1.0rho);
fprintf(fp,"%lf %lf\n",rho,P2[n]);
}
for (n=125; n >= 0 ; n) {
rho = (double)n 0.0051;
fprintf(fp,"%lf %lf\n",rho,P2[n]);
}
for (n=0; n <= 161 ; n++) {
rho = (double)n 0.0051;
P3[n] = 1.0/(2.0*(1.0rho));
fprintf(fp,"%lf %lf\n",rho,P3[n]);
}
}
drawplot ()
{
int i;
int rho;
char ret;
Gd = DETECT;
82
initgraph(&Gd,&Gm,"");
moveto(0,300);
for (i=0; i <= 157; i++)
lineto(i, (400(int)
}
moveto(0,300);
for (i=0; i <= 125; i++)
lineto(i, (400(int)
}
moveto(0,350);
for (i=0; i <= 161; i++)
lineto(i, (400(int)
}
scanf("%c",&ret);
{
(PI [i]*100.0)));
{
(P2 [i]*100.0)));
{
(P3 [i]*100.0)));
}
B.4 Probability of Arrivalsr Variable
/* Probability of Arrivals for Variable Length
Packets */
#include
#include
finclude
fdefine Tg .5
Idefine Tp .5
double pn[7] [201];
FILE *fp;
unsigned long factorial();
main ()
{
int Gd, Gm;
fp = fopen("narr.txt","w");
getProbArrivals();
Gd = DETECT;
initgraph(&Gd,&Gm,"");
drawplot();
closegraph () ;
}
getProbArrivals()
{
83
int t;
int c;
double n;
double time;
double power;
double A;
double B;
double fac;
for (t=0; t <= 200 ; t++) {
time = (double)t 0.05 +.00001;
pn[0][t] = (1.0 + time)*exp(2.0*time);
fprintf(fp,"%lf %lf\n",time,pn[0][t]);
}
for (c=l; c<=6; C++){
n = (double)c;
fac = (double)factorial(2*cl);
for (t=0; t <= 200 ; t++) {
time = (double)t*0.05 + .00001;
power = exp(log(2.0*time)*(2.0*nl.0));
A = Tp*power*exp(time/Tp)/fac;
B = 1.0 + time/(n*Tp) +
time*time/((2.0*n+l.0)*(2.0*n)*Tp*Tp);
pn[c][t] = A*B;
fprintf(fp,"%lf %lf\n",time,pn[c][t]);
}
}
}
unsigned long
factorial(val)
int val;
{
unsigned long answer;
for ( answer = 1 ; val > 1 ; val) {
answer *= val;
}
return(answer);
}
drawplot ()
{
int i,j;
char ret;
moveto (0,300);
linerel (200, 0);
moveto(0,300);
linerel(0,100);
84
moveto(0,300);
for(j=0; j<= 6; j++){
for (i=0; i <= 200; i++) {
lineto (i*2, (300(int) (pn[j] [i]*200.0)));
}
moveto(0,300);
}
scanf("%c",&ret);
}
B.5 Probability of Arrivals, Fixed
/* Probability of Arrivals for Fixed Length Packets
*/
#include
#include
#include
double Tp=0.5;
double Tg=0.5;
double pn[7] [101];
FILE *fp;
unsigned long factorial();
double pow();
main()
{
int Gd, Gm;
fp = fopen("nprob2.dat","w");
getProbArr();
Gd = DETECT;
initgraph(&Gd,&Gm,"");
drawplot () ;
closegraph () ;
}
getProbArr()
{
int t;
int c ;
double n;
double time;
double power;
double fac;
double PI [8] [101];
85
double P2 [8] [101];
double P3 [8] [101];
double zl[6][101];
double z2[6][101];
double z3[6] [101];
for (c = 0; c<= 5; C++)
for(t=0;t<=100;t++) {
pn[c][t] = 0.0;
PI[c][t] = 0.0;
P2[c][t] = 0.0;
P3[c][t] 0.0;
zl[c][t] = 0.0;
z2 [c] [t] = 0.0;
z3[c][t] = 0.0;
}
for (t=0; t <= 100 ; t++) {
time = (double)t 0.1 + .00001;
if (time <= Tp)
pn[0][t] = 1.0 time;
else
pn[0][t] = Tg*exp((timeTp)/Tg);
}
for (t=0; t <= 100 ; t++) {
time = (double)t 0.1 + 0.00001;
pn[1][t] = time;
if (time > Tp) {
z2[l][t] = (time Tp)/Tg;
P2[l][t] = 1.0 exp( z2[1] [t]);
P2[2] [t] = P2 [ 1 ] [t] z2[l] [t]*
exp(z2 [1] [t]);
pn [ 1 ] [ t ] = 2.0*Tg*(z2[l] [t]*P2[l] [t]
P2[2] [t]);
}
if
}
(time > 2.0*Tp) {
z3[l][t] = (time 2.0*Tp)/Tg;
P3[l][t] = 1.0 exp (z3 [1] [t]) ;
P3 [2 ] [t] = P3 [1] [t] z3 [ 1 ] [t]*
exp (z3 [1] [t]);
P3[3] [t] = P3[2] [t] z3 [ 1] [t]*
z3 [1] [t]*exp(z3[l] [t] ) /2.0
pn[1] [t] += Tg*(z3[1] [t]*P3[2] [t] 
2.0*P3[3] [t]);
}
for (c=2; c<= 6; C++){
86
n = (double)c;
for (t=0; t <= 100 ; t++) {
time = (double)t .1 + .00001;
if (time > (n1.0)*Tp) {
zl[c][t] = (time (n1.0)*Tp)/Tg;
PI[1] [t] = 1.0 exp(zl [c] [t]);
PI [2] [t] = Pl[l] [t] z 1 [ c ] [t]*
PI[3] [t] exp(zl[c][t]); = PI [2] [t] pow(zl[c] [t] 2.0)* exp(zl[c][t])/ (double)factorial (2);
Pl[4] [t] = PI [3] [t] pow (zl[c] [t],3.0)* exp(zl[c] [t])/ (double)factorial (3);
PI[5][t] = PI[4] [t] pow(zl[c][t],4.0)* exp(zl[c] [t])/ (double)factorial (4);
PI[6][t]  PI [5] [t] pow(zl[c][t] 5.0)* exp(zl[c] [t])/ (double)factorial (5);
pn[c] [t] = Tg*(zl [c] [t]* Pl[l] [t ] (n1.0) *P1 [ 1 ] [t ] ) ;
}
if (time > n*Tp) {
z2[c][t] = (time n*Tp)/Tg;
P2[2] [t] = P2 [1] [t] z2 [c] [t] exp(z2[c][t]);
P2[3] [t] = P2[2] [t] pow(z2 [c] [t],2.0)* exp(z2 [c] [t])/ (double)factorial (2);
P2[4] [t] = P2 [3] [t] pow(z2[c][t],3.0)* exp(z2[c][t])/ (double)factorial(3);
P2 [5] [t] = P2[4] [t] pow(z2 [c] [t],4.0)* exp(z2[c][t])/ (double)factorial (4);
P2[6] [t] = P2[5] [t] pow(z2 [c] [t],5.0)* exp(z2 [c] [t]) / (double)factorial(5) ;
P2[7] [t] = P2[6] [t] pow(z2 [c] [t],6.0)* exp(z2[c][t])/
87
}
}
if
}
(double)factorial(6);
pn[c][t] = 2.0*Tg*(z2[c][t]*
P2[c][t](n)*P2[c+1][t]);
(time >
z3 [c]
P3[2]
(n+1.0)*Tp) {
[t] = (time (n+1.0)*Tp)/Tg;
[t] = P 3 [ 1] [t] z2[c] [t]*
exp(z2[c] [t] ) ;
P3[3] [t] = P3 [2] [t] 
pow(z3[c] [t] 2.0)*
exp(z3[c] [t])/
(double)factorial (2);
P3[4] [t] = P3 [3] [t] 
pow (z3 [c] ft] 3.0)*
exp(z3[c][t])/
(double)factorial (3);
P3[5] [t] = P3 [4] [t] 
pow(z3[c] [t] 4.0)*
exp(z3[c] [t])/
(double)factorial (4);
P3[6] [t] = P3 [5] [t] 
pow(z3[c][t] 5.0)*
exp(~z3[c] [t])/
(double)factorial (5);
P3[7] [t] = P3 [ 6 ] [t] 
pow(z3[c] [t],6.0)*
exp(~z3[c] [t])/
(double)factorial (6);
P3[8] [t] = P3 [7] [t] 
pow (z3[c] [t] 7.0)*
exp(z3[c] [t])/
(double)factorial (7);
pn[c] [t] += Tg*(z3[c] ft]*
P3 [c+1] [t] (n+1.0)*
P3 [c+2] [t]);
}
}
double
pow (base,exponent)
double base;
double exponent;
{
double p;
p = exp(log(base)*exponent);
return(p);
88
}
unsigned long
factorial(val)
int val;
{
unsigned long answer;
for ( answer = 1 ; val > 1 ; val) {
answer *= val;
}
return(answer);
}
drawplot ()
{
int i, j;
char ret;
double time;
moveto (0, 300);
linerel (200, 0);
moveto (0, 300);
linerel (0,100);
moveto (0, 300);
for(j=0; j<= 6; j++){
for (i=0; i <= 100; i++) {
time = i .1 + 0.00001;
lineto(i, (300(int) (pn[j] [i]*100.0)));
fprintf(fp,"%lf %lf\n",time, pn[j][i]);
}
moveto(0,300);
}
scanf("%c",&ret);
}
B.6 Mean Queue Occupancy, Variable
/* Mean Queue Occupancy for Variable Length Packets
*/
#include
#include
#include
double meanQN[186];
89
double meanQP[186];
FILE *fp;
main()
{
int Gd, Gm;
fp = fopen("meanq.txt","w");
getMeanQO;
Gd = DETECT;
initgraph(&Gd,&Gm,"");
drawplot () ;
closegraph();
getMeanQ ()
{
int n;
double rho;
double power,power2;
for
}
(n=0; n <= 185 ; n++) {
rho = (double)n 0.005 + 0.0000001;
power = exp(log(rho)*3.0);
meanQN[n] = rho/2.0 + rho/2.0*(1.0rho) +
power/(2.0*(1.0rho));
for (n=185; n >= 1; n) {
rho = (double)n*0.005 + 0.0000001;
fprintf(fp,"%lf %lf\n",rho,meanQN[n]);
for (n=l; n <= 185 ; n++) {
rho = (double)n 0.005;
power = exp(log(rho)*3.0);
meanQP[n] = rho/2.0 + rho/(2.0*(1.0rho));
fprintf(fp,"%lf %lf\n",rho,meanQP[n]);
}
drawplot ()
{
int i;
int rho;
char ret;
moveto (0, 300) ;
90
linerel (200,0);
moveto(0,300);
linerel(0,100);
moveto(0,300);
for (i=l; i <= 185; i++) {
rho = (int)(i);
lineto(rho,(300(int)(meanQN[i]*30.0)));
}
moveto(0,300);
for (i=l; i <= 185; i++) {
rho = (int)(i);
lineto(rho, (300(int) (meanQP[i]*30.0))) ;
}
scanf("%c",&ret);
}
B.7 Mean Queue Occupancy, Fixed
/* Mean Queue Occupancy for Fixed Length Packets */
#include
#include
#include
double meanQN[201];
double meanQP[186];
FILE *fp;
main()
{
int Gd, Gm;
fp = fopen("mq2.dat","w");
getMeanQ();
Gd = DETECT;
initgraph(&Gd,&Gm,"");
drawplot();
closegraph();
}
getMeanQ()
{
int n;
double rho;
double power,power2;
91
for (n=0; n <= 200 ; n++) {
rho = (double)n 0.005 + 0.0000001;
meanQN[n] = rho/2.0 + rho/2.0*(1.0rho);
}
for (n=185; n >= 1; n) {
rho = (double)n*0.005 + 0.0000001;
fprintf(fp,"%lf %lf\n",rho,meanQN[n]);
}
for (n=l; n <= 185 ; n++) {
rho = (double)n 0.005;
power = exp(log(rho)*3.0);
meanQP[n] = rho/2.0 + rho/(2.0*(1.0rho));
fprintf(fp,"%lf %lf\n",rho,meanQP[n] ) ;
}
drawplot()
{
int i;
int rho;
char ret;
moveto(0,300) ;
linerel(200,0) ;
moveto(0,300) ;
linerel(0,100) ;
moveto(0,300) ;
for (i=l; i <= 200; i++) {
rho = (int) (i);
lineto(rho,(300(int)(meanQN[i]*30.0)));
}
moveto(0,300);
for (i=l; i <= 185; i++) {
rho = (int)(i);
lineto(rho, (300 (int) (meanQP[i]*30.0))) ;
}
scanf("%c",&ret);
}
92
B.8 Average Time Delay
/* Average Time Delay */
#include
#include
#include
#define Tp 0.5
#define Tg 0.5
double meanQN[181];
double meanQP[186];
double meanQM[176];
double meanQG[186];
FILE *fp;
main()
{
int Gd, Gm;
fp = fopen("wait.dat","w") ;
getDelay();
Gd = DETECT;
initgraph(&Gd, &Gm, "") ;
drawplot ();
closegraph();
}
getDelay ()
{
int n;
double rho;
double power,power2;
for (n=0; n <= 180 ; n++) {
rho = (double)n 0.005 + 0.0000001;
power = exp(log(rho)*3.0);
meanQN[n] = (Tp+Tg)*(rho/2.0 +
rho/2.0*(1.0rho)
+ power/(2.0*(1.0rho)));
}
for (n=180; n >= 1; n) {
rho = (double)n*0.005 + 0.0000001;
fprintf(fp,"%lf %lf\n",rho,meanQN[n]);
}
for (n=l; n <= 185 ; n++) {
93
