Sharing the “cost” of multicast trees: an axiomatic analysis

ABSTRACT

Given the need to provide users with reasonable feedback about the "costs" their network usage incurs, and the increasingly commercial nature of the Internet, we believe that the allocation of cost among users will play an important role in future networks. This paper discusses cost allocation in the context of multicast flows. The question we discuss is this: when a single data flow is shared among many receivers, how does one split the cost of that flow among the receivers? Multicast routing increases network efficiency by using a single shared delivery tree. We address the issue of how these savings are allocated among the various members of the multicast group. We first consider an axiomatic approach to the problem, analyzing the implications of different distributive notions on the resulting allocations. We then consider a one-pass mechanism to implement such allocation schemes and investigate the family of allocation schemes such mechanisms can support.

REFERENCES

• 1: Tony Ballardie , Paul Francis , Jon Crowcroft, Core based trees (CBT), Conference proceedings on Communications architectures, protocols and applications, p.85-95, September 13-17, 1993, San Francisco, California, United States
• 2: H.W. Braun and K. Claffy. A Framework for Flow- Based Accounting on the Internet. Proceedings of SICON '93, fEEE Singapore, 1993.
• 3: David D. Clark , Scott Shenker , Lixia Zhang, Supporting real-time applications in an Integrated Services Packet Network: architecture and mechanism, Conference proceedings on Communications architectures & protocols, p.14-26, August 17-20, 1992, Baltimore, Maryland, United States
• 4: Ron Cocchi , Scott Shenker , Deborah Estrin , Lixia Zhang, Pricing in computer networks: motivation, formulation, and example, IEEE/ACM Transactions on Networking (TON), v.1 n.6, p.614-627, Dec. 1993 [doi>10.1109/90.266050]
• 5: Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
• 6: Stephen Deering , Deborah Estrin , Dino Farinacci , Van Jacobson , Ching-Gung Liu , Liming Wei, An architecture for wide-area multicast routing, Proceedings of the conference on Communications architectures, protocols and applications, p.126-135, August 31-September 02, 1994, London, United Kingdom
• 7: D. Henriet and H. Moulin Traffic Based Cost Allocation in a Network. Rand Journal of Economics, forthcoming.
• 8: S.C. Littlechfld and G. Owen A Simple Expression for the Shapley Value in a Special Case. Management Sci. ence, ~0, 370-~, 1973.
• 9: Jeffrey K. MacKie-Mason , Hal R. Varian, Pricing the Internet, Public access to the Internet, MIT Press, Cambridge, MA, 1995
• 10: J.K. MacKie-Mason and H.R. Varian. Pricing Congestable Network Resources. Preprint, October 1994.
• 11: N. Megiddo Computational Complexity of the Game Theory Approach to Cost Allocation for ,{ Tree. Mathematics of Operations Research, 3, 189-96, 1978.
• 12: H. Moulin Uniform Externalities: Two Axioms for Fair Allocation. Journal o} Public Economy ,i3 (1990) p305- 326.
• 13: H. Moulin Welfare Bound in the Cooperative Production Problem. Games and Economic Behavior Volume ~, (1992) p 37S-~01.
• 14: It. Moulin and S. Shenker Average Cost Pricing versus Serial Cost Sharing: An Axiomatic Comparison. Journal of Economic Theory 6Z(1), (199~) p. 178-201.
• 15: R.B. Myerson Game Theory. Harvard University Press, Cambridge, Massachusetts, 1991.
• 16: it. Peyton and I. Young (Eds.). Cost AUoc~tion: Methods, Principles, Applications. Elseviers Science Publishers, B. V., Amsterdam, The Netherlands and New York, N. v., V.S.A., ~985.
• 17: A.E. Roth (Ed.). The Shapley Value, an Essay in Honor of Lloyd S. Shapley. Cambridge University Press, Cambridge, 1988.
• 18: J. Sairamesh , D. F. Ferguson , Y. Yemini, An approach to pricing, optimal allocation and quality of service provisioning in high-speed packet networks, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 3)-Volume, p.1111, April 02-06, 1995
• 19: L.S. Shapley A Value for N-Person Games. In H.W. Kuhn and A.W. Tucker (Eds.), Contributions to the Theory of Games, Vol Ii, Annals o} Mathematics Studies No. 28, Princeton, N J: Princeton University Press, 307- ~ 7, 195a.
• 20: W.W. Sharkey Network Models in Economics. Handbook ost Operations Research and Management Science: Networks, to appear.
• 21: Scott Shenker, Service models and pricing policies for an integrated services Internet, Public access to the Internet, MIT Press, Cambridge, MA, 1995
• 22: L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala RSVP: A New Resource Reservation Protocol. IEEE Networks Magazine, September 1993.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: Internet

General Terms:
Algorithms, Design, Performance