I detta dokument genomför vi den första studien av statistisk multiplexing ur perspektivet approximationalgoritmer. Den grundläggande frågan bakom statistisk multiplexing är följande: i höghastighetsnät, individuella anslutningar (dvs. Kommunikationssessioner) är mycket bw-sty, med överföringshastigheter som varierar kraftigt över tid. Som sådan, problemet med att packa flera anslutningar tillsammans på en länk blir mer subtil än i fallet när varje anslutning antas ha en fast efterfrågan. Vi anser att en av de mest studerade modellerna inom detta område: den av två kommunicerande noder som är anslutna av en uppsättning parallella kanter, där hastigheten av varje anslutning mellan dem är en slumpmässig variabel. Vi betraktar tre relaterade problem: (1) stokastisk lastbalansering, (2) stokastisk binpackning och (3) stokastisk knapsack. I det första problemet ges antalet länkar och vi vill minimera det förväntade värdet av den maximala belastningen. I de andra två problem länken kapacitet och konst försänkt over@w sannolikhet p anges, och målet är att tilldela anslutningar till länkar, så att sannolikheten för att belastningen överstiger länken kapacitet är som mest p. För stokastisk belastning balansering problem vi ger en O(l) - approximation algoritm för godtyckliga slumpvariabler. För de andra två problemen har vi algoritmer som är begränsade till on-off-källor (det vanligaste specialfallet som studeras i statistisk multiplexing-litteratur), med en standardapproach som har dykt upp för att hantera probabilistiska resursbehov är begreppet @ektiv bandbredd - detta är ett sätt att associera en fast efterfrågan med en bunsty-anslutning som "representerar" dess distribution så nära som möjligt. Våra approximationsalgoritmer använder standarddefinitionen av effektiv bandbredd och även en ny som vi introducq prestandagarantierna bygger på nya resultat som visar att en kombination av dessa åtgärder kan användas för att ge gränser på den optimala lösningen.
Kleinberg et al REF överväger trafikinträdeskontroll i höghastighetsnät och utvecklar approximationsalgoritmer för att lösa motsvarande problem med stochas tic bin packning som är begränsade till on-off-källor.
Allocating bandwidth for bursty connections
{'venue': "STOC '97", 'journal': None, 'mag_field_of_study': ['Computer Science']}