Tata Institute of Fundamental Research
Speed Scaling in Networks
STCS Faculty Seminar
Speaker:
Rahul Vaze
Organiser:
Arkadev Chattopadhyay
Date:
Friday, 25 Sep 2020, 11:30 to 12:30
Venue:
Zoom Meeting https://zoom.us/j/7418257209?pwd=SGhITU5nYVBHRWhhbjc4VXdrZjNYZz09
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Rahul Vaze |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Friday, 25 Sep 2020, 11:30 to 12:30 |
| Venue: | Zoom Meeting https://zoom.us/j/7418257209?pwd=SGhITU5nYVBHRWhhbjc4VXdrZjNYZz09 |
(Scan to add to calendar)
Abstract:
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.