Approximation Algorithms for Data Networks

数据网络的近似算法

• 批准号: 1320854
• 负责人: Shuchi Chawla
• 金额: $ 35.42万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320854&HistoricalAwards=false
• 关键词: Approximation; Algorithms; 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.

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