Shortest Path Versus Multihub Routing in Networks With Uncertain Demand

Alexandre Fréchette, F. Bruce Shepherd, Marina K. Thottan, Peter J. WinzerIEEE/ACM Trans. Networking 2015 · OpenReview

TL;DR

This paper introduces the "capped hose model" for network traffic, which bridges the gap between fixed demand and purely marginal demand models. They propose and evaluate "hierarchical multi-hub routing" (HH) as a more cost-effective solution than traditional shortest path or single-hub routing for these more realistic, uncertain traffic demands.

What Problem Does This Paper Address?

Designing robust communication networks is crucial, especially as traffic patterns become increasingly dynamic and unpredictable. Traditional approaches often fall into two extremes: designing for fixed, peak point-to-point demands (which can be overly conservative and expensive) or designing for "hose models" where only node ingress/egress capacities (marginals) are known (which can also lead to over-provisioning if specific point-to-point demands are known to be lower). The authors identify a gap: how to design networks that are cost-effective when we have some information about both peak demands and marginal capacities, but not a fully deterministic picture. This "capped hose model" aims to capture this intermediate scenario.

Methods

The core of the paper is the introduction and analysis of the capped hose model for traffic demand. This model combines node marginals (like in the hose model) with specific point-to-point peak demands. To address the robust network design (RND) problem under this model, they propose hierarchical hub routing (HH) templates. HH is a generalization of single-hub and tree routing, allowing for multiple levels of hubs to manage traffic within different "regions" of the network. They develop a heuristic algorithm called Binary Tree Sparsest Merging (BTSM) to construct these HH templates. To understand when HH is beneficial, they introduce marginal and peak demand strength metrics (μ and π) to characterize traffic patterns.

Datasets

The authors evaluate their approach using two real-world carrier network topologies:

  • Abilene network: A US backbone network with 11 nodes and 14 edges.
  • Telstra network: An Australian telecom network with 104 nodes and 151 edges.

Traffic data is generated in two ways:

  1. Randomly generated traffic: Based on population statistics and a gravity model for peak demands, with marginals sampled from relevance intervals.
  2. Time-series traffic data: From the Abilene network, using real point-to-point demand measurements over several weeks to create capped hose models.

Key Insights and Ideas

  • The "Capped Hose" is More Realistic: Neither the fixed-demand nor the unconstrained hose model fully captures the nuances of modern network traffic. The capped hose model offers a more flexible and potentially cost-saving approach.
  • Hierarchical Hubs Outperform Simpler Models: For many capped hose scenarios, hierarchical multi-hub routing (HH) is significantly more cost-effective than both shortest path (SP) and single-hub (HUB) routing. This suggests that as traffic becomes more dynamic and less predictable, more sophisticated routing structures are needed.
  • Traffic Characteristics Dictate Routing Choice: The introduced marginal (μ) and peak demand (π) strength metrics provide a way to classify traffic instances. This classification can help predict whether SP or HH routing will be more suitable, offering a potential strategy for carriers to choose their routing templates.
  • Multi-Hubbing Matters: The study highlights that moving beyond single-hub designs to hierarchical multi-hub structures can yield substantial cost benefits, especially when dealing with complex traffic patterns.

Key Results

  • Empirical studies on the Abilene and Telstra networks show that HH routing templates are often more cost-effective than SP and single-hub routing for capped hose traffic models.
  • The paper demonstrates that HH can be significantly cheaper than SP, and conversely, SP can be cheaper than HH, indicating that these routing strategies are not universally superior and depend on the traffic characteristics.
  • Analysis of real traffic data shows that as the time horizon for traffic sampling increases, the traffic becomes more "hose-like" (stronger marginals), favoring more flexible routing like HH. Conversely, shorter sampling intervals (more stable traffic) favor SP.

Limitations and Future Work

  • Heuristic for HH: The paper uses a heuristic (BTSM) for constructing HH templates, meaning the reported HH costs are not necessarily the absolute minimum but are good approximations.
  • Computational Complexity: While the paper discusses theoretical aspects, the empirical evaluation involves computationally intensive optimization problems (RNDSP, RNDHH).
  • Future Work: The authors suggest that their μ and π metrics could be used to develop a practical indicator for carriers to choose between SP and HH routing. They also note that their work opens the door to further investigation into the broader space of robust network design problems with more complex traffic models.

Summary updated

Abstract

We study a class of robust network design problems motivated by the need to scale core networks to meet increasingly dynamic capacity demands. Past work has focused on one of two models. First, design the network for the known point-to-point peak demands. Second, design the network to support all hose matrices (all matrices not exceeding marginal bounds at the nodes). Both models may be too conservative if additional information on traffic patterns is available. We introduce a capped hose model to explore a range of traffic scenarios, which includes the above two as special cases. It is known that optimal network designs for the hose model are always determined by single-hub routing, and for the fixed-demand model are based on shortest-path routing. We demonstrate that a wider variety of routing templates is required to address the broader spectrum of capped hose matrices. We propose the use of hierarchical multihub routing templates, a generalization of hub and tree routing. Our empirical analysis is based on a heuristic for the resulting robust network design problem. These lead to two important findings: 1) designs based on multihub routing are often preferable to both hub and shortest path; 2) it may be possible for a carrier to sample their traffic in order to determine which type of routing is most cost-effective for their network.
BibTeX
@article{frechette2015shortest,
  author = {Alexandre Fréchette and F. Bruce Shepherd and Marina K. Thottan and Peter J. Winzer},
  title = {{Shortest Path Versus Multihub Routing in Networks With Uncertain Demand}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2015},
  url = {https://openreview.net/forum?id=VktduFe00LA},
}
Figure