Approximation Algorithms for Data Networks

该项目旨在为数据网络的设计和路由开发新的算法技术。经典的网络优化问题解决的是运载实物商品的运输网络。数据网络从根本上是不同的——数据可以以很小的成本被修改、压缩和复制。将这种改变流量的灵活性纳入网络优化问题可以大大提高通信网络的容量。该项目旨在在一个新的模型中重新审视经典的网络优化问题，其中携带数据的成本是非线性的，并且取决于其可压缩性。它旨在为网络文献中提出的新的广域网优化方法提供理论基础，包括，例如，流量冗余消除。PI考虑了一个模型，其中网络中的链路可以压缩数据并删除重复的数据包。例如，如果两个流量流包含相同的数据并且使用重叠的路由，则承载两个流的边缘只需要传输一次公共数据包；然后，这些可以在流分叉的路由器上复制。因此，边缘上的负载是使用该边缘的流量流的子模块函数。与以前的非线性成本网络优化工作不同，在这个模型中，路由的成本取决于所涉及的交通流的身份，而不仅仅取决于总流量。考虑的大多数问题在计算上是难以解决的，PI旨在开发近似算法。一些研究生和本科课程将受益于这个项目。

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.