The demand for cloud computing has increased manifold in the recent past.More specifically,on-demand computing has seen a rapid rise as organizations rely mostly on cloud service providers for their day-to-day computi...The demand for cloud computing has increased manifold in the recent past.More specifically,on-demand computing has seen a rapid rise as organizations rely mostly on cloud service providers for their day-to-day computing needs.The cloud service provider fulfills different user requirements using virtualization-where a single physical machine can host multiple VirtualMachines.Each virtualmachine potentially represents a different user environment such as operating system,programming environment,and applications.However,these cloud services use a large amount of electrical energy and produce greenhouse gases.To reduce the electricity cost and greenhouse gases,energy efficient algorithms must be designed.One specific area where energy efficient algorithms are required is virtual machine consolidation.With virtualmachine consolidation,the objective is to utilize the minimumpossible number of hosts to accommodate the required virtual machines,keeping in mind the service level agreement requirements.This research work formulates the virtual machine migration as an online problem and develops optimal offline and online algorithms for the single host virtual machine migration problem under a service level agreement constraint for an over-utilized host.The online algorithm is analyzed using a competitive analysis approach.In addition,an experimental analysis of the proposed algorithm on real-world data is conducted to showcase the improved performance of the proposed algorithm against the benchmark algorithms.Our proposed online algorithm consumed 25%less energy and performed 43%fewer migrations than the benchmark algorithms.展开更多
Classical algorithms and data structures assume that the underlying memory is reliable,and the data remain safe during or after processing.However,the assumption is perilous as several studies have shown that large an...Classical algorithms and data structures assume that the underlying memory is reliable,and the data remain safe during or after processing.However,the assumption is perilous as several studies have shown that large and inexpensive memories are vulnerable to bit flips.Thus,the correctness of output of a classical algorithm can be threatened by a few memory faults.Fault tolerant data structures and resilient algorithms are developed to tolerate a limited number of faults and provide a correct output based on the uncorrupted part of the data.Suffix tree is one of the important data structures that has widespread applications including substring search,super string problem and data compression.The fault tolerant version of the suffix tree presented in the literature uses complex techniques of encodable and decodable error-correcting codes,blocked data structures and fault-resistant tries.In this work,we use the natural approach of data replication to develop a fault tolerant suffix tree based on the faulty memory random access machine model.The proposed data structure stores copies of the indices to sustain memory faults injected by an adversary.We develop a resilient version of the Ukkonen’s algorithm for constructing the fault tolerant suffix tree and derive an upper bound on the number of corrupt suffixes.展开更多
文摘The demand for cloud computing has increased manifold in the recent past.More specifically,on-demand computing has seen a rapid rise as organizations rely mostly on cloud service providers for their day-to-day computing needs.The cloud service provider fulfills different user requirements using virtualization-where a single physical machine can host multiple VirtualMachines.Each virtualmachine potentially represents a different user environment such as operating system,programming environment,and applications.However,these cloud services use a large amount of electrical energy and produce greenhouse gases.To reduce the electricity cost and greenhouse gases,energy efficient algorithms must be designed.One specific area where energy efficient algorithms are required is virtual machine consolidation.With virtualmachine consolidation,the objective is to utilize the minimumpossible number of hosts to accommodate the required virtual machines,keeping in mind the service level agreement requirements.This research work formulates the virtual machine migration as an online problem and develops optimal offline and online algorithms for the single host virtual machine migration problem under a service level agreement constraint for an over-utilized host.The online algorithm is analyzed using a competitive analysis approach.In addition,an experimental analysis of the proposed algorithm on real-world data is conducted to showcase the improved performance of the proposed algorithm against the benchmark algorithms.Our proposed online algorithm consumed 25%less energy and performed 43%fewer migrations than the benchmark algorithms.
文摘Classical algorithms and data structures assume that the underlying memory is reliable,and the data remain safe during or after processing.However,the assumption is perilous as several studies have shown that large and inexpensive memories are vulnerable to bit flips.Thus,the correctness of output of a classical algorithm can be threatened by a few memory faults.Fault tolerant data structures and resilient algorithms are developed to tolerate a limited number of faults and provide a correct output based on the uncorrupted part of the data.Suffix tree is one of the important data structures that has widespread applications including substring search,super string problem and data compression.The fault tolerant version of the suffix tree presented in the literature uses complex techniques of encodable and decodable error-correcting codes,blocked data structures and fault-resistant tries.In this work,we use the natural approach of data replication to develop a fault tolerant suffix tree based on the faulty memory random access machine model.The proposed data structure stores copies of the indices to sustain memory faults injected by an adversary.We develop a resilient version of the Ukkonen’s algorithm for constructing the fault tolerant suffix tree and derive an upper bound on the number of corrupt suffixes.
