article

Optimal link weights for IP-based networks supporting hose-model VPNs

Authors:

Chin-Tau LeaAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 17, Issue 3

Pages 778 - 788

https://doi.org/10.1109/TNET.2008.2006219

Published: 01 June 2009 Publication History

Abstract

From traffic engineering point of view, hose-model VPNs are much easier to use for customers than pipe-model VPNs. In this paper we explore the optimal weight setting to support hose-model VPN traffic in an IP-based hop-by-hop routing network. We try to answer the following questions: 1) What is the maximum amount of hose-model VPN traffic with bandwidth guarantees that can be admitted to an IP-based hop-by-hop routing network (as opposed to an MPLS-based network), and 2) what is the optimal link weight setting that can achieve that? We first present a mixed-integer programming formulation to compute the optimal link weights that can maximize the ingress and egress VPN traffic admissible to a hop-by-hop routing network. We also present a heuristic algorithm for solving the link weight searching problem for large networks. We show simulation results to demonstrate the effectiveness of the search algorithm.

References

[1]

N. G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. K. Ramakrishnan, and J. E. V. der Merwe, "A flexible model for resource management in virtual private networks," in ACM SIGCOMM, San Diego, CA, Aug. 1999.

Digital Library

[2]

A. Jüttner, I. Szabo, and A. Szentesi, "On bandwidth efficiency of the hose resource management model in virtual private networks," in IEEE INFOCOM 2003, San Francisco, CA, Apr. 2003.

[3]

E. Rosen and Y. Rekhter, "BGP/MPLS VPNs," RFC 2547, Mar. 1999.

[4]

S. Kent and R. Atkinson, "Security architecture for the internet protocol," RFC 2401, Nov. 1998.

[5]

J. Lau, M. Townsley, and I. Goyret, "Layer two tunneling protocol--version 3 (L2TPv3)," RFC 3931, Mar. 2005.

[6]

A. Kumar, R. Rastogi, A. Silberschatz, and B. Yener, "Algorithms for provisioning virtual private networks in the hose model," in ACM SIGCOMM, Cambridge, MA, Aug. 2001.

Digital Library

[7]

J. Chu and C. T. Lea, "New architecture and algorithms for fast construction of hose-model VPNs," IEEE/ACM Trans. Networking, vol. 16, no. 4, pp. 670-679, Aug. 2008.

Digital Library

[8]

M. Kodialam, T. V. Lakshman, and S. Sengupta, "Maximum throughput routing of traffic in the hose model," in IEEE INFOCOM 2006, Apr. 2006.

[9]

J. Moy, "OSPF Version 2," RFC 2328, Apr. 1998.

[10]

R. Callon, "Use of OSI IS-IS for routing in TCP/IP and dual environments," RFC 1195, Dec. 1990.

[11]

B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing world," IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 756-757, 2002.

Digital Library

[12]

M. Pióro, A. Szentesi, J. Harmatos, A. Jüttner, P. Gajowniczek, and S. Kozdrowski, "On OSPF related network optimization problems," Perform. Eval., vol. 48, pp. 201-223, 2002.

Digital Library

[13]

K. Holmberg and D. Yuan, "Optimization of internet protocol network design and routing," Networks, vol. 43, pp. 39-53, 2004.

Digital Library

[14]

Z. Wang, Y. Wang, and L. Zhang, "Internet traffic engineering without full mesh overlaying," in IEEE INFOCOM 2001, Anchorage, AK, Apr. 2001.

[15]

B. Fortz and M. Thorup, "Robust optimization of OSPF/IS-IS weights," in Proc. INOC, 2003.

[16]

A. Sridharan and R. Guérin, "Making IGP routing robust to link failures," Networking 2005, pp. 634-646.

Digital Library

[17]

A. Altin, P. Belotti, and M. C. Pinar, "OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty," Tech. Report, Nov. 2006.

[18]

Configuring OSPF, Cisco, 1997.

[19]

A. Sridharan, R. Guérin, and C. Diot, "Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks," in IEEE INFOCOM 2003, San Francisco, CA, Apr. 2003.

[20]

J. Chu and C. T. Lea, "Routing and restoration in networks with hose-model traffic patterns," HPSR'05, May 2005.

[21]

A. Altin, E. Amaldi, P. Belotti, and M. C. Pinar, "Provisioning virtual private networks under traffic uncertainty," DEI, Politecnico di Milano, Milano, Italy, Tech. Rep. no. 16, Jan. 2005.

[22]

D. Applegate and E. Cohen, "Making intra-domain routing robust to changing and uncertain traffic demands: Understanding fundamental tradeoffs," in ACM SIGCOMM, Karlsruhe, Germany, Aug. 2003.

Digital Library

[23]

CPLEX, ILOG CPLEX Division {Online}. Available: http://www. cplex.com/

[24]

Load Balancing With Cisco Express Forwarding, Cisco, Applicat. Note.

[25]

D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, "Optimization by simulated annealing: An experimental evaluation," Oper. Res., vol. 39, no. 1, May-Jun. 1991.

[26]

C. Zhang, Y. Liu, W. Gong, J. Kurose, R. Moll, and D. Towsley, "On optimal routing with multiple traffic matrices," in IEEE INFOCOM 2005, Mar. 2005.

[27]

M. Pióro, Routing, Flow, and Capacity Design in Communication and Computer Networks. New York: Morgan Kaufmann, 2004.

Digital Library

[28]

N. Spring, R. Mahajan, and D. Wetherall, "Measuring ISP topologies with Rocketfuel," in ACM SIGCOMM, 2002.

Digital Library

[29]

A. Medina, A. Lakhina, I. Matta, and J. Byers, BRITE: Boston University Representative Internet Topology Generator, Boston Univ., Boston, MA, Apr. 2001 {Online}. Available: http://www.cs.bu.edu/ brite

[30]

B. M. Waxman, "Routing of multipoint connections," IEEE J. Sel. Areas Commun., vol. 6, pp. 1617-1622, Dec. 1988.

Digital Library

Cited By

Ding MGuo YHuang ZLin BLuo H(2024)GROMJournal of Network and Computer Applications10.1016/j.jnca.2024.103927229:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.jnca.2024.103927
Zhang JGuo ZYe MChao H(2020)SmartEntryProceedings of the Workshop on Network Meets AI & ML10.1145/3405671.3405809(1-7)Online publication date: 10-Aug-2020
https://dl.acm.org/doi/10.1145/3405671.3405809
Ouédraogo IOki E(2016)A Green and Robust Optimization Strategy for Energy Saving Against Traffic UncertaintyIEEE Journal on Selected Areas in Communications10.1109/JSAC.2016.254537834:5(1405-1416)Online publication date: 19-May-2016
https://dl.acm.org/doi/10.1109/JSAC.2016.2545378
Show More Cited By

Recommendations

Resource optimization algorithms for virtual private networks using the hose model

Virtual private networks (VPNs) provide a secure and reliable communication between customer sites over a shared network. With increase in number and size of VPNs, service providers need efficient provisioning techniques that adapt to customer demands. ...
New architecture and algorithms for fast construction of hose-model VPNs

Hose-model virtual private networks (VPNs) provide customers with more flexibility in specifying bandwidth requirements than pipe-model VPNs. Many hose-model VPN provisioning algorithms have been proposed, and they focus on the bandwidth efficiency in ...
Load-balanced IP routing scheme based on shortest paths in hose model

This paper proposes a simple shortest-path-based load-balanced Internet-Protocol (IP) routing scheme based on the hose model. The proposed scheme is an extension of the Smart-OSPF (S-OSPF) scheme. The proposed scheme, the same as S-OSPF, splits traffic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 3

June 2009

329 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 June 2009

Revised: 24 July 2007

Received: 01 January 2007

Published in TON Volume 17, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
291
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ding MGuo YHuang ZLin BLuo H(2024)GROMJournal of Network and Computer Applications10.1016/j.jnca.2024.103927229:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.jnca.2024.103927
Zhang JGuo ZYe MChao H(2020)SmartEntryProceedings of the Workshop on Network Meets AI & ML10.1145/3405671.3405809(1-7)Online publication date: 10-Aug-2020
https://dl.acm.org/doi/10.1145/3405671.3405809
Ouédraogo IOki E(2016)A Green and Robust Optimization Strategy for Energy Saving Against Traffic UncertaintyIEEE Journal on Selected Areas in Communications10.1109/JSAC.2016.254537834:5(1405-1416)Online publication date: 19-May-2016
https://dl.acm.org/doi/10.1109/JSAC.2016.2545378
Lin SWang PLuo M(2016)Jointly optimized QoS-aware virtualization and routing in software defined networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.08.00396:C(69-78)Online publication date: 26-Feb-2016
https://dl.acm.org/doi/10.1016/j.comnet.2015.08.003
Zhang JXi KChao H(2015)Load balancing in IP networks using generalized destination-based multipath routingIEEE/ACM Transactions on Networking10.1109/TNET.2014.234817623:6(1959-1969)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1109/TNET.2014.2348176
Li KWang SXu SWang XHuang HRen JZhai B(2014)Evaluating the benefit of the core-edge separation on intradomain traffic engineering under uncertain traffic demandJournal of Network and Computer Applications10.5555/2773807.277404540:C(216-226)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.5555/2773807.2774045
Xuan YLea C(2011)Network-coding multicast networks with QoS guaranteesIEEE/ACM Transactions on Networking10.1109/TNET.2010.206253319:1(265-274)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1109/TNET.2010.2062533

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents