×

Self-adjusting grid networks to minimize expected path length. (English) Zbl 1406.68002

Moscibroda, Thomas (ed.) et al., Structural information and communication complexity. 20th international colloquium, SIROCCO 2013, Ischia, Italy, July 1–3, 2013. Revised selected papers. Berlin: Springer (ISBN 978-3-319-03577-2/pbk). Lecture Notes in Computer Science 8179, 36-54 (2013).
Summary: Given a network infrastructure (e.g., data-center or on-chip-network) and a distribution on the source-destination requests, the expected path (route) length is an important measure for the performance, efficiency and power consumption of the network. In this work we initiate a study on self-adjusting networks: networks that use local-distributed mechanisms to adjust the position of the nodes (e.g., virtual machines) in the network to best fit the route requests distribution. Finding the optimal placement of nodes is defined as the minimum expected path length (MEPL) problem. This is a generalization of the minimum linear arrangement (MLA) problem where the network infrastructure is a line and the computation is done centrally. In contrast to previous work, we study the distributed version and give efficient and simple approximation algorithms for interesting and practically relevant special cases of the problem. In particular, we consider grid networks in which the distribution of requests is a symmetric product distribution. In this setting, we show that a simple greedy policy of position switching between neighboring nodes to locally minimize an objective function, achieves good approximation ratios. We are able to prove this result using the useful notions of expected rank of the distribution and the expected distance to the center of the graph.
For the entire collection see [Zbl 1277.68017].

MSC:

68M10 Network design and communication in computer systems
68M14 Distributed systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Poess, M., Nambiar, R.: Energy cost, the key challenge of today’s data centers: a power consumption analysis of tpc-c results. Proceedings of the VLDB Endowment 1(2), 1229–1240 (2008)
[2] U.S. Environmental Protection Agency: Report to congress on server and data center energy efficiency public law 109-431 (2007)
[3] Heller, B., Seetharaman, S., Mahadevan, P., Yiakoumis, Y., Sharma, P., Banerjee, S., McKeown, N.: Elastictree: Saving energy in data center networks. In: Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation, p. 17. USENIX Association (2010)
[4] Mirza-Aghatabar, M., Koohi, S., Hessabi, S., Pedram, M.: An empirical investigation of mesh and torus noc topologies under different routing algorithms and traffic models. In: 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools, DSD 2007, pp. 19–26. IEEE (2007)
[5] Greene, K.: TR10: Software-Defined Networking
[6] Hoelzle, U.: Openflow @ google, Open Networking Summit (2012)
[7] McKeown, N., Anderson, T., Balakrishnan, H., Parulkar, G., Peterson, L., Rexford, J., Shenker, S., Turner, J.: Openflow: enabling innovation in campus networks. SIGCOMM Comput. Commun. Rev. 38(2), 69–74 (2008) · Zbl 05395592
[8] Gummadi, K., Dunn, R., Saroiu, S., Gribble, S., Levy, H., Zahorjan, J.: Measurement, modeling, and analysis of a peer-to-peer file-sharing workload. In: Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, pp. 314–329. ACM (2003)
[9] Klemm, A., Lindemann, C., Vernon, M., Waldhorst, O.: Characterizing the query behavior in peer-to-peer file sharing systems. In: Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement, pp. 55–67. ACM (2004)
[10] Johnson, D., Garey, M.: Computers and intractability: A guide to the theory of np-completeness. Freeman&Co., San Francisco (1979) · Zbl 0411.68039
[11] Sleator, D., Tarjan, R.: Self-adjusting binary search trees. Journal of the ACM (JACM) 32(3), 652–686 (1985) · Zbl 0631.68060
[12] Lis, M., Shim, K., Cho, M., Fletcher, C., Kinsy, M., Lebedev, I., Khan, O., Devadas, S.: Brief announcement: distributed shared memory based on computation migration. In: SPAA, pp. 253–256. ACM (2011)
[13] Batista, D., da Fonseca, N., Granelli, F., Kliazovich, D.: Self-adjusting grid networks. In: IEEE International Conference on Communications, ICC 2007, pp. 344–349. IEEE (2007)
[14] Shang, Y., Li, D., Xu, M.: Energy-aware routing in data center network. In: Proceedings of the First ACM SIGCOMM Workshop on Green Networking 2010, pp. 1–8. ACM, New York (2010)
[15] Tang, M., Liu, Z., Liang, X., Hui, P.M.: Self-adjusting routing schemes for time-varying traffic in scale-free networks. Phys. Rev. E 80(2), 026114 (2009)
[16] Zhang, H., Liu, Z., Tang, M., Hui, P.: An adaptive routing strategy for packet delivery in complex networks. Physics Letters A 364(3-4), 177–182 (2007) · Zbl 1203.90036
[17] Jain, N., Menache, I., Naor, J(S.), Shepherd, F.B.: Topology-aware VM migration in bandwidth oversubscribed datacenter networks. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 586–597. Springer, Heidelberg (2012) · Zbl 1369.68040
[18] Bansal, N., Lee, K.W., Nagarajan, V., Zafer, M.: Minimum congestion mapping in a cloud. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011, pp. 267–276. ACM, New York (2011) · Zbl 1321.68446
[19] Chung, F.: Labelings of graphs. Selected Topics in Graph Theory 3, 151–168 (1988)
[20] Díaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Comput. Surv. 34, 313–356 (2002)
[21] Bhatt, S., Cosmadakis, S.: The complexity of minimizing wire lengths in vlsi layouts. Information Processing Letters 25(4), 263–267 (1987) · Zbl 0653.68020
[22] Bhatt, S., Thomson Leighton, F.: A framework for solving vlsi graph layout problems. Journal of Computer and System Sciences 28(2), 300–343 (1984) · Zbl 0543.68052
[23] Demaine, E.D., Fekete, S.P., Rote, G., Schweer, N., Schymura, D., Zelke, M.: Integer point sets minimizing average pairwise l1 distance: What is the optimal shape of a town? Comput. Geom. Theory Appl. 44(2), 82–94 (2011) · Zbl 1208.65085
[24] Avin, C., Haeupler, B., Scheideler, C., Schmid, S.: Locally self-adjusting tree networks. In: 27th IEEE International Parallel and Distributed Processing Symposium, IPDPS (2013) · Zbl 06144250
[25] Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimization by simulated annealing. Science 220(4598), 671 (1983) · Zbl 1225.90162
[26] Rabani, Y., Sinclair, A., Wanka, R.: Local divergence of markov chains and the analysis of iterative load-balancing schemes. In: Focs, p. 694. IEEE Computer Society (1998)
[27] Mukherjee, S., Gupte, N.: Gradient mechanism in a communication network. Phys. Rev. E 77(3), 036121 (2008)
[28] Jacob, R., Richa, A., Scheideler, C., Schmid, S., Täubig, H.: A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, pp. 131–140. ACM (2009) · Zbl 1291.68049
[29] Jacob, R., Ritscher, S., Scheideler, C., Schmid, S.: A self-stabilizing and local delaunay graph construction. Algorithms and Computation, 771–780 (2009) · Zbl 1273.68277
[30] Watts, D., Strogatz, S.: Collective dynamics of ’small-world’networks. Nature 393(6684), 440–442 (1998) · Zbl 1368.05139
[31] Karp, R.: Reducibility among combinational problems. Complexity of Computer Computations, 85–104 (1972)
[32] Leiserson, C.E.: Fat-trees: universal networks for hardware-efficient supercomputing. IEEE Trans. Comput. 34(10), 892–901 (1985)
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.