Hub Based Routing of Highly Variable Traffic

许多新兴的互联网应用程序的特点是随着时间的推移具有难以预测的高度可变的流量行为。大多数解决这类网络设计问题的经典方法都依赖于对单个流量矩阵进行估计的模型。在这种情况下，数学模型允许更极端的交通不可预测性。然而，网络设计模型将以一种鲁棒和有效的方式得到解决。考虑的流量变化模型在假设方面是最小的——只有每个节点的总需求是已知的，而节点对之间的实际流量需求可能随着时间的推移而不可预测地变化。为了以资源高效和稳健的方式路由这些可变的交通，本研究将调查一类通过“枢纽”发送流量的方案，这是一种传统上与航空公司调度和卡车路线等运输问题相关的技术。现实世界的约束要求路由在很长一段时间内保持一致——它不能动态地改变以响应需求的变化。PI将根据该方案开发基于线性规划的算法和快速组合算法，用于最小成本网络设计和最大吞吐量网络路由。还将对该方案进行扩展，以提供针对链路和节点故障的弹性。算法方法的性能将与实际互联网服务提供商（ISP）网络拓扑上路由可变流量的其他方法的性能进行比较。用于比较的方案包括(a)沿着固定路径的直接源-目的路由（而不是通过集线器）和(b)允许路由动态依赖于当前流量矩阵的最优方案。这项研究有可能为处理流量模式极端可变性的路由架构的未来部署做出重大贡献。此外，这些方法可以应用于需求变化很大的运输中出现的网络设计问题。

Many emerging applications for the Internet are characterized by highly variable traffic behavior over time that is difficult to predict. Most of the classical approaches to this network design problem rely on a model in which a single traffic matrix is estimated. In this grant, the mathematical models permits much more extreme traffic unpredictability. Nevertheless, the network design models will be solved in a robust and efficient manner. The traffic variation model considered is minimalist in terms of assumptions -- only the aggregate demand at each node is known while the actual traffic demands between pairs of nodes may vary unpredictably over time. For routing such variable traffic in a resource efficient and robust manner, this research will investigate a class of schemes that send flows through "hubs", a technique that is traditionally associated with transportation problems such as airline scheduling and truck routing. Real-world constraints require that the routing be consistent for long periods of time -- it cannot change dynamically in response to changes in demands. The PI will develop linear programming based algorithms and fast combinatorial algorithms for minimum cost network design and maximum throughput network routing under the scheme. There will also be extensions of the scheme to provide resiliency against link and node failures. The performance of the algorithmic approaches will be compared with that of other methods for routing variable traffic on actual Internet Service Provider (ISP) network topologies. The schemes for comparison include (a) direct source-destination routing (instead of through hubs) along fixed paths, and (b) an optimal scheme that is allowed to make the routing dynamically dependent on the current traffic matrix.This research has the potential for contributing significantly to future deployment of routing architectures for handling extreme variability in traffic patterns. Moreover, these methodologies may have applications to network design problems arising in transportation in which demand is highly variable.