Auction Models Supporting End-to-End Connection Trading

• Autorzy: Kołtyś K. , Pieńkosz K. , Toczyłowski E.
• Języki publikacji: EN

Abstrakty

EN

The paper concerns bandwidth allocation problem on the telecommunication market where there are many sellers and buyers. Sellers offer the bandwidth of telecommunication links. Buyers are interested in the purchase of the bandwidth of several links that makes up an end-to-end connection between two nodes of telecommunication network. We analyze three auction models supporting such a bandwidth exchange: NSP (network second price), BCBT (model for balancing communication bandwidth trading) and BCBT-CG which is a modification of BCBT that applies column generation technique. All of these models concern divisible network resources, treat bandwidth of telecommunication links as an elementary commodity offered for sale, and allow for purchasing bandwidth along multiple paths joining two telecommunication nodes. All of them also aim at maximizing the social welfare. Considered auction models have been compared in the respect of economic and computational efficiency. Experimental studies have been performed on several test instances based on the SNDlib library data sets.

Słowa kluczowe

EN

bandwidth allocation; divisible commodities; end-to-end connections; multi-commodity trade; multipath routing

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2012
• Tom: nr 2
• Strony: 55--62
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Kołtyś K.

autor

Pieńkosz K.

autor

Toczyłowski E.

• Institute of Control and Computation Engineering, Warsaw University of Technology, Nowowiejska st 15/19, 00-665 Warsaw, Poland,

Bibliografia

• [1] D. Upton, “Modelling the market for bandwidth”, Ph.D. thesis, University of Cambridge, 2002.
• [2] G. Cheliotis, “Structure and dynamics of bandwidth markets”, Ph.D. thesis, N.T.U. Athens, 2001.
• [3] A. Iselt, A. Kirstadter, and R. Chahine, “Bandwidth trading – a business case for ASON?”, in Proc. 11th Int. Telecomm. Netw. Strategy Planning Symp. NETWORKS 2004, Viena, Austria, 2004, pp. 63–68.
• [4] R. Rabbat and T. Hamada, “Revisiting bandwidth-on-demand enablers and challengers of a bandwidth market”, in Proc. 10th IEEE/IFIP Netw. Oper. Manag. Symp., Vancouver, Canada, 2006, pp. 1–12.
• [5] F. Kelly, “Charging and rate control for elastic traffic”, Eur. Trans. Telecommun., no. 8, pp. 33–37, 1997.
• [6] B. Hajek and S. Yang, “Strategic buyers in a sum bid game for flat networks” manuscript, 2004.
• [7] R. Johari and J. N. Tsitsiklis, “Efficiency loss in a network resource allocation game”, Mathem. Opera. Research, no. 29, pp. 407–435, 2004.
• [8] A. Lazar and N. Semret, “Design, analysis and simulation of the progressive second price auction for network bandwidth sharing”, in Proc. 8th Int. Symp. Dynamic Games Appl., Vaals-Maastricht, The Netherlands, 1998.
• [9] N. Semret, “Market mechanisms for network resource sharing”, Ph.D. thesis, Columbia University, 1999.
• [10] M. Dramitinos, G. D. Stamoulis, and C. Courcoubetis, “An auction mechanism for allocating the bandwidth of networks to their users”, Comput. Netw., vol. 51, no. 18, pp. 4979–4996, 2007.
• [11] I. Koutsopoulos and G. Iosifidis, “Auction mechanisms for net- work resource allocation”, in Proc. 8th Int. Symp. Model. Optimiz. Mobile, Ad Hoc and Wirel. Netw. WiOpt, Avignon, France, 2010, pp. 554–563.
• [12] R. Jain and J. Walrand, “An efficient mechanism for network bandwidth auction”, in Proc. IEEE/IFIP Network Oper. Manag. Symp.Workshops 2008, Salvador, Brazil, 2008, pp. 227–234.
• [13] W. Stańczuk, J. Lubacz, and E. Toczyłowski, “Trading links and paths on a communication bandwidth markets”, J. Universal Comput. Sci., vol. 14, no. 5, pp. 642–652, 2008.
• [14] R. Jain and P. Varaiya, “Combinatorial exchange mechanisms for efficient bandwidth allocation”, Commun. Inf. Syst., vol. 3, no. 4, pp. 305–324, 2004.
• [15] R. Jain and P. Varaiya, “An efficient incentive-compatible combinatorial market mechanism”, in Proc. 42nd Allerton Conf. Commun. Control. Comput., Monticello, Il, USA, 2004.
• [16] R. Jain and P. Varaiya, “The combinatorial seller’s bid double-auction: an asymptotically efficient market mechanism”, J. Econom. Theory, 2006.
• [17] K. Kołtyś, P. Pałka, E. Toczyłowski, and I. Żółtowska, “Multi- commodity auction model for indivisible network resource allocation”, J. Telecommun. Inform. Technol., no. 4, pp. 25–31, 2008.
• [18] K. Kołtyś, P. Pałka, E. Toczyłowski, and I. Żółtowska, “Bandwidth trading: a comparison of the combinatorial and multicom-modity approach”, J. Telecom. Inform. Technol., no. 2, pp. 67–72, 2010.
• [19] “Survivable network design library” [Online]. Available: http://sndlib.zib.de/