Vi studerar ett grundläggande resursfördelningsproblem som uppstår i molndatamiljöer. Det fysiska nätverket av molnet representeras som en graf med hörn som anger servrar och kanter som motsvarar kommunikationslänkar. En arbetsbörda är en uppsättning processer med bearbetningskrav och ömsesidiga kommunikationskrav. Arbetsbelastningen anländer och avgår över tid, och resursallokatorn måste kartlägga varje arbetsbelastning vid ankomsten till det fysiska nätverket. Vi anser att målet är att minska trängseln. Vi visar att lösa ett subproblem (SingleMap) om att kartlägga en enda arbetsbörda till den fysiska grafen i huvudsak räcker för att lösa det allmänna problemet. I synnerhet ger en α-approximation för SingleMap en O(α log nD)-kompetitiv algoritm för det allmänna problemet, där n är antalet noder i det fysiska nätverket och D är den maximala till minsta arbetsbelastningsförhållandet. Vi visar också hur man löser SingleMap för två naturliga klass av arbetsbelastningar, nämligen djupd träd och komplett-graf arbetsbelastning. För djupd träd, ger vi en n O(d) tid O(d 2 log(nd))-uppskattning baserad på en stark LP avkoppling inspirerad av Sherali-Adams hierarki.
I sitt intressanta arbete, Bansal et al. REF ger en n Opdq tid Opd 2 log pndqq- tillnärmning algoritm för att minimera belastningen av inbäddningar i trädliknande datacenter nätverk, baserat på en stark LP avkoppling inspirerad av Sherali-Adams hierarki.
Minimum congestion mapping in a cloud
{'venue': "PODC '11", 'journal': None, 'mag_field_of_study': ['Chemistry', 'Computer Science']}