Vi undersöker priset på självisk routing i icke-kooperativa nätverk i termer av samordning och bicriteria förhållandet i den nyligen införda spelet teoretiska nätverksmodellen av Koutsoupias och Papadimitriou. Vi presenterar den första grundliga studien av denna modell för allmänna, monotona familjer av kostnadsfunktioner och för kostnadsfunktioner från Queueing Theory. Våra huvudsakliga resultat kan sammanfattas på följande sätt. • Vi ger en exakt karakterisering av kostnadsfunktioner med ett begränsat/obundet samordningsförhållande. Till exempel har kostnadsfunktioner som beskriver den förväntade fördröjningen i kösystem ett obundet samordningsförhållande. • Vi visar att ett obundet samordningsförhållande dessutom innebär en extremt hög prestandanedbrytning under bikriterieåtgärder. Vi visar att priset på självisk routing kan vara lika högt som en bandbreddsnedbrytning av en faktor som är linjär i nätverksstorleken. • Vi skiljer spelteoretisk (integral) fördelning modell från (fraktionell) flöde modell genom att visa att även en mycket liten, i själva verket försumbar, mängd integrality kan leda till en dramatisk prestandanedbrytning. • Vi förenar de senaste resultaten av självisk dirigering under olika mål genom att visa att ett obundet samordningsförhållande under min-max-målet innebär ett obundet samordningsförhållande under det genomsnittliga målet (eller total-latency) och vice versa. Vårt särskilda fokus ligger på kostnadsfunktioner som beskriver beteendet hos webbservrar som bara kan öppna ett begränsat antal TCP-anslutningar. Framför allt jämför vi prestandan hos kösystem som betjänar alla inkommande förfrågningar med servrar som avvisar förfrågningar vid överbelastning. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. STOC '02, 19-21 maj 2002, Montreal, Quebec, Kanada. Upphovsrätt 2002/02/0005...$5.00. Av det resultat som presenteras i detta dokument drar vi slutsatsen att kösystem utan avvisande inte kan ge någon rimlig garanti för den förväntade fördröjningen av förfrågningar under självisk routing även när den injicerade lasten är långt ifrån systemets kapacitet. Däremot kan webbservrar som tillåts avvisa förfrågningar garantera en hög servicekvalitet för varje enskild begäran ström även under relativt höga injektionshastigheter.
I REF studerade författarna prestandan av självisk routing i en server gård med ett minmax-mål, det vill säga när målet är att minimera den maximala vistelsetiden i servrarna.
Selfish traffic allocation for server farms
{'venue': "STOC '02", 'journal': None, 'mag_field_of_study': ['Computer Science']}