Genetic algorithm based approach for designing computer network topology

ABSTRACT

One of the important features of computer networks is the potential for high reliability. The reliability of a network depends on many parameters such as connectivity, degree of each node, and average distance between any pair of nodes. The main focus of the problem considered in this paper is to design reliable computer network topologies. A generalized framework based on Genetic Algorithm is developed which is applicable to wide range of network design problems. Several topology design problems are solved to demonstrate the generality of this solution approach. The results obtained from genetic algorithm based solution approach are compared with the optimal solutions to illustrate the effectiveness of the proposed approach.

REFERENCES

• 1: Dharma P Agrawal, Advanced computer architecture, IEEE Computer Society Press, Los Alamitos, CA, 1986
• 2: K.B. Irani and N. G. Khabbaz,'A Methodology for the Design of Communication Networks and the Distribution of Data in Distributed Supercomputer Systems', Vol. C-31, No.5, 1982, pp. 419-434.
• 3: L. Kleinrock,'Analytic and Simulation Methods in Computer Network Design', Proceedings of Spring Joint Computer Conference, 1970, pp. 569-579.
• 4: H. Frank and W. Chon,'Topological Optimization of Computer Networks', Proceedings of the 1EEE, Vol.60, No.ll, 1972, pp. 1385-1397.
• 5: R. S. Wilkov,'Analysis and Design of Reliable Computer Networks,'IEEE Transactions on Communications, pp. 660-678, 1972.
• 6: R.R. Boorstyn and H. Frank, "Large Scale Network Topological Optimization," IEEE Trans. Communications, COM-26, Jan. 1977, 29.47.
• 7: S.P. Jain and K. Oopal,'On Network Augmentation," IEEE Trans, Reliability, R-35, Dec. 1986, 541-543.
• 8: H. Frank and R.E. Kahn,'Computer Communication Network Design,'AFIPS-C.onference Proceedings, Vol 40, pp. 255-313.
• 9: S.L. Hakimi, A.T. Amin, "On the design of reliable networks', Networks, vol 3, 1973, pp 241-260.
• 10: D. K. Pradhan and S. M. Reddy,'A Fault tolerant communication architecture for distributed system~," IEEE Transactions on Computers, Vol. C-31, Sept 1982.
• 11: K.K. Aggarwal, Y.C. Chopra and J.S. Bajwa, "Topological Layout of Links for Optimizing The Overall Reliability in a Computer Communication System," Microelectronics and Reliability, Vol. 22, No. 3, 1982, pp. 347-351.
• 12: R.S. Wilkov, Design of computer networks based on a new reliability measure, Proc. Syrup. Computer Comm. Networks and Teletraffic, pp. 371-384 (New York, April, 1972).
• 13: Anup Kumar , Dharma P. Agrawal, On evaluation of reliability and integrated performance-reliability parameters for distributed systems, 1989
• 14: K. K. Aggarwal and S. Rai, "Reliability Evaluation in Computer Communication Networks', IEEE Transactions on Reliability, Vol. R-30, June 1981, pp. 32-35.
• 15: J. H. Holland, "Genetic Algorithm and the Optimal Allocation of Trials', SIAM Journal of Computing, Vol. 2(2), 1973a, pp. 88-105.
• 16: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 17: R. M Pathak, A. Kumar and Y. P. Gupta,'Reliability Oriented Allocation of files on Distributed Systems', Proceedings of IEEE Symposium on Parallel and Distributed Systems, pp. 886-893, Dec., 1990.
• 18: Kenneth Alan De Jong, An analysis of the behavior of a class of genetic adaptive systems., 1975

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Reliability