Access the full text.
Sign up today, get DeepDyve free for 14 days.
F. Grandoni, V. Kaibel, G. Oriolo, M. Skutella (2007)
A short proof of the VPN Tree Routing Conjecture on ring networksOper. Res. Lett., 36
S. Sengupta (2005)
Efficient and robust routing of highly variable traffic
Anupam Gupta, J. Kleinberg, Amit Kumar, R. Rastogi, B. Yener (2001)
Provisioning a virtual private network: a network design problem for multicommodity flow
N. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. Ramakrishnan, Jacobus Merive (1999)
A flexible model for resource management in virtual private networks
H. Kerivin, W. Ben-Ameur (2003)
NEW ECONOMICAL VIRTUAL PRIVATE NETWORKSCommunications of The ACM, 46
(2004)
Netswitch: Load-balanced data-over-optical architecture for mesh networks
Cheng-Shang Chang, D. Lee, Yi-Shean Jou (2002)
Load balanced Birkhoff-von Neumann switches, part I: one-stage bufferingComput. Commun., 25
Y. Azar, Edith Cohen, A. Fiat, Haim Kaplan, Harald Räcke (2003)
Optimal oblivious routing in polynomial timeJ. Comput. Syst. Sci., 69
C. Kaklamanis, D. Krizanc, Thanasis Tsantilas (1990)
Tight bounds for oblivious routing in the hypercubeMathematical systems theory, 24
P. Winzer, F. Shepherd, P. Oswald, M. Zimgibl (2005)
Robust network design and selective randomized load balancing, 1
S. Sengupta, Vijay Kumar, D. Saha (2003)
Switched optical backbone for cost-effective scalable core IP networksIEEE Commun. Mag., 41
G. Italiano, S. Leonardi, G. Oriolo (2006)
Design of trees in the hose model: The balanced caseOper. Res. Lett., 34
Samuel Fiorini, G. Oriolo, Laura Sanità, D. Theis (2007)
The VPN Tree Routing Conjecture for Outerplanar NetworksarXiv: Optimization and Control
A. Altin, E. Amaldi, P. Belotti, M. Pınar (2007)
Provisioning virtual private networks under traffic uncertaintyNetworks, 49
T. Erlebach, M. Rüegg (2004)
Optimal bandwidth reservation in hose-model VPNs with multi-path routingIEEE INFOCOM 2004, 4
Rui Zhang-Shen, N. McKeown (2004)
Designing a Predictable Internet Backbone Network
A. Ben-Tal, A. Nemirovski (1999)
Robust solutions of uncertain linear programsOper. Res. Lett., 25
P. Belotti, F. Malucelli, L. Brunetta (2007)
Tailoring neighborhood search for the internet protocol network design problem with reliability and routing constraintsNetworks, 49
David Applegate, E. Cohen (2003)
Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs
W. Ben-Ameur, H. Kerivin (2003)
Networks new economical virtual privateCommun. ACM, 46
D. Mitra, R. Cieslak (1987)
Randomized parallel communications on an extension of the omega networkJ. ACM, 34
Cheng-Shang Chang, D. Lee, Ching-Ming Lien (2002)
Load balanced Birkhoff-von Neumann switches, part II: multi-stage bufferingComput. Commun., 25
I. Keslassy, Shang-Tse Chuang, Kyoungsik Yu, D. Miller, M. Horowitz, O. Solgaard, N. McKeown (2003)
Scaling internet routers using optics
C. Hurkens, J. Keijsper, L. Stougie (2005)
Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring NetworksSIAM J. Discret. Math., 21
Jeff Hartline, Alexa Sharp (2007)
Incremental flow, 50
Harald Räcke (2002)
Minimizing Congestion in General Networks
Georgios Petrou, C. Lemaréchal, A. Ouorou (2007)
An approach to robust network design in telecommunicationsRAIRO Oper. Res., 41
F. Shepherd, P. Winzer (2006)
Selective randomized load balancing and mesh networks with changing demandsJournal of Optical Networking, 5
C. Chekuri (2007)
IntroductionSIGACT News, 38
A. Ben-Tal, A. Nemirovski (1998)
Robust Convex OptimizationMath. Oper. Res., 23
I. Widjaja, A. Elwalid (2003)
Exploiting parallelism to boost data-path rate in high-speed IP/MPLS networkingIEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428), 1
A. Borodin, J. Hopcroft (1982)
Routing, merging and sorting on parallel models of computation
F. Leighton, Satish Rao (1999)
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJ. ACM, 46
J. Fingerhut, S. Suri, Jonathan Turner (1997)
Designing Least-Cost Nonblocking Broadband NetworksJ. Algorithms, 24
The VPN Conjecture is True Navin Goyal College of Computing Georgia Institute of Technology Atlanta, GA, USA Neil Olver Department of Mathematics and Statistics McGill University Montreal, QC, Canada F. B. Shepherd Department of Mathematics and Statistics McGill University Montreal, QC, Canada navin001@gmail.com ABSTRACT olver@math.mcgill.ca bruce.shepherd@mcgill.ca We consider the following network design problem. We are given an undirected graph G = (V, E) with edges costs c(e) and a set of terminal nodes W . A hose demand matrix for W is any symmetric matrix [Dij ] such that for each i, P j=i Dij ¤ 1. We must compute the minimum cost edge capacities that are able to support the oblivious routing of every hose matrix in the network. An oblivious routing template, in this context, is a simple path Pij for each pair i, j ˆ W . Given such a template, if we are to route a demand matrix D, then for each i, j we send Dij units of ‚ow along each Pij . Fingerhut et al. [12] and Gupta et al. [15] obtained a 2-approximation for this problem, using a solution template in the form of a tree. It has been widely asked
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.