Speed Scaling in Networks

Rahul Vaze
Arkadev Chattopadhyay
Friday, 25 Sep 2020, 11:30 to 12:30
Zoom Meeting https://zoom.us/j/7418257209?pwd=SGhITU5nYVBHRWhhbjc4VXdrZjNYZz09
The speed scaling problem has been widely studied in the literature, where there is a single server or a parallel bank of servers with variable speed. Choosing speed s, incurs a power cost given by a convex function P(s), whose integral is the total energy consumed. The problem is to find the optimal service speed/rate for servers that minimizes a linear combination of the flow time (total delay) and total energy. In this work, we take the first steps towards designing speed scaling algorithms for a network of servers. The network is described by a directed acyclic graph, where there are multiple sources that wish to send packets to their respective destinations. Algorithms are derived for both the worst case and stochastic job arrivals setting, whose competitive ratio depends only on the power functions and path diversity in the network, but is independent of the workload, and number of nodes of the network.