2nd International ICST Workshop on Network Coding, Theory, and Applications

Research Article

Min-cost Selfish Multicast with Network Coding

  • @INPROCEEDINGS{10.1109/WIOPT.2006.1666512,
        author={Sandeep  Bhadra  and Sanjay  Shakkottai and Piyush  Gupta},
        title={Min-cost Selfish Multicast with Network Coding},
        proceedings={2nd International ICST Workshop on Network Coding, Theory, and Applications},
        publisher={IEEE},
        proceedings_a={NETCOD},
        year={2006},
        month={8},
        keywords={},
        doi={10.1109/WIOPT.2006.1666512}
    }
    
  • Sandeep Bhadra
    Sanjay Shakkottai
    Piyush Gupta
    Year: 2006
    Min-cost Selfish Multicast with Network Coding
    NETCOD
    IEEE
    DOI: 10.1109/WIOPT.2006.1666512
Sandeep Bhadra 1,*, Sanjay Shakkottai1, Piyush Gupta1
  • 1: Wireless Networking and Communication Group, Department of ECE, University of Texas at Austin, Austin, TX.
*Contact email: bhadra@ece.utexas.edu

Abstract

The single-source min-cost multicast problem is considered, which can be framed as a convex optimization problem with the use of network codes and convex increasing edge costs. A decentralized approach to this problemn is presented by Lun, Ratnakar, et.al. for the case where all users cooperate to reach the global minimum. This paper analyzes the cost for the scenario where each of the multicast receivers greedily routes its flows and shows that a Nash equilibrium exists for such a scenario. An allocation rule by which the edge-cost at each edge is allocated to flows through that edge is presented. Under this rule, it is shown that for any (monomial) power-law cost function on each edge, there is a pricing rule such that the flow cost at user equilibrium is the same as the min-cost. This leads to the construction of an autonomous flow-steering algorithm for each receiver, which is also globally optimal. The algorithm is extended for completely distributed flow adaptation at nodes in the network, which also achieves globally minimal cost in steady state. Finally, the framework is generalized to the case of multiple multicast sessions and the results are shown to hold for user equilibrium in this case as well.