92:
971:
87:
Burke first published this theorem along with a proof in 1956. The theorem was anticipated but not proved by O’Brien (1954) and Morse (1955). A second proof of the theorem follows from a more general result published by Reich. The proof offered by Burke shows that the time intervals between
119:
of rate λ. Moreover, in the forward process the arrival at time t is independent of the number of customers after t. Thus in the reversed process, the number of customers in the queue is independent of the departure process prior to
471:
88:
successive departures are independently and exponentially distributed with parameter equal to the arrival rate parameter, from which the result follows.
522:
115:. Note that the arrival instants in the forward Markov chain are the departure instants of the reversed Markov chain. Thus the departure process is a
127:
This proof could be counter-intuitive, in the sense that the departure process of a birth-death process is independent of the service offered.
811:
406:
728:
587:
993:
998:
799:
515:
880:
769:
842:
143:
44:
480:
146:(MAP) and is conjectured that the output process of an MAP/M/1 queue is an MAP only if the queue is an M/M/1 queue.
685:
847:
652:
108:
1003:
974:
870:
657:
508:
958:
753:
953:
743:
592:
431:
784:
647:
774:
393:. The Kluwer International Series in Engineering and Computer Science. Vol. 91. pp. 313–341.
695:
614:
626:
943:
923:
918:
690:
467:
436:
154:
40:
948:
933:
900:
794:
449:
335:
300:
229:
194:
24:
74:
the number of customers in the queue is independent of the departure process prior to time
938:
837:
748:
738:
678:
402:
91:
789:
733:
619:
441:
422:
Bean, Nigel; Green, David; Taylor, Peter (1998). "The output process of an MMPP/M/1 queue".
394:
366:
327:
292:
263:
221:
186:
112:
100:
577:
56:
806:
673:
531:
116:
60:
20:
816:
779:
875:
150:
95:
Trace with departure/arrival instants highlighted in the forward/reversed time process.
268:
251:
987:
928:
913:
890:
702:
453:
233:
885:
712:
174:
198:
398:
908:
865:
832:
609:
604:
599:
582:
572:
560:
555:
550:
545:
136:
104:
52:
48:
631:
371:
354:
445:
190:
135:
The theorem can be generalised for "only a few cases," but remains valid for
707:
283:
O'Brien, G. G. (September 1954). "The
Solution of Some Queueing Problems".
331:
225:
304:
177:(1983). "A probabilistic look at networks of quasi-reversible queues".
36:
339:
318:
Morse, P. M. (August 1955). "Stochastic
Properties of Waiting Lines".
142:
It is thought that Burke's theorem does not extend to queues fed by a
67:
The departure process is a
Poisson process with rate parameter λ.
296:
500:
90:
504:
389:
Hui, J. Y. (1990). "Queueing for Multi-Stage Packet
Networks".
391:
Switching and
Traffic Theory for Integrated Broadband Networks
285:
Journal of the
Society for Industrial and Applied Mathematics
107:
is a reversible stochastic process. Consider the figure. By
212:
Burke, P. J. (1956). "The Output of a
Queuing System".
320:
Journal of the
Operations Research Society of America
99:
An alternative proof is possible by considering the
899:
858:
825:
762:
721:
666:
640:
538:
111:for reversibility, any birth-death process is a
516:
8:
473:Brownian Motion and Stochastic Flow Systems
256:Stochastic Processes and Their Applications
523:
509:
501:
435:
370:
355:"Waiting Times when Queues are in Tandem"
267:
245:
243:
250:O'Connell, N.; Yor, M. (December 2001).
252:"Brownian analogues of Burke's theorem"
179:IEEE Transactions on Information Theory
166:
59:in the steady state with arrivals is a
23:, a discipline within the mathematical
384:
382:
359:The Annals of Mathematical Statistics
7:
14:
479:. New York: Wiley. Archived from
970:
969:
424:Journal of Applied Probability
131:Related results and extensions
1:
800:Flow-equivalent server method
269:10.1016/S0304-4149(01)00119-3
149:An analogous theorem for the
881:Adversarial queueing network
770:Continuous-time Markov chain
399:10.1007/978-1-4615-3264-4_11
39:(stated and demonstrated by
843:Heavy traffic approximation
588:Pollaczek–Khinchine formula
144:Markovian arrival processes
45:Bell Telephone Laboratories
1020:
47:) asserting that, for the
16:Theorem in queueing theory
967:
848:Reflected Brownian motion
653:Markovian arrival process
871:Layered queueing network
658:Rational arrival process
191:10.1109/TIT.1983.1056762
139:and Geom/Geom/1 queues.
959:Teletraffic engineering
754:Shortest remaining time
372:10.1214/aoms/1177706889
113:reversible Markov chain
63:with rate parameter λ:
954:Scheduling (computing)
593:Matrix analytic method
446:10.1239/jap/1032438394
109:Kolmogorov's criterion
96:
33:Burke's output theorem
994:Single queueing nodes
785:Product-form solution
686:Gordon–Newell theorem
648:Poisson point process
539:Single queueing nodes
353:Reich, Edgar (1957).
94:
25:theory of probability
999:Probability theorems
812:Decomposition method
468:Harrison, J. Michael
332:10.1287/opre.3.3.255
226:10.1287/opre.4.6.699
103:and noting that the
944:Pipeline (software)
924:Flow control (data)
919:Erlang distribution
901:Information systems
691:Mean value analysis
214:Operations Research
155:J. Michael Harrison
949:Quality of service
934:Network congestion
795:Quasireversibility
775:Kendall's notation
97:
981:
980:
939:Network scheduler
838:Mean-field theory
749:Shortest job next
739:Processor sharing
696:Buzen's algorithm
679:Traffic equations
667:Queueing networks
641:Arrival processes
615:Kingman's formula
408:978-1-4613-6436-8
43:while working at
1011:
973:
972:
790:Balance equation
722:Service policies
620:Lindley equation
525:
518:
511:
502:
495:
494:
492:
491:
485:
478:
464:
458:
457:
439:
419:
413:
412:
386:
377:
376:
374:
350:
344:
343:
315:
309:
308:
280:
274:
273:
271:
247:
238:
237:
209:
203:
202:
171:
101:reversed process
1019:
1018:
1014:
1013:
1012:
1010:
1009:
1008:
1004:Queueing theory
984:
983:
982:
977:
963:
895:
854:
821:
807:Arrival theorem
758:
717:
674:Jackson network
662:
636:
627:Fork–join queue
566:Burke's theorem
534:
532:Queueing theory
529:
499:
498:
489:
487:
483:
476:
466:
465:
461:
421:
420:
416:
409:
388:
387:
380:
352:
351:
347:
317:
316:
312:
297:10.1137/0102010
282:
281:
277:
249:
248:
241:
211:
210:
206:
173:
172:
168:
163:
133:
117:Poisson process
85:
61:Poisson process
31:(sometimes the
29:Burke's theorem
21:queueing theory
17:
12:
11:
5:
1017:
1015:
1007:
1006:
1001:
996:
986:
985:
979:
978:
968:
965:
964:
962:
961:
956:
951:
946:
941:
936:
931:
926:
921:
916:
911:
905:
903:
897:
896:
894:
893:
888:
883:
878:
876:Polling system
873:
868:
862:
860:
856:
855:
853:
852:
851:
850:
840:
835:
829:
827:
826:Limit theorems
823:
822:
820:
819:
814:
809:
804:
803:
802:
797:
792:
782:
777:
772:
766:
764:
760:
759:
757:
756:
751:
746:
741:
736:
731:
725:
723:
719:
718:
716:
715:
710:
705:
700:
699:
698:
693:
683:
682:
681:
670:
668:
664:
663:
661:
660:
655:
650:
644:
642:
638:
637:
635:
634:
629:
624:
623:
622:
617:
607:
602:
597:
596:
595:
590:
580:
575:
570:
569:
568:
558:
553:
548:
542:
540:
536:
535:
530:
528:
527:
520:
513:
505:
497:
496:
459:
437:10.1.1.44.8263
414:
407:
378:
365:(3): 768–773.
345:
326:(3): 255–261.
310:
291:(3): 133–142.
275:
262:(2): 285–298.
239:
220:(6): 699–704.
204:
185:(6): 825–831.
165:
164:
162:
159:
153:was proven by
151:Brownian queue
132:
129:
84:
81:
80:
79:
68:
15:
13:
10:
9:
6:
4:
3:
2:
1016:
1005:
1002:
1000:
997:
995:
992:
991:
989:
976:
966:
960:
957:
955:
952:
950:
947:
945:
942:
940:
937:
935:
932:
930:
929:Message queue
927:
925:
922:
920:
917:
915:
914:Erlang (unit)
912:
910:
907:
906:
904:
902:
898:
892:
891:Retrial queue
889:
887:
884:
882:
879:
877:
874:
872:
869:
867:
864:
863:
861:
857:
849:
846:
845:
844:
841:
839:
836:
834:
831:
830:
828:
824:
818:
815:
813:
810:
808:
805:
801:
798:
796:
793:
791:
788:
787:
786:
783:
781:
778:
776:
773:
771:
768:
767:
765:
761:
755:
752:
750:
747:
745:
742:
740:
737:
735:
732:
730:
727:
726:
724:
720:
714:
711:
709:
706:
704:
703:Kelly network
701:
697:
694:
692:
689:
688:
687:
684:
680:
677:
676:
675:
672:
671:
669:
665:
659:
656:
654:
651:
649:
646:
645:
643:
639:
633:
630:
628:
625:
621:
618:
616:
613:
612:
611:
608:
606:
603:
601:
598:
594:
591:
589:
586:
585:
584:
581:
579:
576:
574:
571:
567:
564:
563:
562:
559:
557:
554:
552:
549:
547:
544:
543:
541:
537:
533:
526:
521:
519:
514:
512:
507:
506:
503:
486:on 2012-04-14
482:
475:
474:
469:
463:
460:
455:
451:
447:
443:
438:
433:
429:
425:
418:
415:
410:
404:
400:
396:
392:
385:
383:
379:
373:
368:
364:
360:
356:
349:
346:
341:
337:
333:
329:
325:
321:
314:
311:
306:
302:
298:
294:
290:
286:
279:
276:
270:
265:
261:
257:
253:
246:
244:
240:
235:
231:
227:
223:
219:
215:
208:
205:
200:
196:
192:
188:
184:
180:
176:
170:
167:
160:
158:
156:
152:
147:
145:
140:
138:
130:
128:
125:
123:
118:
114:
110:
106:
102:
93:
89:
82:
77:
73:
69:
66:
65:
64:
62:
58:
54:
50:
46:
42:
41:Paul J. Burke
38:
34:
30:
26:
22:
886:Loss network
817:Beneš method
780:Little's law
763:Key concepts
713:BCMP network
565:
488:. Retrieved
481:the original
472:
462:
427:
423:
417:
390:
362:
358:
348:
323:
319:
313:
288:
284:
278:
259:
255:
217:
213:
207:
182:
178:
169:
148:
141:
137:M/M/c queues
134:
126:
121:
98:
86:
75:
71:
32:
28:
18:
909:Data buffer
866:Fluid queue
833:Fluid limit
744:Round-robin
610:G/G/1 queue
605:G/M/1 queue
600:M/G/k queue
583:M/G/1 queue
578:M/M/∞ queue
573:M/M/c queue
561:M/M/1 queue
556:M/D/c queue
551:M/D/1 queue
546:D/M/1 queue
175:Walrand, J.
105:M/M/1 queue
57:M/M/∞ queue
53:M/M/c queue
49:M/M/1 queue
988:Categories
859:Extensions
632:Bulk queue
490:2011-12-01
430:(4): 998.
161:References
120:time
708:G-network
454:122137199
432:CiteSeerX
975:Category
470:(1985).
234:55089958
70:At time
305:2098899
37:theorem
35:) is a
452:
434:
405:
340:166559
338:
303:
232:
199:216943
197:
484:(PDF)
477:(PDF)
450:S2CID
336:JSTOR
301:JSTOR
230:S2CID
195:S2CID
83:Proof
734:LIFO
729:FIFO
403:ISBN
442:doi
395:doi
367:doi
328:doi
293:doi
264:doi
222:doi
187:doi
55:or
19:In
990::
448:.
440:.
428:35
426:.
401:.
381:^
363:28
361:.
357:.
334:.
322:.
299:.
287:.
260:96
258:.
254:.
242:^
228:.
216:.
193:.
183:29
181:.
157:.
124:.
51:,
27:,
524:e
517:t
510:v
493:.
456:.
444::
411:.
397::
375:.
369::
342:.
330::
324:3
307:.
295::
289:2
272:.
266::
236:.
224::
218:4
201:.
189::
122:t
78:.
76:t
72:t
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
