Principle for high speed network control: congestion-and deadlock-freeness, self-routing, and a single buffer per link

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Principle for high speed network control: congestion-and deadlock-freeness, self-routing, and a single buffer per link

Full text

Pdf (1.50 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the ninth annual ACM symposium on Principles of distributed computing table of contents

Quebec City, Quebec, Canada

Pages: 161 - 175

Year of Publication: 1990

ISBN:0-89791-404-X

Authors

Yoram Ofek	IBM T. J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY
Moti Yung	IBM T. J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 16, Citation Count: 12

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/93385.93414 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.

	1	A. Aggarwal, "A Comparative Study of X-Tree Pyramid, and Related machines," IEEE FOC$-~5, October 84, pp. 89-99.
	2	Baruch Awerbuch , Israel Cidon , Inder Gopal , Marc Kaplan , Shay Kutten, Distributed control for PARIS, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.145-159, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93412]
	3	P. Baron, "On Distributed Communication Networks," IEEE Trana. on Communicationl Systems, Vol. CS-12, No. 1-2, pp. 1-9, March 1964.
	4	Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
	5	I. Cidon and I. S. Gopal, "PARIS: An Approach to Integrated High-Speed Private Networks," Interna\|jonal Journal o~ Digital H Analog Cabled System,, Vol. 1, No. 2, pp. 77-86, April-June 1988.
	6	Israel Cidon , Yoram Ofek, Distributed Fairness Algorithms for Local Area Networks, Proceedings of the 3rd International Workshop on Distributed Algorithms, p.57-69, September 26-28, 1989
	7	I. Cidoa and Y. O\|ek, "MetaRing - A FUll-Duplex King with Fairness and Spatial P~euse," IBM R.esearch Report RC 14961, September !989, also INFOCOM'90.
	8	D. Cotne~, lnterne~t, oriing wiil~ TCP/IP, Prentice H~dt 1988.
	9	M. Gerla and L. Kleinrock, "Flow Control: A Comparative Survey", IJ~EE Trana. Commun., pp. 553-573, April 1980.
	10	Andrew R. Jacob, A survey of fast packet switches, ACM SIGCOMM Computer Communication Review, v.20 n.1, p.54-64, Jan. 1990 [doi>10.1145/86587.86590]
	11	M. T. Liu and D. M. Rouse, "A Study of Ring Networks," Proc. IPIP WG6.~t/Unieersity of Kent Workshop on Ring Technologl/ Baaed Local Area Nettoorka, September 1983, pp. 1-39.
	12	N. F. Maxemchuk, "Routing in the Manhattan Street Network," IEEE Trans. on Communications, Vol. COM-35, No. 5, pp. 503-512, May 1987.
	13	J.M. McQuillan I. Richer and E.C. Rosen, "The New Routing Algorithm for the ARPANET," IEE,E Trans. on Communications, V-28: 711-719.
	14	Y. Ofek and M. Yung, "Self-stabilized Global Fairness and Flow Control on a Spanning Tree," IBM Research Report in preparation.
	15	Y. Ofek and M. Yung, "MetaNet: A General High-Speed Network Architecture," in preparation.
	16	L. Pouzin, "Methods, Tools, and Observations on Flow Control in Packet-Switched Data Networks", IEEE Trans. Commun., pp. 413-426, April 1981.
	17	F. E. Ross, "FDDI - a Tutorial," IEEE Communication Magazine, Vol. 24, No. 5, May 1986, pp. 10-I7.
	18	N. Santoro and R. Khativ, "Labeling and Implicit Routing in Networks," The Compu\|er Journal, ,~8:5-& 1985. April 1981.
	19	M. Schwartz, Telecommunication Nettoorlra, Addison Wesley, 1987.
	20	M. Sidi, W. Z. Liu, I. Cidon and I. Gopal, "Congestion Avoidance through Input Rate Regulation," GLOB. COM'89, Dallas Texas, 1989.
	21	A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	22	R.E. Tarjan and U. Vishkin, "Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time" I~EE FOC5-35, October 84, pp. 12-20.
	23	J. Turner, "New Directions in communications (or Which Way to the Information Age?)", IEEE Communicatioaa Magazine, October 1986, Vol. 24, No. 10.
	24	J. Turner, "Design of a Broadcast Packet Switching Network", IEEB Trana. on Communica\|ionJ, June 1988, Vol. 36, No. 6.
	25	J. Van Leeuwen , R. B. Tan, Interval routing, The Computer Journal, v.30 n.4, p.298-307, Aug. 1987 [doi>10.1093/comjnl/30.4.298]

CITED BY 12

	Bülent Yener , Spyridon Matsoukas , Yoram Ofek, Iterative approach to optimizing convergence routing priorities, IEEE/ACM Transactions on Networking (TON), v.5 n.4, p.530-542, Aug. 1997
	Susan S. Owicki, A perspective on AN2: local area network as distributed system, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.1-11, August 15-18, 1993, Ithaca, New York, United States
	Robert Cypher , Smaragda Konstantinidou, Bounds on the efficiency of message-passing protocols for parallel computers, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.173-181, June 30-July 02, 1993, Velen, Germany
	Alain Mayer , Yoram Ofek , Moti Yung, Local and congestion-driven fairness algorithm in arbitrary topology networks, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.362-372, June 2000
	Hosame Abu-Amara , Brian A. Coan , Shlomi Dolev , Arkady Kanevsky , Jennifer L. Welch, Self-stabilizing topology maintenance protocols for high-speed networks, IEEE/ACM Transactions on Networking (TON), v.4 n.6, p.902-912, Dec. 1996
	Robert Cypher , Luis Gravano, Requirements for deadlock-free, adaptive packet routing, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.25-33, August 10-12, 1992, Vancouver, British Columbia, Canada
	Yoram Ofek , Bülent Yener , Moti Yung, Concurrent Asynchronous Broadcast on the MetaNet, IEEE Transactions on Computers, v.46 n.7, p.737-748, July 1997
	Yueyue Song , Avishai Wool , Bülent Yener, Combinatorial design of multi-ring networks with combined routing and flow control, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.2, p.247-267, 5 February 2003
	Baruch Awerbuch , Rafail Ostrovsky, Memory-efficient and self-stabilizing network RESET (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.254-263, August 14-17, 1994, Los Angeles, California, United States
	Yoram Ofek , Moti Yung, METANET: principles of an arbitrary topology LAN, IEEE/ACM Transactions on Networking (TON), v.3 n.2, p.169-180, April 1995
	Alain Mayer , Yoram Ofek , Rafail Ostrovsky , Moti Yung, Self-stabilizing symmetry breaking in constant-space (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.667-678, May 04-06, 1992, Victoria, British Columbia, Canada
	Ambrose K. Laing , Robert Cypher, Deadlock-free routing in arbitrary networks via the flattest common supersequence method, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.55-66, June 28-July 02, 1998, Puerto Vallarta, Mexico