I den här artikeln överväger vi problemet med ftp på nätet. Målet är att tillhandahålla en sekvens av filöverföringsförfrågningar med tanke på bandbreddsbegränsningarna i det underliggande kommunikationsnätet. Det huvudsakliga resultatet av papperet är en teknik som leder till algoritmer som optimerar flera naturliga mätvärden, såsom Mu-Stretch, total flödestid, max flödestid och total fullbordad tid. I synnerhet visar vi hur man uppnår optimal total flödestid och optimal max. stretch om vi ökar kapaciteten i det underliggande nätverket med en logaritmisk faktor. Vi visar att resursen förstärkning är nödvändig genom att bevisa polynom lägre gränser på max stretch och total flödestid för fallet där online- och offline algoritmer använder samma kapacitet kanter. Dessutom ger vi också poly-logaritmiska lägre gränser på den resursförstärkningsfaktor som krävs för att hålla den totala Aow tiden och max. stretch inom en konstant faktor för optimal. Alla önskemål. Eftersom bandbredden i länkarna i nätverket är begränsad, är det vettigt att försöka schemalägga överföringarna på ett sätt som utnyttjar tillgängliga resurser optimalt. I detta dokument anser vi att problemet med online ftp, som är en formell abstraktion av ovanstående problem med filöverföring. Vi antar att varje ftp begäran anger källa/destination noder och storleken på filen. Målet med online-algoritmen är att välja en sökväg som kommer att användas för att överföra varje fil, och att minska:" på överföringshastigheten. Den största skillnaden mellan denna modell och de (välstuderade) modellerna för online routing och tillträdeskontroll 111, 1, 12,2] är att vi här inte antar att källorna har på förhand specificerade överföringshastighetskrav, dvs.. Vi kan hantera icke-streaming typer av information. Det finns två relaterade mått på prestanda som kan användas för att jämföra olika algoritmer för online ftp problem. Det första måttet är den totala flödestiden, dvs. Summan över alla jobb av den tid som förflyter mellan det ögonblick ftp-begäran lämnas in och den tid den är nöjd (inklusive sändningstiden). Den andra åtgärden är rn~-Stretch, vilket är max. imum över alla förhållanden av flödestiden för varje begäran och den minsta tid som krävs för att uppfylla denna begäran. Den andra kvantiteten bestäms av länken bandbredd och storleken på filen. Båda bländningarna är användbara eftersom de är direkt relaterade till nätets prestanda som uppfattas av slutanvändaren. Låt n vara antalet förfrågningar och P det maximala förhållandet mellan filernas storlek. Anta att den minsta begäran kan behandlas i en enhet. Låt FL, betecknar det optimala max-flödet dvs. Det minsta värdet för den maximala tid en begäran används i systemet. De viktigaste resultaten av papperet är algoritmer som uppnår den optimala maz-Stretch och den optimala totala j% w tid med hjälp av resursförstärkning." För max. stretch-algoritmen behöver vi öka kapaciteten med en faktor av O(log P), medan den totala flödestidsalgoritmen behöver en faktor av O(log FGAx) ökade 189
Referens REF diskuterar problemet online ftp, där reservationer görs för kanaler för överföring av olika filer.
Scheduling data transfers in a network and the set scheduling problem
{'venue': "STOC '99", 'journal': None, 'mag_field_of_study': ['Computer Science']}