Distributed utility maximization for network coding based multicasting: A critical cut approach

Yunnan Wu, Mung Chiang, Sun-Yuan Kung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

A central issue in practically deploying network coding in a shared network is adaptive and efficient allocation of network resources. This issue can be formulated as an optimization problem of maximizing net-utility - difference between a utility derived from attainable multicast throughput and total cost of resource provisioning. We develop a primal-subgradient type distributed algorithm to solve this utility maximization problem. effectiveness of algorithm hinges upon two key properties we discovered: (1) set of subgradients of multicast capacity is convex hull of indicator vectors for critical cuts, and (2) complexity of finding such critical cuts can be reduced by exploiting algebraic properties of linear network coding. extension to multiple multicast sessions is also carried out. effectiveness of proposed algorithm is confirmed by simulations on an Internet Service Providers topology.

Original languageEnglish (US)
Title of host publication2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2006
DOIs
StatePublished - Dec 1 2006
Event2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2006 - Boston, MA, United States
Duration: Feb 26 2006Mar 2 2006

Publication series

Name2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2006

Other

Other2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2006
CountryUnited States
CityBoston, MA
Period2/26/063/2/06

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Modeling and Simulation

Fingerprint Dive into the research topics of 'Distributed utility maximization for network coding based multicasting: A critical cut approach'. Together they form a unique fingerprint.

  • Cite this

    Wu, Y., Chiang, M., & Kung, S-Y. (2006). Distributed utility maximization for network coding based multicasting: A critical cut approach. In 2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2006 [1666491] (2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2006). https://doi.org/10.1109/WIOPT.2006.1666491