MENTour: an algorithm for designing reliable high-speed data networks

Abstract

Interactive design is a foundation of a new generation of design tools, such as INTREPID [1] and NETDA/2. Interactive design requires that low-complexity algorithms be able to design realistic networks in minutes or seconds. The MENTOR algorithm has complexity O(n2) and is suitable to a wide variety of networks. However, if link speeds are much greater than the size of requirements, this algorithm builds networks which are tree-like. The typical design consists of a spanning tree with a few additional links and is generally too sparse to be reliable. Brute-force augmentation of these designs is reliable but too costly. The MENTour design has complexity O(n2) + O(bk), where n is the number of sites, b is the number of backbone sites and 3 ≤ k ≤ 4. It provides high-quality designs which are almost always two-connected. Experience has shown the best of these designs to be only a few per cent more costly than the best MENTOR designs.