Abstract
As it also happens in nature, technological networks typically evolve in an incremental manner, instead of being optimally designed. This evolutionary process is driven by changes in the underlying parameters and constraints (the “environment”) and it typically aims to minimize the modification cost after each change in the environment. In this paper, we first formulate the incremental network design approach and compare that with the more traditional optimized design approach in which the objective is to minimize the total network cost. We evaluate the cost overhead and evolvability of incremental design under two network expansion models (random and gradual), focusing on the simpler case of “ring” networks. We find that even though incremental design has some cost overhead, that overhead does not increase as the network grows. Also, it is less costly to evolve an existing network than to design it from scratch as long as the network expansion factor is less than a critical value.
This research was supported by the National Science Foundation under Grant No. 0831848.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Applegate, D., Bixby, R., Chvtal, V., Cook, W.: The Traveling Salesman Problem: (A Computational Study). Princeton University Press (2006)
Arya, S., Mount, D., Netanyahu, N., Silverman, R., Wu, A.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM 45, 891–923 (1998)
Beardwood, J., Halton, J., Hammersley, J.: The shortest path through many points. Mathematical Proceedings of the Cambridge Philosophical Society (55), 299–327 (1959)
Carvalho, P., Ferreira, L., Lobo, F., Barruncho, L.: Optimal distribution network expansion planning under uncertainty by evolutionary decision convergence. International Journal of Electrical Power & Energy Systems 20(2), 125–129 (1998)
Chiang, M., Yang, M.: Towards Network X-ities From a Topological Point of View: Evolvability and Scalability. In: Proc., Allerton Conf. on Comm., Control, and Computing (2004)
Geary, N., Antonopoulos, A., Drakopoulos, E., O’Reilly, J.: Analysis of Optimisation Issues In Multi-Period DWDM Network Planning. In: IEEE INFOCOM (2001)
Gopal, S., Jain, K.: On Network Augmentation. IEEE Transactions on Reliability 35(5), 541–543 (1986)
Hahsler, M., Hornik, K.: TSP Infrastructure for the Traveling Salesperson Problem. IEEE/ACM Transactions on Networking 23(2) (December 2007)
Herzog, M., Maier, M., Reisslein, M.: Metropolitan area packet-switched WDM networks: A survey on ring systems. IEEE Communications Surveys & Tutorials 6(2), 2–20 (2004)
Lee, H., Dooly, D.: Heuristic algorithms for the fiber optic network expansion problem. Telecommunication Systems 7, 355–378 (1997)
Meyerson, A., Munagala, K., Plotkin, S.: Designing Networks Incrementally. In: IEEE FOCS (2001)
Pickavet, M., Demeester, P.: Long-term planning of WDM networks: A comparison between single-period and multi-period techniques. Photonic Network Communications 1(4), 331–346 (1999)
Pioro, M., Medhi, D.: Routing, Flow and Capacity Design in Communication and Computer Networks. The Morgan Kaufmann Series in Networking (2004)
Tero, A., Takagi, S., Saigusa, T., Ito, K., Bebber, D., Fricker, M., Yumiki, K., Kobayashi, R., Nakagaki, T.: Rules for Biologically Inspired Adaptive Network Design. Science 327(5964), 439–442 (2010)
Vajanapoom, K., Tipper, D.: Risk based incremental survivable network design (2007)
Wu, T., Cardwell, R., Broyden, M.: A multi-period design model for survivable network architecture selection for SONET interoffice networks. IEEE Trans. on Reliability 40, 417–427 (1991)
Yaged, B.: Minimum Cost Routing for Dynamic Network Models. Networks 3, 193–224 (1973)
Zadeh, N.: On Building Minimum Cost Communication Networks over time. Networks 4, 19–34 (1974)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 ICST Institute for Computer Science, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Bakhshi, S., Dovrolis, C. (2012). The Price of Evolution in Incremental Network Design (The Case of Ring Networks). In: Hart, E., Timmis, J., Mitchell, P., Nakamo, T., Dabiri, F. (eds) Bio-Inspired Models of Networks, Information, and Computing Systems. BIONETICS 2011. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 103. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32711-7_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-32711-7_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32710-0
Online ISBN: 978-3-642-32711-7
eBook Packages: Computer ScienceComputer Science (R0)