{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T05:25:28Z","timestamp":1672377928295},"reference-count":6,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2011,9,15]]},"abstract":"\n We consider Jackson queueing networks (JQN) with finite capacity constraints and analyze the temporal computational complexity of sampling from their stationary distribution. In the context of perfect sampling, the monotonicity of JQNs ensures that it is the coupling time of extremal sample-paths. In the context of approximate sampling, it is given by the mixing time. We give a sufficient condition to prove that the coupling time of JQNs with M queues is\n O<\/jats:italic>\n (\n M<\/jats:italic>\n \u2211\n M<\/jats:sub>\n i=1<\/jats:sub>\n C\n i<\/jats:sub>\n ), where C\n i<\/jats:sub>\n denotes the capacity (buffer size) of queue\n i<\/jats:italic>\n . This condition lets us deal with networks having arbitrary topology, for which the best bound known is exponential in the C\n i<\/jats:sub>\n 's or in\n M<\/jats:italic>\n . Then, we use this result to show that the mixing time of JQNs is log\n 2<\/jats:sub>\n 1\/\u2208\n O<\/jats:italic>\n (\n M<\/jats:italic>\n \u2211\n M<\/jats:sub>\n i=1<\/jats:sub>\n C\n i<\/jats:sub>\n ), where \u2208 is a precision threshold. The main idea of our proof relies on a recursive formula on the coupling times of special sample-paths and provides a methodology for analyzing the coupling and mixing times of several monotone Markovian networks.\n <\/jats:p>","DOI":"10.1145\/2034832.2034847","type":"journal-article","created":{"date-parts":[[2011,9,20]],"date-time":"2011-09-20T13:48:54Z","timestamp":1316526534000},"page":"56-58","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["On the efficiency of perfect simulation in monotone queueing networks"],"prefix":"10.1145","volume":"39","author":[{"given":"Jonatha Anselmi","family":"Anselmi","sequence":"first","affiliation":[{"name":"Basque Center for Applied Mathematics, Bizkaia Technology Park, Derio, Spain"}]},{"given":"Bruno","family":"Gaujal","sequence":"additional","affiliation":[{"name":"INRIA and Grenoble University, Montbonnot SaintMartin, France"}]}],"member":"320","published-online":{"date-parts":[[2011,9,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.51.2.272.12778"},{"key":"e_1_2_1_2_1","volume-title":"Queueing Networks and Markov Chains","author":"Bolch G.","year":"2005","unstructured":"G. Bolch , S. Greiner , H. de Meer , and K. Trivedi . Queueing Networks and Markov Chains . Wiley-Interscience , 2005 . G. Bolch, S. Greiner, H. de Meer, and K. Trivedi. Queueing Networks and Markov Chains. Wiley-Interscience, 2005."},{"key":"e_1_2_1_3_1","volume-title":"Monte Carlo Simulation and Queues. Texts in Applied Mathematics","author":"Bremaud P.","year":"1999","unstructured":"P. Bremaud . Markov Chains , Gibbs Fields , Monte Carlo Simulation and Queues. Texts in Applied Mathematics . Springer-Verlag , Berlin- Heidelberg , 1999 . P. Bremaud. Markov Chains, Gibbs Fields, Monte Carlo Simulation and Queues. Texts in Applied Mathematics. Springer-Verlag, Berlin-Heidelberg, 1999."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/06064980X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/058"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2%3C223::AID-RSA14%3E3.0.CO;2-O"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2034832.2034847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T21:16:30Z","timestamp":1672348590000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2034832.2034847"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,15]]},"references-count":6,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,9,15]]}},"alternative-id":["10.1145\/2034832.2034847"],"URL":"http:\/\/dx.doi.org\/10.1145\/2034832.2034847","relation":{},"ISSN":["0163-5999"],"issn-type":[{"value":"0163-5999","type":"print"}],"subject":[],"published":{"date-parts":[[2011,9,15]]},"assertion":[{"value":"2011-09-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
