Article

Free access

Distributed packet switching in arbitrary networks

Authors:

Yuval Rabani,

Éva TardosAuthors Info & Claims

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

Pages 366 - 375

https://doi.org/10.1145/237814.237983

Published: 01 July 1996 Publication History

PDF eReader

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.

Digital Library

Google Scholar

[2]

N. Alon and J.H. Spencer.The Probabilistic Method. Wiley, 1992.

Google Scholar

[3]

J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. On-line load balancing with applications to machine scheduling and virtual circuit routing, in Proc. of the ~$rd Ann. A CM Syrup. on Theory of Computing, San Diego, May 1993.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[5]

J. Beck. An algorithmic approach to the Lov~sz Local Lemma. Random Structures and Algorithms, 2(4):367-378, 1991.

Digital Library

Google Scholar

[6]

A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D.P. Williamson. Adversarial queueing theory. In these proceedings.

Digital Library

Google Scholar

[7]

R.L. Brooks. On colouring the nodes of a network. Proc. Cambridge Philos. Soc., 37:194-197, 1941.

Crossref

Google Scholar

[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.

Google Scholar

[9]

R. Gawlick, A. Kamath, S. Plotkin, and K. Ramakrishnan. Routing and admission control in general topology networks. Technical report no. STAN- CS-TR-95-1548, Stanford University, 1995.

Digital Library

Google Scholar

[10]

F.T. Leighton. Methods for message routing in parallel machines. In Proc. of the ~4th Ann. A CM Syrup. on the Theory of Computing, May 1992, pages 77-96.

Digital Library

Google Scholar

[11]

F.T. Leighton and B.M. Maggs. Fast algorithms for finding O(congestion + dilation) packet routing schedules. In Proc. of the ~Sth Hawaii International Conference on System Sciences, January 1995, vol 2, pages 555-563.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[13]

F.T. Leighton, B.M. Maggs, A.G. Ranade, and S.B. Rao. Randomized routing and sorting on fixedconnection networks. J. Alg., 17(1):157-205, 1994.

Digital Library

Google Scholar

[14]

J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, 1987.

Google Scholar

Cited By

View all

Haeupler BWajc DZuzic G(2020)Network Coding Gaps for Completion Times of Multiple Unicasts2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00053(494-505)Online publication date: Nov-2020
https://doi.org/10.1109/FOCS46700.2020.00053
Busch CKannan RTardos EElkind EVohra R(2018)Polynomial Time Equilibria in Bottleneck Congestion GamesProceedings of the 2018 ACM Conference on Economics and Computation10.1145/3219166.3219221(393-409)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3219166.3219221
Even GMedina M(2017)Online Packet-Routing in Grids with Bounded BuffersAlgorithmica10.1007/s00453-016-0177-078:3(819-868)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s00453-016-0177-0
Show More Cited By

Index Terms

Distributed packet switching in arbitrary networks
1. Networks
  1. Network types
    1. Packet-switching networks

Recommendations

Performance analysis of a packet prioritisation algorithm for optical-packet-switching networks

Because of the explosive growth of network traffic, backbone networks move towards all-optical-packet-switching networks. However, optical buffers implemented by Fibre Delay Lines (FDLs) have a volatile nature because of signal loss and noise ...
Performance analysis of ATM switches with multistage packet switching interconnection networks
LCN '96: Proceedings of the 21st Annual IEEE Conference on Local Computer Networks

A mathematical method for analysis of ATM switches based on multistage packet switching interconnection networks with finite buffering capacity at the output of switching elements is presented. The proposed mathematical method is general in that it ...
Modeling bufferless packet-switching networks with packet dependencies

In this paper we present a stochastic network model for packet-switching networks with no buffering capabilities at the nodes. This model can be directly used in the study of all-optical packet-switching (OPS) and optical burst switching (OBS) networks ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

July 1996

661 pages

ISBN:0897917855

DOI:10.1145/237814

Chairman:
Gary L. Miller

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC96

Sponsor:

SIGACT

STOC96: ACM Symposium on Theory of Computing

May 22 - 24, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

STOC '96 Paper Acceptance Rate 74 of 201 submissions, 37%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
332
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)4

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Haeupler BWajc DZuzic G(2020)Network Coding Gaps for Completion Times of Multiple Unicasts2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00053(494-505)Online publication date: Nov-2020
https://doi.org/10.1109/FOCS46700.2020.00053
Busch CKannan RTardos EElkind EVohra R(2018)Polynomial Time Equilibria in Bottleneck Congestion GamesProceedings of the 2018 ACM Conference on Economics and Computation10.1145/3219166.3219221(393-409)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3219166.3219221
Even GMedina M(2017)Online Packet-Routing in Grids with Bounded BuffersAlgorithmica10.1007/s00453-016-0177-078:3(819-868)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s00453-016-0177-0
Cowen L(2016)Packet RoutingEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_273(1500-1503)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_273
Ghaffari MGeorgiou CSpirakis P(2015)Near-Optimal Scheduling of Distributed AlgorithmsProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767417(3-12)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767417
Antoniadis ABarcelo NCole DFox KMoseley BNugent MPruhs K(2014)Packet Forwarding Algorithms in a Line NetworkLATIN 2014: Theoretical Informatics10.1007/978-3-642-54423-1_53(610-621)Online publication date: 2014
https://doi.org/10.1007/978-3-642-54423-1_53
Shi YZhang FLiu Z(2013)A Universally Stable and Energy-Efficient Scheduling Protocol for Packet Switching Network2013 IEEE 12th International Symposium on Network Computing and Applications10.1109/NCA.2013.20(118-126)Online publication date: Aug-2013
https://doi.org/10.1109/NCA.2013.20
Kowalski DNussbaum ESegal MMilyeykovsky V(2013)Scheduling problems in transportation networks of line topologyOptimization Letters10.1007/s11590-013-0613-x8:2(777-799)Online publication date: 13-Feb-2013
https://doi.org/10.1007/s11590-013-0613-x
Rothvoß T(2013)A simpler proof for O(congestion+dilation) packet routingProceedings of the 16th international conference on Integer Programming and Combinatorial Optimization10.1007/978-3-642-36694-9_29(336-348)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1007/978-3-642-36694-9_29
Kannan RBusch CWei SIyengar SBrooks R(2012)Jamming Games in Wireless and Sensor NetworksDistributed Sensor Networks, Second Edition10.1201/b12991-37(679-692)Online publication date: 13-Dec-2012
https://doi.org/10.1201/b12991-37
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Performance analysis of a packet prioritisation algorithm for optical-packet-switching networks

Performance analysis of ATM switches with multistage packet switching interconnection networks

Modeling bufferless packet-switching networks with packet dependencies