Joint Hub Location; Node Clustering and Network Design of Two-Tiered Meshed Networks

Tommy Thomadsen
Technical University of Denmark

Thomas Stidsenm
Technical University of Denmark

Ladda ner artikel

Ingår i: Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Linköping Electronic Conference Proceedings 14:29, s.

Visa mer +

Publicerad: 2004-12-28


ISSN: 1650-3686 (tryckt), 1650-3740 (online)


In this talk we discuss design of two-tiered meshed networks. A two-tiered meshed network consists of clusters of nodes comprising the access network tier and a backbone tier which interconnects the clusters. Each cluster contains exactly one hub node which routes the traffic between clusters.

Designing a two-tiered meshed network involves a number of interrelated problems: Hub location; clustering of nodes and network design. These problems have often been carried out independently; but since the problems are interrelated; this may lead to suboptimal designs. We determine hub location; clustering of nodes and network design jointly. A mathematical model is presented for the problem and a bound is derived. Also a GRASP heuristic is implemented to obtain feasible solutions.

Tiers exists because of limitations in communication equipment; e.g. hop limits; organizational advantages; e.g. easier upgrade and the observation; that a two-tiered network seems to cope with changes in the traffic better than a network without tiers. However; enforcing tiers does incur some additional cost. This is clear; since any two-tiered network is also a feasible solution when networks without tiers are considered. For that reason we investigate how much cost is incurred by enforcing two tiers; i.e. we compare with networks without tiers.


Inga nyckelord är tillgängliga


Inga referenser tillgängliga

Citeringar i Crossref