Hierarchical Network Design

Communication networks are immensely important today, since both companies and individuals use numerous services that rely on them. This thesis considers the design of hierarchical (communication) networks. Hierarchical networks consist of layers of networks and are well-suited for coping with changing and increasing demands. Two-layer networks consist of one backbone network, which interconnects cluster networks. The clusters consist of nodes and links, which connect the nodes. One node in each cluster is a hub node, and the backbone interconnects the hub nodes of each cluster and thus the clusters. The design of hierarchical networks involves clustering of nodes, hub selection, and network design, i.e. selection of links and routing of ows. Hierarchical networks have been in use for decades, but integrated design of these networks has only been considered for very special types of networks. The thesis investigates models for hierarchical network design and methods used to design such networks. In addition, ring network design is considered, since ring networks commonly appear in the design of hierarchical networks. The thesis introduces hierarchical networks, including a classification scheme of different types of hierarchical networks. This is supplemented by a review of ring network design problems and a presentation of a model allowing for modeling most hierarchical networks. We use methods based on linear programming to design the hierarchical networks. Thus, a brief introduction to the various linear programming based methods is included. The thesis is thus suitable as a foundation for study of design of hierarchical networks. The major contribution of the thesis consists of seven papers which are included in the appendix. The papers address hierarchical network design and/or ring network design. The papers have all been submitted for journals, and except for two papers, are awaiting review. The papers are mostly concerned with optimal methods and, in a few cases, heuristics for designing hierarchical and ring networks. All papers develop bounds which are used in the optimal methods and for comparison. Finally, computational results are reported. In Danish: Kommunikationsnetværk har enorm betydning i dag, da enkeltpersoner og virksomheder anvender utallige tjenester, som afh nger af kommunikationsnetværkene. Denne afhandling omhandler design af hierarkiske (kommunikations-) netværk. Hierarkiske netværk er lagdelte og er velegnede til at håndtere ændringer og gede i krav til båndbredde. Netværk med to niveauer består af et backbone netv rk som forbinder klynger af netværksknuder. Klyngerne består af netværksknuder og forbindelser mellem netværksknuderne internt i klyngen. I hver klynge er en af netværksknuderne udpeget som hoved-netværksknuden, dvs. den har forbindelse til backbone netværket. Backbone netværket forbinder hoved-netværksknuderne og dermed klyngerne. For at designe et hierarkisk netværk, skal der tages stilling til hvilke netværksknuder der er i hvilken klynge, hoved-netværksknuderne skal udvælges, netværksknuderne skal forbindes både i klyngerne og i backbone netværket, og tra k skal rutes i netværket. Hierarkiske netværk har været anvendt i artier, men design af disse netværk er kun blevet undersøgt for specielle netværkstyper. Denne afhandling undersøger modeller til design af hierarkiske netværk og metoder der kan anvendes til at designe hierarkiske netværk. Derudover undersøges ring netværk, da ring netværk ofte forekommer i design af hierarkiske netværk. Afhandlingen introducerer hierarkiske netværk, inklusive et klassifikationsskema af de forskellige typer af hierarkiske netværk. Dette bliver suppleret med en gennemgang af ring netværk problemer og en præsentation af en generel model, der tillader modellering af de este hierarkiske netværk. Metoder baseret på lineær programmering introduceres, idet de anvendes til design af hierarkiske netværk. Afhandlingen kan således danne grundlag for et studie af design af hierarkiske netværk. Afhandlings vigtigste bidrag best ar af syv artikler, der er inkluderet i appendiks. Artiklerne handler om design af hierarkisk netværk og ring netværk. Artiklerne er alle indsendt til videnskablige journaler og afventer bedømmelse, bortset fra to artikler, der allerede er blevet accepteret. Artiklerne beskriver oftest optimale metoder og i enkelte tilfælde heuristikker til at design hierarkiske netværk samt ring netværk. I alle tilfælde er der udviklet grænser, der kan anvendes enten til sammenligning eller indlejret i de optimale metoder. Endelig præsenteres resultater for testkørsler af metoderne.