Minimum congestion mapping in a cloud

N. Bansal, K.-W. Lee, V. Nagarajan, M. Zafer

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    59 Citaten (Scopus)


    We study a basic resource allocation problem that arises in cloud computing environments. The physical network of the cloud is represented as a graph with vertices denoting servers and edges corresponding to communication links. A workload is a set of processes with processing requirements and mutual communication requirements. The workloads arrive and depart over time, and the resource allocator must map each workload upon arrival to the physical network. We consider the objective of minimizing the congestion. We show that solving a subproblem about mapping a single workload to the physical graph essentially suffices to solve the general problem. In particular, an a-approximation for this single mapping problem gives an O(a log nD)-competitive algorithm for the general problem, where n is the number of nodes in the physical network and D is the maximum to minimum workload duration ratio. We also show how to solve the single mapping problem for two natural class of workloads, namely depth-d-trees and complete-graph workloads. For depth-d tree, we give an nO(d) time O(d2 log (nd))-approximation based on a strong LP relaxation inspired by the Sherali-Adams hierarchy.
    Originele taal-2Engels
    TitelProceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2011, San Jose CA, USA, June 6-8, 2011)
    Plaats van productieNew York NY
    UitgeverijAssociation for Computing Machinery, Inc
    ISBN van geprinte versie978-1-4503-0719-2
    StatusGepubliceerd - 2011


    Duik in de onderzoeksthema's van 'Minimum congestion mapping in a cloud'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit