Traditionally, IP network planning and design is mostly based on the average delay or loss constraints which can often be easily calculated. Jitter, on the other hand, is much more difficult to evaluate, but it is particularly important to manage the QoS of real-time and interactive services such as VoIP and streaming video. In this paper, we present simple formulas for the jitter of Poisson traffic in a single queue that can be quickly calculated . It takes into account the packets delay correlation and also the correlation of tandem queues that have a significant impact on the end-to-end jitter. We then extend them to the end-to-end jitter of a tagged stream based on a tandem queueing network. The results given by the model are then compared with event-driven simulations. We find that they are very accurate for Poisson traffic over a wide range of traffic loads and more importantly that they yield conservative values for the jitter so that they can be used in network design procedures. We also find some very counter-intuitive results. We show that jitter actually decreases with increasing load and the total jitter on a path depends on the position of congested links on that path. We finally point out some consequences of these results for network design procedures.
1 Introduction
1.1 Motivation
The main challenge in the engineering of current IP networks is the integration and support of a wide variety of applications and services combining voice, data, streaming, and VoD. The different media types exchanged by these applications have different requirements in terms of bandwidth, latency, jitter, and reliability. The popularity of these applications has highlighted the limitations of the actual Internet infrastructure.
For real-time and interactive services, delay jitter remains one of the most important parameters of quality of service. For most of applications, the variation in the arrival time of packets at the terminal must be compensated by using a playback buffer in order to provide a regular packet stream to the application. Estimating and controlling the delay variation is important for the operator to avoid both a buffer overflow, which causes packet losses, and buffer underflow when the application does not receive packets for some time. In both cases, the users will experience a degraded quality of service. These effects can be avoided to a large degree by controlling packet jitter.
Anzeige
Nevertheless, the effect of jitter on network structure and operation is not well understood. Getting some qualitative understanding of this QoS requirement will be only possible when we have a fast evaluation method for jitter that can be used in network design algorithms. We present here a first solution where we derive a fast jitter model for Poisson traffic that is both accurate and fast enough to be used for network design. We can use it to gain insight into the impact of the jitter on communication data networks.
First, we provide an accurate analytical expression for the end-to-end delay jitter in a single node case. From this, we show that the jitter incurred by an individual network node is bounded by the packet average transit delay and the packet average service time. We then extend this model to calculate an approximate expression for the end-to-end delay jitter along a path in a tandem queueing network. We find that the jitter is significantly important at the first multiplexing node and decreases as the correlation between successive packets increases. We also show that its accuracy is excellent when compared with simulation results of Poisson traffic. We also find the unexpected result that jitter improves as the load increases and that the jitter on a path depends on where the more congested links occur on that path. This is in strong contrast with other QoS measures such as delay or loss.
The technique is fast enough to be used in a network design tool, which could help operators to improve the performance of their networks and provide network optimization that can take into account both jitter and delay QoS constraints.
1.2 Previous work
There has been much work during the 1990s on the estimation of cell delay jitter for ATM networks. This is based on discrete time processes and FCFS multiplexing operation. Most of these results assume that the tagged stream is originally periodic or is a general renewal process. In [15], the jitter steady state is derived for a periodic traffic stream by assuming a Markovian structure for the cell delay process. The authors of [10] and [11] used generating functions to estimate the end-to-end jitter of a general renewal stream in heavy and light traffic.
Anzeige
The jitter pdf for a renewal stream multiplexed with uncorrelated background traffic is derived in [8, 9]. An analytical approximation for the delay jitter first-order and second-order statistics incurred by a periodic traffic is proposed in [7]. In [13], the authors provided a complete characterization of the jitter process when the tagged stream and the background traffic are constant bit rate. A simple analytical approximation for the delay jitter incurred by a periodic stream multiplexed with a background traffic and governed by a general renewal process is described in [2].
Recently, there have been some proposals for delay jitter models in DiffServ networks. An extension of [13] was proposed in [3] to evaluate the per-class jitter. The authors [1] provided some analysis of the delay jitter by means of event-driven simulations (ns-2) where EF flows are represented by renewal periodic ON–OFF flows.
All these methods concentrate on the analysis of the jitter incurred by a tagged periodic cell stream going through nodes of an ATM network so that the service time is constant which is not necessarily the case with IP traffic. Furthermore, the computation time is large which makes them unsuitable as a component of a network dimensioning tool.
1.3 Our contribution
The purpose of this work is to produce a simple formula for the end-to-end delay jitter. The main application is as a component of a network design algorithm, for example, for routing or dimensioning. Typically, these are large nonlinear programs where the jitter appears as a set of QoS constraints. In this context, the evaluation of the jitter has to be done a very large number of times both to test feasibility of a solution and for the calculation of the gradients. This is why the first requirement of such a model is simplicity and fast evaluation. Obviously, accuracy is also needed but it is not very useful to have a very accurate model if it requires such a large computation time that it will make it impossible to solve the design problem in a reasonable time.
For these reasons, the results that we obtain are for Poisson arrivals and exponential holding times. There is a large body of work showing that some real Internet traffic is definitely not Poisson and can exhibit long-range dependence. In these cases, the values obtained from a Poisson-based model might not be very accurate. Nevertheless, a less accurate, but fast, jitter model can still be very useful for the following reasons.
First, we have not found any model with more realistic processes that can be calculated within the times required for network design. Right now, the only thing that seems to be fast enough for network design is a Poisson model.
Second, even though the actual values for the jitter may not be accurate, they could provide some insight when comparing other network parameters with each other. Suppose for instance that we want to choose between two kinds of transmission systems with different costs. We could run the design algorithm with the Poisson model with the two cost values. Suppose that the Poisson model underestimates the jitter. This will produce an under-dimensioned network in the two cases, but the cost difference between the two solutions might very well be close to what we would get with a more realistic jitter model. In other words, the difference in the error might be smaller than the actual difference between the approximate and the real cost in each case.
Another area where this may be useful is related to the modeling of network traffic by hierarchical MMPP processes [12]. The packet process is represented by a Poisson process within the ON period of a session process [5]. An analytic model such as the one that we are presenting here could be used within some decomposition technique of the hierarchical MMPP that would be required to compute the jitter.
Finally, it should also be mentioned that we have looked at actual measurements in the access network of a large ISP. We have found that this traffic, which is generated by several HTTP sources, is a major component of the total traffic and that the downstream, upstream, or total traffic can be very accurately approximated by an exponential distribution. This shows that the Poisson assumption is realistic in some kinds of access networks. In cases like these, the model that we are presenting here can be applied directly to calculate the end-to-end jitter and to design the network.
In the following, we assume that all network nodes have a single output interface, or Egress Port, and several inputs interfaces, or Ingress Ports. Users generate packets of various flows corresponding to different applications on the input interfaces, and all these flows exit the node through the output interface toward different destination nodes. We focus on a particular flow, called the tagged flow, which can be any one of the flows through the node. At each node, the tagged flow is multiplexed under the FCFS discipline with several others flows, called the background traffic. The inputs parameters of the model are the number of input interfaces at the node, the link speed, and the traffic flow matrix, and the output parameters will be the jitter of the tagged flow packets.
In Section 2, we present our definition of jitter. We then present in Section 3 an analysis of the jitter for a single queue. The jitter model for multiple queues in tandem is described in Section 4 and is also checked by simulation. Section 5 briefly discusses planning and design issues whereas Section 6 provides some conclusions.
2 Definition of jitter
Jitter is a measure of the packets’ transfer delay variation. It can depend on the packets’ routes and is caused by multiplexing several flows in the node queues. There are several definitions of jitter that try to capture the delay variation of packets. In this paper, we adopt the IETF [6] definition of jitter. It is based on the transit delay between the entry and the exit nodes. Let Tj represent the delay experienced by the jth packet going through a queue. The difference of transit time between two consecutive packets of the tagged flow can be written as
$$ J_j= T_{j+1}-T_j \label{eq:cdvjitter} $$
(1)
which can be positive or negative. The average end-to-end delay jitter is then given by the expected absolute value of this random variable
$$ J= E \left[ \left\vert\,T_{i+1}-T_{i} \,\right\vert \right]. \label{eq:expjitter} $$
(2)
In the case of a network, let \(T_j^{(n)}\) be the delay of jth packet at node n. The end-to-end jitter for a tagged flow passing through N tandem nodes is given by
We now consider a single queue with infinite buffer and a FCFS discipline. There are K streams of packets arriving to this queue each with possibly different parameters for the inter-arrival time and packet length distributions. We are interested in the jitter of a particular stream k, called a tagged stream. Unless otherwise noted, all these streams are Poisson with arrival rate λm, and all service time distributions are negative exponential with parameter μm. We provide exact formulas for the jitter in two limit cases where either the arrival rate of the tagged stream is much larger or much lower than the others. We also present an approximate formula for the intermediate case which we evaluate through simulation. Define
λ
the total arrival rate \(\lambda = \sum_{m=1}^K \lambda_m\)
λk
the arrival rate of the tagged flow
λ0
the background arrival rate λ0 = λ − λk
3.1 Small arrival rate
Suppose that λk ≪ λ0. In this case, two packets of stream k are separated by a large number of packets from the other streams so that we can ignore the correlation between the transit delays of two consecutive packets and assume that Tj + 1 and Tj are two independent random variables. Since the Tjs are the sojourn time of a customer in a queue, we know that they have a negative exponential distribution with parameter η = μ − λ. Under these conditions, we can use a well-known property of exponential distributions [14].
Theorem 1
Let X1and X2be two continuous independent and identically distributed random variables with the same distribution fas the random variable X. The distribution of the random variable |X1 − X2 | is f if and only if f is the exponential distribution.
From this, we get directly that
Proposition 1
When the arrival rate of the tagged stream is small, the jitter is given by
$$ J = E \left[ \mid T_{j+1}-T_j \mid \right]= \frac{1}{\eta}, \quad where \quad \eta=\mu-\lambda. \label{eq:valj} $$
(4)
3.2 Large arrival rate
Next consider the case where λk ≈ λ. In this case, we can neglect the presence of the other streams and consider that we have a queue with only one flow. The conditions of Proposition 1 no longer apply since the sojourn times of two consecutive packets are clearly not independent and we have to take the correlation between the transit time of two consecutive packets into account. First define
tj
arrival time of packet j and Ij = tj − tj − 1 the inter-arrival time
Note that the random variables Tn, Sn + 1, and In + 1 are independent and also that the distribution of each of these three random variables is the same for all values of n. We can then write
Finally, we consider the case where the arrival rate of the tagged flow takes values between the two extreme points. The tagged flow is multiplexed under the FCFS discipline with a background Poisson traffic with parameter λ0 generated by the others flows. The value of the total traffic load ρ is
where \(T^k_j\) is the delay of the jth packet of flow k. In this case, we provide a light-load approximation only. We denote Pj and Pj + 1 two consecutive packets of the tagged flow with corresponding delays Tj and Tj + 1. The light load assumption can be stated as
Proposition 3
In a lightly loaded system, packet Pj + 1of flow karrives at the queue when Pjhas already left the system.
Given that the arrival process is Poisson with parameter λk, the average time between Pj and Pj + 1 is τk = 1/λk. The light load assumption can then be stated as
In this equation, the expression 1 − f(τk,η) can be seen as an estimate of the degree of correlation of two successive packets from flow k.
We can see that the approximation 15 satisfies a number of requirements. First, if λk ≈ 0, then τk ≈ ∞ and we get Jk ≈ 1/η. This is in line with the argument presented in Proposition 1.
When the tagged flow is dominant, λk ≈ λ so that ητk ≈ (1 − ρ)/ρ. In that case, we have
Consider the two extreme values for ρ. If ρ ≈ 0, we see that the exponential will be small and that J ≈ 1/η as well. In other words, when ρ is small, the jitter does not depend much on the proportion of tagged traffic. If, on the other hand, ρ ≈ 1, then ητk ≈ 0 and we get, after expanding the exponentials to first order, J ≈ 1/μ. To summarize, if ρ is small, J should be relatively insensitive to the mix of traffic while it will be more sensitive when ρ is large. These limit cases are summarized in Table 1.
Table 1
Limit values for J
ρ
λk
0
λ
0
1/η
1/η
1
1/η
1/μ
3.4 Validation of single node model
The model is validated by comparison with simulation results as shown on Fig. 1. We assume that the packet size distribution is exponential with mean 1 Kbyte. C is the capacity of the link, say in bits per second. The average service time of a packet is 1/μ = L/C. In these examples, we consider a link with high capacity C = 622 Mbits/s.
Fig. 1
Validation of model
×
The x axis represents the weight of the tagged flow λk/λ and the vertical axis is the value of the jitter normalized to the largest value 1/η. Three sets of curves were produced where the total load ρ was fixed to the values ρ = 0.1, 0.5, 0.9. In each case, the value of λk was increased from 0 to λ while decreasing the values of the other flows such that λ remained constant. Two curves are shown for each set, a dotted line for the analytic results and a solid one for the simulation results.
For low load, at ρ = 0.1, we see that the model is insensitive to the weight of λk while in reality, there is a slight decrease in the value of the jitter as λk increases. For moderate to high loads, the approximation is reasonably accurate for smaller weights and very good at higher values of the weight. More important, however, is the fact that the model is conservative in the sense that it gives values of the jitter that are somewhat higher than the actual value. In the absence of an exact model, this is a desirable value for network design since it will produce a network with sufficient QoS to meet the required value.
3.5 Jitter under increasing load
It is common wisdom that in a queuing system, performance will degrade as the load increases. This is certainly true for delay and loss, and it is intuitively clear that it should be so. A most surprising feature of delay jitter is that this “obvious” behavior is no longer true. This can be seen from Fig. 2 where we have plotted the average delay and jitter as a function of λk. There is a striking difference in the two curves, and we see that jitter actually decreases as the load increases. This result is confirmed by event-driven simulation and also in realistic environments [4].
Fig. 2
Delay and jitter behavior
×
This behavior is not a consequence of the delay model since it has been observed in more realistic situations [16]. It can be explained to some extent by the following argument: When a queue is nearly empty, arriving packets do not have to wait very often so that the delay depends on the inter-arrival process, the service time, and the time in queue. When the queue is large, almost all packets have to wait so that the inter-arrival process does not contribute much to the sojourn time. In that case, most of the variation in the delay is due to the service time only, and it is not unreasonable to expect that the jitter will be smaller in this case that what it is in a lightly loaded network. This has some consequences for network design that are briefly discussed in Section 5.
4 Multiple node case
The estimation of the jitter along a path is more complicated than for a single queue because of the multiplexing of several flows at each node and the correlation between the service time at a node and the arrival at the next node.
We want to estimate the end-to-jitter for a tagged flow k passing through N tandem nodes, as in the example of an access network of Fig. 3. At each node, flow k is multiplexed under the FCFS discipline with several others flows called background traffic. Let \(\lambda_k^{(n)}\) be the arrival rate of packets of flow k at the node n, and let \(\lambda_0^{(n)}\) the arrival rate of the background traffic at the same node. The service time of all packets is a negative exponential with parameter μ.
Fig. 3
N simple queues in tandem
×
4.1 Correlation in tandem queues
Jitter is defined as the variation in the delay of packets through a router or over the network. The packet delays through a queue are strongly correlated with each other. If we are interested in the delays of a particular flow, this effect can be reduced by the multiplexing of several flows but still needs to be taken into account. In a network, there is also a strong correlation between queues in tandem due to the dependence between the service time of a given packet and the arrival time at the following router. These effects have a significant impact on the end-to-end jitter and the standard queuing theory techniques are too complex to calculate an exact value for the jitter.
We show in Fig. 4 some simulation results for the jitter incurred by two queues in tandem. We can see that the jitter incurred by the second queue is much lower than the jitter at the first queue. But this becomes less important after the second node as shown in Fig. 5. In this figure, we measure the jitter at each queue on a path, and we plot these values as a function of the node number on the path. It is quite clear that the first node has a much larger jitter than the others. We also note that the traffic load has a significant impact on the jitter value at each node.
Fig. 4
Tandem queue correlation impacts on the tagged flow
Fig. 5
Jitter variation as a function of the node number
×
×
Based on these empirical remarks, we assume that the formula of the jitter in the second node can be written as
where \(K(\lambda_k^{(n)},\eta_2)\) depends on the delay correlation at the entrance of the second queue and \(J_1^k\) is the jitter at the first queue given by Eq. 15. The problem will be solved if we can approximate this delay correlation. In the next section, we describe an analytical approximation of this correlation, and from this, we deduce a general formula for the jitter in the case of multiple nodes.
4.2 Analytical model
We consider the case where the tagged flow goes through N tandem nodes. The two measurement points are the entry of the first buffer and the exit from the last server on the path. All the parameters of Section 3 are now indexed with a superscript n to indicate the node. For instance, we let \(\lambda_k^{(n)}\) be the arrival rate of packets of flow k and \(\lambda_0^{(n)}\) the arrival rate of the background traffic at node n.
Let \(T_j^{(n)}\) be the delay of packet j through node n. The path jitter of the tagged flow k is given by
The direct calculation of Eq. 19 is not easy so that we will use a simple approximation that takes into account the correlation of tandem queues. Still, we can see from Eq. 19 that
where \(J_n^k\) is the jitter of flow k at node n given by Eq. 16. Summing the jitter of the queues on a path will produce an overestimate of the true jitter. We quantify in Section 4.3 the magnitude of this over-estimation.
Let \(q_i^{(n)}\) be the queue occupancy at the ith arrival from flow k at queue n. We then obtain the auto-correlation function for packets of flow k by
and\(f \left( \tau_k^{(n)},\eta^{(n)} \right)\)is given by Eq.16.
4.3 Validation of multiple node model
We can estimate the accuracy of formula 23 by comparing with the results of simulations. We show four estimations of the jitter through four queues in tandem, each with a different load ρi, as a function of the importance factor for the tagged flow. Two curves labeled end-to-end jitter represent the actual jitter from the start to the end of the path. The curve labeled analytic shows the results obtained using Eq. 23 and the other one shows those obtained from the simulation. The most important conclusion is that for Poisson traffic, the analytic model is an excellent approximation to the end-to-end jitter over a large range of traffic loads. As we mentioned before, any dimensioning tool based on this model will then produce a conservative design where the actual jitter will be lower than what has been planned.
A similar pair of curves are presented when we replace the end-to-end calculation by the sum of the jitter at each node (Figs. 6, 7, and 8). Although this would simplify the calculation considerably, we see that it is a very large overestimate and it may not be sufficiently accurate for planning purposes.
Fig. 6
Jitter vs arrival rate for four queues in tandem with ρ1 = 0.3, ρ2 = 0.5, ρ3 = 0.5, and ρ4 = 0.8
Fig. 7
Jitter vs arrival rate for four queues in tandem with ρ1 = 0.6, ρ2 = 0.7, ρ3 = 0.7, and ρ4 = 0.9
Fig. 8
Jitter vs arrival rate for four queues in tandem with ρ1 = 0.8, ρ2 = 0.85, ρ3 = 0.87, and ρ4 = 0.9
×
×
×
4.4 Effect of link congestion on jitter
The model provides insight into another unexpected property of path jitter. Suppose that a path has one link more heavily loaded than the others. If we compute the path delay, the location of this congested link on the path will have no impact on the value of the path delay. In the case of jitter, we can see from Fig. 9 that the position of the congested link in the path has a large influence on the total path jitter. We see that when the congested link is at the beginning of the path, the total jitter is much larger than when it is at the end of the path. This is another counter-intuitive result showing that jitter behaves quite differently from other QoS measures.
Fig. 9
Jitter for different positions of congested link
×
5 Planning and design issues
Planning and designing of data communication networks is immensely complex. These problems are generally formulated as large nonlinear optimization problems where any solution algorithm will have to evaluate the QoS a very large number of times while solving a given network. It is essential that any QoS model used in such a design tool can be evaluated quickly and as accurately as possible. The average network delay and throughput have usually been used as metrics to optimize the network cost and performance in current design tools. This is simply due to the absence of a robust and simple formula for the others parameters such as the jitter, so that current network planning and design techniques are mostly based on average delay or loss constraints simply because they can often be easily calculated. We mentioned in this section some recommendations and suggestion to perform optimal network design.
As we have seen from Fig. 2, jitter decreases when the traffic load increases and is a concave function of load. This is very different from delay, which is a convex function of load. Optimizing with a concave objective tends to produce sparse networks while the opposite is true for convex functions which produce networks with higher connectivity. It is thus likely that the choice of QoS, delay or jitter, can have an impact on network routing and structure.
We have also seen in Fig. 5 that jitter is likely to be much more important when it occurs at the access nodes. This is due to the fact that access links have limited capacity so that congestion is more likely to occur on these links as opposed to the core. The results of Fig. 4 show that having jitter at the first node on a path will have a larger impact than when this occurs elsewhere on a path. This is another important effect that will have to be taken into account by network design algorithms.
6 Conclusion
In this paper, we have presented and evaluated an analytical approximation of the end-to-end jitter for Poisson traffic that can be used interactively or within a network design algorithm. We have given simple formulas for the jitter through a single queue and extended these to nodes in tandem. We have shown that in the case of a single network, jitter is bounded by the average service time and average transit time of packets. We have also shown that jitter decreases as packets move forward on a path. The analytic formulas were compared with simulation results. The accuracy was quite good for Poisson traffic. More importantly, however, is that the analytic values were larger than the actual values, which shows that a design tool based on them would produce a conservative solution which would easily meet the requires QoS.
We have found that in some cases, jitter can be a decreasing function of load and that the position where congestion occurs on a path can have a large impact on path jitter. These are counter-intuitive results that can potentially change the routing and/or network structure when jitter is taken into account.
Acknowledgements
The authors would like to thank Weihua Chen for the fruitful discussions and simulation results. This work has been supported by the National Science and Engineering Research Council CRD grant CRDPJ 335934-06.
Open AccessThis is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Appendix: Calculation for intermediate rate
Under the assumption of Proposition 3, Ti + 1 and Ti can be considered as two continuous independent and identically distributed random variables with a negative exponential distribution. That is, the pdf of Δ= Ti + 1 − Ti can be approximated as follows.
