Multiobjective network design for realistic traffic models

ABSTRACT

Network topology design problems find application in several reallife scenarios. However, most designs in the past either optimize for a single criterion like delay or assume simplistic traffic models like Poisson. Such assumptions make the solutions inapplicable in the practical world.In this paper, we formulate and solve a multiobjective network topology design problem for a realistic Internet traffic model which is assumed to be self similar. We optimize for the average packet delivery delay and network layout cost to construct realistic network topologies. We present a multiobjective evolutionary algorithm (MOEA) to obtain the diverse near-optimal network topologies. For fair comparison, we design a multiobjective deterministic heuristic based on branch exchange -- we call the heuristic Pareto Branch Exchange (PBE). We empirically show that the MOEA used performs well for real networks of various sizes, and generated topologies are quite different with significantly larger delays for the self similar traffic model.

REFERENCES

• 1: J. Arabas and S. Kozdrowski. Applying an evolutionary algorithm to telecommunication network design. IEEE Trans. Evolutionary Computation, 5(4), 309--322 2001.
• 2: A. Atamturk and D. Rajan. Survivable network design: simultaneous routing of flows and slacks. Research Report, IEOR, University of California at Berkeley.
• 3: L. W. Clarke and G. Anandalingam. An integrated system for designing minimum cost survivable telecommunication networks. IEEE. Trans. Systems, Man and Cybernetics- Part A, 26(6):856--862, 1996.
• 4: Carlos A. Coello Coello , Gary B. Lamont , David A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 6: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 7: N. Deo and P. Micikevicius. Comparison of prüfer-like codes for labeled trees. In Proc. 32nd South-Eastern Int. Conf. Combinatorics, Graph Theory and Computing, 2001.
• 8: T. A. Feo and M. G. C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 1995.
• 9: C. M. Fonseca and P. J. Fleming. Multiobjective optimization and multiple constraint handling with evolutionary algorithms - Part I: a unified formulation. IEEE Trans. Systems, Man and Cybernetics-Part A: Systems and Humans, 28(1):26--37, 1998.
• 10: H. Frank and W. Chou. Topological optimization of computer networks. Proc. IEEE, 60(11):1395--1397, 1972.
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: S. Ghose, R. Kumar, N. Banerjee, and R. Datta. Multihop virtual topology design in WDM optical networks for self-similar traffic. Photonic Network Communications, 10(2):199--214, Sep. 2005.
• 13: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 14: R. H. Jan, F. J. Hwang, and S. T. Cheng. Topological optimization of a communication network subject to a reliability constraint. IEEE Trans. Reliability, 42(1):63--69, 1993.
• 15: J. D. Knowles and D. W. Corne. A comparison of encodings and algorithms for multiobjective minimum spanning tree problems. In Proc. 2001 Congress on Evolutionary Computation (CEC-01), volume 1, pages 544--551, May 27-30 2001.
• 16: King-Tim Ko , Kit-Sang Tang , Cheung-Yau Chan , Kim-Fung Man , Sam Kwong, Using Genetic Algorithms to Design Mesh Networks, Computer, v.30 n.8, p.56-61, August 1997 [doi>10.1109/2.607086]
• 17: R. Kumar and N. Banerjee. Multicriteria network design using evolutionary algorithm. In Proc. Genetic and Evolutionary Computations Conference (GECCO-03), LNCS 2023, pages 2179--2190. Springer Verlag, 2003.
• 18: R. Kumar, P. P. Parida, and M. Gupta. Topological design of communication networks using multiobjective genetic optimization. In Proc. Congress Evolutionary Computation (CEC-2002), pages 425--430. IEEE Press, 2002.
• 19: Rajeev Kumar , Peter Rockett, Improved sampling of the Pareto-front in multiobjective genetic optimizations by steady-state evolution: a Pareto converging genetic algorithm, Evolutionary Computation, v.10 n.3, p.283-314, Fall 2002 [doi>10.1162/106365602760234117]
• 20: R. Kumar, P. K. Singh, and P. P. Chakrabarti. Multiobjective EA approach for improved quality of solutions for spanning tree problem. In Proc. Int. Conf. Evolutionary Multi-Criterion Optimization (EMO-05), LNCS 3410, pages 811--825, 2005.
• 21: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 22: Günther R. Raidl , Bryant A. Julstrom, Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952678]
• 23: R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt. Approximation algorithms for degree-constrained minimum-cost network design problems. Algorithmica, 31(1):58--78, 2001.
• 24: H.-P. Schwefel. Performance analysis of intermediate systems serving aggregated ON/OFF traffic with long-range dependent properties. PhD Thesis, Institute für Informatik: Technischen Universität München, 2000.
• 25: G. Zohu and M. Gen. Genetic algorithm approach on multi-criteria minimum spanning tree problem. European J. Operations Research, 114(1):141--152, April 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Experimentation

Keywords:
Pareto front, combinatorial optimization, genetic algorithm, heuristics, multiobjective optimization, network topology design, optimization methods, self-similar traffic