Abstract
We consider a model to evaluate performance of streaming media over an unreliable network. Our model consists of a tandem of two fluid queues. The first fluid queue is a Markov modulated fluid queue that models the network congestion, and the second queue represents the play-out buffer. For this model the distribution of the total amount of fluid in the congestion and play-out buffer corresponds to the distribution of the maximum attained level of the first buffer. We show that, under proper scaling and when we let time go to infinity, the distribution of the total amount of fluid converges to a Gumbel extreme value distribution. From this result, we derive a simple closed-form expression for the initial play-out buffer level that provides a probabilistic guarantee for undisturbed play-out.





Similar content being viewed by others
References
Asmussen, S.: Busy period analysis, rare events and transient behavior in fluid flow models. J. Appl. Math. Stoch. Anal. 7(3), 269–299 (1994)
Asmussen, S.: Extreme value theory for queues via cycle maxima. Extremes 1(2), 137–168 (1998)
Asmussen, S., Bladt, M.: A sample path approach to mean busy periods for Markov-modulated queues and fluids. Adv. Appl. Probab. 26, 1117–1121 (1994)
Berman, S.: Limiting distribution of the maximum term in sequences of dependent random variables. Ann. Math. Stat. 33(3), 894–908 (1962)
Bléfari-Melazzi, N., Eramo, V., Listanti, M.: Dimensioning of play-out buffers for real-time services in a b-isdn. Comput. Commun. 21(11), 980–995 (1998). doi:10.1016/S0140-3664(98)00171-6. http://www.sciencedirect.com/science/article/pii/S0140366498001716
Bosman, J., van der Mei, R., Nunez-Queija, R.: A fluid model analysis of streaming media in the presence of time-varying bandwidth. In: 24th International Teletraffic Congress (ITC 2012). Krakow, Poland (2012)
Boxma, O., Dumas, V.: The busy period in the fluid queue. ACM SIGMETRICS Perform. Eval. Rev. 26(1), 100–110 (1998)
Cisco: Cisco Visual Networking Index: Forecast and Methodology, 20122017. Cisco White Paper, Cisco (2013)
Cisco: Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update 20122017. Cisco White Paper, Cisco (2013)
Claerbout, J.: Fundamentals of Geophysical Data Processing. Pennwell Books, Tulsa, OK (1985)
Dua, A., Bambos, N.: Buffer management for wireless media streaming. In: 2007 IEEE Global Telecommunications Conference, GLOBECOM ’07, pp. 5226–5230 (2007). doi:10.1109/GLOCOM.2007.991
Gantmacher, F.: Matrix Theory, vol. 1. AMS Chelsea, New York (2000)
Iglehart, D.: Extreme values in the gi/g/1 queue. Ann. Math. Stat. 43, 627–635 (1972)
Kim, T., Avadhanam, N., Subramanian, S.: Dimensioning receiver buffer requirement for unidirectional vbr video streaming over tcp. In: 2006 IEEE International Conference on Image Processing, pp. 3061–3064 (2006). doi:10.1109/ICIP.2006.313086
Kontovassilis, K., Tsiligaridis, J., Stassinopoulos, G.: Buffer dimensioning for delay- and loss-sensitive traffic. Comput. Commun. 18(5), 315–328 (1995). doi:10.1016/0140-3664(95)96833-C. http://www.sciencedirect.com/science/article/pii/014036649596833C
Kulkarni, V.: Fluid models for single buffer systems. In: Dshalalow, J. H. (ed.) Frontiers in Queueing: Models and Applications in Science and Engineering, pp. 321–338. CRC Press, Boca Raton, FL (1997)
Kulkarni, V., Tzenova, E.: Mean first passage times in fluid queues. Oper. Res. Lett. 30(5), 308–318 (2002)
Molazem Tabrizi, F., Peters, J., Hefeeda, M.: Dynamic control of receiver buffers in mobile video streaming systems. IEEE Trans. Mob. Comput. 12(5), 995–1008 (2013). doi:10.1109/TMC.2012.56
Norris, J.R.: Markov Chains. Cambridge University Press, Cambridge (2008)
Scheinhardt, W.: Markov-modulated and feedback fluid queues. Ph.D. thesis, Faculty of Mathematical Sciences, University of Twente, Enschede, The Netherlands (1998), http://www.ub.utwente.nl/webdocs/tw/1/t0000008.pdf
Scheinhardt, W., Zwart, B.: A tandem fluid queue with gradual input. Probab. Eng. Inf. Sci. 16(1), 29–45 (2002)
Sericola, B., Remiche, M.: Maximum level and hitting probabilities in stochastic fluid flows using matrix differential riccati equations. Methodol. Comput. Appl. Probab. 13(2), 307–328 (2011)
Wu, C., Chen, K., Huang, C., Lei, C.: An empirical evaluation of VoIP playout buffer dimensioning in Skype. In: Proceedings of ACM NOSSDAV 2009 (2009)
Zhang, L., Fu, H.: Dynamic bandwidth allocation and buffer dimensioning for supporting video-on-demand services in virtual private networks. Comput. Commun. 23(1415), 1410–1424 (2000). doi:10.1016/S0140-3664(00)00186-9. http://www.sciencedirect.com/science/article/pii/S0140366400001869
Acknowledgments
This work has been carried out in the context of the IOP GenCom Project Service Optimization and Quality (SeQual), which is supported by the Dutch Ministry of Economic Affairs, Agriculture and Innovation via its agency Agentschap NL.
Author information
Authors and Affiliations
Corresponding author
Appendix 1: Proof of Lemma 2
Appendix 1: Proof of Lemma 2
1.1 a: Preliminaries
Definition 8
Let \(A\) be a \(n\times m\) matrix:
Then any order-\(p\) minor of \(A\) will be denoted as:
provided that
The Binet–Cauchy formula on minors (see Gantmacher [12], page 12):
Let \(A\) be an \(m\times n\) matrix, \(B\) be a \(n\times q\) matrix and \(C\) be an \(m\times q\) matrix and \(C=AB\). Then any minor of \(C\) of order \(p\) is the sum of the products of all possible minors of \(A\) with order p and corresponding minors of the same order of \(B\):
Lemma 9
Let \(A\) be a \(n\times n\) matrix:
with:
Define \(\mathbf{A}\) as a \(n\times mn\) matrix with:
and \(\mathbf{I}\) is a \(mn\times n\) matrix (consisting of \(m\) \(n\times n\) identity matrices \(I_{n}\)) defined by:
Let \(\mathcal {V}\) be the set of subsets with exactly \(n-1\) elements from the set \(\{1,2,\ldots ,mn\}\) which is defined by:
Then the following holds:
with operators:
Operator \(F_{C}(\mathbf{A},v)\) selects the columns from \(\mathbf{A}\) according to vector \(v\), while operator \(F_{R}(\mathbf{I},v)\) selects rows from \(\mathbf{I}\) according to vector \(v\).
Proof
We write \(\sum \limits _{k=1}^{m}A_{k}=\mathbf{A}\mathbf{I}=\begin{bmatrix}A_{1}&A_{2}&\cdots&A_{k}\end{bmatrix}{\begin{bmatrix}I_{n}&I_{n}&\cdots&I_{n}\end{bmatrix}}^\mathrm{T}\). Using the Binet–Cauchy formula on minors, this can be rewritten to:
with:
\(\square \)
1.2 b: Proof of Lemma 2
Proof
Let \(\mathcal {V}\) be the set of subsets with exactly \(n-1\) elements from the set \(\{1,2,\ldots ,mn\}\) which is defined by:
We define \(\mathcal {P}\) as the set containing all k-permutations of \(n-1\) elements from the set \(\{1,\ldots ,n\}\). Furthermore we define \(\mathcal {C}\) as the set with all combinations of \(n-1\) elements from the set \(\{1,\ldots ,m\}\). For each combination \(c\in \mathcal {C}\) we define:
and thus:
Next we apply Lemma 9:
with
and
Because all matrices \(A_{k}\) have rank 1 the only adjugates that remain are those where there are \(n-1\) columns, at \(n-1\) different positions, from \(n-1\) different \(A_{k}\) matrices. All other combinations of columns result in a matrix with rank \(<n-1\) for which the minors of order \(n-1\) are zero. Thus the only elements from \(\mathcal {V}\) that contribute are those that correspond to any k-permutation of \(n-1\) columns from the set \(\{1,\ldots n\}\) where each column is selected from a distinct matrix \(A_{k},~k=1,\ldots ,m\). Note that each selected column remains exactly on its originating column position in the \(A_{k}\) matrix. As the only combinations consisting of \(n-1\) columns at unique positions from \(n-1\) unique matrices contribute to non-zero minors it holds that:
where \(v_{p}\) is the vector that selects the \(p_{i}\)th column from matrix \(A_{c_{i}}\):
We now define \(\mathcal {V}_{c}\) as be the set of subsets with exactly \(n-1\) elements from the set \(\{1,2,\ldots ,n(n-1)\}\) which is defined by:
For each combination \(c\in \mathcal {C}\) we can do the opposite: add again the terms (corresponding to zero valued minors) from the set \(\mathcal {V}_{c}\) corresponding to columns of \(\mathbf{A}_{c}=\begin{bmatrix}A_{c_{1}}&\cdots&A_{c_{n-1}}\end{bmatrix}\):
\(\square \)
Rights and permissions
About this article
Cite this article
Bosman, J.W., Núñez-Queija, R. A spectral theory approach for extreme value analysis in a tandem of fluid queues. Queueing Syst 78, 121–154 (2014). https://doi.org/10.1007/s11134-014-9395-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-014-9395-9
Keywords
- Fluid queue
- Extreme value theory
- Spectral analysis
- Tandem of fluid queues
- Gumbel distribution
- Binet-Cauchy formula
- Time varying service rates