Cost sharing mechanisms for near-optimal traffic aggregation and network design

ABSTRACT

A fundamental network design problem is the one of Traffic Aggregation or Network Design. The goal is to design a network which is able to support a unit flow for each commodity, at a time, between its source-sink pair, e.g., to support buffered multicast traffic. When the flows are unsplittable, this corresponds to the Steiner forest problem and to the problem of sharing cost of multicast by different users.

As a result of greedy selfish behavior of users in the network design game, the overall quality of the resulting solution is often not as good as the globally optimum solution of the underlying problem. We are therefore interested in the problem of designing distributed cost sharing mechanisms that induce the selfish agents to converge to the near-optimum solutions.

In this paper, our main contribution is showing that (1+ε) ratio can be achieved by (non-obvious) unfair cost sharing mechanism, at least for the fractional version of the problem. Our second contribution is showing how to implement our cost sharing mechanism which guarantees fast convergence to a near-optimum equilibrium.

REFERENCES

• 1: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 2: Elliot Anshelevich , Anirban Dasgupta , Eva Tardos , Tom Wexler, Near-optimal network design with selfish agents, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780617]
• 3: Baruch Awerbuch , Rohit Khandekar, Greedy distributed optimization of multi-commodity flows, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281140]
• 4: Miguel Castro , Peter Druschel , Anne-Marie Kermarrec , Animesh Nandi , Antony Rowstron , Atul Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 5: Simon Fischer , Berthold Vöcking, Adaptive routing with stale information, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073868]
• 6: Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132608]
• 7: Naveen Garg , Rohit Khandekar, Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.500, November 16-19, 2002
• 8: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 9: Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, On the topologies formed by selfish peers, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146403]
• 10: V. Pai, K. Kumar, K. Tamilmani, V. Sambamurthy, and A. Mohr. Chainsaw: Eliminating trees from overlay multicast. In International Workshop on Peer-to-Peer Systems, 2005.
• 11: Dongyu Qiu , R. Srikant, Modeling and performance analysis of BitTorrent-like peer-to-peer networks, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
cost sharing mechanism, network design, traffic aggregation