Network Routing for Efficient Energy Usage

Thursday, December 9, 2010 - 11:00am - 12:00pm EST

  • Location:Dibner Building, LC 400
    Five Metrotech Center

    Brooklyn, New York
  • Price:

Speaker: Dr. Lisa Zhang

Faculty Host: Professor Shivendra Panwar


This talk consists of two parts. The first part presents an experimental study that estimates the opportunity for saving electricity in typical service-provider IP networks, using both rate-adaptive network elements and power-aware traffic routing. Service provider networks have significant daily fluctuation in traffic; the energy-savings opportunity is largest during periods of light traffic. However, since service-provider networks are overprovisioned to provide redundancy in case of failure, there is opportunity even in periods of heavy traffic. We observe that the two techniques together provide more benefit than either alone.
The second part focuses on a theoretical study that provides approximation algorithms for a routing problem, for which the incurred cost for carrying traffic is superadditive. Routing under subadditive cost functions corresponds to the well-known buy-at-bulk network design. The case of superadditive cost functions is less studied and it aims to model energy consumption of computing and communication devices. We show a polylogarithmic approximation for a general solution and a constant approximation for a special case.

About the Speaker

Lisa Zhang is a member of technical staff in the Algorithms Research Group at Bell Labs in Murray Hill, NJ.  She received her BA, summa cum laude, in mathematics from Wellesley College in 1993 and her PhD in Theory of Computing from the Massachusetts Institute of Technology in 1997. Her research area is algorithm design and analysis. Her research broadly concerns algorithmic and complexity issues of networking, with a focus on design and optimization, routing and scheduling protocols, and stability and Quality-of-Service analyses. She twice won the Bell Labs President's Gold Award and the Lucent Chairman's Award.