View article

Traffic engineering (TE) is a fundamental task in networking. Conventionally, traffic can take any path connecting the source and destination. Emerging technologies such as segment routing, however, use logical paths that are composed of shortest paths going through a predetermined set of middlepoints in order to reduce the flow table overhead of TE implementation. Inspired by this, in this paper, we introduce the problem of node-constrained TE, where the traffic must go through a set of middlepoints, and study its theoretical fundamentals. We show that the general node-constrained TE that allows the traffic to take any path going through one or more middlepoints is NP-hard for directed graphs but strongly polynomial for undirected graphs, unveiling a profound dichotomy between the two cases. We also investigate a variant of node-constrained TE that uses only shortest paths between middlepoints, and prove …