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.