On the complexity of routing concurrent traffic in capacitated multistage networks

This paper examines the complexity of a fundamental traffic routing problem that arises in the design of routing algorithms based on packing a given set of traffic requirements into a few number of passes through a given multistage interconnection network. Two classes of networks are considered: 3-stage networks, and a generalized class of extra-stage indirect binary n-cube networks. For the former class, it is shown that the problem is NP-complete even if the network has exactly three secondary switches, and all links have unit capacity. In contrast, a sufficient and necessary condition for the existence of a solution is shown when the network has at most two secondary switches. For the latter class, the problem is shown to be NP-complete even if the network has 6 stages, and each link has a capacity ⩽3. The latter result implies that the problem is hard on conventional extra-stage indirect binary cube networks. The above results motivate further search for finding efficient heuristic algorithms to deal with practical cases of the problem