Online packet-routing in grids with bounded buffers. (English) Zbl 1372.68310
Summary: We present deterministic and randomized algorithms for the problem of online packet routing in grids in the competitive network throughput model [W. Aiello et al., in: Proceedings of the 14th annual ACM-SIAM symposium on discrete algorithms, SODA’03. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 771–780 (2003; Zbl 1092.68507)]. In this model the network has nodes with bounded buffers and bounded link capacities. The goal in this model is to maximize the throughput, i.e., the number of delivered packets. Our deterministic algorithm is the first online algorithm with an \(O\left( \log ^{O(1)}(n)\right) \) competitive ratio for uni-directional grids (where \(n\) denotes the size of the network). The deterministic online algorithm is centralized and handles packets with deadlines. This algorithm is applicable to various ranges of values of buffer sizes and communication link capacities. In particular, it holds for buffer size and communication link capacity in the range \([3 \dots \log n]\). Our randomized algorithm achieves an expected competitive ratio of \(O(\log n)\) for the uni-directional line. This algorithm is applicable to a wide range of buffer sizes and communication link capacities. In particular, it holds also for unit size buffers and unit capacity links. This algorithm improves the best previous \(O(\log ^2 n)\)-competitive ratio of Y. Azar and R. Zachut [Lect. Notes Comput. Sci. 3669, 484–495 (2005; Zbl 1162.68313)] .
MSC:
| 68W27 | Online algorithms; streaming algorithms |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68W20 | Randomized algorithms |
References:
| [1] | Awerbuch, B., Azar, Y., Amos, F.: Packet routing via min-cost circuit routing. In: ISTCS, pp. 37-42 (1996) |
| [2] | Awerbuch, B., Azar, Y., Plotkin, S.: Throughput-competitive on-line routing. In: FOCS’93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, pp. 32-40. IEEE Computer Society, Washington (1993) · Zbl 0932.68005 |
| [3] | Angelov, S., Khanna, S., Kunal, K.: The network asa storage device: dynamic routing with bounded buffers. Algorithmica 55(1), 71-94 (2009). (Appeared in APPROX-05) · Zbl 1194.68070 · doi:10.1007/s00453-007-9143-1 |
| [4] | Aiello, W., Kushilevitz, E., Ostrovsky, R., Rosén, A.: Dynamic routing on networks with fixed-size buffers. In: SODA, pp. 771-780 (2003) · Zbl 1092.68507 |
| [5] | Adler, M., Khanna, S., Rajaraman, R., Rosén, A.: Time-constrained scheduling of weighted packets on trees and meshes. Algorithmica 36(2), 123-152 (2003) · Zbl 1053.68013 · doi:10.1007/s00453-002-1019-9 |
| [6] | Adler, M., Rosenberg, A.L., Sitaraman, R.K., Unger, W.: Scheduling time-constrained communication in linear networks. Theory Comput. Syst. 35(6), 599-623 (2002) · Zbl 1012.68024 · doi:10.1007/s00224-002-1001-6 |
| [7] | Azar, Y., Zachut, R.: Packet routing and information gathering in lines, rings and trees. In: ESA, pp. 484-495 (2005). See also manuscript in http://www.cs.tau.ac.il/ azar/ · Zbl 1162.68313 |
| [8] | Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, New York (1998) · Zbl 0931.68015 |
| [9] | Bartal, Y., Leonardi, S.: On-line routing in all-optical networks. In: ICALP, pp. 516-526 (1997) · Zbl 0933.68005 |
| [10] | Buchbinder, N., Naor, J.: Improved bounds for online routing and packing via a primal-dual approach. In: Annual IEEE Symposium on Foundations of Computer Science, pp. 293-304 (2006) · Zbl 0932.68005 |
| [11] | Buchbinder, N., Naor, J.S.: The design of competitive online algorithms via a primal-dual approach. Found. Trends Theor. Comput. Sci. 3(2-3), 99-263 (2009) |
| [12] | Buchbinder, N., Naor, J.S.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270-286 (2009) · Zbl 1216.68335 · doi:10.1287/moor.1080.0363 |
| [13] | Even, G., Medina, M.: An \[{o}(log\mathit{n})\] o(logn)-competitive online centralized randomized packet-routing algorithm for lines. In: Abramsky, S., Gavoille, C., Kirchner, C., auf der Heide, F.M., Spirakis, P.G. (eds.) ICALP (2), volume 6199 of Lecture Notes in Computer Science, pp. 139-150. Springer (2010) · Zbl 1288.68012 |
| [14] | Even, G., Medina, M.: Online packet-routing in grids with bounded buffers. In: Rajaraman, R., auf der Heide, F.M. (eds) SPAA, pp. 215-224. ACM (2011) · Zbl 1372.68310 |
| [15] | Even, G., Medina, M., Patt-Shamir, B.: Better deterministic online packet routing on grids. In: Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pp. 284-293 (2015) |
| [16] | Even, G., Medina, M., Rosén, A.: A constant approximation algorithm for scheduling packets on line networks. CoRR. arXiv:1602.06174, 2016. ESA (2016) · Zbl 1397.68222 |
| [17] | Gupta, U.I., Lee, D.T., Leung, J.Y.-T.: Efficient algorithms for interval graphs and circular-arc graphs. Networks 12(4), 459-467 (1982) · Zbl 0493.68066 · doi:10.1002/net.3230120410 |
| [18] | Kleinberg, J.M., Tardos, É.: Disjoint paths in densely embedded graphs. In: FOCS, pp. 52-61 (1995). See also manuscript in http://www.cs.cornell.edu/home/kleinber/ · Zbl 0938.68752 |
| [19] | Leighton, F.T., Maggs, B.M., Rao, S.B.: Packet routing and job-shop scheduling in O\](congestion+ dilation)\(O\)(congestion+dilation) steps. Combinatorica 14(2), 167-186 (1994) · Zbl 0811.68062 · doi:10.1007/BF01215349 |
| [20] | Leighton, T., Maggs, B., Richa, A.W.: Fast algorithms for finding O\](congestion+ dilation)\(O\)(congestion+dilation) packet routing schedules. Combinatorica 19(3), 375-401 (1999) · Zbl 0932.68005 · doi:10.1007/s004930050061 |
| [21] | Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005) · Zbl 1092.60001 · doi:10.1017/CBO9780511813603 |
| [22] | Räcke, H., Rosén, A.: Approximation algorithms for time-constrained scheduling on line networks. In: SPAA, pp. 337-346 (2009) · Zbl 1216.68335 |
| [23] | Rabani, Y., Tardos, É.: Distributed packet switching in arbitrary networks. In: STOC’96: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 366-375. ACM, New York (1996) · Zbl 0936.68010 |
| [24] | Srinivasan, A., Teo, C.P.: A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 636-643. ACM (1997) · Zbl 0963.68221 |
| [25] | Turner, J.S.: Strong performance guarantees for asynchronous buffered crossbar scheduler. IEEE/ACM Trans. Netw. 17(4), 1017-1028 (2009) · doi:10.1109/TNET.2008.2006221 |
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.
