A CSA Method for Assigning Client to Servers in Online Social Networks

Document Type: Research Paper

Authors

Imam Khomeini International University, Qazvin, Iran

Abstract

This paper deals with the problem of user-server assignment in online social network systems. Online social network applications such as Facebook, Twitter, or Instagram are built on an infrastructure of servers that enables them to communicate with each other. A key factor that determines the facility of communication between the users and the servers is the Expected Transmission Time (ETT). A smart user-server assignment can avoid the low quality links and improve the communication between nodes and also save the valuable communication resources. Unfortunately, finding the optimal assignment turns out to be a NP-hard problem. This paper proposes the use of a heuristic algorithm named Centralized Simulated Annealing (CSA) to get a good near optimum solution for this problem. Simulation results of this investigation show that using a relatively small number of iterations, this approach achieves a very good performance improvement. On the other hand, the average number of iterations needed to achieve the near-optimal solution, will be slightly increased when the number of users in the network increase.

Keywords


[1] A. Lakshman, P. Malik, "Cassandra: A decentralized structured," ACM SIGOPS Oper. Syst. Rev., vol. 44, no. [Online]. Available: http://doi.acm.org/10.1145/, pp. 35–40, Apr. 2010.

[2] K. Lee, M. El-Sharkawi, "Fundamentals of simulated annealing in modern heuristic optimization techniques: Theory and applications to power sSystems," Wiley-IEEE Press, 2008, pp. 123 - 146.

[3] R. Michael Garey, S. David Johnson, "Computers and intractability: A guide to the theory of NP-completeness," New York, NY, USA: W. H. Freeman & Co, 1979. [4] B. W. Kernighan , S. Lin, "An efficient heuristic procedure for partitioning graphs," Bell Syst. Tech. J, vol. 49, no. 2, pp. 291– 307, 1970.

[5] C. M. Fiduccia, R. M. Mattheyses, "A linear-time heuristic for improving network partitions," in Proc. 19th Design Automation Conference, pp. 175-181, 1982.

[6] Z. Wu, R. Leahy, "An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation," IEEE Trans. Pattern Anal. Mach. Intell, vol. 15, no. 11, pp. 1101– 1113, Nov. 1993.

[7] J. Shi, J. Malik, "Normalized cuts and image segmentation," IEEE Trans. Pattern Anal. Mach. Intell, vol. 22, no. 8, pp. 888–905, Aug. 2000.

[8] I. S. Dhillon, Y. Guan, and B. Kulis, "Weighted graph cuts without eigenvectors a multilevel approach," IEEE Trans. Pattern Anal. Mach. Intell, vol. 29, no. 11, pp. 1944–1957, Nov. 2007.

[9] B. Schölkopf, A. Smola, and K.-R. Müller, "Nonlinear component analysis," Neural Comput, vol. 10, no. 5, pp. 1299-1319, 1998.

[10] C. H. Q. Ding, X. He, H. Zha, M. Gu, and H. D. Simon, "‘A minmax cut," in Proc. IEEEInt. Conf. Data Mining (ICDM), pp. 107– 114, Dec. 2001.

[11] H. S. Stone, "Multiprocessor scheduling with the aid of network flow algorithms," IEEE Trans. Softw. Eng, vol. SE-3, no. 1, pp. 85–93, Jan. 1977.

[12] G. Sabin, V. Sahasrabudhe, and P. Sadayappan, "On fairness in distributed job scheduling across multiple sites," in Proc. IEEE Int. Conf. Cluster comput, pp. 35–44, Sep. 2004.

[13] D. P. Vidyarthi, B. K. Sarker, A. K. Tripathi, and L. T. Yang, "Scheduling in distributed computing systems: Analysis, design and models," Berlon, Germany: Springer Publishing Company, Incorporated, 2008.

[14] Y. Jiang, Y. Zhou, and W. Wang, "Task allocation for undependable multiagent systems in social networks," IEEE Trans. Parallel Distrib. Syst., vol. 24, no. 8, pp. 1671–1681, Aug. 2013.

[15] Y. Jiang, J. Jiang, "Contextual resource negotiation-based task allocation and load balancing in complex software systems," IEEE Trans. Parallel Distrib. Syst., vol. 20, no. 5, pp. 641–653, May. 2009.

[16] D. S. J. D. Couto, "High-throughput routing for multi-hop wireless networks," Ph.D. dissertation, Dept. Elect. Eng. Comput. Sci., 2004.

[17] C. A. Chen, M. Won,R. Stoleru, and G. G. Xie, "Energy-Efficient Fault-Tolerant Data Storage and Processing in Mobile Cloud," IEEE Trans. on cloud computing, vol. 3, no. 1, pp. 28 - 41, January. 2015.

[18] S. Kirkpatrick, M. P. Vecchi, "Optimization by simmulated annealing," Science, vol. 220, no. 4598, pp. 671–680, 1983.

[19] D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, "Part I, graph partitioning," Elsevier Science B.V., vol. 37, no. 6, pp. 865–892, June. 1998.