×

Survey on oblivious routing strategies. (English) Zbl 1268.68169

Ambos-Spies, Klaus (ed.) et al., Mathematical theory and computational practice. 5th conference on computability in Europe, CiE 2009, Heidelberg, Germany, July 19–24, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03072-7/pbk). Lecture Notes in Computer Science 5635, 419-429 (2009).
Summary: We give a survey about recent advances in the design of oblivious routing algorithms. These routing algorithms choose their routing paths independent of the traffic in the network and they are therefore very well suited for distributed environments in which no central entitiy exists that could make routing decisions based on the whole traffic pattern in the network.
For the entire collection see [Zbl 1192.68004].

MSC:

68W15 Distributed algorithms
68M10 Network design and communication in computer systems
68M11 Internet topics
68M14 Distributed systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.S.: A general approach to online network optimization problems. In: Proc. of the 15th SODA, pp. 577–586 (2004) · Zbl 1318.68199
[2] Azar, Y., Cohen, E., Fiat, A., Kaplan, H., Räcke, H.: Optimal oblivious routing in polynomial time. In: Proc. of the 35th STOC, pp. 383–388 (2003) · Zbl 1192.90253 · doi:10.1145/780542.780599
[3] Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: Proc. of the 37th FOCS, pp. 184–193 (1996) · doi:10.1109/SFCS.1996.548477
[4] Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: Proc. of the 30th STOC, pp. 161–168 (1998) · Zbl 1029.68951 · doi:10.1145/276698.276725
[5] Bartal, Y., Leonardi, S.: On-line routing in all-optical networks. Theor. Comput. Sci. 221(1-2), 19–39 (1999); Also In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 516–526. Springer, Heidelberg (1997) · Zbl 0933.68005 · doi:10.1007/3-540-63165-8_207
[6] Bienkowski, M., Korzeniowski, M., Räcke, H.: A practical algorithm for constructing oblivious routing schemes. In: Proc. of the 15th SPAA, pp. 24–33 (2003) · doi:10.1145/777412.777418
[7] Borodin, A., Hopcroft, J.E.: Routing, merging and sorting on parallel models of computation. J. Comput. Syst. Sci. 30(1), 130–145 (1985) · Zbl 0603.68065 · doi:10.1016/0022-0000(85)90008-X
[8] Busch, C., Magdon-Ismail, M., Xi, J.: Oblivious routing on geometric networks. In: Proc. of the 17th SPAA, pp. 316–324 (2005) · doi:10.1145/1073970.1074022
[9] Busch, C., Magdon-Ismail, M., Xi, J.: Optimal oblivious path selection on the mesh. In: Proc. of the 20th IPDPS, pp. 82–91 (2005) · Zbl 1373.68039 · doi:10.1109/IPDPS.2005.311
[10] Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.A.: Approximating a finite metric by a small number of tree metrics. In: Proc. of the 39th FOCS, pp. 379–388 (1998) · doi:10.1109/SFCS.1998.743488
[11] Chekuri, C., Khanna, S., Shepherd, B.: The all-or-nothing multicommodity flow problem. In: Proc. of the 36th STOC, pp. 156–165 (2004) · Zbl 1192.68878 · doi:10.1145/1007352.1007383
[12] Fakcharoenphol, J., Rao, S.B., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proc. of the 35th STOC, pp. 448–455 (2003) · Zbl 1192.68977 · doi:10.1145/780542.780608
[13] Harrelson, C., Hildrum, K., Rao, S.B.: A polynomial-time tree decomposition to minimize congestion. In: Proc. of the 15th SPAA, pp. 34–43 (2003) · doi:10.1145/777412.777419
[14] Harsha, P., Hayes, T.P., Narayanan, H., Räcke, H., Radhakrishnan, J.: Minimizing average latency in oblivious routing. In: Proc. of the 19th SODA, pp. 200–207 (2008) · Zbl 1192.90035
[15] Kaklamanis, C., Krizanc, D., Tsantilas, T.: Tight bounds for oblivious routing in the hypercube. In: Proc. of the 2nd SPAA, pp. 31–36 (1990) · Zbl 0731.68046 · doi:10.1145/97444.97453
[16] Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. J. Algorithms 61(1), 20–44 (2006) · Zbl 1101.68110 · doi:10.1016/j.jalgor.2004.07.006
[17] Maggs, B.M., Meyer auf der Heide, F., Vöcking, B., Westermann, M.: Exploiting locality for networks of limited bandwidth. In: Proc. of the 38th FOCS, pp. 284–293 (1997)
[18] Maggs, B.M., Miller, G.L., Parekh, O., Ravi, R., Woo, S.L.M.: Finding effective support-tree preconditioners. In: Proc. of the 17th SPAA, pp. 176–185 (2005) · doi:10.1145/1073970.1073996
[19] Meyer auf der Heide, F., Vöcking, B.: A packet routing protocol for arbitrary networks. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol. 900, pp. 291–302. Springer, Heidelberg (1995) · Zbl 1379.68019 · doi:10.1007/3-540-59042-0_81
[20] Ostrovsky, R., Rabani, Y.: Universal \({O}(\mbox{congestion}+\mbox{dilation}+\log^{1+\epsilon} {N})\) local control packet switching algorithms. In: Proc. of the 29th STOC, pp. 644–653 (1997) · Zbl 1072.68514
[21] Rabin, M.O.: Efficient dispersal of information for security, load balancing and fault tolerance. J. ACM 36, 335–348 (1989) · Zbl 0677.68024 · doi:10.1145/62044.62050
[22] Räcke, H.: Minimizing congestion in general networks. In: Proc. of the 43rd FOCS, pp. 43–52 (2002) · doi:10.1109/SFCS.2002.1181881
[23] Räcke, H.: Data Management and Routing in General Networks. PhD thesis, Universität Paderborn (2003)
[24] Räcke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proc. of the 40th STOC, pp. 255–264 (2008) · Zbl 1231.68051 · doi:10.1145/1374376.1374415
[25] Upfal, E.: Efficient schemes for parallel communication. J. ACM 31(3), 507–517 (1984) · Zbl 0628.68021 · doi:10.1145/828.1892
[26] Valiant, L.G., Brebner, G.J.: Universal schemes for parallel communication. In: Proc. of the 13th STOC, pp. 263–277 (1981) · doi:10.1145/800076.802479
[27] Vöcking, B.: Static and Dynamic Data Management in Networks. PhD thesis, Universität Paderborn (December 1998) · Zbl 0931.68010
[28] Vöcking, B.: Almost optimal permutation routing on hypercubes. In: Proc. of the 33rd STOC, pp. 530–539 (2001) · Zbl 1323.68019 · doi:10.1145/380752.380848
[29] Westermann, M.: Caching in Networks: Non-Uniform Algorithms and Memory Capacity Constraints. PhD thesis, Universität Paderborn (November 2000)
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.