# A note on hierarchical hubbing for a generalization of the VPN problem

@article{Olver2016ANO, title={A note on hierarchical hubbing for a generalization of the VPN problem}, author={Neil Olver}, journal={Oper. Res. Lett.}, year={2016}, volume={44}, pages={191-195} }

Robust network design refers to a class of optimization problems that occur when designing networks to efficiently handle variable demands. In this context, Frechette et?al. (2013) recently explored hierarchical hubbing: a routing strategy involving a multiplicity of "hubs" connected to terminals and each other in a treelike fashion. For a natural generalization of the VPN problem, we prove a structural characterization implying that the optimal hierarchical hubbing solution can be found… Expand

#### Figures and Topics from this paper

#### 3 Citations

Shortest Path Versus Multihub Routing in Networks With Uncertain Demand

- Computer Science
- IEEE/ACM Transactions on Networking
- 2015

Designs based on multihub routing are often preferable to both hub and shortest path; 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. Expand

Exploring the Tractability of the Capped Hose Model

- Computer Science
- ESA
- 2017

This work uncovers further tractable cases of the capped hose model, and involves optimally embedding a certain auxiliary graph into the network, and has a connection to a heuristic suggested by Frechette et al. Expand

#### References

SHOWING 1-10 OF 20 REFERENCES

Hub routing for the robust network design problem

- Computer Science
- 2013

Conditions under which multi-hub routings, that is HH, gives improvements over single-hub and shortest path routings are revealed, and a heuristic algorithm for RNDHH is developed and provided. Expand

Shortest path versus multi-hub routing in networks with uncertain demand

- Computer Science
- 2013 Proceedings IEEE INFOCOM
- 2013

By adding peak capacities into the hose model, the single-hub tree-routing template is no longer cost-effective and this initiates the study of a class of robust network design (RND) problems restricted to these templates. Expand

Provisioning a virtual private network: a network design problem for multicommodity flow

- Computer Science, Mathematics
- STOC '01
- 2001

This work establishes a relation between this collection of network design problems and a variant of the facility location problem introduced by Karger and Minkoff, and provides optimal and approximate algorithms for several variants of this problem, depending on whether the traffic matrix is required to be symmetric. Expand

Approximability of robust network design

- Mathematics, Computer Science
- SODA '10
- 2010

This paper establishes that the general robust design is hard to approximate to within polylogarithmic factors, and gives a constant factor approximation algorithm for this problem that achieves factor 8 in general, and 2 for the case where the tree has unit capacities. Expand

Provisioning a Virtual Private Network Under the Presence of Non-communicating Groups

- Computer Science
- CIAC
- 2006

A variant of the virtual private network design problem which generalizes the previously studied symmetric and asymmetric case, where the terminal set is partitioned into a number of groups, where terminals of each group do not communicate with each other. Expand

Robust network design

- Mathematics
- 2010

Robust network design takes the very successful framework of robust optimization and applies it to the area of network design, motivated by applications in communication networks. The main premise is… Expand

Designing Least-Cost Nonblocking Broadband Networks

- Computer Science
- J. Algorithms
- 1997

This paper proposes a new model for broadband networks and investigates the question of their optimal topology from a worst-case performance point of view, and shows that a minimum-cost nonblockingstarnetwork achieves near-optimal cost. Expand

Selective randomized load balancing and mesh networks with changing demands

- Computer Science
- 2006

Of these three networks, SRLB maintains the resilience properties of RLB while achieving a significant cost reduction over all other architectures, including RLB and multihop Internet protocol/multiprotocol label switching (IP/MPLS) networks using VPN-tree routing. Expand

A flexible model for resource management in virtual private networks

- Computer Science
- SIGCOMM '99
- 1999

A new service interface is proposed, termed a hose, to provide the appropriate performance abstraction to manage network resources in the face of increased uncertainty, and the statistical multiplexing and resizing techniques deal effectively with uncertainties about the traffic. Expand

Approximation algorithms for the 0-extension problem

- Mathematics, Computer Science
- SODA '01
- 2001

It is proved that the integrality ratio of the metric relaxation is at least c√lgk for a positive c for infinitely many k and the results improve some of the results of Kleinberg and Tardos and they further the understanding on how to use metric relaxations. Expand