Approximation Algorithms for Data Networks

点击翻译按钮获取中文摘要

This project seeks to develop new algorithmic techniques for thedesign of and routing in data networks. Classical network optimizationproblems address transportation networks that carry physicalcommodities. Data networks are fundamentally different --- data can bemodified, compressed, and replicated at little cost. Incorporatingthis flexibility in altering traffic into network optimizationproblems can bring about a considerable improvement in the capacitiesof communication networks.This project aims to revisit classical network optimization problemswithin a new model where the cost of carrying data is non-linear anddepends on its compressibility. It aims to provide theoreticalunderpinnings for new WAN optimization approaches proposed in thenetworking literature, including, for example, traffic redundancyelimination.The PI considers a model where links in the network can compress data andremove duplicate packets. For example, if two traffic streams containidentical data and use overlapping routes, edges carrying both streamsneed only transmit the common packets once; these can then bereplicated at routers where the streams diverge. Accordingly, the loadon an edge is a submodular function of the traffic streams that usethe edge. Unlike previous work on network optimization with non-linearcosts, in this model, the cost of routing depends on the identities ofthe traffic streams involved, and not just on the total trafficvolume. Most of the problems considered are computationallyintractable and the PI aims to develop approximation algorithms.Several graduate and undergraduate courses will benefit from this project.