On the Optimal Placement of Web Proxies in the Internet: The Linear Topology

Bo Li, Xin Deng, Mordecai J. Golin, Kazem SohrabyHPN 1998 · OpenReview

Abstract

As web traffic grew exponentially in the late 1990s, network congestion and latency became critical issues. While caching content was a known solution, the strategic placement of these caches remained under-explored. This paper presents a mathematically optimal strategy for placing $m$ proxy servers within a linear network of $n$ potential sites. Using a dynamic programming approach, the authors provide a solution with $O(n^2m)$ time complexity, accounting for the interdependent traffic patterns created by proxy placement.

Introduction

The effectiveness of web caching depends not only on what is cached but also on where the cache is located. Sub-optimal placement wastes resources and fails to provide the maximum possible latency reduction for users. The challenge lies in the "downstream dependency": placing a proxy at one node reduces the traffic seen by all nodes between it and the origin server. This paper addresses this complexity by modeling the problem on a linear topology and seeking an arrangement that maximizes the total "Gain" (latency saved).

The Linear Model

The authors simplify the network into a linear array starting from a central web server. Each node $i$ is characterized by its distance $L(i)$ from the server and the traffic $P(i)$ passing through it.

Linear topology model showing the relationship between the web server, nodes, and traffic parameters.

In this model, $Q(i, j)$ represents the traffic originating between nodes $i$ and $j$. The goal is to select $m$ nodes to host proxies such that the total reduction in propagation delay is maximized.

Methodology: Dynamic Programming

The core contribution is the identification of an "optimal substructure" within the placement problem. An optimal arrangement of $m$ proxies for $n$ nodes contains an optimal arrangement of $m-1$ proxies for a subset of those nodes.

The authors developed a dynamic programming (DP) recurrence relation:

  1. Initialization: Determine the optimal single-proxy placement ($m=1$) for all possible segments of the line.
  2. Iteration: Iteratively build the solution for $m$ proxies using the results from $m-1$ proxies.
  3. Complexity: The algorithm runs in $O(n^2m)$ time, making it computationally efficient for practical network sizes.

Numerical Validation

To validate the algorithm, the authors used a synthetic 10-node network ($N=10$) with balanced traffic (each node contributing 10% of total traffic) and specific delay parameters.

Optimal proxy locations for varying numbers of proxies (m) in a 10-node network.

As shown in the table above, the algorithm identifies the specific set of nodes that maximize gain for any given number of proxies. For example, with 5 proxies, the optimal sites are nodes 4, 6, 8, 9, and 10.

Conclusion and Future Work

By treating latency as a distance and traffic as a flow, the authors transformed a network engineering problem into a geometric optimization task. While the linear model is a simplification, it serves as a foundational "base case" for more complex topologies. Future work involves extending this DP approach to tree topologies, which better represent hierarchical Internet structures, and exploring dynamic placement strategies that adapt to changing traffic patterns.

Summary updated

BibTeX
@inproceedings{li1998optimal,
  author = {Bo Li and Xin Deng and Mordecai J. Golin and Kazem Sohraby},
  title = {{On the Optimal Placement of Web Proxies in the Internet: The Linear Topology}},
  booktitle = {HPN},
  year = {1998},
  url = {https://openreview.net/forum?id=Kpra3WTBCj},
}
Figure