Adaptive packet routing for bursty adversarial traffic

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Adaptive packet routing for bursty adversarial traffic

Full text

Pdf (1.46 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 359 - 368

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

William Aiello	Bellcore
Eyal Kushilevitz	Dept. of Computer Science, Technion, Haifa, Israel
Rafail Ostrovsky	Bellcore
Adi Rosén	Dept. of Computer Science, University of Toronto, Toronto, Canada

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 15, Citation Count: 17

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

	AAF+	A. Fernandez, Universal stability results for greedy contention-resolution protocols, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.380, October 14-16, 1996
	AAG+	Yehuda Afek , Baruch Awerbuch , Eli Gafni , Yishay Mansour , Adi Rosén , Nir Shavit, Slide—the key to polynomial end-to-end communication, Journal of Algorithms, v.22 n.1, p.158-186, Jan. 1997 [doi>10.1006/jagm.1996.0819]
	AAMR	William Aiello , Baruch Awerbuch , Bruce Maggs , Satish Rao, Approximate load balancing on dynamic and asynchronous networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.632-641, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167250]
	AAP	B. Awerbuch, Y. Azar, and S. Plotkin, '~Throughput Competitive On-Line Routing," Proc. of 3~th FOG'S, pp. 32-40, 1993.
	AAPW	Baruch Awerbuch , Yossi Azar , Serge Plotkin , Orli Waarts, Competitive routing of virtual circuits with unknown duration, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.321-327, January 23-25, 1994, Arlington, Virginia, United States
	AFH+	M. Andrews , A. Fernandez , M. Harchol-Balter , T. Leighton , L. Zhang, General dynamic routing with per-packet delay guarantees of O(distance+1/session rate), Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.294, October 19-22, 1997
	AGR	Yehuda Afek , Eli Gafni , Adi Rosén, The slide mechanism with applications in dynamic networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.35-46, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135430]
	AL	B. Awerbuch and T. Leighton, "A Simple Local- Control Approximation Algorithm for Multicommodity Flow", Proc. of $4th FOCS, pp. 459--468, 1993.
	AL2	Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195238]
	AMS	B. Awerbuch, Y. Mansour, N. Shavit, "End-to- End Communication with Polynomial Overhead," Proc. of 30th FOC$, pp. 358-363, 1989.
	BFU	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, Dynamic Packet Routing on Arrays with Bounded Buffers, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.273-281, April 20-24, 1998
	BKR+	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]
	BU	Andrei Broder , Eli Upfal, Dynamic deflection routing on arrays (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.348-355, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237981]
	C	R. Cruz, "A Calculus for Network Delay, Part I: Network Elements in Isolation," IEEE Transactions on Information Theory, pp. 114-131, 1991.
	C2	R. Cruz, "A Calculus for Net~,ork Delaj; Part II: Network Analysis," IEEE ~~ansactions on Informarion Theory, pp. 132-141, 1991.
	CMSV	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]
	GL+	Bhaskar Ghosh , F. T. Leighton , Bruce M. Maggs , S. Muthukrishnan , C. Greg Plaxton , R. Rajaraman , Andréa W. Richa , Robert E. Tarjan , David Zuckerman, Tight analyses of two local load balancing algorithms, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.548-558, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225272]
	GM	Bhaskar Ghosh , S. Muthukrishnan, Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.226-235, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181366]
	HB	Mor Harchol-Balter , Paul E. Black, Queueing analysis of oblivious packet-routing networks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.583-592, January 23-25, 1994, Arlington, Virginia, United States
	HW	Mor Harchol-Balter , David Wolfe, Bounding delays in packet-routing networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.248-257, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225133]
	KPP	Anil Kamath , Omri Palmon , Serge Plotkin, Routing and admission control in general topology networks with Poisson arrivals, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 28-30, 1996, Atlanta, Georgia, United States
	KT	J. Kzeinberg , E. Tardos, Disjoint paths in densely embedded graphs, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.52, October 23-25, 1995
	L	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]
	LMR	T. Leighton, B. Maggs, S. Rao, "Packet Routing and job-Shop Scheduling in O(congestion+dilation) Steps," Combinatorica, Vol. 14, No. 2, pp. 167-180, 1994.
	LMRi	T. Leighton, B. Maggs and A. Richa, "Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules," Combinatorica, to appear.
	M	M. Mihail, "Conductance and Convergence of Markov Chains---A Combinatorial Treatment of Expanders," Proc. of 30th FOGS, pp. 526-531, 1989.
	MP	Yishay Mansour , Boaz Patt-Shamir, Greedy packet scheduling on shortest paths, Journal of Algorithms, v.14 n.3, p.449-465, May 1993 [doi>10.1006/jagm.1993.1024]
	MV	F. Meyer auf der Heide and B. ViJcking. "A packet routing protocol for arbitrary netxvorks". Proc. of STACS '95.
	OR	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 [doi>10.1145/258533.258659]
	PG	Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
	PG2	Abhay K. Parekh , Robert G. Gallagher, A generalized processor sharing approach to flow control in integrated services networks: the multiple node case, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.137-150, April 1994 [doi>10.1109/90.298432]
	RT	Yuval Rabani , Éva Tardos, Distributed packet switching in arbitrary networks, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.366-375, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237983]
	ST	Aravind Srinivasan , Chung-Piaw Teo, A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.636-643, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258658]
	STs	G. Stamoulis and J. Tsitsiklis, "The Efficiency of Greedy Routing in Hypercubes and Butterflies," iEEE Transactions on Communications, 42 (11), pp. 3051-208, 1994.
	SV	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]

CITED BY 17

	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
	Elliot Anshelevich , David Kempe , Jon Kleinberg, Stability of load balancing algorithms in dynamic adversarial systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	David Gamarnik, Stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.206-214, May 01-04, 1999, Atlanta, Georgia, United States
	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Stability preserving transformations: packet routing networks with edge capacities and speeds, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.601-610, January 07-09, 2001, Washington, D.C., United States
	Zvi Lotker , Boaz Patt-Shamir, Average-case analysis of greedy packet scheduling (extended astract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.31-40, July 16-19, 2000, Portland, Oregon, United States
	Uriel Feige, Nonmonotonic phenomena in packet routing, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.583-591, May 01-04, 1999, Atlanta, Georgia, United States
	Peter Sanders, Asynchronous scheduling of redundant disk arrays, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.89-98, July 09-13, 2000, Bar Harbor, Maine, United States
	Lujun Jia , Rajmohan Rajaraman , Christian Scheideler, On local algorithms for topology control and routing in ad hoc networks, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	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, Routing and scheduling in multihop wireless networks with time-varying channels, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Peter Sanders, Asynchronous Scheduling of Redundant Disk Arrays, IEEE Transactions on Computers, v.52 n.9, p.1170-1184, September 2003
	Matthew Andrews , Antonio Fernández , Ashish Goel , Lisa Zhang, Source routing and scheduling in packet networks, Journal of the ACM (JACM), v.52 n.4, p.582-601, July 2005
	Matthew Andrews , Lisa Zhang, Scheduling over a time-varying user-dependent channel with applications to high-speed wireless data, Journal of the ACM (JACM), v.52 n.5, p.809-834, September 2005
	Kishore Kothapalli , Christian Scheideler, Information gathering in adversarial systems: lines and cycles, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Leonidas Georgiadis , Leandros Tassiulas, Optimal overload response in sensor networks, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2684-2696, June 2006
	Leonidas Georgiadis , Michael J. Neely , Leandros Tassiulas, Resource allocation and cross-layer control in wireless networks, Foundations and Trends® in Networking, v.1 n.1, p.1-144, April 2006
	Matthew Andrews , Kyomin Jung , Alexander Stolyar, Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA