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

The traditional approaches to optimal design and planning of packet-switching networks focus on the network layer infrastructure, thus neglecting end-to-end Quality of Service (e2e QoS) issues, and Service Level Agreement (SLA) guarantees. This is quite inappropriate since the Inter net 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 per formance constraints into transport-layer performance con straints first, and then into network-layer performance con straints. 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 esti mates for general-topology packet networks subject to realis tic traffic patterns. We illustrate an example of its application to the optimization of link capacities and routing in a corpo rate 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 so lutions for the considered problem. Numerical results for a variety of problem instances are reported.