Paradoxes in distributed decisions on optimal load balancing for networks of homogeneous computers

ABSTRACT

In completely symmetric systems that have homogeneous nodes (hosts, computers, or processors) with identical arrival processes, an optimal static load balancing scheme does not involve the forwarding of jobs among nodes. Using an appropriate analytic model of a distributed computer system, we examine the following three decision schemes for load balancing: completely distributed, intermediately distributed, and completely centralized. We show that there is no forwarding of jobs in the completely centralized and completely distributed schemes, but that in an intermediately distributed decision scheme, mutual forwarding of jobs among nodes is possible, leading to degradation in system performance for every decision maker. This result appears paradoxical, because by adding communication capacity to the system for the sharing of jobs between nodes, the overall system performance is degraded. We characterize conditions under which such paradoxical behavior occurs, and we give examples in which the degradation of performance may increase without bound. We show that the degradation reduces and finally disappears in the limit as the intermediately distributed decision scheme tends to a completely distributed one.

REFERENCES

• 1: Arora, N., and Sen, S. 1997. Resolving social dilemmas using genetic algorithms: Initial results. In Proceedings of the 7th International Conference on Genetic Algorithms. Michigan State University, 689--695.
• 2: Braess, D. 1968. Über ein Paradoxen aus der Verkehrsplanung. Unternehmensforschung 12, 258--268.
• 3: Calvert, B., Solomon, W., and Ziedins, I. 1997. Braess's paradox in a queueing network with state-dependent routing. J. Appl. Prob. 34, 134--154.
• 4: Joel E. Cohen , Clark Jeffries, Congestion resulting from increased capacity in single-server queueing networks, IEEE/ACM Transactions on Networking (TON), v.5 n.2, p.305-310, April 1997 [doi>10.1109/90.588114]
• 5: Cohen, J. E., and Kelly, F. P. 1990. A paradox of congestion in a queuing network. J. Appl. Prob. 27, 730--734.
• 6: Frank, M. 1981. The Braess paradox. Math. Prog. 20, 283--302.
• 7: Haurie, A., and Marcotte, P. 1985. On the relationship between Nash--Cournot and Wardrop equilibria. Networks 15, 295--308.
• 8: Kameda, H. 2002. How harmful the paradox can be in the Braess/Cohen--Kelly--Jeffries networks. In Proceedings of IEEE INFOCOM 2002 (New York, NY). IEEE Computer Society Press, Los Alamitos, Calif.
• 9: Kameda, H., Altman, E., Kozawa, T., and Hosokawa, Y. 2000. Braess-like paradoxes in distributed computer systems. IEEE Trans. Automatic Contr. 45, 1687--1691.
• 10: Kameda, H., Hosokawa, Y., and Pourtallier, O. 2001a. Effects of symmetry on Braess-like paradoxes in distributed computer systems---A numerical study --. In Proceedings of the 40th IEEE Conference on Decision and Control (Orlando, Fl.) IEEE Computer Society Press, Los Alamitos, Calif., 831--836.
• 11: Kameda, H., Kozawa, T., and Li, J. 1997a. Anomalous relations among various performance objectives in distributed computer systems. In Proceedings of the 1st World Congress on Systems Simulation. IEEE Computer Society Press, Los Alamitos, Calif., 459--465.
• 12: Hisao Kameda , Jie Li , Chonggun Kim , Yongbing Zhang, Optimal load balancing in distributed computer systems, Springer-Verlag, London, 1997
• 13: Kameda, H., Ohta, M., and Hosokawa, Y. 2001b. Effects of symmetry on paradoxical cost degradation in a Nash non-cooperative network system. In Proceedings of IFAC Symposium on Modeling and Control of Economic Systems (SME 2001) (Klagenfurt, Austria).
• 14: Chonggun Kim , Hisao Kameda, An Algorithm for Optimal Static Load Balancing in Distributed Computer Systems, IEEE Transactions on Computers, v.41 n.3, p.381-384, March 1992 [doi>10.1109/12.127455]
• 15: Kleinrock, L. 1976. Queueing Systems, Volume II: Computer Applications. Wiley, New York.
• 16: Korilis, Y. A., Lazar, A. A., and Orda, A. 1995. Architecting noncooperative networks. IEEE J. Sel. Areas Commun. 13, 1241--1251.
• 17: Korilis, Y. A., Lazar, A. A., and Orda, A. 1999. Avoiding the Braess paradox in noncooperative networks. J. Appl. Prob. 36, 211--222.
• 18: Koutsoupias, E., and Papadimitriou, C. 1999. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science. 404--413.
• 19: Jie Li , Hisao Kameda, Load Balancing Problems for Multiclass Jobs in Distributed/Parallel Computer Systems, IEEE Transactions on Computers, v.47 n.3, p.322-332, March 1998 [doi>10.1109/12.660168]
• 20: Murchland, J. D. 1970. Braess's paradox of traffic flow. Transpn. Res. 4, 391--394.
• 21: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 22: Rosen, J. B. 1965. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33, 153--163.
• 23: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 24: Samuelson, P. 1992. Tragedy of the open road: Avoiding paradox by use of regulated public utilities that charge corrected Knightian tolls. J. Int. Comparat. Econ. 1, 3--12.
• 25: Shapiro, J. F. 1979. Mathematical Programming, Structures and Algorithms. Wiley, New York.
• 26: Asser N. Tantawi , Don Towsley, Optimal static load balancing in distributed computer systems, Journal of the ACM (JACM), v.32 n.2, p.445-465, April 1985 [doi>10.1145/3149.3156]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.8 Performance
          Subjects: Modeling and prediction; Queueing theory

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management
          Subjects: Centralization/decentralization; Quality assurance

General Terms:
Algorithms, Management, Performance, Theory

Keywords:
Braess paradox, Nash equilibrium, Wardrop equilibrium, distributed decision, homogeneous distributed system, load balancing, noncooperative game, performance optimization