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.