The performance of simple routing algorithms that drop packets

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The performance of simple routing algorithms that drop packets

Full text

Pdf (1.33 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures table of contents

Newport, Rhode Island, United States

Pages: 159 - 169

Year of Publication: 1997

ISBN:0-89791-890-8

Authors

Suprakash Datta	Department of Computer Science, Univ. of Massachusetts, Amherst, MA
Ramesh Sitaraman	Department of Computer Science, Univ. of Massachusetts, Amherst, MA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 10, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258492.258508 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Ale82	R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
	Bat68	K. Batcher. Sorting networks and their applications. In Proceedings of AFIPS Spring Joint Computing Conference, volume 32, pages 307- 314, 1968.
	BG87	Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
	BFU96	A. Z. Broder , A. M. Frieze, A general approach to dynamic packet routing with bounded buffers, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.390, October 14-16, 1996
	CadHSV96	Robert Cypher , Friedhelm Meyer auf der Heide , Christian Scheideler , Berthold Vöcking, Universal algorithms for store-and-forward and wormhole routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.356-365, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237982]
	CLR92	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	dB58	N.G. de Bruijn. Asymptotic Methods in Analysis. Interscience Publishers, 1958.
	Gal96	R.G. Gallagher. Discrete Stochastic Processes. Kluwer Academic Publishers, 1996.
	Got87	A. Gottlieb. An overview of the NYU UI- tracomputer project. In J. J. Dongarra, editor, Experimental Parallel Computing Architectures, pages 25-95. North-Holland, 1987.
	GP93	S. Gianatti and A. Pattavina. Analytical models for the performance evaluation of banyan networks with shared queueing. In Proceedings of the IEEE GLOBECOM, volume 2, pages 860-866, 1993.
	GP94	Stefano Gianatti , Achille Pattavina, Performance analysis of ATM Banyan networks with shared queueing—part I: random offered traffic, IEEE/ACM Transactions on Networking (TON), v.2 n.4, p.398-410, Aug. 1994 [doi>10.1109/90.330420]
	Int91	Intel Corporation. Paragon XP/S Product Overview, 1991.
	Jen83	Y. Jenq. Performance analysis of a packet switch based on a single-buffered banyan network. IEEE Journal on Selected Areas in Communications, 1:1014-1021, December 1983.
	Koc88	R Koch. Increasing the size of a network by a constant factor can increase performance by more than a constant factor. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 221-230, October 1988.
	KS83	C.P. Kruskal and M. Snir. The performance of multistage interconnection networks for multiprocessors. IEEE 7#ns. on Computers, C- 32(12):1091-1098, December 1983.
	Lei92	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	Lei92a	Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129721]
	LMRR94	F. T. Leighton , Bruce M. Maggs , Abhiram G. Ranade , Satish B. Rao, Randomized routing and sorting on fixed-connection networks, Journal of Algorithms, v.17 n.1, p.157-205, July 1994 [doi>10.1006/jagm.1994.1030]
	MadHV95	F. Meyer auf der Heide and B. VScking. A packet routing protocol for arbitrary networks. In Proceedings of the I 2th S TA CS, pages 291- 302, 1995.
	Mer91	Arif Merchant, A Markov chain approximation for the analysis of banyan networks, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.60-67, May 21-24, 1991, San Diego, California, United States
	MS92	Bruce M. Maggs , Ramesh K. Sitaraman, Simple algorithms for routing on butterfly networks with bounded queues, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.150-161, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129728]
	NMT+91	T. Nakata, S. Matsushita, N. Tanabe, N. Kajihara, H. Onozuka, Y. Asano, and N. Koike. Parallel programming on Cenju: A multiprocessor system for modular circuit simulation. NEC Research # Development, 32(3):421-429, July 1991.
	Pat81	J.H. Patel. Performance of processor-memory interconnections for multiprocessors. IEEE Trans. on Computers, C-30(10), 1981.
	PBG+87	G.F. Pfister, W. C. Brantley, D. A. George, S. L. Harvey, W. J. Kleinfelder, K. P. McAuliffe, E. A. Melton, V. A. Norton, and J. Weiss. An introduction to the IBM Research Parallel Processor Prototype (RP3). In J. J. Dongaxra, editor, Experimental Parallel Computing Architectures, pages 123-140. North- Holland, 1987.
	Pip84	N. Pippenger. Parallel communication with limited buffers. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pages 127-136, October 1984.
	Ran91	Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
	RCG94	Reza Rooholamini , Vladimir Cherkassky , Mark Garver, Finding the right ATM switch for the market, Computer, v.27 n.4, p.16-28, April 1994 [doi>10.1109/2.274995]
	RMDL96	Ralf Rehrmann , Burkhard Monien , Reinhard Lüling , Ralf Diekmann, On the communication throughput of buffered multistage interconnection networks, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.152-161, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237521]
	SS89	T. Szymanski and S. Shaikh. Markov chain analysis of packet-switched banyans with arbitrary switch sizes, queue sizes, link multiplicities and speedups. In Proceedings of the IEEE INFOCOM '89, pages 960-971, April 1989.
	ST91	George D. Stamoulis , John N. Tsitsiklis, The efficiency of greedy routing in hypercubes and butterflies, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.248-259, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113402]
	TRH91	T.H. Theimer, E.P. Rathgeb, and M.N. Huber. Performance analysis of buffered banyan networks. IEEE Trans. on Communications, 39(2):269-277, February 1991.
	Tur93	J.S. Turner. Queueing analysis of buffered switching networks. IEEE Trans. on Communications, pages 412-420, February 1993.
	Upf84	Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]
	Val82	L.G. Valiant. A scheme for fast parallel communication SIAM J. Comput., 11 (2):350-361, May 1982.
	VB81	L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
	VS96	Christian Scheideler , Berthold Vöcking, Universal continuous routing strategies, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.142-151, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237519]
	YLL90	Hyunsoo Yoon, Performance Analysis of Multibuffered Packet-Switching Networks in Multiprocessor Systems, IEEE Transactions on Computers, v.39 n.3, p.319-327, March 1990 [doi>10.1109/12.48863]

CITED BY 2

	Analytically Modeling a Fault-Tolerant Messaging Protocol, IEEE Transactions on Computers, v.53 n.7, p.870-878, July 2004
	Jeremy Brown , J. P. Grossman , Tom Knight, A lightweight idempotent messaging protocol for faulty networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada

INDEX TERMS

Primary Classification:
C. Computer Systems Organization
C.2 COMPUTER-COMMUNICATION NETWORKS
C.2.1 Network Architecture and Design
Subjects: Packet-switching networks

Additional Classification:
B. Hardware
B.7 INTEGRATED CIRCUITS
B.7.2 Design Aids
Subjects: Placement and routing

C. Computer Systems Organization
C.2 COMPUTER-COMMUNICATION NETWORKS

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Routing and layout

G. Mathematics of Computing
G.4 MATHEMATICAL SOFTWARE
Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Standardization, Theory, Verification

Collaborative Colleagues:

Suprakash Datta: colleagues

Ramesh Sitaraman: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein

Adobe Acrobat

QuickTime

Windows Media Player

Real Player