Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Annals of Telecommunications
Erschienen in: Annals of Telecommunications 5-6/2012

01.06.2012

Combinatorial double-sided auctions for network bandwidth allocation: a budget-balanced and decentralized approach

verfasst von: Hoang-Hai Tran, Bruno Tuffin

Erschienen in: Annals of Telecommunications | Ausgabe 5-6/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Telecommunication networks are now an interconnection of competitive operators that need to cooperate to ensure end-to-end delivery of traffic. Inter-domain agreements have to be performed, and pricing is seen as a relevant way to reward intermediate domains for forwarding the traffic of others. In previous works, Vickrey–Clark–Groves (VCG) double-sided auctions have been applied because they provide proper incentives, lead to an efficient use of the network, and verify other relevant characteristics. However, it has been highlighted that the resource allocation schemes applying VCG auction are neither budget-balanced nor solvable in a decentralized way. In this paper, we apply combinatorial double-sided auction to allocate the bandwidth resources over nodes. While previous works were using a centralized algorithm, we use here a new pricing rule, leading to a new budget-balanced pricing scheme for which allocations and charges can be computed in a decentralized way. We also analyze the impact of this scheme on the game over declared costs of nodes.
Vorheriger Artikel Multi-radio multi-channel routing metrics in IEEE 802.11s based wireless mesh networks
Nächster Artikel Estimation of cross-polarization due to rain over some stations in Nigeria

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
The resource allocation mechanism is said to be socially optimal or efficient if it maximizes the sum of utility functions of all users involved in the game. In networking literature, social optimality and efficiency are often used interchangeably [3].
 
2
Convergence to a Nash equilibrium is not always ensured though [29].
 
3
Note that agents, nodes, or autonomous systems are used interchangeable in our paper.
 
4
\(\hat{y}_r(j)\) may be different from \(\hat{y}_r\) of the source node, depending on its own demand traffic to destination on route r and its own maximum supplies.
 
5
It can be counted in algorithm by the number of neighbors in which v k received the same request message to a destination.
 
6
Number of links in the shortest path between the farthest pair of nodes.
 
7
A bid fee ϵ is chosen as maximal gain of nodes from previous oscillation, where u osc is the net pay-off during oscillation.
 
8
Aggregated utilities of the sellers.
 
Literatur
1.
Caesar M, Rexford J (2005) BGP routing policies in ISP networks. IEEE Netw 19(6):5–11CrossRef
2.
Nick F, Jay B, Jennifer R (2003) Guidelines for interdomain traffic engineering. ACM SIGCOMM Comput Commun Rev 33:2003
3.
Asu Ozdaglar RS (2007) Incentive and pricing in communications networks. In: Nisam N, Roughgarden T, Tardos E, Vazirani VV (eds) Algorithmic game theory. Cambridge University Press, Cambridge
4.
Altman E, Boulogne T, El-Azouzi R, Jiménez T, Wynter L (2006) A survey on networking games in telecommunications. Comput Oper Res 33(2):286–311MathSciNetMATHCrossRef
5.
Courcoubetis C, Weber R (2003) Pricing communication networks: economics, technology and modelling. Wiley, New York
6.
Nisam N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic game theory. Cambridge University Press, CambridgeCrossRef
7.
Shoham Y, Leyton-Brown K (2008) Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge University Press, New York
8.
Feigenbaum J, Papadimitriou C, Sami R, Shenker S (2005) A BGP-based mechanism for lowest-cost routing. Distrib Comput 18(1):61–72CrossRef
9.
Feigenbaum J, Ramachandran V, Schapira M (2006) Incentive-compatible interdomain routing. In: EC ’06: proceedings of the 7th ACM conference on electronic commerce. ACM, New York, pp 130–139CrossRef
10.
Liu J, Issarny V (2004) On service allocation in selfish mobile ad hoc networks. In: Proc of EDBT PIM
11.
Eiji T, Yoshiaki T (2001) Bandwidth allocation by using generalized Vickrey auction. In: Asia Pacific symposium on information and telecommunication technologies
12.
Eidenbenz S, Resta G, Santi P (2005) COMMIT: a sender-centric truthful and energy-efficient routing protocol for ad hoc networks with selfish nodes. In: Parallel and distributed processing symposium, 2005. Proceedings 19th IEEE international, p 10
13.
Anderegg L, Eidenbenz S (2003) Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents. In: MobiCom ’03: proceedings of the 9th annual international conference on mobile computing and networking. ACM, New York, pp 245–259CrossRef
14.
Wang W, Li XY, Wang Y (2004) Truthful multicast routing in selfish wireless networks. In: Proceedings of MobiCom. ACM, New York, pp 245–259CrossRef
15.
Hershberger J, Suri S (2001) Vickrey pricing in network routing: fast payment computation. In: Proc of the 42nd IEEE symposium on foundations of computer science, pp 252–259
16.
Jain R, Walrand J (2010) An efficient Nash-implementation mechanism for network resource allocation. Automatica 46:1276–1283MATHCrossRef
17.
Maille P, Tuffin B (2007) Why VCG auctions can hardly be applied to the pricing of inter-domain and ad hoc networks. In: 3rd EuroNGI conference on next generation internet networks, pp 36–39
18.
19.
Barth D, Blin L, Echabbi L, Vial S (2005) Distributed cost management in a selfish multi-operators BGP network. In: Proceeding of next generation internet networks, 2005, pp 24–30
20.
21.
Sichao Yang Hajek B (2007) VCG–Kelly mechanisms for allocation of divisible goods: adapting VCG mechanisms to one-dimensional signals. IEEE J Sel Areas Commun 25(6):1237–1243CrossRef
22.
Moulin H, Shenker S (1996) Strategyproof sharing of submodular access costs: budget balance versus efficiency. Working papers 96-31, Duke University, Department of Economics
23.
Su X, Chan S, Peng G (2009) Auction in multi-path multi-hop routing. Commun Lett 13(2):154–156CrossRef
24.
Wu F, Zhong S, Liu J (2007) Cost-effective traffic assignment for multipath routing in selfish networks. In: Global telecommunications conference, 2007. GLOBECOM ’07, IEEE, pp 453–457
25.
Jain R, Varaiya P (2005) Efficient market mechanisms for network resource allocation. In: 4th IEEE conference and European control conference on decision and control, CDC-ECC ’05, pp 1056–1061
26.
Gibbens RJ, Kelly FP (1998) Resource pricing and the evolution of congestion control. Automatica 35:1969–1985MathSciNetCrossRef
27.
Crowcroft J, Gibbens R, Kelly F, Östring S (2004) Modelling incentives for collaboration in mobile ad hoc networks. Perform Eval 57(4):427–439CrossRef
28.
Crowcroft J, Gibbens R, Kelly F, Östring S (2004) Providing incentives in providerless networks. Ad Hoc Netw 2(3):283–289CrossRef
29.
Barth D, Echabbi L, Hamlaoui C (2008) Optimal transit price negotiation: the distributed learning perspective. J Univers Comput Sci 14(5):745–765
30.
Sastry P, Phansalkar V, Thathachar M (1994) Decentralized learning of Nash equilibria in multi-person stochastic games with incomplete information. IEEE Trans Syst Man Cybern 24(5):769–777MathSciNetCrossRef
31.
Xuezhi T, Yutao L, Guisen X (2009) Dynamic spectrum allocation in cognitive radio: auction and equilibrium. In: International forum on information technology and applications, 2009. IFITA ’09, vol 1, pp 554 –558
32.
Wang S, Xu P, Xu X, Tang S, Li X, Liu X (2010) Toda: truthful online double auction for spectrum allocation in wireless networks. In: 2010 IEEE symposium on new frontiers in dynamic spectrum, pp 1–10
33.
Zhou X, Gandhi S, Suri S, Zheng H (2008) eBay in the sky: strategy-proof wireless spectrum auctions. In: Proceedings of the 14th ACM international conference on mobile computing and networking, MobiCom ’08. ACM, New York, pp 2–13CrossRef
34.
Zhou X, Zheng H (2009) Trust: a general framework for truthful double spectrum auctions. In: INFOCOM 2009, IEEE, pp 999–1007
35.
Toka L, Vidács A (2009) General distributed economic framework for dynamic spectrum allocation. Comput Commun 32(18):1955–1964 (Cognitive Radio and Dynamic Spectrum Sharing Systems)
36.
Toka L, Korosi A, Vidacs A (2010) On distributed dynamic spectrum allocation for sequential arrivals. In: 2010 IEEE symposium on new frontiers in dynamic spectrum, pp 1–12
37.
Chen L, Iellamo S, Coupechoux M, Godlewski P (2010) An auction framework for spectrum allocation with interference constraint in cognitive radio networks. In: INFOCOM, 2010 Proceedings IEEE, pp 1–9
38.
Rodriguez V, Moessner K, Tafazolli R (2005) Auction driven dynamic spectrum allocation: optimal bidding, pricing and service priorities for multi-rate, multi-class CDMA. In: Personal, indoor and mobile radio communications, 2005. IEEE 16th International Symposium on PIMRC 2005, vol 3, pp 1850–1854
39.
Chun SH, La R (2009) Auction-based dynamic spectrum trading market—spectrum allocation and profit sharing. In: 47th annual Allerton conference on communication, control, and computing, 2009. Allerton 2009
40.
Sengupta S, Chatterjee M, Ganguly S (2007) An economic framework for spectrum allocation and service pricing with competitive wireless service providers. In: New frontiers in dynamic spectrum access networks, DySPAN 2007, pp 89–98
41.
Wu Y, Wang B, Liu K, Clancy T (2008) A multi-winner cognitive spectrum auction framework with collusion-resistant mechanisms. In: New frontiers in dynamic spectrum access networks, DySPAN 2008, pp 1–9
42.
Menezes FM, Monteiro PK (2000) Internet routing architectures. Sam Halabi
43.
44.
45.
Scheinerman ER (2006) Matgraph: a MATLAB toolbox for graph theory. Tech rep, Johns Hopkins University
46.
Barnard W (1988) Routing of multipoint connections. IEEE J Sel Areas Commun 6(9):1617–1622CrossRef
Metadaten
Titel
Combinatorial double-sided auctions for network bandwidth allocation: a budget-balanced and decentralized approach
verfasst von
Hoang-Hai Tran
Bruno Tuffin
Publikationsdatum
01.06.2012
Verlag
Springer-Verlag
Erschienen in
Annals of Telecommunications / Ausgabe 5-6/2012
Print ISSN: 0003-4347
Elektronische ISSN: 1958-9395
DOI
https://doi.org/10.1007/s12243-011-0250-2

Weitere Artikel der Ausgabe 5-6/2012

Annals of Telecommunications 5-6/2012 Zur Ausgabe

OriginalPaper

Estimation of cross-polarization due to rain over some stations in Nigeria

OriginalPaper

A routing protocol using a reliable and high-throughput path metric for multi-hop multi-rate ad hoc networks

OriginalPaper

Multi-radio multi-channel routing metrics in IEEE 802.11s based wireless mesh networks

OriginalPaper

When should I use network emulation?

OriginalPaper

Beam reconfiguration of linear array of parallel dipole antennas through switching with real excitation voltage distribution

OriginalPaper

Analysis of three-dimensional turbo codes