Efficient and robust streaming provisioning in VPNs

Z. Morley Mao (茅斫青), Zhuoqing Morley Mao, David Johnson, Oliver Spatscheck, Jacobus E. van der Merwe, Jia WangWWW 2003 · DOI

TL;DR

This paper tackles the challenge of efficiently delivering live video streams within corporate VPNs, where traditional multicast is often unavailable. They propose and evaluate algorithms for strategically placing caching servers to minimize both the number of caches and overall network bandwidth usage, proving the core problem is NP-hard but offering efficient solutions for practical scenarios.

What Problem Does This Paper Address?

Large organizations often use Virtual Private Networks (VPNs) to connect their numerous remote locations into a single, secure network. While VPNs are great for general connectivity and privacy, they present a significant challenge when it comes to distributing high-bandwidth, real-time content like live video streams (e.g., CEO town halls). The typical VPN architecture, often a "hub-and-spoke" model, struggles with the sheer volume of unicast streams required to reach thousands of endpoints. Simply increasing bandwidth on all links is prohibitively expensive, especially across geographically dispersed locations. The paper addresses the problem of optimally deploying streaming cache servers within these VPNs to alleviate this bottleneck, aiming to minimize the number of caches needed and the associated bandwidth consumption.

Methods

The paper introduces a two-pronged approach:

  • Interception Proxy-Based Solution: For scenarios where network infrastructure can be modified to intercept traffic at the network layer (layer 3), the authors develop provably optimal algorithms.
  • Greedy Minimum Cache Placement: A greedy algorithm is proposed to find the minimum number of caches required. It works by identifying "red nodes" (routers where demand exceeds capacity) and placing caches starting from the farthest nodes from the origin server, working inwards. This approach is proven to yield the optimal number of caches.
  • Minimum Bandwidth Usage: Following the greedy placement, a dynamic programming algorithm is used to further optimize the placement of these caches to minimize total bandwidth usage.
  • Additional Redirection Systems (Heuristics): For scenarios where layer 3 interception isn't feasible, the paper explores layer 7 redirection (e.g., DNS, HTTP/RTSP). Since this problem is NP-hard, they propose heuristics:
  • Router-Based Redirection: Clients connected to the same router are directed to the same cache.
  • Client-Based Redirection: A finer-grained approach where individual clients can be directed to different caches.

The paper also addresses robustness by evaluating algorithm performance under imperfect network topology and link capacity estimations.

Datasets

Not discussed in the paper. The authors used a custom simulator and generated network topologies based on the GT-ITM internetwork topology generator.

Key Insights and Ideas

  • VPNs are a unique challenge for streaming: The hub-and-spoke architecture and cost constraints of VPNs make traditional internet streaming solutions less applicable.
  • Optimal cache placement is NP-hard: The core problem of finding the absolute minimum number of caches is computationally intractable for large networks.
  • Layer 3 interception enables optimal solutions: When traffic can be intercepted at the network layer, provably optimal algorithms for both cache count and placement can be achieved.
  • Greedy is surprisingly effective: The greedy algorithm for minimum cache placement is not only efficient but also provides the optimal number of caches when interception is used.
  • Finer-grained redirection pays off: For non-interception scenarios, client-based redirection (as opposed to router-based) can significantly reduce the number of caches needed, especially in large networks.
  • Robustness matters: Real-world VPNs have imperfect data. The algorithms' performance under estimated capacities and link sharing is crucial for practical deployment.

Key Results

  • The paper proves that the minimum cache placement problem is NP-hard by reducing it from the Exact Cover by 3-Sets problem.
  • The greedy algorithm for interception proxy-based redirection achieves the provably optimal minimum number of caches.
  • The dynamic programming approach for minimum bandwidth usage, following the greedy placement, can achieve up to 20% improvement in bandwidth saving, with an average of 4.1%.
  • For non-interception scenarios, client-based redirection can reduce the number of caches by over 17% compared to router-based redirection in large networks.
  • In robustness evaluations, even with imperfect topology data, the percentage of unsatisfied users remained below 6%.

Limitations and Future Work

  • Assumptions: The paper assumes a single distribution tree for interception proxy-based solutions and doesn't explicitly consider server load as a bottleneck (though it notes this can be modified).
  • Future Work: The authors plan to investigate the impact of source routing (available in MPLS VPNs) on cache placement, as it could potentially allow for more optimized data transfer paths beyond shortest paths, further reducing cache requirements. They also aim to verify their algorithms by implementing them in a large VPN.

Summary updated

BibTeX
@inproceedings{2003efficient,
  author = {Z. Morley Mao (茅斫青) and Zhuoqing Morley Mao and David Johnson and Oliver Spatscheck and Jacobus E. van der Merwe and Jia Wang},
  title = {{Efficient and robust streaming provisioning in VPNs}},
  booktitle = {The Web Conference},
  year = {2003},
  doi = {10.1145/775152.775170},
}
Figure