Article

Multiobjective network design for realistic traffic models

Authors:

Nilanjan Banerjee,

Rajeev KumarAuthors Info & Claims

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Pages 1904 - 1911

https://doi.org/10.1145/1276958.1277341

Published: 07 July 2007 Publication History

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.

Digital Library

[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.

Digital Library

[4]

C. A. C. Coello, D. A. V. Veldhuizen, and G. B. Lamont. Evolutionary Algorithms for Solving Multiojective Problems. Boston, MA: Kluwer, 2002.

Digital Library

[5]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001.

Digital Library

[6]

K. Deb. Multiobjective Optimization Using Evolutionary Algorithms. Chichester, UK: Wiley, 2001.

Digital Library

[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.

Digital Library

[10]

H. Frank and W. Chou. Topological optimization of computer networks. Proc. IEEE, 60(11):1395--1397, 1972.

[11]

M. R. Garey and D. S. Johnson. Computers and Interactability: A Guide to the Theory of NPCompleteness. San Francisco, LA: Freeman, 1979.

Digital Library

[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]

D. S. Hochbaum. Approximation Algorithms for NP-Hard Problems. Boston, MA: PWS, 1997.

Digital Library

[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]

K. T. Ko, K. S. Tang, C. Chan, K. F. Man, and S. Kwong. Using multiobjective genetic algorithms to design mesh networks. IEEE Computer, 30(8):56--61, 1997.

Digital Library

[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.

Digital Library

[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]

R. Kumar and P. I. Rockett. Improved Sampling of the Pareto-front in Multiobjective Genetic Optimization by Steady-State Evolution: A Pareto Converging Genetic Algorithm. Evolutionary Computation, 10(3):283--314, 2002.

Digital Library

[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.

Digital Library

[21]

V. Paxson and S. Floyd. Wide-area traffic: The failure of Poisson modelling. IEEE/ACM Trans. Networking, 3(3):226--244, 1995.

Digital Library

[22]

G. R. Raidl and B. A. Julstrom. Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In Proc. 18th ACM Symposium on Applied Computing (SAC 2003), pages 747--752, March 9-12 2003.

Digital Library

[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.

Cited By

Nascimento JAraujo DBastos-Filho CMartins-Filho J(2018)Manyobjective Optimization to Design Physical Topology of Optical Networks with Undefined Node Locations2018 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2018.8477824(1-7)Online publication date: Jul-2018
https://doi.org/10.1109/CEC.2018.8477824
Araujo DBastos-Filho C(2017)Robustness of physical topologies of optical networks created by variants of Gabriel graphs2017 IEEE 18th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2017.7968686(1-6)Online publication date: Jun-2017
https://doi.org/10.1109/HPSR.2017.7968686
Rodriguez-Lozano DGomez-Pulido JDuran-Dominguez A(2016)Predicting Access Points Workload in Wi-Fi Infrastructures According to Users' BehaviorProceedings of the International Conference on Big Data and Advanced Wireless Technologies10.1145/3010089.3010106(1-6)Online publication date: 10-Nov-2016
https://dl.acm.org/doi/10.1145/3010089.3010106
Show More Cited By

Recommendations

Evolution of hyperheuristics for the biobjective 0/1 knapsack problem by multiobjective genetic programming
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

The 0/1 knapsack problem is one of the most exhaustively studied NP-hard combinatorial optimization problems. Many different approaches have been taken to obtain an approximate solution to the problem in polynomial time. Here we consider the biobjective ...
Multiobjective genetic programming approach to evolving heuristics for the bounded diameter minimum spanning tree problem: MOGP for BDMST
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

The bounded-diameter (or diameter-constrained) minimum spanning tree (BDMST) problem is a well-studied combinatorial optimization problem for which several heuristics such as: one-time tree construction (OTTC), center based tree construction(CBTC), ...
Evolution of hyperheuristics for the biobjective graph coloring problem using multiobjective genetic programming
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

We consider a formulation of the biobjective soft graph coloring problem so as to simultaneously minimize the number of colors used as well as the number of edges that connect vertices of the same color. We aim to evolve hyperheuristics for this class ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

July 2007

2313 pages

ISBN:9781595936974

DOI:10.1145/1276958

General Chair:
Hod Lipson
Cornell University, USA

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO07

Sponsor:

GECCO07: Genetic and Evolutionary Computation Conference

July 7 - 11, 2007

London, England

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
526
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nascimento JAraujo DBastos-Filho CMartins-Filho J(2018)Manyobjective Optimization to Design Physical Topology of Optical Networks with Undefined Node Locations2018 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2018.8477824(1-7)Online publication date: Jul-2018
https://doi.org/10.1109/CEC.2018.8477824
Araujo DBastos-Filho C(2017)Robustness of physical topologies of optical networks created by variants of Gabriel graphs2017 IEEE 18th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2017.7968686(1-6)Online publication date: Jun-2017
https://doi.org/10.1109/HPSR.2017.7968686
Rodriguez-Lozano DGomez-Pulido JDuran-Dominguez A(2016)Predicting Access Points Workload in Wi-Fi Infrastructures According to Users' BehaviorProceedings of the International Conference on Big Data and Advanced Wireless Technologies10.1145/3010089.3010106(1-6)Online publication date: 10-Nov-2016
https://dl.acm.org/doi/10.1145/3010089.3010106
Figueiredo EAraujo DFilho CLudermir T(2016)Physical Topology Design of Optical Networks Aided by Many-Objective Optimization Algorithms2016 5th Brazilian Conference on Intelligent Systems (BRACIS)10.1109/BRACIS.2016.080(409-414)Online publication date: Oct-2016
https://doi.org/10.1109/BRACIS.2016.080
Clímaco JCraveirinha JGirão-Silva R(2016)Multicriteria Analysis in Telecommunication Network Planning and Design: A SurveyMultiple Criteria Decision Analysis10.1007/978-1-4939-3094-4_26(1167-1233)Online publication date: 2016
https://doi.org/10.1007/978-1-4939-3094-4_26
de Araujo DMartins-Filho JBastos-Filho C(2015)New Graph Model to Design Optical NetworksIEEE Communications Letters10.1109/LCOMM.2015.248071619:12(2130-2133)Online publication date: Dec-2015
https://doi.org/10.1109/LCOMM.2015.2480716
Elshqeirat BSoh SKwan-Wu Chin (2015)Bi-objective network topology design with reliability constraint2015 6th International Conference on Information and Communication Systems (ICICS)10.1109/IACS.2015.7103233(234-239)Online publication date: Apr-2015
https://doi.org/10.1109/IACS.2015.7103233
de Araújo DBastos-Filho CMartins-Filho J(2015)An evolutionary approach with surrogate models and network science concepts to design optical networksEngineering Applications of Artificial Intelligence10.1016/j.engappai.2015.04.00443:C(67-80)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1016/j.engappai.2015.04.004
Dasgupta MBiswas GBhar C(2013)Design of network topology based on delay-cost sink treeInternational Journal of Communication Networks and Distributed Systems10.1504/IJCNDS.2013.05183410:2(146-162)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1504/IJCNDS.2013.051834
Gu YShenq SWu QDasgupta DBiaz S(2012)On a multi-objective evolutionary algorithm for optimizing end-to-end performance of scientific workflows in distributed environmentsProceedings of the 45th Annual Simulation Symposium10.5555/2331751.2331758(1-9)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.5555/2331751.2331758
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten