Abstrakt. Vi anser att virtuella kretsen multicast routing i ett nätverk av länkar som är hastighet skalbar. Vi antar att en länk till last f använder effekt σ + f α, där σ är den statiska effekten, och α > 1 är något konstant. Vi antar att en länk kan stängas av om den inte används. Som svar på ankomsten av klienten i på vertex ti en routing bana (den virtuella kretsen) Pi ansluter en fast källa s att sjunka ti måste fastställas. Målet är att minimera den sammanlagda effekt som används av alla länkar. Vi ger en polylog-konkurrenskraftig online-algoritm, och en polynom tid O(α)-uppskattning offline algoritm om effektfunktionerna för alla länkar är samma. Om varje länk kan ha en annan effektfunktion, visar vi att problemet är APX-hård. Om dessutom kanterna kan styras, då visar vi att ingen poly-log approximation är möjlig i polynom tid enligt standard komplexa antaganden. Dessa är de första resultaten på multicast routing i hastighet skalbara nätverk i algoritmisk litteratur.
Bansal m.fl. REF studera en minimal kostnad virtuella krets multicast routing problem med hastighet skalbara länkar.
Multicast Routing for Energy Minimization Using Speed Scaling
{'venue': 'MedAlg', 'journal': None, 'mag_field_of_study': ['Computer Science']}