A Lagrangean Relaxation Approach for IP Network CFA Problems Whith End-to-end Qos Performance Constraints

Abstract

The traditional approaches to optimal design and planning of packet-switching networks focus on the networklayer infrastructure, thus neglecting end-to-end Quality of Service (e2e QoS) issues, and Service Level Agreement (SLA) guarantees. This is quite inappropriate since the Internet today carries a wide range of critical telecommunication services. In this paper, we propose a packet network design and planning approach that considers the dynamics of packet networks, as well as the effect of protocols at the different layers of the Internet architecture on the e2e QoS experienced by end-users. Our proposed approach maps the end-user performance constraints into transport-layer performance constraints first, and then into network-layer performance constraints. This translating process is then considered together with a refined TCP/IP traffic modeling technique that is both simple and capable of producing accurate performance estimates for general-topology packet networks subject to realistic traffic patterns. We illustrate an example of its application to the optimization of link capacities and routing in a corporate VPN (Virtual Private Network) where traffic is mainly due to TCP connections. An efficient Lagrangean relaxation based heuristic procedure is developed to find bounds and solutions for the considered problem. Numerical results for a variety of problem instances are reported.