Basic Data Communications Series
1.0 Performance Analysis Introduction
A standard performance criterion of a network node is its throughput delay and queue occupancy of the input buffer. Thus the efficacy of the transmission protocol, for a given traffic level, will determine the delay performance and the resulting queue build up. When the finite length input buffer is full, the traffic will be blocked leading to congestion.
Performance analysis is thus based on queuing theory.
1.1 Queuing Theory Basics
The model of a queue is illustrated in fig 1-1.
Packets arriving Packets departing
Figure 1.1 : Single Server Queue
Packets arrive into the buffer and are processed by the server(s) following a service discipline, for example First Come First Served. Fig 3-1 illustrates a single server (the circle) but there could be more than one server for example in a network that has more than one link from a node. A simple notation due to the statistician Kendal is as follows: A/B/1. The first letter indicates the packet arrival process, the second letter indicates the departure process, and the number indicates the quantity of servers.
The arrival process universally used in queuing theory is that of a Poisson process whose probability density has a single parameter l . The Poisson process is a special case of a Markov process, this is explained below.
1.2 Poisson Arrival Process
t t+Dt
Figure 1.2: Poisson Process
A Poisson process describes the arrival of events in a discrete time interval Dt. A Markov process is one in which the probability of an event at time t+Dt depends only on the probability at time t and not on previous or future events. A Poisson process is the probability of an event arriving in the interval Dt and is independent of previous or future events arriving in a similar interval Dt. The Poisson process is thus a special case of the Markov process.
Consider now a longer period in time T composed of k periods of Dt
The probability of k arrivals in the period T is as follows [3]:
k = 0, 1, 2, 3 ….etc ……. (1)
This is a Poisson distribution and the expectation (mean) E of this distribution is given by:
……….. (2)
The mean rate of arrivals is therefore just:
……… (3)
The general form of the Poisson distribution (equation 1) is an exponential with a parameter l. The inter-arrival time of the k events is thus exponentially distributed with the rate parameter l - (equation 3). Therefore as the traffic rate increases the inter-arrival time decreases exponentially.
The next thing to consider is the departure process out of the buffer.
1.3 Departure process
Several departure processes can be defined. For example a Poisson process could be used as described above or perhaps a Gaussian process. In a similar way to arrivals all departure processes are parameterized by a rate parameter m. The service time of a single departure is thus 1/ m.
If the server is a simple controller with a fixed service interval given by the packet length multiplied by the bit period of the data, then the departure process is deterministic. Thus a single server queue with Poisson arrivals and deterministic departures would be designated as an M/D/1 queue – M for Markov, D for deterministic.
An important parameter is the traffic intensity r through the queue. This is defined as follows:
……. (4)
A general service distribution can also be defined (M/G/1) for any departure process. This is considered in the next section.
1.4 The General Service Distribution
To complete the discussion of basic queuing theory, two important equations are defined for the queue length and throughput delay performance criteria quoted in the introduction.
These are the Pollaczek-Khinchine equations for the general service distribution M/G/1. The expected average queue occupancy as follows:
…….. (5)
s2 is the variance of the service distribution process.
Little’s result [6] relates the average queue occupancy to the queuing time as follows:
……….. (6)
Where L is the queue length, and W is the waiting time, l the arrival rate as before
Using Little’s result, the expected average waiting time in the queue is therefore:
……… (7)
The Deterministic Service Distribution
For the M/D/1 queue, all packets have the same deterministic service time. Thus the variance of the service time, s2, is zero. Hence the two equations above reduce to:
……….. (8)
………. (9)