IEEE/ACM Transactions on Networking · 2019 · 36 citations · 41 references
ComputingComputer ScienceAlgorithmsComputer NetworksTransportationGraph AlgorithmsNetwork Flow AlgorithmsNetwork FlowsNetwork OptimizationRoutingTraffic Flow TheoryCentralityComplexityDirected GraphsFlow CentralityNetwork Flow ProblemsSegment RoutingShortest Path In Directed GraphsShortest Paths
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 that the problem can now be solved in weakly polynomial time for a fixed number of middlepoints, which explains why existing work focuses on this variant. Yet, if we constrain the end-to-end paths to be acyclic, the problem can become NP-hard. An important application of our work concerns flow centrality, for which we are able to derive complexity results. Furthermore, we investigate the middlepoint selection problem in general node-constrained TE. We introduce and study group flow centrality as a solution concept, and show that it is monotone but not submodular. Our work provides a thorough theoretical treatment of node-constrained TE and sheds light on the development of the emerging node-constrained TE in practice.
41
Centrality in social networks conceptual clarification
Linton C. Freeman · Social Networks · 1978 · 16.9K citations
A Set of Measures of Centrality Based on Betweenness
Linton C. Freeman · Sociometry · 1977 · 10.2K citations
Network Flows: Theory, Algorithms, and Applications.
David K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti et al. · Journal of the Operational Research Society · 1994 · 8.2K citations · Full text