Newsgroups: comp.parallel From: John.Bothner@si.sintef.no (John Bothner) Subject: pointers to queueing theory in general, & crossbar switches Organization: SINTEF SI, Oslo, Norway Date: Tue, 23 Aug 1994 08:43:00 GMT Message-ID: <33ccqk$jmt@fenrix.si.sintef.no> A few months ago I asked for pointers to queueing theory in general and specially for queueing theory applied to crossbar switches. I received only one reply, albeit a very good one. After a long leave of absence I feel it is about time I share such a list of pointers with the readers of comp.parallel. -- John Bothner ( John.Bothner@si.sintef.no ) ------------------------------------------------------- From: Jennifer Lynn Rexford Hello, I saw your posting about queueing theory and crossbar switches on comp.parallel. 1) Queueing theory in general In addition to Kleinrock's books ("Communication Nets: Stochastic Message Flow and Delay" and "Queueing Systems" [Vol I and II]): @article{nelson:93, author = "Randolph Nelson", title = "The Mathematics of Product Form Queueing Networks", volume = 25, number = 3, pages = "339--369", journal = "ACM Computing Surveys", month = SEP, year = 1993 } 2) Queueing theory and crossbar switches Seems most of the ATM papers just study the behavior of a single output line of the crossbar. Anyway, there are a ton of papers (particularly in the INFOCOM proceedings, IEEE Trans. on Communications, and certain issues of IEEE J. on Selected Areas in Comm.), but here are a few relevant papers: @article{hluchyj:88a, author = "Michael G. Hluchyj and Mark J. Karol", title = "Queueing in High-Performance Packet Switching", volume = "6", number = 9, pages = "1587--1597", journal = "IEEE Journal on Selected Areas in Communications", month = DEC, year = 1988 } @article{chen:91, author = "Jeane S.-C. Chen and Thomas E. Stern", title = "Throughput Analysis, Optimal Buffer Allocation, and Traffic Imbalance Study of a Generic Nonblocking Packet Switch", volume = 9, number = 3, pages = "439--449", journal = "IEEE Journal on Selected Areas in Communications", month = APR, year = 1991 } @inproceedings{eckberg:88, author = "A. Eckberg and T. -C. Hou", title = "Effects of Output Buffer Sharing on Buffer Requirements in an {ATDM} Packet Switch", booktitle = INFOCOM, pages = "5A.4.1--5A.4.8", month = MAR, year = 1988 } @article{fendick:89, author = "Kerry Fendick and Vikram Sakena and Ward Whitt", title = "Dependence in Packet Queues", volume = "37", number = 11, pages = "1173--1183", journal = "IEEE Trans. Communications", month = NOV, year = 1989 } @inproceedings{lau:93, author = "{Wing-cheong} Lau and {San-qi} Li", title = "Traffic Analysis in Large-Scale High-Speed Integrated Networks: Validation of Nodal Decomposition Approach", booktitle = INFOCOM, pages = "1320--1329", year = 1993 } 3) Queueing theory and mesh topologies @article{dally:90a, author = "William J. Dally", title = "Performance Analysis of k-ary n-cube Interconnection Networks", volume = "39", number = "6", pages = "775--785", journal = "IEEE Trans. Computers", month = jun, year = 1990 } @article{dolter:91, author = "J. W. Dolter and P. Ramanathan and K. G. Shin", title = "Performance Analysis of Virtual Cut-Through Switching in {HARTS}: A Hexagonal Mesh Multicomputer", volume = "40", number = 6, pages = "669--680", journal = "IEEE Trans. Computers", month = jun, year = 1991 } @inproceedings{kim:91a, author = "Jong Kim and Chita Das", title = "Modeling Wormhole Routing in a Hypercube", booktitle = "Proc. Int. Conf. on Distributed Computer Systems", pages = "386--393", month = may, year = 1991 } @article{abraham:89, dbasekey = "abraham:89", author = "Seth Abraham and Krishnan Padmanabhan", title = "Performance of the Direct Binary $n$-Cube Network for Multiprocessors", volume = 38, number = 7, pages = "1000--1011", journal = "IEEE Trans. Computers", month = jul, year = 1989 } @article{agarwal:91, author = "A. Agarwal", title = "Limits on Interconnection Network Performance", volume = "2", number = 4, pages = "398--412", journal = "IEEE Trans. Parallel and Distributed Systems", month = oct, year = 1991 } @inproceedings{abraham:90, author = "Seth Abraham and Krishnan Padmanabhan", title = "Constraint Based Evaluation of Multicomputer Networks", booktitle = "International Conference on Parallel Processing", pages = "I-521--I-525", year = 1990 } Anyway, I'm curious to see what other responses you get, particularly about analysis of mesh and k-ary n-cube networks. Good luck. -- Jennifer jrexford@eecs.umich.edu