Patent ID: 7756042

Claim:
A method for optimally provisioning connectivity for network-based mobile virtual private network (VPN) services, the method comprising a network service provider for: identifying a set of virtual private network (VPN) customers, at least one mobile access point (MAP) and at least one customer premise equipment (CPE) associated with each VPN customer, and at least one Internet Protocol (IP) service gateway (IPSG) for facilitating VPN tunneling between a MAP and a CPE, wherein each MAP is geographically remote from each IPSG; and selecting a subset of IPSGs to maximize total profit resulting from provisioning a subset of VPN customers on the selected IPSGs by: (a) determining network parameters; (b) formulating an aggregate costs per customer for provisioning a customer and resultant profit; and (c) solving optimization problem for integer variable S ijk , Z jk such that profit G is maximized, wherein said total profit from all the customers comprises the sum of profits from each customer (l), where for each customer profit (U l ) equals weighted revenue (γV l ) less cost (C l ), (U l =γV l −C l ), wherein said cost per customer comprises a total tunnel bandwidth cost (C l C ) from said MAP to said CPE, and a cost (C l V ) of provisioning an IPSG node.