| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Fair Bandwidth Sharing in Distributed Systems: A Game-Theoretic Approach
November 2005 (vol. 54 no. 11)
pp. 1384-1393
Fair sharing of bandwidth remains an unresolved issue for distributed systems. In this paper, the users of a distributed LAN are modeled as selfish users with independence to choose their individual strategies. With these selfish users, the contention-based distributed medium access scenario is modeled as a complete-information, noncooperative game, designated the "Access Game.” A novel MAC strategy based on p-persistent CSMA is presented to achieve fairness in the "Access Game.” It is proven that there are an infinite number of Nash Equilibria for the "Access Game,” but they do not result in fairness. Therefore, it may be beneficial for the selfish users to adhere to a set of constraints that result in fairness in a noncooperative fashion. This leads to the formulation of a constrained "Access Game” with fairness represented as a set of algebraic constraints. It is proven that the solution of the constrained game, the Constrained Nash Equilibrium, is unique. Further, it is shown that, in addition to achieving fairness, this solution also optimizes the throughput. Finally, these results are extended to a more realistic incomplete-information scenario by approximating the incomplete-information scenario as a complete-information scenario through information gathering and dissemination.
[1] J. Kruys, “HIPERLAN, Applications and Requirements,” Proc. IEEE Int'l Symp. Personal Indoor and Mobile Radio Comm. (PIMRC '92), pp. 133-138, 1992.
[2] ETSI TS-RES 300 652, “Radio Equipment and Systems (RES); High Performance Radio Local Area Networks (HIPERLAN); Type 1; Functional Specifications,” Oct. 1996.
[3] N. Abramson, “The ALOHA System— Another Alternative for Computer Communications,” Am. Federation of Information Processing Socs. Conf. Proc., pp. 281-285, 1970.
[4] A.L. Garcia and I. Widjaja, Communication Networks. McGraw-Hill, 2000.
[5] G. Nutt and D. Bayer, “Performance of CSMA/CD Networks under Combined Voice and Data Loads,” IEEE Trans. Comm., vol. 30, no. 1, pp. 6-11, 1982.
[6] G. Exley and L. Merakos, “Throughput-Delay Performance of Interconnected CSMA Local Area Networks,” IEEE J. Selected Areas in Comm., vol. 5, no. 9, pp. 1380-1390, 1987.
[7] Y.-C. Liu and G. Wise, “Performance of a CSMA/CD Protocol for Local Area Networks,” IEEE J. Selected Areas in Comm., vol. 5, no. 6, pp. 948-955, 1987.
[8] P. O'Reilly and J. Hammond Jr., “An Efficient Simulation Technique for Performance Studies of CSMA/CD Local Network,” IEEE J. Selected Areas in Comm., vol. 2, no. 1, pp. 238-249, 1984.
[9] T. Vo-Dai, “Throughput-Delay Analysis of the Nonslotted and Nonpersistent CSMA-CD Protocol,” Local Computer Networks, P.C. Ravasio, G. Hopkins, and N. Naffah, eds., pp. 459-476, Amsterdam: North-Holland, 1982.
[10] M. Visser and M. El Zarki, “Voice and Data Transmission over an 802.11 Wireless Network,” Proc. IEEE Int'l Symp. Personal Indoor and Mobile Radio Comm. (PIMRC), pp. 648-652, Sept. 1995.
[11] P802.11, IEEE Draft Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification, D6.1, May 1997.
[12] IEEE 802.11e draft/D4.0, “Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Medium Access Control (MAC) Enhancements for Quality of Service (QoS),” Nov. 2002.
[13] A.B. MacKenzie and S.B. Wicker, “Stability of Multipacket Slotted Aloha with Selfish Users and Perfect Information,” Proc. INFOCOM 2003, vol. 3, pp. 1583-1590, 2003.
[14] D. Fudenberg and J. Tirole, Game Theory. MIT Press, 1991.
[15] Y.A. Korilis, A.A. Lazar, and A. Orda, “The Designer's Perspective to Noncooperative Networks,” Proc. INFOCOM '95, 1995.
[16] A. Orda, R. Rom, and N. Shimkin, “Competitive Routing in Multiuser Communication Networks,” ACM/IEEE Trans. Networking, vol. 1, no. 5, pp. 510-521, Oct. 1993.
[17] E. Koutsoupias and C. Papadimitriou, “Worst-Case Equilibria,” Proc. 16th Ann. Symp. Theoretical Aspects of Computer Science, pp. 404-413, 1999.
[18] T. Roughgarden and E. Tardos, “How Bad Is Selfish Routing?” J. ACM, vol. 49, no. 2, pp. 236-259, 2002.
[19] S. Shenker, “Making Greed Work in Networks: A Game-Theoretic Analysis of Switch Service Disciplines,” Proc. SIGCOMM '94, 1994.
[20] A. Akella, S. Seshan, R. Karp, S. Shenker, and C. Papadimitriou, “Selfish Behavior and Stability of the Internet: A Game-Theoretic Analysis of TCP,” Proc. SIGCOMM '02, Aug. 2002.
[21] C. Papadimitriou, “Algorithms, Games, and the Internet,” Proc. ACM Symp. Theory of Computing (STOC), 2001.
[22] L. Kleinrock and F. Tobagi, “Packet Switching in Radio Channels: Part I— Carrier Sense Multiple-Access Modes and Their Throughput-Delay Characteristics,” IEEE Trans. Comm., vol. 23, no. 12, pp. 1400-1416, 1975.
[23] D. Bertsekas, Nonlinear Programming. Athena Scientific, Sept. 1999.
[24] D. Qiao and K.G. Shin, “Achieving Efficient Channel Utilization and Weighted Fairness for Data Communications in IEEE 802.11 WLAN under the DCF,” Proc. 10th Int'l Workshop Quality of Service (IWQoS 2002), May 2002.
[25] G. Fayolle, E. Gelenbe, and J. Labetoulle, “Stability and Optimal Control of the Packet Switching Broadcast Channel,” J. ACM, vol. 24, pp. 375-386, July 1977.
[26] J. Nash, “Non-Cooperative Games,” Annals of Math., vol. 54, pp. 286-295, 1951.
[27] J. Harsanyi, “Games with Incomplete Information Played by Bayesian Players,” Management Science, vol. 14, pp. 159-182, 320-334, 486-502, 1967-1968.
[28] J. Rosen, “Existence and Uniqueness of Equilibrium Points for Concave n-Person Games,” Econometrica, vol. 33, pp. 520-534, July 1965.
[29] A. Demers, S. Keshav, and S. Shenker, “Analysis and Simulation of a Fair Queueing Algorithm,” ACM SIGCOMM Computer Comm. Rev., vol. 10 no. 4, pp. 1-12, Sept. 1989.
[30] S. Rakshit and R. Guha, “Optimal Mac Protocols,” Proc. Int'l Computing Conf., 2004.
[31] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, “MACAW: A Media Access Protocol for Wireless LANs,” Proc. ACM SIGCOMM, pp. 212-225, Aug. 1994.
[32] M. Gerla, K. Tang, and R. Bagrodia, “TCP Performance in Wireless Multi-Hop Networks,” Proc. IEEE Workshop Mobile Computing Systems and Applications (WMCSA), pp. 41-50, Feb. 1999.
[33] G.L. Choudhury and S.S. Rappaport, “Priority Access Schemes Using CSMA-CD,” IEEE Trans. Comm., vol. 33, pp. 620-626, July 1985.
[34] S.M. Sharrock and D.H. Du, “Efficient CSMA/CD-Based Protocols for Multiple Priority Classes,” IEEE Trans. Computers, vol. 38, pp. 943-954, July 1989.
[35] N.H. Vaidya, P. Bahl, and S. Gupta, “Distributed Fair Scheduling in a Wireless LAN,” Proc. MOBICOM, 2000.
[36] S. Rakshit and R. Guha, “A Non-Cooperative Game-Theoretic Model for the Medium Access and Fair Bandwidth Sharing in WLAN,” Wireless Comm. and Mobile Computing, in revision.
[37] M. Cagalj, S. Ganeriwal, I. Aad, and J.P. Hubaux, “On Cheating in CSMA/CA Ad Hoc Networks,” Proc. Infocom, 2005.
[38] L. Kleinrock, Queueing Systems Vol. 2: Computer Applications. New York: John Wiley & Sons, 1976.
[39] A. Parekh and R. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single Node Case,” IEEE/ACM Trans. Networking, vol. 1, no. 3, pp. 344-357, June 1993.
[40] J.C.R. Bennet and H. Zhang, “WF2Q: Worst-Case Fair Weighted Fair Queueing,” Proc. IEEE INFOCOM '96, Mar. 1996.
[41] F.A. Tobagi, “Carrier Sense Multiple Access with Message-Based Priority Functions,” IEEE Trans. Comm., vol. 30, no. 1, pp. 185-200, Jan. 1982.
[42] E. Altman and R. El Azouzi, “Constrained Traffic Equilibrium in Routing Networks,” IEEE Trans. Automatic Control, vol. 48, no. 9, pp. 1656-1660, Sept. 2003.
Index Terms:
Index Terms- Distributed systems, local area networks, fair bandwidth share, selfish users, game theory.
Citation:
Sudipta Rakshit, Ratan K. Guha, "Fair Bandwidth Sharing in Distributed Systems: A Game-Theoretic Approach," IEEE Transactions on Computers, vol. 54, no. 11, pp. 1384-1393, Nov. 2005, doi:10.1109/TC.2005.183
