TOPOLOGY OF NETWORKS

Some Topics

1. General design
2. Allocation of resources (facilities, etc.)
3. Routing
4. Reliability issues
5. Survivable networks
6. Upgradeability
7. Flexibility reconfigurablity
8. Testing and maintenance (e.g., probing problems)
9. Performance analysis
10. Issues of Quality of Service QoS
11. Global information networks
12. Proximity for networks
13. Clustering (decomposition)
14. Spanning trees (e.g., minimum spanning tree, Steiner tree)
15. Multi-layer networks, hierarchical networks, hierarchical network design problems
16. Augmentation problems

Research Groups

  • Columbia Network Research Center
  • Integrated Research and Education in Advanced Networking, Virginia Tech.,
  • Computer and Network Architecture Lab., Swedish Inst. of Computer Science
  • Computer Networks Research Group (Prof. Peter Marbach, Univ. of Toronto)
  • Communication Research Group (Tim C. Tozer, Univ. of York, Dept. of Electronics)
  • Networks Research Group (Prof. Lautie Cuthbert, Dept. of Electronic Engineering, Queen Mary, University of London)
  • Computer Communication Research Group (Univ. of California, Santa Cruz; Director: Prof. J.J. Garcia-Luna-Aceves)
  • Inst. of Communication Networks (Prof. J. Eberspaecher, Technical Univ. of Muenich)
  • The Computer Technology Documentation Project, Networking
  • David S. Johnson (AT & T Labs-Research)
  • Philip K. McKinley (Dept. of CS & Eng., Michigan State Univ.)
  • Clyde Monma (TelCordia Technologies)
  • Communication Technology Lab. (Swiss Federal Inst. of Technology)
  • The Center for Information and Communication Technology Research (CICTR), The Pennsylvania State Univ.
  • The Center for Networking and Distributed Systems CNDS (Prof. Baruch Awerbuch et. al., CS Dept., Johns Hopkins Univ.)
  • Prof. Bernard Fortz (Universite Catholique de Louvain)
  • Prof. Patrick Jaillet (MIT, Dept. of Civil & Environmental Eng.)
  • School of Information Technology and Engineering (Univ. of Ottawa):
    (a) Ad Hoc and Sensor Networking Research Group,
    (b) Bell Advanced Researcg Lab. (BARLO),
    (c) Communication Software Engineering Research Group (CSERG),
    (d) Communication Theory Research Group,
    (e) Computer Communication Network Research Group (CCNR),
    (f) Distributed Computing Research Group,
    (g) Distributed Systems Research Group (DSRG),
    (h) IPCOS Lab.: Integer Proramming, Combinatorial Optimization and Structures,
    (i) Laboratory for Wireless Devices & Systems (LWDS),
    (j) Large-Scale Distributed Interactive Simulation and Mobile Networking and Computing Research Lab. (PARADISE),
    (k) Multimedia Communication Research Lab. (MCRLab),
    (l) Network Computing and Control Technologies Lab.,
    (m) Optical Networks Lab.,
    (n) Systems Theory Applied to Engineering, Control and Communication Research Group.

  • Computing Center of Russian Academy of Sciences
    (Profs. Yuri E. Malashenko, Natalia M. Novikova)

  • Vladimir K. Popkov (Lab. of Mathematical Modeling of Information Networks,
    Computing Center, Dept. of Communication Systems, Sibirian Branch of Russian Academy of Sciences, Novosibirsk;
    "Mathematical Models of Connectivity")

  • Prof. Albert-Laszlo Barabasi (Center for complex Network Research Lab., Dept. of Physics, Northeastern University, Boston;
    "Free-scale nertworks, etc.")

    Journals

  • Networks
  • Telecommunication Systems
  • IEEE Network
  • IEEE J. of Selected Areas of Communications
  • Computer Networks
  • Ad Hoc Networks
  • Wireless Networks
  • Computer Communications
  • J. of Networks and Computers
  • Int. J. of Network Management
  • Int. J. of Communication Systems
  • Wireless Communication & Mobile Computing
  • IEEE Trans. on SMC
  • J. of Network and Computer Applications

    Bibliography

  • Books
    1. A.S. Tannenbaum, Computer Networks. Prentice Hall, NJ, 1981. 2. L.R. Ford, Jr., D.R. Fulkerson, Flows in Networks. Princeton Univ. Press, 1962.
    3. P. Oppenheimer, Top-Down Network Design, 2nd ed., Pearson Education, 2004.
    4.V.M. Vishnevsky, Theoretical Fundamentals of Computer Network Design. Technosfera, Moscow, 2003.
    5. A.V. Butrimenko, Design and Utilization of Computer Networks. Mowcow, Finansy i Statistika, (in Russian) 1981.
    6. G. Daryani, Principles of Active Network Synthesis and Design. Wiley, 1976.
    7. E.A. Yakubaytis, Architecture of Computer Networks. Moscow, Statistika, (in Russian) 1980.
    8. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, (eds.), The Traveling Salesman Problem. Chichester: J.Wiley & Sons, 1985.
    9. Micro/minicomputer systems. Structure, Implementation, and Application. Prentice Hall, NJ, 1980.
    10. D.R. Sheer, Network Reliability and Algebraic Structures. Oxford, Claredon Press, 1991.
    11. E. Minieka, Optimization Algorithms for Networks and Graphs. Marcel Dekker, New York, 1978.
    12. F.R. Roberts, Discrete Mathematical Models with Applications to Social, Biological and Environmental Problems, Prentice Hall, 1976.
    13. M.R. Garey, and D.S. Johnson, Computers and Intractability. The Guide to the Theory of NP-Completeness. San-Francisco: W.H. Freeman and Company, 1979.
    14. Ch. Wynants, Network Synthesis Problems. Kluwer, 2001.
    15. F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem. Elsevier, Amsterdam, 1992.
    16. F.K. Hwang, F.S. Roberts. C. Monma, Reliability of Computer and Communication Networks. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 5, AMS/ACM publisher, 1991.
    17. I. Stojmenovic, Ed., Handbook of Wireless Networks and Mobile Computing, Wiley, 2002.
    18. M. Pioro, D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann, (Morgan kaufmann Series in Networking), 2004.
    19. A. Kumar, D. Naujaunath, J. Kuri, Communication Networks. An Analytical Approach. Morgan Kaufmann, (Morgan Kaufmann Series in Networking), 2004.
    20. A. Leon-Garsia, I. Widjaja, Communication Networks. Fundamental Concepts and Key Architectures. McGraw-Hill, 2nd ed., 2004.
    21. R. Horak, H. Newton, M.A. Miller, Communication Systems and Networks. Wiley, 3rd ed., 2002.
    22. P.R. Monge, N.S. Contractor, Theories of Communication Networks. Oxford University Press, 2003.
    23. B. Fortz, Design of Survivable Networks with Bounded Rings, Kluwer, 2000.
    24. G.R. Ash, Dynamic Routing in Telecommunication Networks. McGraw-Hill, 1998.
    25. D. Cieslik, Shortest Connectivity. An Introduction with Application in Phylogeny. Springer, 2005.
    26. H. Yaman, Concentrator Location in Telecommunications Networks. Springer, 2005.
    27. Murhammer M.W., Lee K.-K., Motallebi P., Borghi P., Wozabal K.: IP Network Design Guide, IBM Red Book, 1999.
    28. D.-Z. Du, X. Hu, Steiner Tree Problems in Computer Communication Networks. Singapore: World Scientific Publishing Co., 2008.
    29. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms, 2nd ed., Boston: MIT Press \& McGraw-Hill, 2001.

  • Basic Papers
    1. J. Current, C. ReVelle, J. Cohon, The hierarchical network design problem. Eur. J. of Operational Research, 27(1), 57-66, 1986.
    2. B. Gavish, H. Pirkul, Computer and database location in distributed computer systems. IEEE Trans. Comput., C-35, 583-590, 1986.
    3. S.-G. Chang, B. Gavish, Telecommunications networks topological design and capacity expansion: Formulations and Algorithms. Telecommunication Systems, 1, 99-131, 1993.
    4. C.L. Monma, D.R. Smith, Probavilistic Analysis of Interframe Tie Requirements for Cross-Connect Systems. AT & T Bell Labs. Technical J., 63(4), 643-664, 1984.
    5. C.L. Monma, B.S. Munson, W.R. Pulleyblank, Minimum-Weight Two-Connected Spanning Networks. Mathematical Programming, 46, 153-172, 1990.
    6. D. Bienstock, E.F. Brickell, C.L. Monma, On the structure of minimum-weighted k-connected spanning networks. SIAM J. Discr. Math., 3, 320-329, 1990.
    7. G. Dahl, The deisgn of survivable directed networks. Telecommunication Systems, 2, 349-377, 1994.
    8. H.L. Morgan, D.K. Levin, Optimal program and data locations in computer networks. Communications of the ACM. 20, 305-312, 1977.
    9. R.-H. Jain, Design of reliable networks. Computer and Oper. Res., 20(1), 25-34, 1993.
    10. F. Chauvet, J.M. Proth, V.M. Vishnevsky, E. Levner, Hub facility location in corporate communication networks. Scientific Israel, 2(1), 37-41, 2000.
    11. R.R. Boorstyn, H. Frank, Large-scale network topological optimization. IEEE Trans. Communications, 25(1), 29-47, 1977.
    12. S.I. Hakimi, Steiner problems in graphs and its implications. Networks, 1, 113-133, 1971.
    13. Dror, M. Haouari, Generalized Steiner problems and other variants. J. of Combinatorial Optimization, 4(4), 415-436, 2000.
    14. M. Dror, M. Haouari, J. Chaouachi, Generalized spanning trees. EJOR, 120(3), 583-592, 2000.
    15. Eswaran K.P., Tarjan R.E., Augmentation problems. SIAM J. on Computing, 5(4) 653-665, 1976.
    16. Fernau H., Kneis J., Kratsch D., Langer A., Liedloff M., Raible D., Rossmanith P.: An exact algorithm for the Maximum Leaf Spanning Tree problem. Theor. Computer Science, 412(45) 6290-6302, 2011.
    17. L. Kou, G. Markowsky, L. Berman, A fast algorithm for Steiner trees. Acta Informatica, 15, 141-145, 1981.
    18. S. Pierre, G. Legault, A genetic algorithm for designing distributed computer network topologies. IEEE Trans. SMC, Part B, 28(2), 249-258, 1998.
    19. I. Stojmenovic, J. Wu, Broadcasting and activity scheduling in ad hoc networks. In: S. Basagni, M. Conti, S. Giordano, I. Stojmenovic, Eds., Mobile Ad Hoc Networking, IEEE/Wiley, 205-229, 2004.
    20. I. Stojmenovic, M. Seddigh, J. Zunic, Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks. IEEE Trans. on Parallel and Distributed Systems, 13(1), 14-25, 2002.
    21. Gavish B., Topological design of telecommunication networks - the overall design problem. EJOR, 58(2) 149-172, 1992.
    22. Goemans M.X., Myung Y.-s.: A catalog of Steiner tree formulations. Networks, 23(1) 19-28, 1993.
    23. M. Imase, B.M. Waxman, Dynamic Steiner tree problem. SIAM J. on Discr. Math. 4(3), 369-384, 1991.
    24. A. Joshi, N. Mishra, R. Batta, R. Nagi, Ad Hoc network topology design for distributed fusion: A mathematical programming approach. Proc. of the 7th Int. Conf. on Information Fusion, Stockholm, 836-841, 2004.
    25. A. Balakrishnan, T. Magnanti, P. Mirchandani, A dual-based algorithm for multi-level network design. Manag. Sci., 40(5) 567-581, 1994.
    26. Carlos Obreque, Macarena Donoso, Gabriel Gutiérrez, Vladimir Marianov, A branch and cut algorithm for the hierarchical network design problem. EJOR 200(1) 28-35, 2010.
    27. S. Voss, Modern heuristic search methods for the Steiner tree problem in graph. In: Du, D.-Z., Smith, J.M., Rubinstein, J.H., Eds., In: Advances in Steiner Trees, Boston, Kluwer, pp. 283-323, 2000
    28. S. Orlowski, M. Pioro, A. Tomaszewski, R. Wessaly, SNDlib 1.0-Survivable Network Design Library. Networks, 55, 276-286, 2010.

  • Papers
    1. J. Chiarongse, M.M. Srinisavan, T.J. Teory, Performance analysis of a large interconnected networks by decomposition techniques. IEEE Netwroks, 2(4), 19-27, 1988.
    2. N.A. Kuznetsov, M.Sh. Levin, V.M. Vishnevsky, Some Combinatorial Optimization Schemes for Multi-Layer Network Topology. Electronic Proc. of 17th IMACS World Congress, Paris, France, Paper T4-I-42-0485, 2005
    3. Chen G., Chen S., Guo W., Chen W., The multicriteria minimum spanning tree problem based genetic algorithm. Inform. Sci., 177(22) 5050--5063, 2007.
    4. S.M. Nazem, Y.H. Liu, Y. Shi, Implementing Telecommunication Infrastructure: A rural America case. Telematics and Informatics, 13, 23-31, 1996.
    5. M. Jorgic, I. Stojmenovic, M. Hauspie, D. Simplot-Ryl, Localized Algorithms for Detection of Critical Nodes and Links for Connectivity in Ad Hoc Networks. The 3rd Annual Mediterranean Ad Hoc Workshop Med-Hoc-Net, Bordum, Turkey, 360-371, June 2004.
    6. I. Dumitrescu, N. Boland, Improved Preprocessing, Labeling and Scaling Algorithms for the Weight-Constrained Shortest Path Problem. Networks, 42(3), 135-153, 2003.
    7. L. Bao, J.J. Garcia-Luna-Aceves, Transmission Scheduling in Ad Hoc Networks with Directional Antennas. MOBICOM'02, Atlanta, Sept. 2002.
    8. H. Lee, Y. Shi, J.D. Stolen, Allocating data files over a wide area network: Goal setting and compomise design. Information and Management. 26, 85-93, 1994.
    9. Levin M.Sh., Selection of user's connection in last mile problem. IEEE Trans. SMC - Part A, 41(2), 370-374, 2011.
    10. Levin M.Sh., Petukhov M.V., Multicriteria assignment problem (selection of access points). Proc. of 23rd Int. Conf. IEA/AIE 2010, "Trends in Applied Intelligent Systems", LNCS 6097, part II, Springer, pp. 277-287, 2010.
    11. M.Sh. Levin, M.V. Petukhov, Connection of users with a telecommunications network: multicriteria assignment problem. J. of Communications Technology and Electronics, vol. 55, no. 12, pp. 1532-1541, 2010.
    (journal site)
    Levin M.Sh., Petukhov M.V., Connection of users and telecommunication network
    (multicriteria assignment problem). Electronic Scientific Journal "Information Processes",
    vol. 9, no. 4, pp. 332-342, 2009 (in Russian)

    12. M.Sh. Levin, A.A. Zamkovoy, Multicriteria Steiner tree with the cost of Steiner vertices. J. of Communications Technology and Electronics, vol. 56, no. 12, 1527-1542, 2011.
    (journal site)
    Levin M.Sh., Zamkovoy A.A., Multicriteria Steiner tree with cost of Steiner vertices. Electronic Scientific Journal "Information Processes",
    vol. 11, no. 1, pp. 140-160, 2011 (in Russian).

    13. D.M. Belozerkovsky, V.M. Vishnevsky, New algorithm of generating a two-connected subgraphs in optimization of communicaiton network topology. Automation and Remote Control, No. 1, 1997.
    14. M.-J. Lee, J.R. Yee, A design algorithm for reconfigurable ATM networks. Telecommunication Systems, 2, 197-224, 1994.

  • Electronic Preprints
    1. M.Sh. Levin, Towards design of hierarchy (research survey). Electronic preprint. 36 pp., Dec. 8, 2012.
    http://arxiv.org/abs/1212.1735 [math.OC]

    2. M.Sh. Levin, R.I. Nuriakhmetov, Multicriteria Steiner tree problem for communication network. Electronic preprint, 11 pp., Febr. 12, 2011.
    http://arxiv.org/abs/1102.2524 [cs.DS]


  • PhD Dissertations
    1. A. Bley, Routing and capacity optimization for IP networks. PhD thesis, Technische Universitat Berlin, 2007.
    2. O. Gunluk, Computational problems in telecommunication networks. PhD thesis, Dept. of IEOR, Columbia University, 1994.
    3. S. Raghavan, Strong formulations for network design problems with connectivity requirements. PhD Thesis, MIT, 1995.
    4. M. Prytz, On optimization in design of telecommunication networks with multicast and unicast traffic. Ph.D. thesis, Royal Inst. of Technology, Stockholm, Sweden, 2002.