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.
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.
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.