hledat:

Delay Variation Model with Two Service Queues

CESNET technical report 16/2008
PDF format

František Hromek, Miroslav Vozňák

Received 3.12.2008

Abstract

This technical report deals with the mathematical model of an end-to-end delay and a delay variation in VoIP connections going through a two priority queue' serving system. This report focuses on delay components and its mathematical formulations.

Keywords: VoIP, delay, jitter, M/D/2

1  Introduction

A delay is one of the main issues in packet-based networks which have impact on QoS. There are several components of the delay in an IP network which differ from each other in the way they originate. Each delay component has different impact on a voice packet delay. Delay components can be divided according to their origin [1], [2], [8], [11]:

• Coder delay and packetization delay in transmitter,

• Queuing delay, serialization delay and propagation delay in transmission network,

• De-jitter delay, de-packetization delay and decompression delay in receiver.

2  Delay variation model with two service queues

Based on the analysis of the principle of service models with two priority queues, we can assume that delays in a higher priority service queue are shorter. If we opt for better system resources for the high-priority service queue, we are likely to experience poorer system resources for voice packets in the lower-priority service queue. Delays are likely to get longer in a lower priority queue, see [3] and [12].

Even if service parameters get weaker, standard users are not likely to perceive the poorer quality provided the longer delay is offset by the size of the De-jitter buffer or where, given the imperfection of human hearing, the total length of the delay has a negligible impact.

In order to be able to express the delay in the service element with priority queues, it is necessary to monitor solely queues that are used for the voice flow service. The method applied to transmit voice packets in priority queues corresponds with the M/D/n/k [9] model where n is the number of service queues and k is the size of the cache memory [4], [5].

In order to express the mathematical model which uses two service queues for transmission of voice streams, we can substitute the M/D/n/k model by the M/D/2/k model. In order to express the model we disregard the size of cache memory. This assumption enables us to replace the M/D/2/k model by the M/D/2 model. The conditions for validating the M/D/2 model are as follows:

• No interruption of the priority service process: Packets in the higher priority queue are served before packets in the lower priority queue. When a packet with some priority arrives, the service is provided first.

• Priority queues are served based on the FIFO (First In First Out) method,

• The arrival process corresponds to the Poisson distribution. Where every single stream matches the Poisson distribution, then the sum of such streams also matches the Poisson distribution,

• The service rate is a constant because the same codec and packets of the same size are used,

• The arrival rate is also a constant since we assume a constant number of the flows with the same codec,

• The size of the priority queue's cache memory is infinite.

The system's utilisation can by express by the following formula:

(1)

where:

• ρ – system utilisation [-]
• λ – arrival rate [s^-1]
• μ – service rate [s^-1]

The stability condition 0 ≤ ρ < 1 needs to apply.

The utilisation of a system with two priority queues can be express as follows:

(2)

where ρ_i is the utilisation of the system queue.

So, the system utilisation can be express as follows:

(3)

The arrival rate can be expressed by the following equation:

(4)

where

• M_i – number of streams in queue i [-]
• C_BW – codec bandwidth [b/s]
• P_S – payload size [b]

The service rate can by express by the following equation:

(5)

where:

• T_SER – serialization delay [s]
• T_S – processing time [s]

The mean service time of the process in a higher priority queue can be express as follows, see [10] and [12]:

(6)

Similarly, the mean service time of the process in a lower priority queue can be express as follows:

(7)

The relation between the mean service time and the system utilisation of the queue is shown in the Figure 2.

In the system “without interruption” the mean service time is generally the sum of the service time, time of the remaining services, time it takes voice packets included in the same or a higher-priority queue to be transmitted and time needed to transmit voice packets of a higher priority that came while the packet was waiting to be processed by the system, see [6], [7] and [10].

A key parameter is the time it takes to process a service element. This parameter needs to be determined individually for each service element. It is determined by hardware (processor, motherboard and network card, etc.) and software (operating system, kernel, etc.) used. The only option to determine the processing time is based on knowledge of the behaviour characteristic of the element in the increasing load, see [8] and [12].

Assuming we know both the line speed and the processing time, we can express the service rate by the following equation:

(8)

where:

• H_L – header length [b]
• L_S – line speed [b/s]

The utilisation of the system queue can by express as follows:

(9)

The system utilisation can be expressed as follows:

(10)

The mean service time of the process in a higher priority queue can be express by the following formula:

(11)

The mean service time of the process in a lower priority queue can be expressed by the following formula:

(12)

End-to-end delay can be expressed by substituting the model designed for a single service queue. The end-to-end delay in a lower priority queue can by express as follows, see [8], [11] and [12]:

(13)

where:

• T_1c – end-to-End delay [s]
• N – number of voice blocks in a packet [-]
• T_CD – total delay of the codec [s]
• L_i – length of line i [m]
• v – speed of signal transmission in the environment [m/s]
• T_DJD – de-jitter delay [s]
• T_1i – mean service time i service element i [s]

End-to-end delay in a higher priority queue can by expressed by the following formula [12]:

(14)

3  Experiment

The workplace in which we carried out the estimation of the proposed model consisted of a service element (PC1) with Traffic Control, three performance endpoints and a console workstation. VoIP calls were emulated by IxChariot Performance endpoints and the IxChariot Console was used to assess VoIP calls. Experiments were carried out under different conditions. IxChariot endpoints generate voice streams between PC2 and PC3 and between PC4 and PC3.

Linux distribution OpenSuse 10.3, with the implemented support of the QoS was used as the operating system in the core element. Two queues to process voice streams and one queue to process the rest of the traffic have been defined.

The structure of the experimental workplace is illustrated in Figure 4.

The configuration of the Traffic Control in the core element is described below. Three priority queues were defined.

tc qdisc add dev eth1 root handle 1:0 prio
tc filter add dev eth1 parent 1:0 prio 1 protocol ip u32 match ip tos 0x28 0xff flowid 1:1
tc filter add dev eth1 parent 1:0 prio 2 protocol ip u32 match ip tos 0x48 0xff flowid 1:2
tc filter add dev eth1 parent 1:0 prio 3 protocol ip u32 match ip tos 0x00 0xff flowid 1:3
tc qdisc add dev eth2 root handle 1:0 prio
tc filter add dev eth2 parent 1:0 prio 1 protocol ip u32 match ip tos 0x28 0xff flowid 1:1
tc filter add dev eth2 parent 1:0 prio 2 protocol ip u32 match ip tos 0x48 0xff flowid 1:2
tc filter add dev eth2 parent 1:0 prio 3 protocol ip u32 match ip tos 0x00 0xff flowid 1:3
tc qdisc add dev eth3 root handle 1:0 prio
tc filter add dev eth3 parent 1:0 prio 1 protocol ip u32 match ip tos 0x28 0xff flowid 1:1
tc filter add dev eth3 parent 1:0 prio 2 protocol ip u32 match ip tos 0x48 0xff flowid 1:2
tc filter add dev eth3 parent 1:0 prio 3 protocol ip u32 match ip tos 0x00 0xff flowid 1:3
      

The Network Interface Cards were configured using Ethtool. The network address was configured using standard Linux commands. An example NIC configuration for PC2 is described below.

ethtool –s eth1 speed 10 duplex full autoneg off
ifconfig eth1 192.168.102.2 netmask 255.255.255.0
route add default gw 192.168.102.1
      

The number of voice streams was the same. TOS 0x28 values were used in voice streams between PC2 and PC3. TOS 0x48 values were used in RTP streams between PC4 and PC3. Each RTP stream used a different communication port. For our experiment, we used G.711a and 20ms as a delay between the datagram.

The relation between the mean service time in a higher and lower priority queue and equally distributed load in the queues is shown in Figure 6.

The mathematical model uses values characteristic for the G.711 codec. The length of transmission lines was set to 50 meters and the De-jitter buffer size was set to 1ms.

The accuracy of the model depends on what T_S parameter is chosen. In order to compare the conformity of real and theoretical values, T_S = 0,11 ms was applied.

A comparison of theoretical values and the results of the experiment is shown in the diagrams below.

In experimental workplace we have been theoretically able to run approximately 110 calls. In real terms we performed only 75 calls without other influences that we were not able to reflect in the model, such as an unpredictable processing of the call and loss of the information.

Relative errors of the model for each of the queues are shown in Figure 8.

4  Conclusion

The proposed mathematical model is suitable for the approximation of voice traffic which consists of sources with the Poisson’s probability distribution. However, as the load increases, the mathematical model does not return exact information. The measurements have shown that the mathematical model strongly depends on selection of T_S value. T_S has proved to be significant between 50 % and 70 % of the line load, due of the emergence of the processing delay. Because of the use of the processing time in the mathematical model, we are able to get data with accuracy below ± 3 % up to the 70 % of line load. Furthermore (over 70% of line load), the tests did not reproduce due to the unpredictable behaviour of call processing and loss.

T_S is a key parameter is the time it takes to process a service element. This parameter needs to be determined individually for each service element. It is determined by hardware (processor, motherboard and network card, etc.) and software (operating system, kernel, etc.) used. The only option to determine the processing time is based on knowledge of the behaviour characteristic of the element in the increasing load

Up to the 70 % of line load, the maximum deviation between the theoretical model and real values was 0,75 ms. The delay incurred in the queuing element with delay below 1ms can not be considered as sufficiently precise since the absolute measurement error of the method using IxChariot equals 1ms. As regards the end-to-end delay, the relative error measured during the experiment is less than 3 % when compared to the theoretical values obtained through the application of the mathematical model.

Even though individual voice connections do not match the model of a signal source with the Poisson’s probability distribution, the sum of a greater number of voice connections returns average values that are closer to values returned by the proposed model. If we apply this model to describe VoIP networks that process a greater number of simultaneous voice connections, we can assume that the proposed model will return sufficiently exact assessment of an average delay in the network

References

[1]	VOZŇÁK, M. Voice over IP and Jitter Avoidance on Low Speed Links. In Proceedings RTT2002, Žilina, 2002. ISBN 80-227-1934-X.
[2]	HARDY, W. VoIP Service Quality. New York: McGraw-Hill, 2003. ISBN 0-07-141076-7.
[3]	HALÁS, M.; KYRBASHOV, B.; VOZŇÁK, M. Factors influencing voice quality in VoIP technology. In 9th International Conference on Informatics. Bratislava, 2007, p. 32-35. ISBN 978-80-969243-7-0.
[4]	VOZŇÁK, M.; HROMEK, F. Optimalization of VoIP service queues. In Proceedings RTT2008, Vyhne, Slovakia, 2008. Bratislava: Slovak University of Technology. ISBN 978-80-227-2939-0.
[5]	GROSS, D.; HARRIS, C. Fundamentals of Queuing Theory. New York: John Wiley & Sons, 1998. ISBN 0-471-17083-6.
[6]	BERGIDA, S.; SHAVITT, Y. Analysis of shared memory priority queues with two discard levels. In IEEE Israel Conference, 2006, p. 42-46. ISBN 1-4244-0230-1
[7]	MARIANOV, V.; SERRA, D. Location Models for Airline Hubs Behaving as M/D/c Queues. Available online.
[8]	VOZŇÁK, M.; HROMEK, F. Analytic model of a delay variation valid for the RTP. In LHOTKA, L.; SATRAPA, P. Networking Studies II: Selected Technical Reports. Praha: CESNET, 2008, p.103-113. ISBN 978-80-254-2151-2. Available online.
[9]	HAMPL, P. Kendallova klasifikace obsluhových systémů.Access Server, 2005. ISSN 1214-9675. Available online.
[10]	ZÍTEK, F. Ztracený čas: Elementy teorie hromadné obsluhy. Praha: Academia, 1969.
[11]	HALÁS, M. Optimalizácia hlasovej prevádzky s ohľadom na kvalitu hovoru v sieťach s technológiou VoIP. Doctoral Thesis, 2006.
[12]	HROMEK, F. Optimalizace obsluhy RTP front. Doctoral Thesis, Ostrava, 2008.