Models and algorithms for the design of service overlay networks

被引：9

作者：

Capone, Antonio ^{[1
]}

Elias, Jocelyn ^{[1
]}

Martignon, Fabio ^{[2
]}

机构：

[1] Department of Electronics and Information, Politecnico di Milano, Milan

[2] Department of Information Technology and Mathematical Methods, University of Bergamo, Dalmine

来源：

IEEE Transactions on Network and Service Management | 2008年 / 5卷 / 03期

关键词：

Heuristics; Network Planning; Optimization; Overlay Networks; Service Deployment; Service-Level Agreements;

D O I：

10.1109/TNSM.2009.031102

中图分类号：

学科分类号：

摘要：

Service Overlay Networks (SONs) can provide endto- end Quality of Service guarantees in the Internet without requiring significant changes to the underlying network infrastructure. A SON is an application-layer network operated by a third-party Internet Service Provider (ISP) that owns a set of overlay nodes, residing in the underlying ISP domains, interconnected by overlay links. The deployment of a SON can be a capital-intensive investment, and hence its planning requires careful decisions, including the overlay nodes' placement, the capacity provisioning of overlay links as well as of access links that connect the end-users to the SON infrastructure. In this paper, we propose two novel optimization models for the planning of SONs. The first model minimizes the SON installation cost while providing full coverage to all network's users. The second model maximizes the SON operator's profit by further choosing which users to serve, based on the expected gain, and taking into consideration budget constraints. We also introduce two efficient heuristics to get near-optimal solutions for largescale instances in a reasonable computation time. We provide numerical results of the proposed models and heuristics on a set of realistic-size instances, and discuss the effect of different parameters on the characteristics of the planned networks. We show that in the considered network scenarios the proposed heuristics perform close to the optimum with a short computing time. © 2009 IEEE.

引用

页码：143 / 156

页数：13

共 32 条

[1]

Integrated Services Charter

[2]

Differentiated Services Charter

[3]

Duan Z., Zhang Z.-L., Hou Y.T., Service overlay networks: SLAs, QoS, and bandwidth provisioning, IEEE/ACM Trans. Networking, 11, 6, pp. 870-883, (2003)

[4]

Li Z., Mohapatra P., QRON: QoS-aware routing in overlay networks, IEEE J. Select. Areas Commun, 22, 1, pp. 29-40, (2004)

[5]

Subramanian L., Stoica I., Balakrishnan H., Katz R.H., OverQoS: Offering Internet QoS using overlays, Proc. 1st Workshop on Hot Topics in Networks HotNets-I, (2002)

[6]

Touch J., Hotz S., The X-Bone, Proc. Third Global Internet Mini-Conference, pp. 75-83, (1998)

[7]

Tran H.T., Ziegler T., A design framework towards the profitable operation of service overlay networks, Computer Networks, 51, 1, pp. 94-113, (2007)

[8]

Rosen E., Viswanathan A., Callon R., Multiprotocol Label Switching Architecture, (2001)

[9]

Vieira S.L., Liebeherr J., Topology design for service overlay networks with bandwidth guarantees, Proc. 12th IEEE International Workshop on Quality of Service (IWQoS), pp. 211-220, (2004)

[10]

Li Z., Mohapatra P., On investigating overlay service topologies, Computer Networks, 51, 1, pp. 54-68, (2007)

← 1 2 3 4 →