Theory Seminar

Energy Efficient Multicommodity Routing

Viswanath Nagarajan

Assistant Professor
University of Michigan
 
Friday, September 12, 2014
10:30am - 11:30am
BBB 3941

 

About the Event

We consider virtual circuit routing protocols, with an objective of minimizing energy, in a network of components that are speed scalable, and that may be shutdown when idle. We assume that the speed s of the router is proportional to its load, and assume the standard model for component power, namely that the power is some constant static power plus s^b, where typically b is between 1.1 and 3. We give a polynomial-time off-line algorithm that is the combination of three natural combinatorial algorithms, and show that for any fixed b the algorithm has approximation ratio O(log^b k), where k is the number of demand pairs. The algorithm extends rather naturally to a randomized online algorithm, which we show has competitive ratio O~(log^{3b +1} k). This is the first online result for the problem. We also show that this online algorithm has competitive ratio O~(log^{b+1} k) for the case that all connections have a common source. Joint work with Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs, and Cliff Stein:

Additional Information

Contact: Grant Schoenebeck

Event Sponsor: CSE

Open to: Public