Distributed packet switching in arbitrary networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Distributed packet switching in arbitrary networks

Full text

Pdf (1.38 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 366 - 375

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Yuval Rabani	The Technion, Haifa 32000, Israel
Éva Tardos	Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 14, Citation Count: 20

Additional Information:

references cited by index terms collaborative colleagues

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/237814.237983 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. Albanese, J. B1fmer, J. Edmonds, M. Luby, and M. Sudan. Priority encoding transmission. In Proc. 35th Ann. IEEE S~imp. on Foundations of Computer Science, November 1994, pages 604-612.
	2	N. Alon and J.H. Spencer.The Probabilistic Method. Wiley, 1992.
	3	James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line load balancing with applications to machine scheduling and virtual circuit routing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.623-631, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167248]
	4	B. Awerbuch, Y. Azar, and S. Plotkin. Throughput competitive on-line routing. In Proc. of the 3jth Ann. Syrup. on Foundations of Computer Science, Palo Alto, November 1993.
	5	J. Beck. An algorithmic approach to the Lov~sz Local Lemma. Random Structures and Algorithms, 2(4):367-378, 1991.
	6	Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queueing theory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.376-385, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237984]
	7	R.L. Brooks. On colouring the nodes of a network. Proc. Cambridge Philos. Soc., 37:194-197, 1941.
	8	P. Erd6s and L. Lov~sz. Problems and results on 3- chromatic hypergraphs and some related questions. In A. Hajnal et al., eds., Infinite and Finite Sets. North Holland, 1975, pages 609-628.
	9	Rainer Gawlick , Anil Kamath , Serge Plotkin , K. G. Ramakrishnan, Routing and Admission Control in General Topology Networks, Stanford University, Stanford, CA, 1995
	10	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]
	11	T. Leighton , B. Maggs, Fast algorithms for finding O(congestion+dilation) packet routing schedules, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.555, January 04-07, 1995
	12	F.T. Leighton, B.M. Maggs, and S.B. Rao. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, 14(2):167-186, 1994.
	13	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]
	14	J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, 1987.

CITED BY 20

	S. Muthukrishnan , Rajmohan Rajaraman, An adversarial model for distributed dynamic load balancing, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.47-54, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queuing theory, Journal of the ACM (JACM), v.48 n.1, p.13-38, Jan. 2001
	Micah Adler , Ramesh K. Sitaraman , Arnold L. Rosenberg , Walter Unger, Scheduling time-constrained communication in linear networks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.269-278, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Micah Adler , Christian Scheideler, Efficient communication strategies for ad-hoc wireless networks (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.259-268, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Christian Scheideler , Berthold Vöcking, From static to dynamic routing: efficient transformations of store-and-forward protocols, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.215-224, May 01-04, 1999, Atlanta, Georgia, United States
	Uriel Feige , Christian Scheideler, Improved bounds for acyclic job shop scheduling (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.624-633, May 24-26, 1998, Dallas, Texas, United States
	Rafail Ostrovsky , Yuval Rabani, Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.644-653, May 04-06, 1997, El Paso, Texas, United States
	Matthew Andrews , Lisa Zhang, The effects of temporary sessions on network performance, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 09-11, 2000, San Francisco, California, United States
	Petra Berenbrink , Christian Scheideler, Locally efficient on-line strategies for routing packets along fixed paths, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.112-121, January 17-19, 1999, Baltimore, Maryland, United States
	Matthew Andrews , Lisa Zhang, Packet routing with arbitrary end-to-end delay requirements, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.557-565, May 01-04, 1999, Atlanta, Georgia, United States
	V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Matthew Andrews , Baruch Awerbuch , Antonio Fernández , Tom Leighton , Zhiyong Liu , Jon Kleinberg, Universal-stability results and performance bounds for greedy contention-resolution protocols, Journal of the ACM (JACM), v.48 n.1, p.39-69, Jan. 2001
	Matthew Andrews , Lisa Zhang, Minimizing end-to-end delay in high-speed networks with a simple coordinated schedule, Journal of Algorithms, v.52 n.1, p.57-81, July 2004
	William Aiello , Rafail Ostrovsky , Eyal Kushilevitz , Adi Rosén, Dynamic routing on networks with fixed-size buffers, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Costas Busch, Õ(congestion + dilation) hot-potato routing on leveled networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Kevin F. Chen , Edwin H.-M. Sha, The fat-stack and universal routing in interconnection networks, Journal of Parallel and Distributed Computing, v.66 n.5, p.705-715, May 2006
	William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Adaptive packet routing for bursty adversarial traffic, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.359-368, May 24-26, 1998, Dallas, Texas, United States
	Costas Busch , Malik Magdon-Ismail , Marios Mavronicolas, Efficient bufferless packet switching on trees and leveled networks, Journal of Parallel and Distributed Computing, v.67 n.11, p.1168-1186, November, 2007
	Costas Busch , Rajgopal Kannan , Athanasios V. Vasilakos, Quality of routing congestion games in wireless sensor networks, Proceedings of the 4th Annual International Conference on Wireless Internet, November 17-19, 2008, Maui, Hawaii
	Costas Busch , Malik Magdon-Ismail, Atomic routing games on maximum congestion, Theoretical Computer Science, v.410 n.36, p.3337-3347, August, 2009