Modeling and Optimization Algorithm for Capacity Planning in Hose Model VPN Networks

Hose-based VPNs offer greater bandwidth flexibility, as they allow traffic to and from a hose endpoint to be arbitrarily distributed across other endpoints. Existing studies on hose-based VPNs have primarily focused on VPN provisioning algorithms, while optimal capacity planning for hose-based VPN networks remains largely unexplored. Given budget constraints and forecasts of future bandwidth demands at VPN endpoints, the capacity planning problem requires the joint optimization of routing decisions and link capacity allocation. Although the problem can be formulated as a nonlinear programming model, its nonconvex nature makes direct solution computationally challenging. To address this issue, we reformulate the problem as a sequence of linear programming problems and develop a solution framework based on a water-filling algorithm. For any defined budget and relative tolerance, the proposed algorithm yields a near-optimal solution where the network expansion cost stays within the allowed margin. Numerical results demonstrate that the proposed approach efficiently solves the hose-based VPN capacity planning problem within practical computation time.