{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T23:10:36Z","timestamp":1648941036812},"reference-count":5,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2001,12]]},"abstract":"\n For a given\n k<\/jats:italic>\n \u2265 1, subintervals of a given interval\n[0,\n X<\/jats:italic>\n ] arrive at random and are accepted (allocated) so long\nas they overlap fewer than\n k<\/jats:italic>\n subintervals already accepted.\nSubintervals not accepted are cleared, while accepted subintervals\nremain allocated for random retention times before they are\nreleased and made available to subsequent arrivals. Thus, the\nsystem operates as a generalized many-server queue under a loss\nprotocol. We study a discretized version of this model that appears\nin reference theories for a number of applications; the one of most\ninterest here is linear communication networks, a model originated\nby Kelly [2]. Other applications include surface\nadsorption\/desorption processes and reservation systems [3, 1].\n <\/jats:p>\n \n The interval [0,\n X<\/jats:italic>\n ],\n X<\/jats:italic>\n an integer, is subdivided\nby the integers into slots of length 1. An\n interval<\/jats:italic>\n is\nalways composed of consecutive slots, and a configuration C of\nintervals is simply a finite set of intervals in [0,\n X<\/jats:italic>\n ]. A\nconfiguration C is\n admissible<\/jats:italic>\n if every non-integer point in\n[0,\n X<\/jats:italic>\n ] is covered by at most\n k<\/jats:italic>\n intervals in C. Denote\nthe set of admissible configurations on the interval [0,\n X<\/jats:italic>\n ]\nby\n \n C\n X<\/jats:sub>\n .\n <\/jats:italic>\n Assume that, for any integer point\n i,<\/jats:italic>\n intervals of length l with left endpoint\n i<\/jats:italic>\n arrive\nat rate \u03bb\n l<\/jats:sub>\n ; the arrivals of intervals at\ndifferent points and of different lengths are independent. A newly\narrived interval is included in the configuration if the resulting\nconfiguration is admissible; otherwise the interval is rejected. It\nis convenient to assume that the arrival rates \u03bb\n l<\/jats:sub>\n vanish for all but a finite number of lengths l, say\n\u03bb\n l<\/jats:sub>\n > 0, 1 \u2264 l \u2264\n L,<\/jats:italic>\n and\n\u03bb\n l<\/jats:sub>\n = 0 otherwise.\n <\/jats:p>\n \n The departure of intervals from configurations has a similar\ndescription: the flow of \"killing\" signals for intervals of length\nl arrive at each integer\n i<\/jats:italic>\n at rate \u00b5\n l<\/jats:sub>\n . If\nat the time such a signal arrives, there is at least one interval\nof length l with its left endpoint at\n i<\/jats:italic>\n in the\nconfiguration, then one of them leaves.\n <\/jats:p>\n \n Our primary interest is in steady-state estimates of the vacant\nspace, i.e., the total length of available subintervals\n kX<\/jats:italic>\n -\n\u2211l\n \n i<\/jats:italic>\n <\/jats:sub>\n , where the l\n \n i<\/jats:italic>\n <\/jats:sub>\n are the\nlengths of the subintervals currently allocated. We obtain explicit\nresults for\n k<\/jats:italic>\n = 1 and for general\n k<\/jats:italic>\n with all\nsubinterval lengths equal to 2, the classical\n dimer<\/jats:italic>\n case of\nchemical applications. Our analysis focuses on the asymptotic\nregime of large retention times, and brings out an apparently new,\nbroadly useful technique for extracting asymptotic behavior from\ngenerating functions in two dimensions.\n <\/jats:p>\n \n Our model, as proposed by Kelly [2], arises in a study of\none-dimensional communication networks (LAN's). In this\napplication, intervals correspond to the circuits connecting\ncommunicating parties and [0,\n X<\/jats:italic>\n ] represents the bus. Kelly's\nmain results apply to the case\n k<\/jats:italic>\n = 1 and to the case of\ngeneral\n k<\/jats:italic>\n with interval lengths governed by a geometric\nlaw.\n <\/jats:p>\n \n The focus here is on space utilization, so the results here add\nto the earlier theory in three principal ways. First, we give\nexpected vacant space for\n k<\/jats:italic>\n = 1, with special emphasis on\nsmall-\u00b5 asymptotics. Behavior in this regime is quite\ndifferent from that seen in the \"jamming\" limit (absorbing state)\nof the pure filling model (all \u00b5's are identically 0).\nSecond, the important dimer case of chemical applications, where\nall intervals have length 2, is covered. Finally, the approach of\nthe analysis itself appears to be new and to hold promise for the\nanalysis of similar Markov chains. In very broad terms, expected\nvacant space is expressed in terms of the geometric properties of a\ncertain plane curve defined by a bivariate generating function.\n <\/jats:p>","DOI":"10.1145\/507553.507565","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"28-29","source":"Crossref","is-referenced-by-count":0,"title":["Kelly's LAN model revisited"],"prefix":"10.1145","volume":"29","author":[{"given":"Yuliy","family":"Baryshnikov","sequence":"first","affiliation":[{"name":"Lucent Technologies, Murray Hill, NJ"}]},{"suffix":"Jr.","given":"E. G.","family":"Coffman","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}]},{"given":"Predrag","family":"Jelenkovi\u0107","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","first-page":"129","article-title":"Reservation probabilities","volume":"2","author":"Coffman E. G.","year":"1999","journal-title":"Adv. Perf. Anal."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176992089"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-7757(99)00409-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.61.5429"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/3214219"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/507553.507565","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T08:53:53Z","timestamp":1614848033000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/507553.507565"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12]]},"references-count":5,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2001,12]]}},"alternative-id":["10.1145\/507553.507565"],"URL":"http:\/\/dx.doi.org\/10.1145\/507553.507565","relation":{},"ISSN":["0163-5999"],"issn-type":[{"value":"0163-5999","type":"print"}],"subject":["Computer Networks and Communications","Hardware and Architecture","Software"],"published":{"date-parts":[[2001,12]]}}}