臺灣博碩士論文加值系統

以往的工作與機器分配問題只注重於最小化工作分配給機器所產生的成本，而忽略了分配後機器間所產生的成本，因此，在論文中，我們研究一個限制機器間成本的工作與機器分配問題；精確來說，我們的目標是同時考慮工作與機器間成本和機器間成本之情況下，最小化分配後所產生的最大成本。這類問題可以應用在必須同時考慮資料存儲裝置與虛擬機器間溝通距離和虛擬機器之間溝通距離的虛擬機器配置問題，也就是說，如何在平行處理環境下，有效率地配置虛擬機器來減少資料傳輸和虛擬機器間溝通所需要的時間；如此一來，資料傳輸時間和機器間溝通時間得以減少，進而使得整體工作完成時間縮短。在過去的文獻中，這個問題已被證實為NP困難且理論上可以推得的最優近似比不可能低於2，同時此問題目前並未存在任何近似演算法；因此，在論文中，我們初步設計一個近似比為3的近似演算法；接著，我們提出一個近似比為2 但時間複雜度較高的近似演算法，換句話說，我們設計出最優近似比的演算法。在論文中，我們提出此問題的兩個變異問題並針對這兩個問題設計近似演算法，也探討一個更為廣義的分配問題並設計其近似演算法。最後，我們藉由模擬實驗來檢驗所提出演算法的效能。

In this dissertation, we investigate the assignment problem of jobs to machines with bounded inter-machine costs, which aims at minimizing the maximum cost among not only all pairs of a job and its assigned machine but also all pairs of the selected machines. The problem can be applied to the traffic-aware data-locality-aware virtual machine (VM) placement where we consider the hop count between the mountable device and its assigned VM as well as the hop count between any two assigned VMs to reduce the latency of data transmission and shorten the job completion time. In the literature, it has been proved that the proposed assignment problem does not admit any approximation algorithm within a factor of two, whereas no approximation algorithms have been proposed so far. Hence, we initially propose a 3-approximation algorithm, and then propose a 2-approximation algorithm, i.e., an optimal approximation algorithm, with a higher time complexity for the proposed assignment problem. In addition, we generalize the one-to-one assignment problem to a many-to-many assignment problem and propose the approximation algorithms for the many-to-many assignment problem. Finally, we conduct the simulations to evaluate the performance of the proposed algorithms.

Abstract i
Contents ii
List of Figures iv
1 Introduction 1
2 Related Work 5
3 The One-to-One Assignment Problem 8
3.1 Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 The Problem and Hardness . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 3-Approximation Algorithm . . . . . . . . . . . . . . . . . . . . . . . 12
3.3.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3.2 The Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.4 Optimal Approximation Algorithm . . . . . . . . . . . . . . . . . . . 20
3.5 The Problem Variant . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5.1 The sVMPDN . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5.2 The kVMPDN . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4 The Many-to-Many Assignment Problem 39
4.1 Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 The Problem and Hardness . . . . . . . . . . . . . . . . . . . . . . . 41
4.3 (3,2)-Approximation Algorithm . . . . . . . . . . . . . . . . . . . . . 44
4.3.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.2 The Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4 (2,2)-Approximation Algorithm . . . . . . . . . . . . . . . . . . . . . 59
5 Simulation 64
5.1 Results for VMPDN . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2 Results for GVMPDN . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6 Conclusion and Future Work 69

[1] Applying the cloud to big data storage. [Online]. Available: http://www.appistry.com/sites/default/files/downloads/Applying_the_Cloud to Big Data Storage.pdf
[2] M. Alicherry and T. V. Lakshman, "Optimizing data access latencies in cloud systems by intelligent virtual machine placement," in IEEE INFOCOM, 2013.
[3] J. Dean and S. Ghemawat, "MapReduce: Simplified data processing on large clusters," Commun. ACM, vol. 51, pp. 107-113, 2008.
[4] Hadoop. [Online]. Available: http://hadoop.apache.org/
[5] M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar, and A. Goldberg, "Quincy: fair scheduling for distributed computing clusters," in ACM SIGOPS, 2009.
[6] M. Zaharia, A. Konwinski, A. D. Joseph, R. Katz, and I. Stoica, "Improving MapReduce performance in heterogeneous environments," in USENIX OSDI, 2008.
[7] X. Meng, V. Pappas, and L. Zhang, "Improving the scalability of data center networks with traffic-aware virtual machine placement," in IEEE INFOCOM, 2010.
[8] Red hat global file system 2. [Online]. Available: https://access.redhat.com/documentation/en-US/Red_Hat_Enterprise_Linux/6/html/Global_File_System_2/index.html
[9] J. F. Kurose and K. W. Ross, Computer Networking: A Top-Down Approach, 5th ed. Addison-Wesley Publishing Company, 2009.
[10] Understanding switch latency. [Online]. Available: http://www.cisco.com/en/US/prod/collateral/switches/ps9441/ps11541/white_paper_c11-661939.html
[11] Speed reduction by distance. [Online]. Available: http://www.numion.com/calculators/Distance.html
[12] M. Alicherry and T. Lakshman, "Network aware resource allocation in distributed clouds," in IEEE INFOCOM, 2012.
[13] G. T. Ross and R. M. Soland, "A branch and bound algorithm for the generalized assignment problem," Math. Program., vol. 8, pp. 91-103, 1975.
[14] M. L. Fisher, R. Jaikumar, and L. N. Van Wassenhove, "A multiplier adjustment method for the generalized assignment problem," Manage. Sci., vol. 32, pp. 1095-1103, 1986.
[15] D. B. Shmoys and E. Tardos, "An approximation algorithm for the generalized assignment problem," Math. Program., vol. 62, pp. 461-474, 1993.
[16] C. Chekuri and S. Khanna, "A PTAS for the multiple knapsack problem," in ACM-SIAM SODA, 2000.
[17] L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko, "Tight approximation algorithms for maximum general assignment problems," in ACM-SIAM SODA, 2006.
[18] D. S. Hochbaum, "Heuristics for the fixed cost median problem," Math. Program., vol. 22, pp. 148-162, 1982.
[19] M. Pal, E. Tardos, and T. Wexler, "Facility location with nonuniform hard capacities," in IEEE FOCS, 2001.
[20] R. Levi and D. B. Shmoys, "LP-based approximation algorithms for capacitated facility location," in ACM-SIAM SODA, 2004.
[21] M. H. Bateni and M. T. Hajiaghayi, "Assignment problem in content distribution networks: Unsplittable hard-capacitated facility location," in ACM-SIAM SODA, 2009.
[22] V. Shrivastava, P. Zerfos, K.-W. Lee, H. Jamjoom, Y.-H. Liu, and S. Banerjee, "Application-aware virtual machine migration in data centers," in IEEE INFOCOM, 2011.
[23] J. Jiang, T. Lan, S. Ha, M. Chen, and M. Chiang, "Joint VM placement and routing for data center traffic engineering," in IEEE INFOCOM, 2012.
[24] D. Breitgand and A. Epstein, "Improving consolidation of virtual machines with risk-aware bandwidth oversubscription in compute clouds," in IEEE INFOCOM, 2012.
[25] H. Yanagisawa, T. Osogami, and R. Raymond, "Dependable virtual machine allocation," in IEEE INFOCOM, 2013.
[26] R. Cohen, L. Lewin-Eytan, J. S. Naor, and D. Raz, "Almost optimal virtual machine placement for traffic intense data centers," in IEEE INFOCOM, 2013.
[27] G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica, "Disk-locality in datacenter computing considered irrelevant," in USENIX HotOS, 2011.
[28] J. Ousterhout, P. Agrawal, D. Erickson, C. Kozyrakis, J. Leverich, D. Mazieres, S. Mitra, A. Narayanan, D. Ongaro, G. Parulkar, M. Rosenblum, S. M. Rumble, E. Stratmann, and R. Stutsman, "The case for RAMCloud," Commun. ACM, vol. 54, pp. 121-130, 2011.
[29] L. Lovasz, "On the ratio of optimal integral and fractional covers," Discrete Math., vol. 13, pp. 383-390, 1975.
[30] L. Lovasz and M. D. Plummer, Matching Theory. Elsevier Science Ltd, 1986.
[31] R. Monteiro and I. Adler, "Interior path following primal-dual algorithms. part I: Linear programming," Math. Program., vol. 44, pp. 27-41, 1989.
[32] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979.
[33] IBM ILOG CPLEX optimizer. [Online]. Available: http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/