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.