Improved algorithm produces more efficient traffic management for cloud data
Tue 29 Nov 2016
Researchers from universities in Ghana and Nigeria have improved a commonly-used data center traffic management algorithm, increasing efficiency in cloud computing through effective resource allocation and traffic management.
The algorithm, which applies calculated average mean time to execute for a bundle of tasks, optimizes the allocation of resources and assigning of priorities, resulting in better efficiency and reduced operating time than the existing Max-Min algorithm.
Data centers must assign and prioritize tasks within the existing environment to optimize resource allocation throughout the system. Currently, many data centers employ a Max-Min scheduling algorithm, which queues tasks based on their estimated time to complete. The time required to complete all tasks is measured as makespan. The research team adjusted the Max-Min algorithm in an effort to reduce makespan, thereby narrowing the performance gap between service providers and users.
They did this by noting that the Max-Min algorithm consistently places the tasks requiring the most time to execute on the fastest available machine or resource, which completes that task in the fastest possible time frame.
However, giving these tasks priority to the fastest machines increases the total length of the scheduled tasks, or makespan, by delaying tasks requiring the minimum time to execute. This is particularly evident if the number of complex requests requiring maximum execution time outstrips the number of simple requests made to the system.
The team proposed an improved Max-Min algorithm that works in two phases. First, like the existing algorithm, it assembles all requests in increasing order of the time required to execute. But then, instead of a streamlined queueing system, whereby tasks are selected from the ordered list with maximum execution time tasks receiving highest priority for resources, the team implemented arithmetic and geometric means, to calculate the average execution time for assigned tasks.
Tasks were then assigned based not upon which required the maximum time to execute, but rather on which tasks approached the calculated mean time to execute. Middle-of-the-road requests, requiring average time to execute, were completed first and statistical outliers (max and min) requests were completed last.
CloudSim was used to test the original Max-Min algorithm against the improved version. Experimental results show that using means calculations and assigning tasks based on proximity to the mean, rather than consistently selecting those requiring the highest execution time, results in a better makespan and improved resource optimization compared to the original algorithm.
This finding held best for datasets of 50-100 requests. When the number of requests was over 1000, the benefits of the improved algorithm were negligible.
The researchers propose that in the future, the research be extended to study simultaneous executing of tasks which they believe could improve efficiency even further.