Abstract
Time-division multiplexing over packet-switched network (TDMoPSN) is an intermediate phase of transition from current synchronous TDM to future all-optical converged network. TDMoPSN is exclusively used to transport interactive voice traffic transparently over a PSN (e.g., IP, MPLS or Ethernet). The goal of this paper is to reduce rate-jitter that is introduced into a stream of packets carrying TDM payload. We have proposed two online algorithms, algorithm-A and algorithm-B, to reduce the rate-jitter and shown analytically that the rate-jitter achieved by algorithm-A is strictly less than the rate-jitter of online algorithm proposed by Mansour et al. [1]. We have used three stochastic processes, namely Poisson, Markov-modulated Poisson process (MMPP) and an arrival process with Pareto-distributed inter-arrival times (see [2–4]) for modeling the arrival of TDM packets (say, IP packets with single or many TDM frames as payloads) at the destination. We undertook statistical analysis of the proposed algorithms by modeling the jitter-buffer as \(M/\widetilde{D}/1/\, B_{on}\) and \(MMPP/\widetilde{D}/1/B_{on}\) queues, to derive steady-state queue-length distribution, mean waiting time and distribution of inter-departure times. We also simulate the most realistic queueing model \(Pareto/\widetilde{D}/1/B_{on}\) of our study and evaluated its performance with respect to the metrics: rate-jitter, mean waiting time, packet loss probability and steady-state queue-length distribution. Simulation results show that our proposed algorithms far outperforms the scheme proposed in [1]. We also present simulation results to verify the correctness of analytical queueing models. The algorithms proposed here are more general (for TDMoPSNs) and can be used to study TDMoIP, pseudowire, CES over metro Ethernet network (MEN), etc.
Similar content being viewed by others
References
Mansour, Y., Patt-Shamir, B.: Jitter control in QoS networks. IEEE/ACM Trans. Netw. 9(4), 492–502 (2001)
Fowler, T.B.: A short tutorial on fractals and internet traffic. Telecommun. Rev. 10, 1–14 (1999)
Fischer, M.J., Gross, D., Masi, D.M.B., Shortle, J.F.: Analyzing the waiting time process in internet queueing systems with the transform approximation method. Telecommun. Rev. 12, 21–32 (2001)
Paxson, V., Floyd, S.: Wide area traffic: the failure of poisson modeling. IEEE/ACM Trans. Netw. 3(3), 226–244 (1995)
Parikh, K., Kim, J.: TDM services over IP networks. IEEE Military Communications Conference (MILCOM), pp. 1–10 (2007)
Stein, Y., Schwartz, E.: Circuit extension over IP: an evolutionary approach to transporting voice and legacy data over IP networks, White paper. RAD Data Communications Inc (2001)
Stein, Y., Stroehlein, B.: Taking an Inside Look at TDMoIP: a tutorial, last accessed on Dec 20, (2013)
Stein, Y., Shashoua, R., Insler, R., Anavi, M.: Time Division Multiplexing over IP (TDMoIP), RFC 5087 (2007). http://tools.ietf.org/html/rfc5087
Giacomazzi, P.: Pseudowire, http://home.deib.polimi.it/giacomaz/multimedia_internet_lessons2012-2013MN_12_pseudowire. Last accessed on Dec 20, (2014)
Stein, Y.J., Druker, I.: IETF: draft—the effect of packet loss on voice quality for TDM over pseudowires (2003). https://tools.ietf.org/html/draft-stein-pwe3-tdm-packetloss-01
Elbatt, T.A., El-Henaoui, S., Shaheen, S.: Jitter recovery strategies for multimedia traffic in ATM networks. In: Proceedings of GLOBECOM’96, 2, pp. 1202–1206, (1996)
Zhang, H., Keshav, S.: Comparison of rate-based services disciplines. In: Proceedings of ACM SIGCOMM, pp. 113–121, (1991)
Hay, D., Scalosub, G.: Jitter regulation for multiple streams. ACM Trans. Algorithms, 6(1), Article 12, 12.1–12.19, (2009). doi:10.1145/1644015.1644027
Yan, Z., Yih-Chyun, J.: Performance analysis of adaptive timing method for voice over ATM using queuing models. In: Proceedings of Winter International Symposium on Information and Communication Technologies (WISICT’04), 1–8 (2004)
Sriram, K., Lucatoni, D.M.: Traffic smoothing effects of bit dropping in a packet voice multiplexer. IEEE Trans. Commun. 37(7), 703–712 (1989)
Choi, B.D., Choi, D.I.: Queueing system with queue length dependent service times and its application to cell discarding scheme in ATM networks. In: Proceedings of IEE, 5–11 (1996)
Sikha, M., Manivasakan, R.: Novel rate-jitter control algorithms for TDMoIP. IEEE \(19^{th}\) National Conference on Communications (2013)
Sikha, M.B., Rathinam, M.: Novel rate-jitter control algorithms modeling and analysis, The Sixth International Conference on Communication Theory, Reliability, and Quality of Service, pp. 22–28 (2013)
Gupta, U.C., Samanta, S.K., Goswami, V.: Analysis of a discrete-time queue with load dependent service under discrete-time Markovian arrival process. J. Korean Stat. Soc. 43(4), 545–557 (2014)
Andersen, A.T., Nielsen, B.F.: A Markovian approach for modeling packet traffic with long-range dependence. IEEE J. Sel. Areas Commun. 16(5), 719–732 (1998)
Muscariello, L., Mellia, M., Meo, M., Ajmone Marsan, M., Lo Cigno, R.: Markov models of Internet traffic and a new hierarchical MMPP model. J. Comput. Commun. 28(16), 1835–1851 (2005)
Yoshihara, T., Kasahara, S., Takahashi, T.: Practical time-scale fitting of self-similar traffic with Markov-modulated Poisson process. Telecommun. Syst. 17(1–2), 185–211 (2001)
Nogueira, A., Salvador, P., Valadas, R., Pacheco, A.: Modeling self-similar traffic through markov modulated poisson processes over multiple time scales. In: Proceedings of 6th IEEE International Conference on High Speed Networks and Multimedia Communications (HSNMC’03) (2003)
Fischer, W., Meier-Hellstern, K.: The Markov-modulated poisson process (MMPP) cookbook. Perform. Eval. 18(2), 149–171 (1993)
Yegenoglu, F., Jabbari, B.: Modeling of aggregated bursty traffic sources in ATM multiplexers. In: Proceedings of ICC’93, 1703–1707 (1993)
Yegenoglu, F., Jabbari, B.: Performance evaluation of MMPP/D/1/K queues for aggregate ATM traffic models. In: Proceedings of INFOCOM’93, 1314–1319 (1993)
Mirtchev, S., Goleva, R.: Evaluation of Pareto/D/1/K Queue by Simulation. \(6^{th}\) International Conference on Information Research and Applications-i.Tech 2008, Bulgaria, 45–52 (2008)
Fischer, M., Cart, H.: A method for analyzing congestion in pareto and related queues. Telecommun. Rev. 10, 15–28 (1999)
Koh, Y., Kim, K.: Loss probability behavior of pareto/M/1/K queue. IEEE Commun. Lett. 7(1), 39–41 (2003)
Koh, Y., Kim, K.: Evaluation of steady-state probability of pareto/M/1/K experiencing tail-raising effect. Lecture Notes in Computer Science 2720, 561–570 (2003)
Bertsekas, D.P., Tsitsiklis, J.N.: Introduction to Probability, 2nd edn, p. 430. Athena Scientific (2002)
Narayan Bhat, U.: An Introduction to Queueing Theory: Modeling and Analysis in Applications. Springer, Boston (2008)
Gross, D., Harris, C.M.: Fundamentals of Queueing Theory, 2nd edn. Wiley, New York (1985)
Blondia, C.: The N/G/l finite capacity queue. Commun. Stat. Stoch. Models 5(2), 273–294 (1989)
Neuts, Marcel F.: A versatile Markovian point process. J. Appl. Probab. 16(4), 764–779 (1979)
Heffes, H., Lucantoni, D.: A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance. Sel. Areas Commun. IEEE J. 4(6), 856–868 (1986)
Grassmann, W.K.: The GI/PH/1 queue: a method to find the transition matrix. Infor 20(2–3), 144–156 (1982)
Lucantoni, D.M., Ramaswami, V.: Efficient algorithms for solving the nonlinear matrix equations arising in phase type queues. Stoch. Models 1(1), 29–51 (1985)
Nogueira, A., Salvador, P., Valadas, R.: Fitting algorithms for MMPP ATM traffic models. In: Proceedings of the Broadband access conference, Cracow, 167–174 (1999)
Gross, D., Shortle, J.F., Fischer, M.J., Masi, D.M.B.: Difficulties in simulating queues with pareto service. In: Proceedings of the Winter Simulation Conference 1, 407–415 (2002)
Jain, R.: The Art of Computer Systems Performance Analysis. Wiley (2008)
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix 1: MMPP
MMPP can be viewed as a super-position of ’\(M\)’ independent Poisson processes, where switching among the processes is governed by an \(M\)-state CTMC, i.e., when the MMPP is in state \(i\), arrivals occur according to a Poisson process with rate \(\lambda _{i}\). The amount of time that the MMPP spends in state \(j\) is exponentially distributed with mean \(1/\mu _j\). If \(N_{MMPP}(t)\) and \(N_i(t)\) represent the counting process of MMPP and Poisson process with rate \(\lambda _i\), at any arbitrary time \(t\), then \( N_{MMPP}(t)=N_i(t)\), whenever \(J(t)=i\).
1.1 Derivation of average arrival rate \(\lambda ^{*}\) of MMPP
The MMPP is characterized by the UMC \(\{J(t),t\ge 0\}\), with transition rate matrix (infinitesimal generator matrix) \(\mathbf {Q}^{\mathbf {*}}\) and arrival rate matrix \(\varvec{{\varLambda }}\). For the four-state MMPP in Fig. 4, these matrices are given by,
and \(\varvec{{\varLambda }} = diag(\lambda _{0}, \lambda _{1}, \lambda _{2}, \lambda _{3})\). The steady-state probability vector \(\varvec{{\varPhi }}=(\phi _{0},\phi _{1},\phi _{2},\phi _{3})\) of the UMC \(\{J(t),t\ge 0\}\) can be obtained by solving the following equations:
By solving Eq. (47), we get the steady-state probability vector \(\varvec{{\varPhi }}\) as,
where \(\theta =\mu _0\mu _1(\mu _3+\mu _2p_{23})(1-p_{10})+\mu _2\mu _3(\mu _0+\mu _1p_{10})(1-p_{23})\).
Now, the average arrival rate \(\lambda ^{*}\) of MMPP can be calculated as, \(\lambda ^{*}=\varvec{{\varPhi } {\varLambda }\ e}\) and is given by,
1.2 Calculation of blocks of \(\mathbf {Q}\) matrix:
In this section, we would present an algorithm to compute the state transition probability transition matrix \(\mathbf {Q}\) [Eq. (13)] of the bivariate EMC \(\{(J_{k},Q^{D}_{k}),\, k\ge 0\}\). This means we need to compute the entries \(\mathbf {A}(n,s_m)\) and \(\mathbf {A}^{'}(n,s_1)\) of \(\mathbf {Q}\) matrix. We closely follow the procedure given in [34], to compute the matrix \(\mathbf {Q}\). The authors in [37, 38] presented a method to calculate the elements of blocks of matrix \(\mathbf {Q}\), corresponding to the buffer occupancy EMC in a queue with general independent arrival process as input and a general distribution for service times, namely \((GI/PH/1\ \text {and}\ PH/G/1\ \text {queues})\). In [34], elements of \(\mathbf {Q}\) matrix are computed for \(N/G/1/K\) queue, where the input is Neuts process (N-process [35]), which is a more general form of MMPP.
To start with, we note that in [34], the infinitesimal generator matrix \(\mathbf {Q}^{\mathbf {*}}\) is represented as, \(\mathbf {Q}^\mathbf {*}=\mathbf {T}+\mathbf {T}^\mathbf {o}\mathbf {A}^\mathbf {o}\), all (\(\mathbf {Q}^{\mathbf {*}}, \mathbf {T},\mathbf {T}^\mathbf {o}\ \text {and}\ \mathbf {A}^\mathbf {o}\)) are \(M\times M\) matrices. The columns of matrix \(\mathbf {T}^\mathbf {o}\) are the vector \(\bar{\mathbf {T}}^\mathbf {o}\) and \(\mathbf {A}^\mathbf {o}\!=\!diag(\beta _0,\!\beta _1,\ldots ,\!\beta _{M-1})\) and \(\bar{\varvec{\beta }}=(\beta _0,\beta _1,\ldots ,\beta _{M-1})\). For the four-state MMPP (Fig. 4), considered in this paper, these matrices are given by,
In [37, 38], it is proved that \(\mathbf {A}(n,s_m)\) can be written as an infinite sum of product of \(\gamma _l^{m}\) and \(\mathbf {K}\) as below:
where \(\gamma _l^{m}\) is defined in Eq. (37) and \(\eta =\underset{0\le i \le M-1}{\text{ max }}\Big (\big (-\mathbf {R}(0)\big )_{i,i}\Big )\).
Now, \(\mathbf {K}_n^l\) is recursively defined as,
where
In order to compute \(\mathbf {A}(n,s_m)\) in Eq. (49) numerically, a truncation method is proposed in [38], which is an approximation, as given under:
In this method, a minimum value of index \(N_0\) has to be found, such that \(\overset{N_0}{\underset{l=0}{\sum }}\gamma _l^{m} \ge 1-\epsilon \), for any given small \(\epsilon \) and \(\forall s_m\). Then, \(\mathbf {A}(n,s_m)\) is calculated as,
In order to compute first row of \(\mathbf {Q}\), we identify, \(\mathbf {A}^{'}(n,s_1) = {\mathbf {U A}}(n,s_1)\), where for MMPP input, \(\mathbf {U}=(\varvec{{\varLambda }}-\mathbf {Q}^{\mathbf {*}})^{-1}\varvec{{\varLambda }}\) [36]. Therefore, \(\mathbf {A}^{'}(n,s_1) = (\varvec{{\varLambda }}-\mathbf {Q}^{\mathbf {*}})^{-1}\varvec{{\varLambda }} \mathbf {A}(n,s_1)\). Similarly, the last column of \(\mathbf {Q}\) matrix is computed using Eq. (14).
Appendix 2: Generalized Pareto-distributed inter-arrival process
The CDF of GPD is given by,
Let,
substitute these in Eq. (51) to get a new form for GPD.
where \(\lambda \) is the average arrival rate, i.e., \(X_{a}=1/\lambda \) is the average IAT of GPD.
The variance \(v\) of the GPD can be shown as,
Variance is finite if \(\xi <0.5\). Now, by using Eqs. (52) and (54), we can derive the parameters of the GPD. They are given by,
The parameters in Eq. (55) are used to generate Pareto-distributed random numbers by using the inverse CDF method.
Rights and permissions
About this article
Cite this article
Sikha, M.B., Manivasakan, R. On the rate-jitter performance of jitter-buffer in TDMoPSN: study using queueing models with a state-dependent service. Photon Netw Commun 30, 108–130 (2015). https://doi.org/10.1007/s11107-015-0486-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11107-015-0486-2