Asymptotics of stochastic networks with subexponential service times View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1999-12

AUTHORS

François Baccelli, Sabine Schlegel, Volker Schmidt

ABSTRACT

We analyse the tail behaviour of stationary response times in the class of open stochastic networks with renewal input admitting a representation as (max,+)-linear systems. For a K-station tandem network of single server queues with infinite buffer capacity, which is one of the simplest models in this class, we first show that if the tail of the service time distribution of one server, say server i0 ∈ {1,...,K}, is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until the completion of service at server j ⩾ i0 asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i0. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically tail-equivalent. This result is then extended to the asymptotics of general (max,+)-linear systems associated with i.i.d. driving matrices having one (or more) dominant diagonal entry in the subexponential class. In the irreducible case, the asymptotics are surprisingly simple, in comparison with results of the same kind in the Cramér case: the asymptotics only involve the excess distribution of the dominant diagonal entry, the mean value of this entry, the intensity of the arrival process, and the Lyapunov exponent of the sequence of driving matrices. In the reducible case, asymptotics of the same kind, though somewhat more complex, are also obtained. As a direct application, we give the asymptotics of stationary response times in a class of stochastic Petri nets called event graphs. This is based on the assumption that the firing times are independent and that the tail of the firing times of one of the transitions is subexponential and heavier than those of the others. An extension of these results to nonrenewal input processes is discussed. Asymptotics of queue size processes are also considered. More... »

PAGES

205-232

Journal

TITLE

Queueing Systems

ISSUE

1-3

VOLUME

33

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1019176129224

DOI

http://dx.doi.org/10.1023/a:1019176129224

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1009270978


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "\u00c9cole Normale Sup\u00e9rieure", 
          "id": "https://www.grid.ac/institutes/grid.5607.4", 
          "name": [
            "ENS, DMI, 45 rue d\u2019Ulm, 75005, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Baccelli", 
        "givenName": "Fran\u00e7ois", 
        "id": "sg:person.013374336621.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013374336621.69"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Ulm", 
          "id": "https://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Institute of Stochastics, University of Ulm, D-89069, Ulm, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schlegel", 
        "givenName": "Sabine", 
        "id": "sg:person.012660272622.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012660272622.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Ulm", 
          "id": "https://www.grid.ac/institutes/grid.6582.9", 
          "name": [
            "Institute of Stochastics, University of Ulm, D-89069, Ulm, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schmidt", 
        "givenName": "Volker", 
        "id": "sg:person.01051347101.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01051347101.48"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0304-4149(77)90047-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000866427"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s1446788700021340", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015226589"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s1446788700021224", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015796694"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6687(82)90021-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027824735"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00344720", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032951078", 
          "https://doi.org/10.1007/bf00344720"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-4149(98)00064-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035186611"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-4149(82)90013-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037852006"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-4062-4_12", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041461865", 
          "https://doi.org/10.1007/978-1-4612-4062-4_12"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-4062-4_12", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041461865", 
          "https://doi.org/10.1007/978-1-4612-4062-4_12"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01149173", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048779700", 
          "https://doi.org/10.1007/bf01149173"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01149173", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048779700", 
          "https://doi.org/10.1007/bf01149173"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1019128213295", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049672284", 
          "https://doi.org/10.1023/a:1019128213295"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1109088", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062865842"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1214/aoap/1028903373", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064397567"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1214/aoap/1034968069", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064397710"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/3212351", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1070226575"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/3212870", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1070227068"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/3214240", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1070228412"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1999-12", 
    "datePublishedReg": "1999-12-01", 
    "description": "We analyse the tail behaviour of stationary response times in the class of open stochastic networks with renewal input admitting a representation as (max,+)-linear systems. For a K-station tandem network of single server queues with infinite buffer capacity, which is one of the simplest models in this class, we first show that if the tail of the service time distribution of one server, say server i0 \u2208 {1,...,K}, is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until the completion of service at server j \u2a7e i0 asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i0. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically tail-equivalent. This result is then extended to the asymptotics of general (max,+)-linear systems associated with i.i.d. driving matrices having one (or more) dominant diagonal entry in the subexponential class. In the irreducible case, the asymptotics are surprisingly simple, in comparison with results of the same kind in the Cram\u00e9r case: the asymptotics only involve the excess distribution of the dominant diagonal entry, the mean value of this entry, the intensity of the arrival process, and the Lyapunov exponent of the sequence of driving matrices. In the reducible case, asymptotics of the same kind, though somewhat more complex, are also obtained. As a direct application, we give the asymptotics of stationary response times in a class of stochastic Petri nets called event graphs. This is based on the assumption that the firing times are independent and that the tail of the firing times of one of the transitions is subexponential and heavier than those of the others. An extension of these results to nonrenewal input processes is discussed. Asymptotics of queue size processes are also considered.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/a:1019176129224", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1048269", 
        "issn": [
          "0257-0130", 
          "1572-9443"
        ], 
        "name": "Queueing Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "33"
      }
    ], 
    "name": "Asymptotics of stochastic networks with subexponential service times", 
    "pagination": "205-232", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "2c29d83ed801c080af94bc837f0a60208d6c7e2ddc9869b64206109c560a25e6"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1019176129224"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009270978"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1019176129224", 
      "https://app.dimensions.ai/details/publication/pub.1009270978"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T21:41", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8687_00000536.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023%2FA%3A1019176129224"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1023/a:1019176129224'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1023/a:1019176129224'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1019176129224'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1019176129224'


 

This table displays all metadata directly associated to this object as RDF triples.

130 TRIPLES      21 PREDICATES      43 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1019176129224 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author Ne3a5e9d7a3b446bf84f85c0b4f39a6ad
4 schema:citation sg:pub.10.1007/978-1-4612-4062-4_12
5 sg:pub.10.1007/bf00344720
6 sg:pub.10.1007/bf01149173
7 sg:pub.10.1023/a:1019128213295
8 https://doi.org/10.1016/0167-6687(82)90021-x
9 https://doi.org/10.1016/0304-4149(77)90047-3
10 https://doi.org/10.1016/0304-4149(82)90013-8
11 https://doi.org/10.1016/s0304-4149(98)00064-7
12 https://doi.org/10.1017/s1446788700021224
13 https://doi.org/10.1017/s1446788700021340
14 https://doi.org/10.1137/1109088
15 https://doi.org/10.1214/aoap/1028903373
16 https://doi.org/10.1214/aoap/1034968069
17 https://doi.org/10.2307/3212351
18 https://doi.org/10.2307/3212870
19 https://doi.org/10.2307/3214240
20 schema:datePublished 1999-12
21 schema:datePublishedReg 1999-12-01
22 schema:description We analyse the tail behaviour of stationary response times in the class of open stochastic networks with renewal input admitting a representation as (max,+)-linear systems. For a K-station tandem network of single server queues with infinite buffer capacity, which is one of the simplest models in this class, we first show that if the tail of the service time distribution of one server, say server i0 ∈ {1,...,K}, is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until the completion of service at server j ⩾ i0 asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i0. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically tail-equivalent. This result is then extended to the asymptotics of general (max,+)-linear systems associated with i.i.d. driving matrices having one (or more) dominant diagonal entry in the subexponential class. In the irreducible case, the asymptotics are surprisingly simple, in comparison with results of the same kind in the Cramér case: the asymptotics only involve the excess distribution of the dominant diagonal entry, the mean value of this entry, the intensity of the arrival process, and the Lyapunov exponent of the sequence of driving matrices. In the reducible case, asymptotics of the same kind, though somewhat more complex, are also obtained. As a direct application, we give the asymptotics of stationary response times in a class of stochastic Petri nets called event graphs. This is based on the assumption that the firing times are independent and that the tail of the firing times of one of the transitions is subexponential and heavier than those of the others. An extension of these results to nonrenewal input processes is discussed. Asymptotics of queue size processes are also considered.
23 schema:genre research_article
24 schema:inLanguage en
25 schema:isAccessibleForFree false
26 schema:isPartOf N3c5e250964b94216afdc834a1aede3a0
27 Nbd6c8caa4dd24ae491944b8d3877251d
28 sg:journal.1048269
29 schema:name Asymptotics of stochastic networks with subexponential service times
30 schema:pagination 205-232
31 schema:productId N803bacdfedb944d4ac7d2f5f50289fef
32 N92368c73ed924e1a8c8f7fa4fd2b9f4a
33 Na8f5fa3935bf40c0baf1f60a5ee7bb07
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009270978
35 https://doi.org/10.1023/a:1019176129224
36 schema:sdDatePublished 2019-04-10T21:41
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher Neea741b75e8f4853a5e63f692793fccb
39 schema:url http://link.springer.com/10.1023%2FA%3A1019176129224
40 sgo:license sg:explorer/license/
41 sgo:sdDataset articles
42 rdf:type schema:ScholarlyArticle
43 N3c5e250964b94216afdc834a1aede3a0 schema:issueNumber 1-3
44 rdf:type schema:PublicationIssue
45 N803bacdfedb944d4ac7d2f5f50289fef schema:name dimensions_id
46 schema:value pub.1009270978
47 rdf:type schema:PropertyValue
48 N92368c73ed924e1a8c8f7fa4fd2b9f4a schema:name readcube_id
49 schema:value 2c29d83ed801c080af94bc837f0a60208d6c7e2ddc9869b64206109c560a25e6
50 rdf:type schema:PropertyValue
51 Na8f5fa3935bf40c0baf1f60a5ee7bb07 schema:name doi
52 schema:value 10.1023/a:1019176129224
53 rdf:type schema:PropertyValue
54 Nb9b145f04b6448f69ce25356fb9ceb3c rdf:first sg:person.01051347101.48
55 rdf:rest rdf:nil
56 Nbd6c8caa4dd24ae491944b8d3877251d schema:volumeNumber 33
57 rdf:type schema:PublicationVolume
58 Nc35c6d2a172047908a920ec766f215b7 rdf:first sg:person.012660272622.35
59 rdf:rest Nb9b145f04b6448f69ce25356fb9ceb3c
60 Ne3a5e9d7a3b446bf84f85c0b4f39a6ad rdf:first sg:person.013374336621.69
61 rdf:rest Nc35c6d2a172047908a920ec766f215b7
62 Neea741b75e8f4853a5e63f692793fccb schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
65 schema:name Mathematical Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
68 schema:name Statistics
69 rdf:type schema:DefinedTerm
70 sg:journal.1048269 schema:issn 0257-0130
71 1572-9443
72 schema:name Queueing Systems
73 rdf:type schema:Periodical
74 sg:person.01051347101.48 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
75 schema:familyName Schmidt
76 schema:givenName Volker
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01051347101.48
78 rdf:type schema:Person
79 sg:person.012660272622.35 schema:affiliation https://www.grid.ac/institutes/grid.6582.9
80 schema:familyName Schlegel
81 schema:givenName Sabine
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012660272622.35
83 rdf:type schema:Person
84 sg:person.013374336621.69 schema:affiliation https://www.grid.ac/institutes/grid.5607.4
85 schema:familyName Baccelli
86 schema:givenName François
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013374336621.69
88 rdf:type schema:Person
89 sg:pub.10.1007/978-1-4612-4062-4_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041461865
90 https://doi.org/10.1007/978-1-4612-4062-4_12
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/bf00344720 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032951078
93 https://doi.org/10.1007/bf00344720
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/bf01149173 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048779700
96 https://doi.org/10.1007/bf01149173
97 rdf:type schema:CreativeWork
98 sg:pub.10.1023/a:1019128213295 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049672284
99 https://doi.org/10.1023/a:1019128213295
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/0167-6687(82)90021-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1027824735
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/0304-4149(77)90047-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000866427
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/0304-4149(82)90013-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037852006
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/s0304-4149(98)00064-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035186611
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1017/s1446788700021224 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015796694
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1017/s1446788700021340 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015226589
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1137/1109088 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062865842
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1214/aoap/1028903373 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064397567
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1214/aoap/1034968069 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064397710
118 rdf:type schema:CreativeWork
119 https://doi.org/10.2307/3212351 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070226575
120 rdf:type schema:CreativeWork
121 https://doi.org/10.2307/3212870 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070227068
122 rdf:type schema:CreativeWork
123 https://doi.org/10.2307/3214240 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070228412
124 rdf:type schema:CreativeWork
125 https://www.grid.ac/institutes/grid.5607.4 schema:alternateName École Normale Supérieure
126 schema:name ENS, DMI, 45 rue d’Ulm, 75005, Paris, France
127 rdf:type schema:Organization
128 https://www.grid.ac/institutes/grid.6582.9 schema:alternateName University of Ulm
129 schema:name Institute of Stochastics, University of Ulm, D-89069, Ulm, Germany
130 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...