Authors: Di Niu (University of Alberta, Canada) and Baochun Li (University of Toronto, Canada)
Title: “Congestion-Aware Internet Pricing for Media Streaming”
Publication: 2014 IEEE INFOCOM Workshop on Smart Data Pricing
Taking inspiration from proposed congestion-dependent road pricing policies where a vehicle is charged in proportion to the distance it travels along the road, the authors in this paper propose a new metric for congestion-sensitive pricing of streaming media content over a network. In particular, the ISP computes the product of the (instantaneous) streaming media rate (the application throughput) times the (instantaneous) packet transmission delay on each link. The overall cost to the content consumer is computed by summing this cost over all links between the content source and destination. A little thought shows that this metric is equivalent to computing the so-called bandwidth-delay product on each link. The bandwidth delay product of a flow of packets over a link is the product of the rate at which packets are transmitted onto the link times the end-to-end delay for a packet on that link, and equals the amount of data from the flow on the link at any point in time. The proposed pricing mechanism is congestion dependent, since the transmission delay on the link is increasing in the link congestion level.
The authors then consider some implications of such a pricing policy for media content providers. Content providers would wish to form minimum cost overlay networks to connect with their clients. By minimizing the cost of the sum bandwidth delay products, the clients are by definition minimizing the amount of “waiting data” on the network. Focusing on the particular case of streaming video multicast, each multicast session wishes to find the collection of relays such that the resulting distribution tree has minimum cost. As an example, applications like Google Hangouts, Facetime, and Skype need to form these kinds of overlay networks.
To approximate this hard problem, the authors study a “network coordinate system” (or, in their words, “delay space”), where the delay between two nodes determines the delay between them, and idealized relay locations must be eventually mapped back to the actual underlying network. Specifically, given the spatial locations of the terminal nodes to be connected, and a limit on the allowed number of relays nodes, the goal is to place the relays in space so as to form a multicast tree of minimum cost.
Unfortunately, the resulting optimization problem is non-convex, and as such the authors investigate an appealing approximation based on the expectation-maximization (EM) paradigm. In this context, the algorithm iteratively solves for the optimal flow given a fixed set of relay positions (a linear program), then solves for the optimal set of relay positions given a flow (a convex program).
The simulations section demonstrate that using this optimized approach to relay and flow selection will yield potentially significant savings in overall cost for multicast networks relative to the naïve approach of sending the content directly.
In summary, this paper proposes a natural congestion-dependent pricing principle for streaming content, and uses this metric to illustrate a principled approach to forming multicast session trees.
[Odlyzko 2013] Andrew Odlyzko, “Will smart pricing finally take off?”, Available at http://www.dtc.umn.edu/~odlyzko, dated October 20, 2013.
[SDP 2014] The IEEE INFOCOM Workshop on Smart Data Pricing (SDP), Available at http://infocom2014.ieee-infocom.org/Workshops_SDP.html
[Sen et al. 2013] Soumya Sen, Carlee Joe-Wong, Sangtae Ha, and Mung Chiang, “A Survey of Smart Data Pricing: Past Proposals, Current Plans, and Future Trends”, ACM Computing Surveys, Vol. 46, No. 2, Article 15, November, 2013.
[Sen et al. 2014] Soumya Sen, Carlee Joe-Wong, Sangtae Ha, and Mung Chiang, Smart Data Pricing, Wiley Series on Information and Communication Technology, September, 2014.
[DataMi 2014] Available at http://www.datami.com
[inmobly 2014] Available at http://www.inmobly.com
[SDP 2012] Available at http://scenic.princeton.edu/SDP2012/