Keywords

1 Introduction

Our research concerns the Next Generation Network (NGN) [1], which is a standardized network architecture based on the IP Multimedia Subsystem (IMS) [2] (hence the names “IMS-based NGN” and “IMS/NGN” are commonly used), proposed for fulfilling the needs of current and future information society concerning delivering multimedia services. For a commercial success this new concept of telecommunication network should be properly designed, to guarantee the values of quality parameters, which are satisfactory for users (e.g. standardized call processing performance parameters [3, 4], which include mean Call Set-up Delay E(CSD) mean Call Disengagement Delay E(CDD)). To achieve this aim, proposition and application of appropriate traffic models is necessary to investigate the relations between network parameters and guaranteed quality parameters.

Performed review indicated that research on these aspects is in early phase and the majority of available traffic models do not include the operation of all standardized IMS/NGN elements (such as RACF, Resource and Admission Control Functions, responsible for resource control) or service scenarios and do not allow assessment of call processing performance parameters. The fact that IMS/NGN is now in the implementation stage and the problem of ensuring quality becomes more and more important led us to start investigations in this area.

In the paper we continue our research concerning the formerly proposed simulation [5] and analytical [6] traffic model of a single domain of IMS/NGN, which allow evaluation of E(CSD) and E(CDD). Our latest investigations focus on finding the best queuing system for the analytical model to achieve the best conformity with the experimental results provided by the simulation model. In the simulation model not theoretical queuing systems but the operation of real network elements and standardized call scenarios are accurately implemented (the simulated elements process SIP and Diameter messages according to standards). Consequently, the simulation model reflects the phenomena taking place in real IMS/NGN network and can be considered as a reference for evaluation of quality of the analytical results. In the previous stages of our research we examined the following queuing systems in our analytical model (as IMS/NGN elements are servers with lots of memory available for message queues and in all examined cases high queue lengths are very improbable – due to constraints on E(CSD) and E(CDD) – the analysis of the system can be readily done using queuing models with infinite waiting room capacity):

  • M/G/1 based on two moments of service distribution – used in our first approach [6] although were aware of the fact that intervals between messages at the inputs of IMS/NGN elements are generally not exponential; the results were under many conditions acceptable but poor conformity of calculations and simulations could be observed under high load and also when IMS/NGN elements were connected using links with relatively low bandwidth,

  • G/G/1 based on two or three moments of arrival distribution and two moments of service distribution [7] – used in the next step of our research; they did not significantly improve the results,

  • PH/PH/1 with arrival and service distributions represented by phase-type distributions [8,9,10,11] obtained using moment matching algorithms [12]; good conformity between analytical and simulation results were observable but we still did not find one universal queuing system for all considered data sets.

The completion of the above mentioned research, introduced in this paper, are investigations with PH/PH/1 queuing systems obtained using maximum likelihood and distance minimization fitting algorithms, which base on whole experimental histograms (not only on their moments) and due to this fact can lead to better results than for the previously examined queuing systems. In this paper the results for PH/PH/1 queuing systems obtained using maximum likelihood and distance minimization fitting algorithms are compared to the best results achieved in the previous stages. Moreover, we present the analysis of computational complexity for the queuing systems used in all stages of our research (M/G/1, G/G/1, PH/PH/1 with all investigated fitting algorithms), which has not been evaluated before. The rest of the text is organized as follows. Basic details about the proposed IMS/NGN traffic models are presented in Sect. 2. Elementary information about phase-type distributions, algorithms for fitting this type of distributions to arrival and service distributions in IMS/NGN and analyzing PH/PH/1 queuing systems is provided in Sect. 3. The results of the performed investigations are presented and discussed in Sect. 4. Summary and future work are described in Sect. 5.

2 Traffic Model of IMS/NGN

Our research concerns the ITU-T NGN architecture, which is the most advanced of all available NGN solutions [13]. Based on current standards and scientific work we have proposed an analytical [6] and simulation [5] model of a single ITU-T NGN domain, which contain the elements depicted in Fig. 1, performing the following roles [6, 7, 12]:

Fig. 1.
figure 1

Model of a single domain of IMS/NGN [6, 14, 15].

Full size image

  • User Equipments (UEs): user terminals generating call set-up and disengagement requests, registered in the domain,

  • P-CSCF (Proxy – Call Session Control Function): the server responsible for receiving all messages from UEs and forwarding them to the S-CSCF server,

  • S-CSCF (Serving – Call Session Control Function): the main server handling all calls,

  • RACF (Resource and Admission Control Functions): the unit of the transport stratum, which allocates resources for a new call and releases resources during call disengagement.

The above mentioned network elements participate in a standardized voice call scenario [14,15,16,17,18] depicted in Fig. 2. For resource operations (allocation, release) Diameter protocol [19] messages are exchanged between P-CSCF and RACF. Other elements communicate using SIP protocol [20]. More details regarding the call scenario are out of the scope of this paper and can be found in [6].

Fig. 2.
figure 2

Call set-up (messages 1–24) and call disengagement (messages 26–35) scenario in a single domain of IMS/NGN [6].

Full size image

Based on the t 1 –t 10 times illustrated in Fig. 2 and the definitions given by the ITU-T [3, 4], Call Set-up Delay (CSD) and Call Disengagement Delay (CDD) for a single call can be calculated as follows:

$$ CSD = \left( {t_{ 2} {-}t_{ 1} } \right) + \, \left( {t_{ 4} {-}t_{ 3} } \right) \, + \, \left( {t_{ 6} {-}t_{ 5} } \right) $$
(1)
$$ CDD = \left( {t_{ 8} {-}t_{ 7} } \right) \, + \, \left( {t_{ 10} {-}t_{ 9} } \right) $$
(2)

Formulas (1) and (2) are used to obtain the output variables evaluated by our traffic models, which are mean CSD, E(CSD), and mean CDD, E(CDD) [3, 4]. The analytical and simulation models represent different approaches to assess E(CSD) and E(CDD) (more details will be provided later). However, both of them use a similar set of the input variables, from which the most vital are [5, 6]:

  • λ INV : the intensity of aggregated call set-up requests (SIP INVITE messages from many terminals) generated by UE1 with exponential intervals,

  • T INV1 and T INV2 : the times of processing SIP INVITE messages by P-CSCF and S-CSCF correspondingly,

  • a k (k = 1, 2, …, 8): the factors determining times of processing other SIP and Diameter messages by CSCF servers according to Table 1,

    Table 1. Message processing times of CSCF servers.
    Full size table

  • T X : the time of processing messages by RACF,

  • lengths and bandwidths of optical links, lengths of transmitted messages: values necessary to calculate communication times between network elements.

The simulation model [5, 6], developed in the OMNeT++ framework [21], implements the operation of the network elements and call scenario depicted in Figs. 1 and 2. CSCF servers in the model include Central Processing Units (CPUs), which are responsible for handling messages incoming from other elements according to the assumed call scenario (Fig. 2). When CPUs are busy incoming messages are stored in CPU queues. Other network elements in the model respond with a particular delay (RACF responsible for resource allocation and release as well as UEs representing many user terminals). Each element of the model includes communication queues (one for each outgoing link), which buffer messages before sending them through links when links are busy. During simulation the t 1 –t 10 times (Fig. 2) are stored for all performed call scenarios and used to obtain CSD (1) and CDD (2). At the end of simulation E(CSD) and E(CDD) are calculated along with corresponding confidence intervals for a defined confidence level [5, 6].

In the analytical model mean values of theoretical delays introduced by the elements depicted in Fig. 1 are calculated and appropriately summed to obtain mean CSD and mean CDD [6, 7, 12]. These component delays include:

  • mean message waiting times in communication queues; for calculation of these times mathematical models of queuing systems are used,

  • message transmission times (message lengths divided by links bandwidths),

  • propagation times (equal to 5 μs/km – optical links are assumed),

  • mean message waiting times in CSCF servers CPU queues; for calculation of these times mathematical models of queuing systems are used,

  • message processing times by CSCF servers CPUs (Table 1) and RACF (T X input variable).

Due to the fact that the simulation model implements real IMS/NGN elements and call scenario, it reflects the phenomena occurring in the real network (message transmission, queuing, handling, etc.) and can be used to assess the quality of the analytical model based on theoretical calculations. More details about both models cannot be provided in this paper due to lack of space and can be found in [5,6,7, 12].

3 Phase-Type Distributions

Phase-type distributions [8,9,10,11] are probability distributions that result from a system of one or more inter-related Poisson processes occurring in sequence or phases. Special cases of continuous phase-type distributions are [8,9,10,11]: exponential distribution, Erlang distribution, Coxian distribution, Hyperexponential distribution (also called a mixture of exponential) and Hypoexponential distribution.

Our interest in phase-type distributions is related to their very important feature. As the set of phase-type distributions is dense in the field of all positive-valued distributions [8,9,10,11], they can represent or approximate (with any accuracy) any positive valued distribution. There are several algorithms for fitting different subsets of phase-type distributions to experimental data based on a specified number of first moments [8,9,10,11] or whole experimental histograms [11, 22,23,24].

Using such algorithms phase-type distributions can be fitted to all arrival and service distributions in the network [25]. After that, some characteristics of queues, like mean message waiting times (required in our research), can be calculated through analysis of PH/PH/1 queuing systems. Such analysis can be done by solving quasi-birth-and-death (QBD) Markov chains using matrix-analytic methods [26, 27]. Alternatively, formulas for analyzing queues with MAP (Markovian Arrival Process) or BMAP (Batch Markovian Arrival Process) distributions [28, 29] can be used as these types of distributions are supersets of phase-type distributions. Several solvers are available and we have tested two [30, 31] designed for the MATLAB environment used in our research. Both of the tested solvers provided very similar results, however the second one [31] was chosen for further use due to faster and direct calculation of mean waiting time [12].

As already mentioned, in this paper we perform investigations with PH/PH/1 queuing systems, in which phase-type distributions are fitted using maximum likelihood and distance minimization algorithms based on whole experimental histograms. The set of investigated algorithms included (the first three belong to the family of maximum likelihood algorithms, while the last two are distance minimization algorithms):

  • EMpht [11] – fitting general phase-type distributions using Expectation-Maximisation (EM) algorithm; in our research distributions of order 4 were fitted with the number of iterations equal to 6000; due to large computation times the number of samples of each experimental histogram was limited to 100000,

  • GFIT1 [22] – fitting Hyper-Erlang phase-type distributions using Expectation-Maximisation (EM) algorithm; the order of fitted distributions was set to 4; the number of samples of each experimental histogram was limited to 1000000,

  • GFIT2 [22] – the same algorithm as in GFIT1, however, here distributions of order 10 were fitted and the number of samples of each experimental histogram was limited to 700000,

  • PhFit1 [24] – fitting acyclic phase-type distributions using distance minimization algorithm; distributions of order 4 were fitted with total number of iterations equal to 3000 (3 rounds with 1000 iterations); the investigated distance metric was relative entropy; the number of samples of each experimental histogram was limited to 200000,

  • PhFit3 [24] – the same algorithm as in PhFit1, however, here distributions of order 10 were fitted and the number of samples of each experimental histogram was limited to 100000.

The number of iterations was chosen experimentally for each of the algorithms according to its convergence speed.

To apply the above mentioned fitting algorithms in the analytical model, a full description of arrival and service distributions for all IMS/NGN elements was necessary. This was not a problem for service distributions as they result from times of processing individual messages by network elements (defined by the input variables; for links they are determined by message lengths and link bandwidths) and the set of messages handled by each element (given by the assumed call scenario).

When it comes to arrival distributions, only theoretical intensity of messages handled by all networks elements is known from the call scenario and λ INV . Therefore, in this case phase-type distributions were fitted to experimental histograms recorded using the simulation model [25]. The results of the performed investigations are described in the next section.

4 Results

In order to compare the latest E(CSD) and E(CDD) results with these obtained in our previous papers [6, 7, 12], the same input data sets (presented in Table 2) were used. We also assumed identical message lengths (Table 3) as well as the a k factors: a 1  = 0.2, a 2  = 0.2, a 3  = 0.6, a 4  = 0.3, a 5  = 0.6, a 6  = 0.3, a 7  = 0.6, a 8  = 0.6 (Table 1).

Table 2. Input data sets.
Full size table
Table 3. Message lengths [32].
Full size table

The values of the input variables were taken according to current research (e.g. message lengths, which were measured experimentally in paper [32]) and our experience regarding telecommunication networks (e.g. the length of 300 km assumed for all links represents a typical distance between larger cities in Poland). Due to the fact that in our traffic models quite a large number of the input variables is used (Sect. 2), in the research presented in this paper we focused on call set-up request intensity, which is a typical and very commonly investigated parameter for telecommunication networks. Additionally, we examined different parameters of links (length and bandwidth), which have a significant impact on the final results.

As already mentioned in Sect. 3, in the research described in this paper phase-type distributions were fitted to message arrival and service distributions for all network elements, using maximum likelihood and distance minimization algorithms. In the next step mean message waiting times were calculated through analysis of PH/PH/1 queuing systems. The resultant mean waiting times were applied to compute the considered total system responses – E(CSD) and E(CDD).

Apart from fitting phase-type distributions to both arrival and service distributions of all elements (PH/PH/1 queuing systems), we also assumed that either arrival or service distributions are exponential (special cases of phase-type distributions), which resulted in M/PH/1 and PH/M/1 queuing systems correspondingly.

The above mentioned computations required full description of arrival and service distributions for all network elements. As arrival distributions are not fully described by the input variables (Sect. 3), they were obtained experimentally, using our simulation model. The simulations were performed with the following parameters [7, 12]:

  • warm-up period: 1500 s,

  • 5 measurement periods,

  • 0.95 confidence level,

  • simulation is finished when confidence intervals for E(CSD) and E(CDD) do not exceed 5% of mean Call Set-up Delay and mean Call Disengagement Delay or when total simulation time exceeds 10000 s; with such stop conditions at least 10000 message inter-arrival times were obtained during each simulation.

The results obtained for data sets 1a–1c (Table 2) are presented in Figs. 3, 4 and 5 as E(CSD) and E(CDD) versus call set-up request intensity curves. In each subfigure (Figs. 3, 4 and 5 contain six subfigures) we present results of simulations, calculations using M/G/1 queuing systems (our initial approach [6]) and analytical approaches based on phase type distributions (PH/PH/1, PH/M/1, M/PH/1) obtained using maximum likelihood and distance minimization algorithms (Sect. 3). The names of the fitting algorithms are included in legends (after colons).

Fig. 3.
figure 3

Results for data set 1a (no links); left: PH/PH/1 queuing systems, center: PH/M/1 queuing systems, right: M/PH/1 queuing systems; results at the top refer to E(CSD) and at the bottom – to E(CDD).

Full size image
Fig. 4.
figure 4

Results for data set 1b (link length 300 km and bandwidth 10 Mbit/s); left: PH/PH/1 queuing systems, center: PH/M/1 queuing systems, right: M/PH/1 queuing systems; results at the top refer to E(CSD) and at the bottom – to E(CDD).

Full size image
Fig. 5.
figure 5

Results for data set 1c (link length 300 km and bandwidth 100 Mbit/s); left: PH/PH/1 queuing systems, center: PH/M/1 queuing systems, right: M/PH/1 queuing systems; results at the top refer to E(CSD) and at the bottom – to E(CDD).

Full size image

Generally, it can be noticed that conformity of calculations and simulations of call processing performance parameters is dependent on many factors, including queuing systems used in the analytical model (Figs. 3, 4 and 5). Very important is also call set-up request intensity as well as available link bandwidth (links involve communication queues, which load is related to message intensity and link bandwidth; in data set 1a network elements are connected directly without links, thus, there are no communication queues).

We can observe that the relations between analytical and simulation results are similar for E(CSD) and E(CDD), when the same queuing systems are investigated. However, E(CSD) values are always larger than E(CDD), since the process of call set-up is much more complicated, comparing to call disengagement, and involves more messages. For each analyzed data set (Table 2) PhFit1 and PhFit3 algorithms give analytical results very far from simulations and other calculations. This rule applies especially for PH/PH/1 and M/PH/1 queuing systems with PhFit1 and PhFit3 algorithms. As a result, these algorithms are not useful in practice.

Based on Figs. 3, 4 and 5, it can be also noticed that in the majority of analyzes cases PH/M/1 queuing systems overestimate E(CSD) and E(CDD), while M/PH/1 queuing systems give results very similar to M/G/1 (this does not apply to PhFit1 and PhFit3 algorithms).

In order to thoroughly examine the subject of the paper, we have also done some more extended research with the root-mean-square error (RMSE) [7, 12] defined as follows:

$$ {\text{RMSE}} = \sqrt {\mathop E\limits_{{\lambda_{INV} \in \varLambda }} \left( {Y_{\text{simulation}} - Y_{\text{analytical}} } \right)^{2} } , $$
(3)

where Y is either E(CSD) or E(CDD) and E() is the averaging operator over a particular set of call set-up request intensities λ INV  ∈ Λ. To investigate different network conditions, for all data sets the following sets of λ INV were assumed [7, 12]:

  • “green” – IMS/NGN elements are low loaded and E(CSD), E(CDD) change very little with call set-up request intensity (λ INV  = 20, 60, 100 [1/s]),

  • “yellow” – IMS/NGN elements are quite highly loaded and E(CSD), E(CDD) start noticeably increasing with call set-up request intensity (λ INV  = 130, 160, 190 [1/s]),

  • “red” – IMS/NGN elements are overloaded and E(CSD), E(CDD) start going to infinity (λ INV  = 205, 220, 225 [1/s]),

  • “gr-yel” – the set including all call set-up request intensities from the “green” set and almost all call set-up request intensities from the “yellow” set (λ INV  = 20, 60, 100, 130, 160 [1/s]),

  • “all” – the set containing all call set-up request intensities from the “green”, “yellow” and “red” sets (λ INV  = 20, 60, 100, 130, 160, 190, 205, 220, 225 [1/s]).

The results of RMSE computations are presented in Tables 4, 5 and 6. The RMSE values were calculated for the analytical results presented in Figs. 3, 4 and 5 as well as for other queuing systems investigated in our previous papers – G/G/1 based on moments [7] (“G/G/1” in Tables 4, 5 and 6), PH/PH/1 with phase-type distributions obtained using moment matching algorithms [12] (“PH/PH/1 moments” in Tables 4, 5 and 6). Two best results for each of these previous queuing systems are included along with the names of G/G/1 formulas and PH/PH/1 fitting algorithms based on moments. The names are provided in the brackets below the results. In each column of Tables 4, 5 and 6 we marked two best (bold and underlined font) and two worst RMSE results (bold and italic font with gray background).

Table 4. RMSE for data set 1a (no links).
Full size table
Table 5. RMSE for data set 1b (link length 300 km and bandwidth 10 Mbit/s).
Full size table
Table 6. RMSE for data set 1c (link length 300 km and bandwidth 100 Mbit/s).
Full size table

The obtained RMSE values demonstrate that for various IMS/NGN parameters the best analytical E(CSD) and E(CDD) results can be achieved using different queuing systems (PH/PH/1 with phase-type distributions based on whole experimental histograms or only on their moments; G/G/1; M/G/1). Moreover, particular fitting algorithms for PH/PH/1 and G/G/1 formulas offer different efficiency. It is also important that often several of the above mentioned approaches offer very good performance (RMSE about 0.5 ms or even smaller), however, our aim is to find the best one.

In the majority of cases PH/PH/1 queuing systems (and their special cases – PH/M/1, M/PH/1) with proper fitting algorithms based on whole experimental histograms (EMpht, GFIT1, GFIT2) are the best or almost the best in terms of RMSE. However, the differences to the other queuing systems are often minimal. To decide which queuing system is the most suitable for IMS/NGN, we also investigated computational complexity (the time required to obtain analytical results for particular queuing systems). It is especially important in engineering applications, in which both accuracy and complexity count. In the next part we present some details about calculation times in the analytical model for one data set (Intel Core i7-2670QM CPU 8 × 2.20 GHz, 8 GB RAM, Windows 7 Professional SP1 64-bit):

  • for M/G/1 [6] computations are the fastest of all (several seconds) and require only the input variables (there is no need to use experimental histograms),

  • for G/G/1 [7] computations last about one minute (experimental histograms are needed to obtain second and third moments of arrival distributions, which are used in calculations),

  • for PH/PH/1 (and their special cases – PH/M/1, M/PH/1) with moment matching algorithms [12] computations take from one to several minutes (experimental histograms are needed to obtain second, third, fourth and fifth moments of arrival distributions, which are used in calculations),

  • PH/PH/1 (and their special cases – PH/M/1, M/PH/1) with maximum likelihood and distance minimization fitting algorithms are the worst case; fitting phase-type distributions to whole experimental histograms lasts from 30 min to several hours with parameters of the algorithms described in the previous section; therefore, fitting was performed offline and its results were saved to disk for further use.

Taking into account all the aspects presented in the previous part of this section (accuracy and complexity), we propose to use the following queuing systems in the analytical model of a single domain of IMS/NGN. For data sets 1a (no links; Table 4) and 1c (links with relatively high bandwidth; Table 6) we suggest using simple M/G/1 queuing systems, which give acceptable results (comparable to the best results), when “green” and “yellow” sets of λ INV are considered. For “red” and “all” sets of call set-up request intensity PH/M/1 queuing systems are the best.

When links with relatively low bandwidth are used (data set 1b; Table 5) the situation is different. PH/PH/1 queuing systems give the best results for “green” and “yellow” sets of λ INV . For “red” and “all” the smallest and very comparable RMSE values are offered by M/G/1 and M/PH/1 queuing systems. Due to much simpler calculations, we propose to use M/G/1.

For the above mentioned PH/PH/1 and PH/M/1 queuing systems RMSE results obtained using maximum likelihood and distance minimization algorithms operating on whole experimental histograms are in most cases not significantly better than for algorithms based only on moments [12]. As only slightly better results do not compensate for the high computational complexity (many hours of calculations for maximum likelihood and distance minimization algorithms), for engineering purposes more applicable are moment matching algorithms.

The necessity to choose different queuing systems in the analytical traffic model for different data sets and call set-up request intensities results from the complexity of IMS/NGN elements and call scenario. In the network there are many instances of call scenarios performed simultaneously, each of them concern sending and processing a set of signaling messages (Fig. 2). During a single instance most of the network elements is used several times. Our previous research [25] indicated that in many cases even a small change in load of one IMS/NGN element results in modification of types of message inter-arrival time distributions in the whole system. Consequently, it is very difficult to select a single queuing system, which would be efficient for all sets of investigated input variables.

5 Conclusions and Future Work

In the paper we continue our work on analytical and simulation traffic model of a single domain of IMS/NGN. Our aim is to find the best queuing system for the analytical model, to achieve possibly the best conformity with experimental results. These are provided by our simulation model, which does not implement theoretical queuing systems, but reflects the operation of real IMS/NGN network elements and standardized call scenarios.

In this paper investigations using PH/PH/1 queuing systems (and their special cases – PH/M/1, M/PH/1) are performed, in which arrival and service distributions are represented by phase-type distributions obtained using maximum likelihood and distance minimization algorithms. The obtained results are compared to these calculated using previously investigated queuing systems (M/G/1; G/G/1 based on two or three moments of arrival distribution and two moments of service distribution; PH/PH/1 with phase-type distributions obtained using moment matching algorithms). The compared parameters are total system responses – mean Call Set-up Delay E(CSD) as well as mean Call Disengagement Delay E(CDD), standardized by the ITU-T.

The performed research demonstrates that performance of the tested queuing systems in IMS/NGN depends on several network parameters, including load of network elements and links (for links load results from message intensity and available bandwidth). Often for the assumed set of parameters more than one of the investigated queuing systems offer accuracy, which can be considered as good or even very good. However, due to specific nature of IMS/NGN elements and call scenario, it is very difficult to point one universal queuing system, appropriate for all sets of network parameters.

Apart from accuracy, in engineering applications very important is also computational complexity (the time necessary to obtain analytical results for particular queuing system), which has not been analyzed in our previous papers. Considering both accuracy and complexity, and assuming that network is not overloaded (“green” and “yellow” sets of call set-up request intensity; Sect. 4), we suggest using M/G/1 and PH/PH/1 queuing systems in the analytical model of a single domain of IMS/NGN. The first type of queuing systems should be applied when IMS/NGN elements are connected directly or when links with relatively high bandwidth are used (data sets 1a, 1c; Table 2). The second one performs the best for links with relatively low bandwidth (data set 1b; Table 2). Due to smaller time necessary to fit phase-type distributions, for PH/PH/1 queuing systems we propose to use moment matching algorithms, which offer final results only slightly worse than maximum likelihood and distance minimization algorithms operating on whole experimental histograms.

In the next step we are going to perform similar research to that described in this paper, but in a multidomain IMS/NGN environment (appropriate analytical and simulation traffic models are under development [33,34,35]).