平穩透通的虛擬機器搬遷對於雲端資源使用最大化和確保用戶滿意度來說是至
關重要的。然而，vSphere和Hyper-V等虛擬化系統雖然可以透過同時搬遷多個虛擬機器來縮短整體搬遷時間，但臨時儲存在緩衝區中的數據量的快速增長會導致大量數據封包的損失和系統吞吐量崩落下降。因此本研究提出了一種透過按照虛擬機器負載量遞減順序排序方法，將負載較輕的虛擬機器與負載較重的虛擬機器交錯搬遷來減輕傳輸控制協定效能崩落的問題。透過做種方法，虛擬機器搬遷的重疊時間可以減少，也可降低溢出所引起的數據封包丟失的風險。根據對目的地伺服器的CPU和記憶體可使用資源的預先定義約束，導出伺服器合併效率得以估算透過伺服器關閉來實現節能效益。實驗模擬結果得出，所提出的交錯虛擬機器搬遷方案與現有順序虛擬機器搬遷方法在伺服器整合效率上有類似結果，但在同時搬遷導致緩衝區數據儲存量上，本提案有較低的結果和較少的搬遷嘗試次數。此外考慮了四種不同的虛擬機器搬遷場景和問題轉化方法，來證明虛擬機器搬遷是非決定性多項式時間完備問題。同時亦提出了一種用於在預複製虛擬機器搬遷模型下來估算虛擬機器傳輸時間的方法。

Smooth and transparent VM migration is essential in maximizing the utilization of cloud resources and ensuring user satisfaction. However, while virtualization systems such as vSphere and Hyper-V enable the overall migration time to be reduced by moving more than one VM at the same time,the resulting rapid growth in the volume of data temporarily stored at the buffer can lead to significant packet losses and a catastrophic drop in the system throughput. The present study proposes a method for mitigating this so-called TCP Incast effectby sorting the VMsin order of descending load and then interleavingthe migrations of the more lightly-loaded VMs with those of the more heavily-loaded VMs. By doing so, the overlapping time of the VM migrations is reduced, and hence the risk of overflow-induced packet losses is decreased. Aserver consolidation ratio is derived to estimate the energy saving achieved via server shutdowngivenpre-definedconstraints on the CPU and memory resources of the destination servers.The simulation results show that the proposed staggeredVM migration schemeachieves a similar server consolidation performance as existing sequential VM migration methods, but results in both a lower data storage requirement at the buffer and fewer vMotions.Four different scenarios and problem reduction methods are considered for VM migration and are proven to be NP-Complete. Furthermore, a method is proposed for estimating the VM transfer timeunder the pre-copy VM migration model.

[1]Barham, Paul, et al, "Xen and the art of virtualization," ACM SIGOPS Operating Systems Review 37.5: 164-177, 2003.
[2]"VMware vSphere5.1 vMotion Architecture, Performance and Best Practices.　"VMware　TECHNICAL WHITE PAPER, Available at: https://www.vmware.com/files/pdf/techpaper/VMware-vSphere51-vMotion-Perf.pdf.
[3]Microsoft, "Configure Live Migration and Migrating Virtual Machines without Failover Clustering." Available at: https://technet.microsoft.com/en-us/library/jj134199.aspx
[4]"Xen live migration." Available at: https://access.redhat.com/documentation/en-US/Red_Hat_Enterprise_Linux/5/html/Virtualization/chap-Virtualization-Xen_live_migration.html
[5]KVM,　"Migration." Available at: https://access.redhat.com/documentation/en-US/Red_Hat_Enterprise_Linux/6/html/Virtualization_Administration_Guide/chap-Virtualization_Administration_Guide-KVM_live_migration.html
[6]Lei Cui, Jinpeng　Huai, Jianxin Li, Chunming Hu, Bo Li, Tianyu　Wo, Hussain Al-Aqrabi, Lu Liu , 2013. VMScatter: Migrate Virtual Machines to Many Hosts, In: VEE’13, ACM 978-1-4503-1266-0/13/03.
[7]FeiMa, Feng Liu, and Zhen Liu, 2010. Live virtual machine migration based on improved pre-copy approach, Software Engineering and Service Sciences (ICSESS), IEEE International Conference.
[8]Michael R.　Hines , and Kartik　Gopalan, 2009. Post-copy based live virtual machine migration using adaptive pre-paging and dynamic self-ballooning, ACM SIGPLAN/SIGOPS international conference on Virtual execution environments.　ACM.
[9]Sherif Akoush, RipdumanSohan, Andrew Rice, Andrew W. Moore and Andy Hopper, 2010. Predicting the Performance of Virtual Machine Migration, Modeling, Analysis & Simulation of Computer and Telecommunication Systems (MASCOTS), IEEE International Symposium.
[10]Mohamed EsamElsaid, ChristophMeinel, 2014. Live Migration Impact on Virtual Datacenter Performance :VmwarevMotion Based Study, Future Internet of Things and Cloud (FiCloud), International Conference.
[11]Mohamed EsamElsaid, ChristophMeinel, 2016. Multiple Virtual Machines Live Migration Performance Modelling VMware vMotion based Study, CloudEngineering (IC2E), IEEE International Conference.
[12]Felix Salfner, Peter Troger, Andreas Polze, 2011. Downtime Analysis of Virtual Machine Live Migration, The Fourth International Conference on Dependability, ISBN: 978-1-61208-149-6.
[13]Hai Jin, Wei Gao, Song Wu, Xuanhua Shi, Xiaoxin Wu, Fan Zhou, 2011. Optimizing the live migration of virtual machine by CPU scheduling, Journal of Network and Computer Applications.
[14]TusherKumerSarker, Maolin Tang, 2013. Performance-driven Live Migration of Multiple Virtual Machines in Datacenters, Granular Computing (GrC), IEEE International Conference.
[15]Arsch Sharma, AshuSaxena, KarthickNanmaran, 2017. A Survey on Live Virtual Machine Migraton, Available at: http://uksim.info/uksim2017/CD/data/2735a187.pdf
[16]ANDREW S. TANENBAUM, DAVID J. WETHERALL, Computer Networks (5th). PearsonPrentice Hall, 2010.
[17]"TCP Extensions for High Performance.　"RFC 1323.Available at: https://www.ietf.org/rfc/rfc1323.txt
[18]"TCP Slow Start, Congestion Avoidance,Fast Retransmit, and Fast Recovery Algorithms.　"RFC 2001.Available at: https://tools.ietf.org/html/rfc2001
[19]H. Jin, L. Deng, and S. Wu. , " Live virtual machine migration withadaptive memory compression,"In Proceedings of CLUSTER, pages1–10, 2009.
[20]Umesh Deshpande andKate Keahey,"Traffic-Sensitive Live Migration of Virtual Machines,"Cluster, Cloud and Grid Computing (CCGrid), 2015 15th IEEE/ACM International Symposium , 4-7 May 2015, pp. 51–60.
[21]Franco Callegati, Walter Cerroni,"Live Migration of Virtualized Edge Networks:Analytical Modeling and Performance Evaluation,"Future Networks and Services (SDN4FNS) , 2013 IEEE Conference on. IEEE, 2013.
[22]Xiujie Feng, Xuan Luo,Yaohui Jin," An acceleration system for long distance live migration of virtual machine."The 10th International Conference on Optical Internet (COIN2012) ,2012.
[23]Mohamed EsamElsaid, Ahmed Shawish,ChristophMeinel,” Enhanced Cost Analysis of Multiple Virtual Machines Live Migration in VMware Environments.” IEEE 8th International Symposium on Cloud and Service Computing (SC2), 2018.
[24]Lars Lundberg,” Performance Implications of Resource Over-Allocation During the Live Migration.” IEEE International Conference on Cloud Computing Technology and Science (CloudCom), 2016.
[25]Preeti P. Thakre,Vaishali N. Sahare,”VM live migration time reduction using NAS based algorithm during VM live migration .” Third International Conference on Sensing, Signal Processing and Security (ICSSS), 2017.
[26]Virtual Machine Live Migration Overview, Microsoft TechNet, https://technet.microsoft.com/en-us/library/hh831435(v=ws.11).aspx, 21 August. 2013.
[27]Christopher Clark, Keir Fraser, Steven Hand, Jacob Gorm Hansen, Live Migration of Virtual Machines, Available at: https://www.usenix.org/legacy/event/nsdi05/tech/full_papers/clark/clark.pdf
[28]Michael R. Hines, Umesh Deshpande, KartikGopalan, Post-Copy Live Migration of Virtual Machines, Available at: http://osnet.cs.binghamton.edu/publications/hines09postcopy_osr.pdf
[29]ZiyuLi ,Gang Wu, 2016. Optimizing VM Live Migration Strategy Based On Migration Time Cost Modeling, Architectures for Networking and Communications Systems (ANCS), ACM/IEEE Symposium.
[30]Walter Cerroni, Flavio Esposito, 2016. Optimizing Live Migration of Multiple Virtual Machines, IEEE Transactions on Cloud Computing.
[31]Adel Amani, Kamran Zamanifar, 2014. Improving the time of live migration virtual machine by optimized algorithm scheduler credit, Computer and Knowledge Engineering (ICCKE), International Conference.
[32]Megha R. Desai, Hiren B. Patel, 2015. Efficient Virtual Machine Migration in Cloud Computing, Communication Systems and Network Technologies (CSNT), International Conference.
[33]Konstantinos Tsakalozos ,VasilisVerroios, MemaRoussopoulos , Alex Delis, 2017. Live VM Migration Under Time-Constraints in Share-Nothing IaaS-Clouds, IEEE Transactions on Parallel and Distributed Systems.
[34]KasiditChanchio, PhithakThaenkaew, 2017. Performance comparisons and data compression of time-bound live migration and pre-copy live migration of virtual machines, Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD),IEEE/ACIS International Conference.
[35]Xibo Yao, Hua Wang, Chuangen Gao, Fangjin Zhu, LinboZhai, 2017. VM Migration Planning in Software-Defined Data Center Networks, High Performance Computing and Communications; IEEE 14th International Conference.
[36]YonghuiRuan, Zhongsheng Cao, Zongmin Cui, 2016. Pre-Filter-Copy: Efficient and Self-Adaptive Live Migration of Virtual Machines, IEEE Systems Journal , vol.10, pp. 1459 - 1469.
[37]Flavio Esposito , Walter Cerroni, 2016. GeoMig: Online Multiple VM Live Migration, Cloud Engineering Workshop (IC2EW), IEEE International Conference.
[38]M. Alizadeh,A . Greenberg,D . A. Maltz,J . Padhye,P . Patel,B . Prabhakar,S. Sengupta, and M. Sridharan, "Data Center TCP (DCTCP)," SIGCOMM2010, pp. 63-74.
[39]H. Wu,Z . Feng,C . Guo and Y. Zhang, "ICTCP: Incast Congestion Controlfor TCP in Data Center Networks," ACM CoNEXT, 2010.
[40]Y. Chen, R. Griffith, J. Liu, R. H. Katz, and A. D. Joseph, "UnderstandingTCP Incast Throughput Collapse in Datacenter Networks, " inProc. of the 1st ACM workshop on Research on enterprise networking,Barcelona, Spain, August 21, 2009, pp. 73–82.
[41]A. Phanishayee, E. Krevat, Y. Vasudevan, D. G. Andersen, G. R. Ganger,G. A. Gibson and S. Seshan, "Measurement and Analysis of TCP ThroughputCol/apse in Cluster-based Storage Systems, " The 6th USEUNTXConference on File and Storage Technologies (FAST 2008), pp. I-B.
[42]Shigeyuki Osada, KazutoshiKajita, Yukinobu Fukushima and TokumiYokohira, "TCP Incast Avoidance Based onConnection Serialization in Data Center Networks," Communications (APCC), 2013 19th Asia-Pacific Conference, August 29, 2013, pp. 142–147.
[43]Chunghan Lee, Yukihiro Nakagawa, KazukiHyoudou, Shinji Kobayashi, Osamu Shiraki, Takeshi Shimizu,"Flow-Aware Congestion Control to ImproveThroughput under TCP Incast in Datacenter Networks," Computer Software and Applications Conference (COMPSAC),2015 IEEE 39th Annual (Volume:3 ) , 1-5 July 2015, pp. 155–162.
[44]Jiao Zhang, Fengyuan Ren, Xin Yue, Chuang Lin, "Sharing Bandwidth by Allocating Switch Buffer in Data Center Networks, "IEEE Journal on Selected Areas in Communications, vol.32, no. 1, pp. 39–51, 2014.
[45]AkintomideAdesanmi, LotfiMhamdi, "M21TCP: Overcoming TCP IncastCongestion in Data Centres,"Cloud Networking (CloudNet), 2015 IEEE 4th International Conference ,5-7Oct 2015, pp.20-25.
[46]Robert J. FOWLER, Michael S. PATERSON and Steven L. TANIMOTO, 1981. Optimal Packing and convering in the plane are NP-Complete, INFORMATION PROCESSING LETTERS, V. 12, n.3.
[47]Michail G. Lagoudakis, 1996. The 0–1 Knapsack Problem--An Introductory Survey, Technical report, University of Southwestern Louisiana.
[48]Jun Gu, Paul W. Purdom, John Franco, Benjamin W. Wah, Algorithms for the Satisfiability (SAT) Problem: A Survey, Available at: https://www.cs.toronto.edu/~chechik/courses03/csc2108/algorithms-for-satisfiability.pdf
[49]Kangkang Li, Huanyang Zheng, and Jie Wu, 2013. Migration-based virtual machine placement in cloud systems, Cloud Networking (CloudNet), 2013 IEEE 2nd International Conference.
[50]RajalakshmiShenbagaMoorthy et al, 2017. An Effective Mechanism for Virtual Machine Placement using Aco in IAAS Cloud, IOP Conference Series: Materials Science and Engineering 225012227.
[51]Sai Qian Zhang, Pouya Yasrebi, Ali Tizghadam, Hadi Bannazadeh, Alberto Leon-Garcia, 2015. Fast Network Flow Resumption for Live Virtual Machine Migration on SDN, Network Protocols (ICNP), International Conference.
[52]Weizhe Zhang, Shuo Han, Hui He, Huixiang Chen, 2016. Network-aware virtual machine migration in an overcommitted cloud, Future Generation Computer Systems.
[53]A. Murtazaev and S. Oh, "Sercon : Server Consolidation Algorithmusing Live Migration of Virtual Machines for Green Computing," IETETechnical Review, vol. 28, no. 3, pp. 212–231, 2011.
[54]Microsoft, "Configure Available Memory for Report Server Applications." Available at: https://msdn.microsoft.com/en-us/library/ms159206.aspx
[55]SoramichiAkiyama,TakahiroHirofuchi,Shinichi Honiden,"Evaluating Impact of Live Migration onData Center Energy Saving, "Cloud Computing Technology and Science (CloudCom), 2014 IEEE 6th International Conference ,15-18 Dec. 2014,pp.759-762
[56]Inderjit Singh Dhanoa, Dr.Sawtantar Singh Khurmi,"Analyzing Energy Consumption during VM Live Migration,"Computing, Communication & Automation (ICCCA), 2015 International Conference ,15-16 May 2015, pp.584-588
[57]G. Galambos, and G. Woeginger, “On-line bin packing─A restricted survey,” Mathematical Methods of Operational Research, 1995.
[58]"TCP Congestion Control." RFC 5681. Available at: https://tools.ietf.org/html /rfc5681
[59]Ren Wang, Giovanni Pau, Kenshin Yamada, M.Y. Sanadidi, and Mario Gerla, "TCP Startup Performance in Large Bandwidth Delay Networks." INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, 7-11 March 2004.
[60]Jiao Zhang, Fengyuan Ren, and Chuang Lin,"Modeling and Understanding TCP Incast in DataCenterNetworks," Proceedings of the IEEE International Conference on Computer Communications (INFCOM). Shanghai, China, 2011 :1377-1385
[61]Jiao Zhang, Fengyuan Ren, and Chuang Lin,"Modeling and Solving TCP Incast Problem in DataCenter Networks," IEEE Transactions on Parallel and Distributed Systems ,VOL. 26, NO. 2, FEBRUARY 2015, pp. 478 – 491
[62]AnjaStrunk,"Costs of Virtual Machine Live Migration: A Survey.” Services (SERVICES), 2012 IEEE Eighth World Congress, 24-29 June 2012