Sharing the "cost" of multicast trees: an axiomatic analysis

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.