Hub Based Routing of Highly Variable Traffic

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

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.