document: Efficient and robust streaming provisioning in VPNs Today , most large companies maintain virtual private networks ( VPNs ) to connect their remote locations into a single secure network . VPNs can be quite large covering more than 1000 locations and in most cases use standard Internet protocols and services . Such VPNs are implemented using a diverse set of technologies such as Frame Relay , MPLS , or IPSEC to achieve the goal of privacy and performance isolation from the public Internet . Using VPNs to distribute live content has recently received tremendous interest . For example , a VPN could be used to broadcast a CEO-employee town hall meeting . To distribute this type of content economically without overloading the network , the deployment of streaming caches or splitters is most likely required . In this paper , we address the problem of optimally placing such streaming splitters or caches to broadcast to a given set of VPN endpoints under the constraints typically found within a VPN . In particular , we introduce an efficient algorithm with complexity O ( V ) , V being the number of routers in the VPN . This guarantees the optimal cache placement if interception is used for redirection . We prove that the general problem is NP-hard and introduce multiple heuristics for efficient and robust cache placement suitable under different constraints . At the expense of increased implementation complexity , each heuristic solution provides additional saving in the number of caches required . We evaluate proposed solutions using extensive simulations . In particular , we show our flow-based solution is very close to the optimal .
doc_bio_tags: O O O O O O B O O O O O O O O O O B O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O