More Web Proxy on the site http://driver.im/

research-article

Node-Constrained Traffic Engineering: Theory and Applications

Authors:

George Trimponias,

Yanhui GengAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 27, Issue 4

Pages 1344 - 1358

https://doi.org/10.1109/TNET.2019.2921589

Published: 01 August 2019 Publication History

Abstract

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.

References

[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Upper Saddle River, NJ, USA: Prentice-Hall, 1993.

Digital Library

[2]

F. Aubry et al., "SCMon: Leveraging segment routing to improve network monitoring," in Proc. IEEE INFOCOM, Apr. 2016, pp. 1-9.

[3]

K. Bérczi and Y. Kobayashi, "The directed disjoint shortest paths problem," Egerváry Res. Group, Budapest, Hungary, Tech. Rep. TR- 2016-13, 2016.

[4]

R. Bhatia, F. Hao, M. Kodialam, and T. V. Lakshman, "Optimized network traffic engineering using segment routing," in Proc. IEEE INFOCOM, Apr./May 2015, pp. 657-665.

[5]

P. Bonacich, "Power and centrality: A family of measures," Amer. J. Sociol., vol. 92, no. 5, pp. 1170-1182, 1987.

[6]

U. Brandes, "A faster algorithm for betweenness centrality," J. Math. Sociol., vol. 25, no. 2, pp. 163-177, 2001.

[7]

C. Chen, W. Wang, and X. Wang, "Efficient maximum closeness centrality group identification," in Proc. Australas. Database Conf., 2016, pp. 43-55.

[8]

S. Dolev, Y. Elovici, R. Puzis, and P. Zilberman, "Incremental deployment of network monitors based on group betweenness centrality," Inf. Process. Lett., vol. 109, no. 20, pp. 1172-1176, 2009.

Digital Library

[9]

T. Eilam-Tzoreff, "The disjoint shortest paths problem," Discrete Appl. Math., vol. 85, no. 2, pp. 113-138, 1998.

Digital Library

[10]

A. Elwalid, C. Jin, S. Low, and I. Widjaja, "MATE: MPLS adaptive traffic engineering," in Proc. IEEE INFOCOM, Apr. 2001, pp. 1300-1309.

[11]

S. Even, A. Itai, and A. Shamir, "On the complexity of time table and multi-commodity flow problems," in Proc. 16th Annu. Symp. Found. Comput. Sci., Oct. 1975, pp. 184-193.

Digital Library

[12]

M. G. Everett and S. P. Borgatti, "The centrality of groups and classes," J. Math. Sociol., vol. 23, no. 3, pp. 181-201, Aug. 1999.

[13]

N. Feamster, J. Rexford, and E. Zegura, "The road to SDN," ACM Queue, vol. 11, no. 12, pp. 20:20-20:40, Dec. 2013.

Digital Library

[14]

U. Feige, "A threshold of ln n for approximating set cover," J. ACM, vol. 45, no. 4, pp. 634-652, 1998.

Digital Library

[15]

C. Filsfils et al., "Segment routing with MPLS data plane," in Proc. Internet Eng. Task Force, Internet Draft (Work Prog.), 2014, p. 2. [Online]. Available: https://datatracker.ietf.org/doc/draft-ietf-spring-segment-routing-mpls/.

[16]

C. Filsfils, P. Francois, and S. Previdi, "Segment routing use cases," IETF draft-filsfils-spring-segment-routing-use-cases-01, Oct. 2014.

[17]

C. Filsfils, N. K. Nainar, C. Pignataro, J. C. Cardona, and P. Francois, "The segment routing architecture," in Proc. IEEE Globecom, Dec. 2015, pp. 1-6.

[18]

S. Fortune, J. Hopcroft, and J. Wyllie, "The directed subgraph homeomorphism problem," Theor. Comput. Sci., vol. 10, no. 2, pp. 111-121, 1980.

[19]

B. Fortz and M. Thorup, "Internet traffic engineering by optimizing OSPF weights," in Proc. IEEE INFOCOM, Mar. 2000, pp. 519-528.

[20]

L. C. Freeman, S. P. Borgatti, and D. R. White, "Centrality in valued graphs: A measure of betweenness based on network flow," Social Netw., vol. 13, no. 2, pp. 141-154, Jun. 1991.

[21]

L. C. Freeman, "A set of measures of centrality based on betweenness," Sociometry, vol. 40, no. 1, pp. 35-41, Mar. 1977.

[22]

L. C. Freeman, "Centrality in social networks conceptual clarification," Social Netw., vol. 1, no. 3, pp. 215-239, 1979.

[23]

A. Ghosh, S. Ha, E. Crabbe, and J. Rexford, "Scalable multi-class traffic management in data center backbone networks," IEEE J. Sel. Areas Commun., vol. 31, no. 12, pp. 2673-2684, Dec. 2013.

[24]

A. Giorgetti et al., "Path encoding in segment routing," in Proc. IEEE Globecom, Dec. 2015, pp. 1-6.

Cited By

Pei XSun PHu YLi DChen BTian L(2024)Enabling efficient routing for traffic engineering in SDN with Deep Reinforcement LearningComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2024.110220241:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.comnet.2024.110220
Zheng JXu YWang LDai HChen G(2021)Online Joint Optimization on Traffic Engineering and Network Update in Software-defined WANsIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488837(1-10)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1109/INFOCOM42981.2021.9488837

Node-Constrained Traffic Engineering: Theory and Applications
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

Traffic Engineering Using Multipath Routing Approaches: Multipath Routing in MPLS and WSNs
Computing $$k$$k shortest paths from a source node to each other node

The single-pair K shortest path (KSP) problem can be described as finding $$k$$k least cost paths through a graph between two given nodes in a non-decreasing order, while single-source KSP algorithms aim to find KSPs from a given node to each other ...
RFC 4206: Label Switched Paths (LSP) Hierarchy with Generalized Multi-Protocol Label Switching (GMPLS) Traffic Engineering (TE)

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 27, Issue 4

August 2019

479 pages

ISSN:1063-6692

Issue’s Table of Contents

Copyright © 2019.

Publisher

IEEE Press

Publication History

Published: 01 August 2019

Published in TON Volume 27, Issue 4

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
71
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pei XSun PHu YLi DChen BTian L(2024)Enabling efficient routing for traffic engineering in SDN with Deep Reinforcement LearningComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2024.110220241:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.comnet.2024.110220
Zheng JXu YWang LDai HChen G(2021)Online Joint Optimization on Traffic Engineering and Network Update in Software-defined WANsIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488837(1-10)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1109/INFOCOM42981.2021.9488837

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents