Computer and Communication Networks (paperback)
11.5. Non-Markovian and Self-Similar Models
Another class of queueing systems is either completely or partially non-Markovian . Partial non-Markovian means that either arrival or service behavior is not based on Markovian models. We first consider a single server in which packets arrive according to a Poisson process, but the service-time distribution is non-Poisson or non-Markovian as general distribution . One example of a non-Markovian system is M/G/ 1 queues with priorities. Another is M/D/ 1, where the distribution of service time is deterministic, not random. Yet another example is reservation systems in which part of the service time is occupied with sending packetsserving packetsand part with sending control information or making reservations for sending the packets. 11.5.1. Pollaczek-Khinchin Formula and M/G/1
Let us consider a single-server scenario in which packets arrive according to a Poisson process with rate » , but packet service times have a general distribution . This means that the distribution of service times cannot necessarily be exponential, as shown in Figure 11.16. Suppose that packets are served in the order they are received, with T si the service time of the i th packet. In our analysis, we assume that random variables T s 1 , T s 2 , ... are identically distributed, mutually independent, and independent of the interarrival times. Let T qi be the queueing time of the i th packet. Then: Equation 11.50
Figure 11.16. A general distribution of service times
where K qi is the number of packets found by the i th packet waiting in the queue on arrival, and i is the partial service time seen by the i th packet if a given packet j is already being served when packet i arrives. If no packet is in service, i is zero. In order to understand the averages of the mentioned times, we take expectations of two sides in Equation (11.50): Equation 11.51
With the independence induction of the random variables K qi and T qj , we have Equation 11.52
It is clear that we can apply the average service time as E [ T si ] = 1/¼ in Equation (11.52). Also, by forcing Little's formula, where E [ K qi ] = »E [ T qi ], Equation (11.52) becomes Equation 11.53
where = »/ µ is the utilization. Thus, Equation 11.54
Figure 11.17 shows an example of mean i representing the remaining time for the completion of an in-service packet as a function of time. If a new service of T si seconds begins, i starts at value T si and decays linearly at 45 degrees for T si seconds. Thus, the mean i in the interval [0, t ] with n triangles is equal to the area of all triangles ( Equation 11.55
Figure 11.17. Mean partial service time
If n and t are large enough, n/t becomes » and & pound ; n i=1 T 2 si /n becomes E [ T 2 si ], the second moment of service time. Then, Equation (11.55) can be rewritten as Equation 11.56
Combining Equations (11.55) and (11.54) forms the Pollaczek-Khinchin (P-K) formula: Equation 11.57
Clearly, the total queueing time and service time is E [ T qi ] + E [ T si ]. By inducing Little's formula, the expected number of packets in the queue, E [ K qi ], and the expected number of packets in the system, E [ K i ], we get Equation 11.58
and Equation 11.59
These results of the Pollaczek-Khinchin theorem express the behavior of a general distribution of service time modeled as M/G/ 1. For example, if an M/M/ 1 system needs to be expressed by these results, and since service times are exponentially distributed, we have Equation 11.60
Note that the queueing metrics as the expected value of queuing delay obtained in Equation (11.60) is still a function of the system utilization. However, the notion of service rate ¼ has shown up in the equation and is a natural behavior of the non-Markovian service model. 11.5.2. M/D/1 Models
The distribution of service time in a computer network is deterministic. In the asynchronous transfer mode , discussed in Chapter 2, packets are equal sized , and may be so ATM fits well fits in the M/D/ 1 model. When service times are identical for all packets, we have Equation 11.61
Note that the value of E [ T qi ] for an M/D/ 1 queue is the lower bound to the corresponding value for an M/G/ 1 model of the same » and ¼ . This is true because the M/D/ 1 case yields the minimum possible value of 11.5.3. Self-Similarity and Batch-Arrival Models
The case of video streaming traffic, which obeys a model in the form of batch arrival , not Poisson, is analyzed in Chapter 18, so our analysis on non-Poisson arrival models is presented there. Here, we give some descriptive and intuitive examples of such models, which give rise to self-similar traffic. Non-Markovian arrival models , or basically non-Poisson arrival models , have a number of important networking applications. The notion of self-similarity, for example, applies to WAN and LAN traffic. One example of such arrival situations is self-similarity traffic owing to the World Wide Web (WWW). The self-similarity in such traffic can be expressed based on the underlying distributions of WWW document sizes, the effects of caching and user preference in file transfer, and even user think time. Another example of self-similar traffic is video streaming mixed up with regular random traffic backgrounds. In such a case, batches of video packets are generated and are directed into a pool of mixed traffic in the Internet. Traffic patterns indicate significant burstiness, or variations on a wide range of time scales . Bursty traffic can be described statistically by using self-similarity patterns . In a self-similar process, the distribution of a packet, frame, or object remains unchanged when viewed at varying scales. This type of traffic pattern has observable bursts and thus exhibits long-range dependence. The dependency means that all values at all times are typically correlated with the ones at all future instants. The long-range dependence in network traffic shows that packet loss and delay behavior are different from the ones in traditional network models using Poisson models. |