Abstract
Exact analysis of queueing networks under real traffic histograms becomes quickly intractable due to the state explosion. In this paper, we propose to apply the stochastic comparison method to derive performance measure bounds under histogram-based traffics. We apply an algorithm based on dynamic programming to derive bounding traffic histograms on reduced state spaces. We indeed obtain easier bounding stochastic processes providing stochastic upper and lower bounds on buffer occupancy histograms (queue length distributions) for finite queue models. We evaluate the proposed method under real traffic traces, and we compare the results with those obtained by an approximative method. Numerical results illustrate that the proposed method provides more accurate results with a tradeoff between computation time and accuracy. Moreover, the derived performance bounds are very relevant in network dimensioning.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Caida, traces of oc48 link at ames internet exchange (aix), accessed via datcat - internet data measurement catalog (April 24, 2003), http://imdc.datacat.org
Aït-Salaht, F., Cohen, J., Castel-Taleb, H., Fourneau, J.M., Pekergin, N.: Accuracy vs. complexity: the stochastic bound approach. In: 11th International Workshop on Disrete Event Systems, pp. 343–348 (2012)
Baccelli, F., Cohen, G., Olsder, G.J., Quadrat, J.-P.: Synchronization and Linearity: An Algebra for Discrete Event Systems. Willey, New York (1992)
Guérin, R., Orda, A.: Computing shortest paths for any number of hops. IEEE/ACM Trans. Netw. 10(5), 613–620 (2002)
Hernández-Orallo, E., Vila-Carbó, J.: Network performance analysis based on histogram workload models. In: MASCOTS, pp. 209–216 (2007)
Hernández-Orallo, E., Vila-Carbó, J.: Web server performance analysis using histogram workload models. Computer Networks 53(15), 2727–2739 (2009)
Hernández-Orallo, E., Vila-Carbó, J.: Network queue and loss analysis using histogram-based traffic models. Computer Communications 33(2), 190–201 (2010)
Kweon, S.-K., Shin, K.G.: Real-time transport of mpeg video with a statistically guaranteed loss ratio in atm networks. IEEE Transactions on Parallel and Distributed Systems, 12–4 (2001)
Muller, A., Stoyan, D.: Comparison Methods for Stochastic Models and Risks. Wiley, New York (2002)
Robertson, J.P.: The computation of aggregate loss distributions. In: Proceedings of the Casualty Actuarial Society, pp. 57–133 (1992)
Skelly, P., Schwartz, M., Dixit, S.S.: A histogram-based model for video traffic behavior in an atm multiplexer. IEEE/ACM Trans. Netw. 1(4), 446–459 (1993)
Sony, K.C., Cho, K.: Traffic data repository at the wide project. In: Proceedings of USENIX 2000 Annual Technical Conference: FREENIX Track, pp. 263–270 (2000)
Stewart, W.J.: Introduction to the numerical Solution of Markov Chains. Princeton University Press, New Jersey (1995)
Tancrez, J.-S., Semal, P., Chevalier, P.: Histogram based bounds and approximations for production lines. European Journal of Operational Research 197(3), 1133–1141 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aït-Salaht, F., Castel-Taleb, H., Fourneau, JM., Pekergin, N. (2013). Stochastic Bounds and Histograms for Network Performance Analysis. In: Balsamo, M.S., Knottenbelt, W.J., Marin, A. (eds) Computer Performance Engineering. EPEW 2013. Lecture Notes in Computer Science, vol 8168. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40725-3_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-40725-3_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40724-6
Online ISBN: 978-3-642-40725-3
eBook Packages: Computer ScienceComputer Science (R0)