Designing Reliable IP Networks with an Access/Edge/Core Hierarchical Structure

Abstract

In this paper, we tackle the design problem of reliable internet protocol (IP) networks with a three-level (access/edge/core) hierarchical structure. This problem consists in selecting the number of routers of each type to install at each level, locating each router, selecting the port types to install in each router, finding the access, edge and core networks, selecting the link types and finally, routing the traffic within the network. The routes are computed using the shortest paths using link metrics as the lengths of the links such as for the open shortest path first (OSPF) routing protocol; the most widely deployed intra domain routing protocol in IP networks. Moreover, a minimum information rate traffic parameter is guaranteed between each pair of access devices (routers and switches) for the normal state of the network (no failure) and for all single core router failure scenarios. A mathematical programming model is proposed for this problem and a tabu-based metaheuristic algorithm is proposed to find solutions within a reasonable amount of computational time. Finally, numerical results are presented and analyzed. The results show that for the test problems generated, the proposed approach found solutions, on average, 3,17% from a lower bound.

Keywords:

• Network design
• three-level (access/edge/core) networks
• mathematical programming model
• tabu search