Abstract-We studerar multicast i en icke-kooperativ miljö där information flödar själviskt rutt sig genom de billigaste vägar som finns tillgängliga. Den största utmaningen är att se till att sådana själviska multicastflöden stabiliseras vid en socialt optimal driftpunkt med minimala totala kantkostnader, genom lämplig kostnadsfördelning och andra ekonomiska åtgärder, med replikerbara och kodbara egenskaper hos informationsflöden som beaktas. Vi visar att kända kostnadsfördelningssystem inte är tillräckliga. Vi tillhandahåller en skuggprisbaserad kostnadsfördelning för nät utan kapacitetsbegränsningar, och visar att det upprätthåller minimikostnadsmulticast. Detta förbättrar tidigare resultat där ett 2-ungefärligt multicastflöde upprätthålls. För kapacierade nät ger beräkning av kostnader genom att man bortser från kantkapacitet inte korrekta resultat. Vi visar att ett system med kantskatt kan kombineras med en kostnadsfördelning för att strikt upprätthålla optimala multicastflöden i detta mer realistiska fall. Om skatter inte är önskvärda kan de återföras till flöden samtidigt som det optimala flödet upprätthålls. Vi relaterar skatterna till VCG:s betalningssystem och diskuterar en effektiv primal-dual algoritm som samtidigt beräknar skatterna, kostnadsfördelningen och det optimala multicastflödet.
Våra bevis använder det dubbla linjära programmet för nätverkskodad multicast, först studeras av REF, som visade att de dubbla variablerna kan användas som en kantkostnad fördelningsschema för att genomdriva optimal multicast routing i närvaro av självisk nätverkstrafik.
Min-Cost Multicast of Selfish Information Flows
{'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']}