research-article

On economic heavy hitters: shapley value analysis of 95th-percentile pricing

Authors:

Rade Stanojevic,

Nikolaos Laoutaris,

Pablo RodriguezAuthors Info & Claims

IMC '10: Proceedings of the 10th ACM SIGCOMM conference on Internet measurement

Pages 75 - 80

https://doi.org/10.1145/1879141.1879151

Published: 01 November 2010 Publication History

Abstract

Cost control for the Internet access providers (AP) influences not only the nominal speeds offered to the customers, but also other, more controversial, policies related to traffic shaping and discrimination. Given that the cost for the AP is determined by the peak-hour traffic (e.g. through the 95th-percentile), the individual user contribution towards the aggregate cost is not a linear function of its byte usage. In this paper we propose a metric for evaluating the contribution each individual user has on the peak demand, that is based on Shapley value, a well known game-theoretic concept. Given the computational complexity of calculating the Shapley value, we use a Monte Carlo method for approximating it with reasonable accuracy. We employ our methodology to study a dataset that logs per-subscriber temporal usage patterns over one month period for 10K broadband subscribers of a European AP and report observed results.

References

[1]

G. Biczok, S. Kardos, T. A. Trinh. "Pricing internet access for disloyal users: a game-theoretic analysis". In Proceedings of NetEcon 2008.

Digital Library

[2]

B. Briscoe. "A Fairer, Faster Internet Protocol". IEEE Spectrum, Dec 2008.

Digital Library

[3]

B. Briscoe. "Flow Rate Fairness: Dismantling a Religion". ACM Computer Communication Review vol. 37(2), 2007.

Digital Library

[4]

K. Cho, K. Fukuda, H. Esaki, A. Kato. "The impact and implications of the growth in residential user-to-user traffic". In Proceedings of SIGCOMM 2006.

Digital Library

[5]

K. Cho, K. Fukuda, H. Esaki, A. Kato. "Observing slow crustal movement in residential user traffic". In Proceedings of CoNEXT 2008.

Digital Library

[6]

C. Courcoubetis, R. Weber. "Pricing communication networks". John Wiley and Sons, 2003.

Digital Library

[7]

A. Dhamdhere, C. Dovrolis. "Can ISPs be profitable without violating "netwotk neutrality"?". In Proceedings of NetEcon 2008.

Digital Library

[8]

X. Dimitropoulos, P. Hurley, A. Kind. M. Stoecklin "On the 95-percentile billing method". In Proceedings of PAM 2009.

Digital Library

[9]

M. Dischinger et al. "Glasnost: Enabling End Users to Detect Traffic Differentiation". In Proceedings of NSDI 2010.

Digital Library

[10]

D. Kim, S. Sra, I. S. Dhillon. "Fast Projection-Based Methods for the Least Squares Nonnegative Matrix Approximation Problem". Statistical Analysis and Data Mining, vol. 1(1), 2008.

Digital Library

[11]

N. Laoutaris, P. Rodriguez. "Good Things Come to Those Who (Can) Wait $-$ or how to handle Delay Tolerant traffic and make peace on the Internet". In Proceedings of ACM HotNets 2008.

[12]

N. Laoutaris, G. Smaragdakis, P. Rodriguez, R. Sundaram. "Delay Tolerant Bulk Data Transfers on the Internet". In Proceedings of ACM SIGMETRICS 2009.

Digital Library

[13]

R. T. B. Ma, D.M. Chiu, J. C. S. Lui, V. Misra, D. Rubenstein. "Internet economics: the use of Shapley value for ISP settlement". In Proceeding of CoNEXT 2007.

Digital Library

[14]

R. T. B. Ma, D.M. Chiu, J. C. S. Lui, V. Misra, D. Rubenstein. "On cooperative settlement between content, transit and eyeball internet service providers.". In Proceeding of CoNEXT 2008.

Digital Library

[15]

G. Maier, A. Feldmann, V. Paxson, M. Allman. "On dominant characteristics of residential broadband internet traffic". In Proceedings of IMC 2009.

Digital Library

[16]

M. Marcon, M. Dischinger, K. P. Gummadi, A. Vahdat. "The Local and Global Effects of Traffic Shaping in the Internet". In Proceedings of SIGCOMM 2008.

[17]

V. Misra, S. Ioannidis, A. Chaintreau, L. Massoulié. "Incentivizing Peer-Assisted Services: A Fluid Shapley Value Approach". In Proceedings of SIGMETRICS 2010.

Digital Library

[18]

A. Odlyzko. "Internet pricing and the history of communications". Computer Networks, vol. 36, 2001.

[19]

S.Shakkottai, R. Srikant, A. E. Ozdaglar, D. Acemoglu. "The Price of Simplicity". IEEE Journal on Selected Areas in Communications, vol 26(7), 2008.

Digital Library

[20]

L. S. Shapley. "A Value for n-person Games". Annals of Mathematical Studies vol. 28, 1953.

[21]

R. Stanojevic, N. Laoutaris, P. Rodriguez. "On Economic Heavy Hitters: Shapley value analysis of the 95th-percentile pricing". Technical report, available online: http://www.hamilton.ie/person/rade/TREHH.pdf.

[22]

R. Tongia. "Why is connectivity in developing regions expensive: policy challenges more than technical limitations?". In Proceedings of WWW 2006.

Digital Library

[23]

E. Winter. "The Shapley Value". The Handbook of Game Theory, North-Holland, 2002.

Cited By

Wang YZhao DHuang CYang FGao TZhou AZhang HMa HDu YChen A(2024)TrafAda: Cost-Aware Traffic Adaptation for Maximizing Bitrates in Live StreamingIEEE/ACM Transactions on Networking10.1109/TNET.2023.328581232:1(96-109)Online publication date: Feb-2024
https://doi.org/10.1109/TNET.2023.3285812
Wang YZhao DGuo ZGao TMa HDu Y(2024)CEL: Cost-Aware Edge-Assisted Livecast via Optimization With Shapley ValueIEEE Internet of Things Journal10.1109/JIOT.2023.332044211:5(7805-7816)Online publication date: 1-Mar-2024
https://doi.org/10.1109/JIOT.2023.3320442
Ma XLi QPeng JTyson GYe ZTang SMa QMeng SMuntean G(2024)Smart Data-Driven Proactive Push to Edge Network for User-Generated VideosIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621410(511-520)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621410
Show More Cited By

Index Terms

On economic heavy hitters: shapley value analysis of 95th-percentile pricing
1. General and reference
  1. Cross-computing tools and techniques
    1. Measurement
    2. Metrics

Recommendations

On cooperative settlement between content, transit, and eyeball internet service providers

Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. This concern is at the heart ...
CIPT: using tuangou to reduce IP transit costs
CoNEXT '11: Proceedings of the Seventh COnference on emerging Networking EXperiments and Technologies

A majority of ISPs (Internet Service Providers) support connectivity to the entire Internet by transiting their traffic via other providers. Although the transit prices per Mbps decline steadily, the overall transit costs of these ISPs remain high or ...
Auction, but don't block
NetEcon '08: Proceedings of the 3rd international workshop on Economics of networked systems

This paper argues that ISP's recent actions to block certain applications (e.g. BitTorrent) and attempts to differentiate traffic could be a signal of bandwidth scarcity. Bandwidth-intensive applications such as VoD could have driven the traffic demand ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IMC '10: Proceedings of the 10th ACM SIGCOMM conference on Internet measurement

November 2010

496 pages

ISBN:9781450304832

DOI:10.1145/1879141

Program Chair:
Mark Allman
International Computer Science Institute

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

USENIX Assoc: USENIX Assoc

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

IMC '10

Sponsor:

IMC '10: Internet Measurement Conference

November 1 - 30, 2010

Melbourne, Australia

Acceptance Rates

Overall Acceptance Rate 277 of 1,083 submissions, 26%

Upcoming Conference

IMC '24

Sponsor:
sigcomm
sigcomm

ACM Internet Measurement Conference

November 4 - 6, 2024

Madrid , AA , Spain

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
416
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)2

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang YZhao DHuang CYang FGao TZhou AZhang HMa HDu YChen A(2024)TrafAda: Cost-Aware Traffic Adaptation for Maximizing Bitrates in Live StreamingIEEE/ACM Transactions on Networking10.1109/TNET.2023.328581232:1(96-109)Online publication date: Feb-2024
https://doi.org/10.1109/TNET.2023.3285812
Wang YZhao DGuo ZGao TMa HDu Y(2024)CEL: Cost-Aware Edge-Assisted Livecast via Optimization With Shapley ValueIEEE Internet of Things Journal10.1109/JIOT.2023.332044211:5(7805-7816)Online publication date: 1-Mar-2024
https://doi.org/10.1109/JIOT.2023.3320442
Ma XLi QPeng JTyson GYe ZTang SMa QMeng SMuntean G(2024)Smart Data-Driven Proactive Push to Edge Network for User-Generated VideosIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621410(511-520)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621410
Zhang RYang CWang XHuang TWu CLiu JSun L(2023)Practical Cloud-Edge Scheduling for Large-Scale Crowdsourced Live StreamingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.326773134:7(2055-2071)Online publication date: Jul-2023
https://doi.org/10.1109/TPDS.2023.3267731
Zhang YZhang HCong PWang WXu K(2023)Grandet: Cost-aware Traffic Scheduling without Prior Knowledge in SD-WAN2023 IEEE/ACM 31st International Symposium on Quality of Service (IWQoS)10.1109/IWQoS57198.2023.10188706(1-10)Online publication date: 19-Jun-2023
https://doi.org/10.1109/IWQoS57198.2023.10188706
Zhan HTan HXu HZhang CNi HZhang PShan WLi X(2023)Online Midgress-Sensitive Traffic Allocation for Percentile Charging in Pracitcal CDNs2023 IEEE/ACM 31st International Symposium on Quality of Service (IWQoS)10.1109/IWQoS57198.2023.10188693(1-10)Online publication date: 19-Jun-2023
https://doi.org/10.1109/IWQoS57198.2023.10188693
Hu QPeng QShang JLi YHe J(2023)EBA: An Adaptive Large Neighborhood Search-Based Approach for Edge Bandwidth AllocationCollaborative Computing: Networking, Applications and Worksharing10.1007/978-3-031-24383-7_14(249-268)Online publication date: 25-Jan-2023
https://doi.org/10.1007/978-3-031-24383-7_14
Overko ROrdonez-Hurtado RZhuk SFerraro PCullen AShorten R(2022)Spatial Positioning Token (SPToken) for Smart MobilityIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.302953723:2(1529-1542)Online publication date: Feb-2022
https://doi.org/10.1109/TITS.2020.3029537
Chen HZhan HTan HXu HShan WChen SLi X(2022)Online Traffic Allocation Based on Percentile Charging for Practical CDNs2022 IEEE/ACM 30th International Symposium on Quality of Service (IWQoS)10.1109/IWQoS54832.2022.9812878(1-10)Online publication date: 10-Jun-2022
https://doi.org/10.1109/IWQoS54832.2022.9812878
Ramirez SBauso D(2022)Gradient Tracking for Coalitional Aggregation of Wind Power2022 IEEE 61st Conference on Decision and Control (CDC)10.1109/CDC51059.2022.9992440(6383-6388)Online publication date: 6-Dec-2022
https://doi.org/10.1109/CDC51059.2022.9992440
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents