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 <jrexford@eecs.umich.edu>


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