Abstrakt. Vi studerar algoritmiska problem som motiveras av bandbreddshandel i nästa generations nätverk. Vanligtvis innebär bandbreddshandel säljare (t.ex., nätoperatörer) som är intresserade av att sälja bandbreddsrör som erbjuder köpare en garanterad servicenivå under ett visst tidsintervall. Köparna (t.ex. bandbreddsmäklare) är ute efter att upphandla bandbreddsrör för att tillgodose slutanvändarnas önskemål om bokning (t.ex. Internetprenumeranter). Beroende på vad som är tillgängligt i bandbreddsbörsen, är målet för en köpare att antingen spendera den minsta mängden pengar för att tillfredsställa alla reservationer som görs av sina kunder, eller att maximera sina intäkter från alla reservationer kan tillfredsställas. Vi modellerar detta som ett icke förebyggande schemaläggningsproblem i realtid där maskintyper motsvarar bandbreddsrör och jobb motsvarar förfrågningar om bokning för slutanvändare. Varje jobb anger ett tidsintervall under vilket det måste bearbetas, och en uppsättning maskintyper som det kan utföras på. Tillstånd att göra digitala eller hårda kopior av delar eller allt detta arbete för personligt bruk eller klassrum beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller direkt kommersiell fördel och att kopior visar detta meddelande på första sidan eller första skärmen av en skärm tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Behörighet kan begäras från publikationsavdelningen, ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, eller behörigheter@acm.org. Vid behov kan flera maskiner av en viss typ tilldelas, men var och en måste betalas för. Slutligen, varje jobb har förknippat med det en inkomst, vilket realiseras om jobbet är planerad på någon maskin. Det finns två versioner av problemet som vi överväger. I kostnadsminimeringsversionen är målet att minimera den totala kostnaden för schemaläggning alla jobb, och i intäktsmaximeringsversionen målet är att maximera intäkterna från de jobb som är planerade för bearbetning på en given uppsättning maskiner. Vi överväger flera varianter av de problem som uppstår i praktiska scenarier, och ger konstanta faktor approximationer.
Det har också förekommit tidigare arbete med problemet med att schemalägga alla jobb på en uppsättning maskiner för att minimera den totala kostnaden (se t.ex. REF ), men i dessa arbeten kostnaden för schemaläggning varje jobb är fast.
Algorithmic aspects of bandwidth trading
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics']}