Efficient delay routing. (English) Zbl 0902.68086
Summary: The computational complexity of finding packet routing schemes provably efficient with respect to the end-to-end delay is studied. The attention is focused on polynomial-time algorithms able to optimize the end-to-end delay when the number of packets in the network increases, and the number of packets that can be accepted in the network in order to keep the end-to-end delay within a constant value. In particular, the hardness of approximating in polynomial time both the minimum end-to-end delay and the maximum number of accepted packets within any sublinear error in the number of packets is proved.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
packet routing schemesReferences:
| [1] | Aleliunas, R., Randomized parallel communication, (Proc. ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) (1982)), 60-72 |
| [2] | Aggarwal, A.; Bar-Noy, A.; Coppersmith, D.; Ramaswami, R.; Schieber, B.; Sudan, M., Efficient routing and scheduling algorithms for optical networks, (Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA) (1994)), 412-423 · Zbl 0874.68018 |
| [3] | Aumann, Y.; Rabani, Y., Improved bounds for all optical routing, (Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA) (1995)), 567-576 · Zbl 0960.68514 |
| [4] | Awerbuch, B.; Bartal, Y.; Fiat, A.; Rosen, A., Competitive non-preemptive call control, (Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA) (1994)), 312-320 · Zbl 0876.68047 |
| [5] | Awerbuch, B.; Gawlick, R.; Leighton, F. T.; Rabani, Y., On-line admission control and circuit routing for high performance computing and communication, (Proc. 35th IEEE Ann. Symp. on Foundations of Computer Science (FOCS) (1994)), 412-423 |
| [6] | Bar-Noy, A.; Raghavan, P.; Schieber, B.; Tamaki, H., Fast deflection routing for packets and worms, (Proc. 12th ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) (1993)), 75-86 · Zbl 1373.68035 |
| [7] | Beck, J., An algorithmic approach to the Lovász Local Lemma I, Random Struct. Algorithms, 2, 343-365 (1991) · Zbl 0756.05080 |
| [8] | Cidon, I.; Kutten, S.; Mansour, Y.; Peleg, D., Greedy packet scheduling, (Proc. of the 4th Workshop on Distributed Algorithms (WDAG) (1990)) · Zbl 0828.68026 |
| [9] | Clementi, A.; Di Ianni, M., Optimum schedule problems in store-and-forward networks, (Proc. IEEE Conf. on Computer Communications (INFOCOM) (1994)), 1336-1343 |
| [10] | Clementi, A.; Di Ianni, M., On the hardness of approximating optimum schedule problems in Store-and-Forward networks, IEEE-ACM Trans. Networking, 4, 272-280 (1996) |
| [11] | Cypher, R.; der Heide, F. Meyer auf; Scheideler, C.; Vöcking, B., Universal algorithms for store-and-forward and wormhole routing, (Proc. 28th ACM Symp. on Theory of Computing (STOC) (1996)) · Zbl 0922.68013 |
| [12] | Di Ianni, M., Efficient delay routing, (Proc. of EuroPar ’96 Parallel Processing. Proc. of EuroPar ’96 Parallel Processing, Lecture Notes in Computer Science, vol. 1123 (1996), Springer: Springer Berlin), 258-269, (extended abstract) |
| [13] | Feige, U.; Killian, J., Zero knowledge and the chromatic number, (Proc. of the IEEE Conf. on Computational Complexity (1996)) |
| [14] | Feldmann, A.; Maggs, B.; Sgall, J.; Sleator, D. D.; Tomkins, A., Competitive analysis of call admission algorithms that allow delay, (Tech. Report CMU-CS-95-102 (1995), Carnegie Mellon University) |
| [15] | Felperin, S.; Raghavan, P.; Upfal, E., A theory of wormhole routing in parallel computers, (Proc. 33rd IEEE Ann. Symp. on Foundations of Computer Science (FOCS) (1992)), 563-572 · Zbl 0977.68503 |
| [16] | Garay, J. A.; Gopal, I.; Kutten, S.; Yung, M., Efficient on-line call control algorithms, (Proc. 2nd Ann. Israel Conf. on Theory of Computing and Systems (1993)), 285-293 |
| [17] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [18] | Hastad, J., Clique is hard to approximate within \(n^{1 − ε}\), (Proc. of the 37th IEEE Ann. Symp. on Foundations of Computer Science (FOCS) (1996)), 627-636 |
| [19] | Johnson, D. S., Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9, 256-278 (1974) · Zbl 0296.65036 |
| [20] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041 |
| [21] | Koutsoupias, E.; Papadimitriou, C. H., Beyond competitive analysis (on-line algorithms), (Proc. 35th IEEE Ann. Symp. on Foundations of Computer Science (FOCS) (1994)), 394-400 |
| [22] | Krizanc, D.; Rajasekaran, S.; Tsantilis, T., Optimal routing algorithms for mesh-connected processor array, (Lecture Notes in Computer Science, vol. 319 (1988), Springer: Springer Berlin), 411-422 |
| [23] | Leighton, T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA · Zbl 0743.68007 |
| [24] | Leighton, T.; Maggs, B., Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks, IEEE Trans. Comput., 41, 578-587 (1992) |
| [25] | Leighton, T.; Maggs, B.; Rao, S., A preliminary version of this paper appeared as “Universal packet routing algorithms”, (Proc. 29th IEEE Ann. Symp. on Foundations of Computer Science (FOCS) (1988)), 256-269 |
| [26] | Leighton, T.; Maggs, B.; Rao, S.; Ranade, A. G., Randomized routing and sorting on fixed-connection networks, J. Algorithms, 17, 157-205 (1994) · Zbl 0808.68048 |
| [27] | Leighton, T.; Maggs, B.; Rao, S., Packet routing and job-shop scheduling in O(congestion + dilation) steps, Combinatorica, 2, 167-186 (1994) · Zbl 0811.68062 |
| [28] | Leighton, T.; Maggs, B.; Richa, A., Fast algorithms for finding O(congestion + dilation) packet routing schedules, (Tech. report CMU-CS-96-152 (1996), School of Computer Science, Carnegie-Mellon University), Combinatorica, to appear. · Zbl 0932.68005 |
| [29] | Leighton, T.; Makedon, F.; Tollis, I., A \(2N\) − 2 step algorithm for routing in an ((N × N\) mesh, (Proc. 1989 ACM Symp. on Parallel Algorithms and Architectures (SPAA) (1989)) · Zbl 0833.68058 |
| [30] | Leiserson, C. E.; Maggs, B., Communication-efficient parallel graph algorithms for distributed randomaccess machines, Algorithmica, 3, 53-77 (1988) · Zbl 0646.68067 |
| [31] | Mansour, Y.; Patt-Shamir, B., Greedy packet scheduling on shortest paths, (Proc. ACM SIGACT-SIGOPS Principles of Distributed Computing ’91 (PODC) (1991)), 165-175 · Zbl 1314.68092 |
| [32] | der Heide, F. Meyer auf; Vöcking, B., A packet routing protocol for arbitrary networks, (Proc. of the 12th Symp. on Theoretical Aspects of Computer Sience (STACS) (1995)), 291-302 · Zbl 1379.68019 |
| [33] | Ni, L. M.; McKinley, P. H., A survey of wormhole routing techniques in direct networks, IEEE Comput., 26, 62-76 (1993) |
| [34] | Ostrovsky, R.; Rabani, Y., Universal \(O\)(congestion + dilation + \( log^{1+N} )\) local control packet switching algorithms, (Proc. 29th Ann. ACM Symp. on Theory of Computing (STOC) (1997)), 644-653 · Zbl 1072.68514 |
| [35] | Papadimitriou, C. H.; Yannakakis, M., Optimization, approximation and complexity classes, J. Comput. System Sci., 43, 425-440 (1991) · Zbl 0765.68036 |
| [36] | Pippenger, N., Parallel communication with limited buffers, (Proc. 25th IEEE Ann. Symp. on Foundations of Computer Science (FOCS) (1984)), 127-136 |
| [37] | Raghawan, P.; Upfal, E., Efficient routing in all-optical networks, (Proc. 26th Ann. ACM Symp. on Theory of Computing (STOC) (1994)), 133-143 · Zbl 1345.90038 |
| [38] | Ranade, A. G., How to emulate shared memory, J. Comput. System Sci., 42, 307-326 (1991) · Zbl 0732.68024 |
| [39] | Ranade, A.; Schleimer, S.; Wilkerson, D. S., Nearly tight bounds for wormhole routing, (Proc. 35th IEEE Ann. Symp. on Foundations of Computer Science (FOCS) (1994)), 347-355 |
| [40] | Srinivasan, A.; Teo, C., A constant factor approximation algorithm for packet routing, and balancing local vs. global criteria, (Proc. 29th Ann. ACM Symp. on Theory of Computing (STOC) (1997)), 636-643 · Zbl 0963.68221 |
| [41] | Upfal, E., Efficient schemes for parallel communication, (Proc. ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) (1982)), 55-59 |
| [42] | Valiant, L. G., A scheme for fast parallel communication, SIAM J. Comput., 11/2, 350-361 (1982) · Zbl 0478.94034 |
| [43] | Valiant, L. G.; Brebner, G. J., Universal schemes for parallel communication, (Proc. 13th ACM Symp. on Theory of Computing (1981)), 263-277 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
