Abstract-Effektiviteten av tillhandahållande av tjänster i storskaliga nätverk är i hög grad beroende av antalet och placeringen av serviceanläggningar som används vid olika värdar. Den klassiska, centraliserade metoden för att bestämma den senare skulle innebära att formulera och lösa problemet med okapacitet k-median (UKM) (om det begärda antalet anläggningar är fast), eller problemet med okapacitet anläggning (UFL) (om antalet anläggningar också ska optimeras). Det är uppenbart att sådana centraliserade tillvägagångssätt kräver kunskap om global topologisk information och kräver information, och därför inte skalas och är inte praktiskt för stora nätverk. Den viktigaste frågan som ställs och besvaras i detta dokument är följande: "Hur kan vi på ett distribuerat och skalbart sätt fastställa antal och plats för serviceanläggningar?" Vi föreslår en innovativ strategi där topologi och efterfrågan information är begränsad till bostadsområden, eller bollar med liten radie runt utvalda anläggningar, medan efterfrågan information fångas implicit för de återstående (fjärr) klienter utanför dessa områden, genom att kartlägga dem till kunder i utkanten av grannskapet; bollradien reglerar avvägningen mellan skalbarhet och prestanda. Vi utvecklar en skalbar, distribuerad strategi som besvarar vår nyckelfråga genom en iterativ återoptimering av platsen och antalet anläggningar inom sådana bollar. Vi visar att även för små värden av radien (1 eller 2), vår distribuerade strategi uppnår prestanda under olika syntetiska och verkliga Internet topologier som är jämförbar med den av optimala, centraliserade metoder som kräver full topologi och efterfrågan information.
Utnyttjandet av de centraliserade algoritmerna i en lokal region (r-balls) kräver kunskap om topologin och kräver information i denna region, och hädanefter algoritmen i REF är inte en fullt distribuerad algoritm.
Distributed Placement of Service Facilities in Large-Scale Networks
{'venue': 'IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications', 'journal': 'IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications', 'mag_field_of_study': ['Computer Science']}