Hub Based Routing of Highly Variable Traffic

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

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.