An efficient algorithm for designing reliable ip networks with an access/edge/core hierarchical structure
Steven Chamberland · 2008
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 and their types to install at each level, selecting the port types to install in each router, finding the access, edge and core networks, selecting the link types and 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, i.e., the most widely deployed intra domain routing protocol for IP networks. Moreover, a minimum information rate (MIR) traffic parameter is guarantee between each pair of clients for the normal state of the network and for all single edge and core links failure scenarios. A tabu search algorithm is proposed to find network solutions rapidly. Finally, numerical results are presented and analyzed. The results show that the algorithm found solutions, on average, within 3.26% of the optimal solutions.