. .. Related-work, 6.2.2 SDN and Network Energy Efficiency

. Sfc and . .. Placement,

. .. Greenchains,

. .. Numerical-experiments,

.. .. Conclusion,

T. Achterberg, SCIP-a framework to integrate constraint and mixed integer programming, p.29, 2004.

J. Hatem-ben-amor, A. Desrosiers, and . Frangioni, Stabilization in column generation. Groupe d'études et de recherche en analyse des décisions, p.30, 2004.

C. Barnhart, L. Ellis, G. L. Johnson, . Nemhauser, W. P. Martin et al., Branch-and-price: Column generation for solving huge integer programs, Operations research, vol.46, p.30, 1998.

E. Robert and . Bixby, A brief history of linear and mixed-integer programming computation, Documenta Mathematica, p.28, 2012.

V. Chvatal and V. Chvatal, Linear programming. Macmillan, 1983 (cit, p.30

P. Crescenzi, M. Viggo-kann, and . Halldórsson, A compendium of NP optimization problems, p.31, 1995.

Z. Chen and W. Powell, Solving parallel machine scheduling problems by column generation, INFORMS Journal on Computing, vol.11, issue.1, p.29, 1999.

. Ibm and . Cplex, V12. 1: User's Manual for CPLEX, International Business Machines Corporation, vol.46, p.29, 2009.

B. George and . Dantzig, Programming in a linear structure, p.28, 1948.

G. Desaulniers, J. Desrosiers, and M. M. Solomon, Column generation, vol.5, p.30, 2006.

M. Desrochers, J. Desrosiers, and M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Operations research, vol.40, p.29, 1992.

M. Alanyali and E. Ayanoglu, Provisioning algorithms for WDM optical networks, IEEE/ACM Transactions On Networking, vol.7, issue.5, p.109, 1999.

G. Ausiello, A. D. Atri, and M. Protasi, Structure preserving reductions among convex optimization problems, Journal of Computer and System Sciences, vol.21, issue.1, p.48, 1980.

Y. K. Agarwal and P. Venkateshan, Survivable network design with shared-protection routing, European Journal of Operational Research, vol.238, p.110, 2014.

M. Beck, J. F. Botero, and K. Samelin, Resilient allocation of service Function chains, Network Function Virtualization and Software Defined Networks (NFV-SDN), IEEE Conference on, p.110, 2016.

F. Jacques and . Benders, Partitioning procedures for solving mixedvariables programming problems, Numerische mathematik, vol.4, pp.238-252, 1962.

P. Berde, M. Gerola, J. Hart, Y. Higuchi, M. Kobayashi et al., ONOS: towards an open, distributed SDN OS, Proceedings of the third workshop on Hot topics in software defined networking, pp.1-6, 2014.

M. Casazza, P. Fouilhoux, M. Bouet, and S. Secci, Securing virtual network function placement with high availability guarantees, 2017 IFIP Networking Conference (IFIP Networking) and Workshops, p.110, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01445494

C. Chu, K. Xi, M. Luo, and H. Chao, Congestion-aware single link failure recovery in hybrid SDN networks, Proceedings of IEEE INFOCOM, p.82, 2015.

V. , Linear Programming. Freeman, 1983 (cit, vol.148, p.88

. Cisco, Bidirectional Forwarding Detection, p.105

I. Dinur and D. Steurer, Analytical Approach to Parallel Repetition, Proceedings ACM STOC 2014, vol.85, p.44

P. Fonseca and E. Mota, A survey on fault management in software-defined networks, IEEE Communications Surveys & Tutorials, p.82, 2017.

B. Fortz and M. Thorup, Optimizing OSPF/IS-IS weights in a changing world, IEEE journal on selected areas in communications, vol.20, p.96, 2002.
URL : https://hal.archives-ouvertes.fr/hal-01255600

A. Fumagalli and L. Valcarenghi, IP restoration vs. WDM protection: Is there an optimal choice?, In: IEEE network, vol.14, p.82, 2000.

P. Gill, N. Jain, and N. Nagappan, Understanding network failures in data centers: measurement, analysis, and implications, ACM SIGCOMM Computer Communication Review, vol.41, p.107, 2011.

J. Hrastad, Some optimal inapproximability results, Journal of the ACM (JACM), vol.48, p.92, 2001.

N. Huin, B. Jaumard, and F. Giroire, Optimization of Network Service Chain Provisioning, IEEE International Conference on Communications, vol.111, p.110, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01476018

N. Huin, B. Jaumard, and F. Giroire, Optimal Network Service Chain Provisioning, IEEE/ACM Transactions on Networking, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01920951

A. Hmaity, M. Savi, F. Musumeci, M. Tornatore, and A. Pattavina, Protection strategies for virtual network functions placement and service chains provisioning, pp.1-15, 2017.

J. Hu, Diverse routing in optical mesh networks, IEEE Transactions on Communications, vol.51, p.80, 2003.

N. Huin, A. Tomassilli, F. Giroire, and B. Jaumard, Energy-Efficient Service Function Chain Provisioning, IEEE/OSA Journal of Optical Communications and Networking, vol.10, p.110, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01920960

R. R. Iraschko, M. H. Macgregor, and W. D. Grover, Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks, IEEE/ACM Transactions on Networking, vol.6, p.108, 1998.

A. Kvalbein, T. Cicic, and S. Gjessing, Post-failure routing performance with multiple routing configurations, Proceedings of IEEE INFOCOM, vol.83, p.82, 2007.

J. Kempf, E. Bellagamba, A. Kern, and D. Jocha, Scalable fault management for OpenFlow, Communications (ICC), 2012 IEEE international conference on, p.80, 2012.

S. Kandula, D. Katabi, and J. Vasseur, Shrink: A tool for failure diagnosis in IP networks, Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, pp.173-178, 2005.

A. Kvalbein, S. Audun-fosselie-hansen, O. Gjessing, and . Lysne, Fast IP network recovery using multiple routing configurations, Proceedings of IEEE INFOCOM, p.83, 2006.

B. Lantz, B. Heller, and N. Mckeown, Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks. Hotnets-IX. Monterey, vol.19, p.101, 2010.

. .. Related-work, 138 6.2.3 Network Virtualization and Network Energy Efficiency

. Sfc and . .. Placement,

. .. Power-model, , p.142

.. .. Layered-graph,

. .. Numerical-experiments,

J. Araujo, F. Giroire, J. Moulierac, Y. Liu, and R. Modrzejewski, Energy Efficient Content Distribution, The Computer Journal, vol.59, issue.2, p.153, 2016.
URL : https://hal.archives-ouvertes.fr/hal-00800273

R. Bolla, R. Bruschi, F. Davoli, and F. Cucchietti, Energy efficiency in the future internet: A survey of existing approaches and trends in energy-aware fixed network infrastructures, IEEE Communications Surveys & Tutorials, vol.13, p.138, 2010.

R. Bolla, C. Lombardo, R. Bruschi, and S. Mangialardi, DROPv2: energy efficiency through network function virtualization, IEEE Network, vol.28, p.139, 2014.

J. Chabarek, J. Sommers, P. Barford, C. Estan, D. Tsiang et al., Power Awareness in Network Design and Routing, Annual Joint Conference of the IEEE Computer and Communications Societies -INFOCOM, p.142, 2008.

V. , Linear Programming. Freeman, 1983 (cit, vol.148, p.88

L. Chiaraviglio, M. Mellia, and F. Neri, Minimizing ISP network energy cost: formulation and solutions, IEEE/ACM Transactions on Networking (TON), p.138, 2012.

F. Floriano-de-rango, P. Guerriero, and . Fazio, Link-stability and energy aware routing protocol in distributed wireless networks, IEEE Transactions on Parallel and Distributed systems, vol.23, p.138, 2010.

C. Fraleigh, S. Moon, B. Lyles, C. Cotton, M. Khan et al., Packet-level traffic measurements from the Sprint IP backbone, IEEE network, vol.17, p.153, 2003.

F. Giroire, D. Mazauric, J. Moulierac, and B. Onfroy, Minimizing routing energy consumption: from theoretical to practical results, 2010 IEEE/ACM Int'l Conference on Green Computing and Communications & Int'l Conference on Cyber, p.138, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00531468

F. Giroire, J. Moulierac, F. Truong-khoa-phan, and . Roudaut, Minimization of network power consumption with redundancy elimination, Computer communications, vol.59, p.139, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00721855

F. Giroire, J. Moulierac, and K. Phan, Optimizing Rule Placement in Software-Defined Networks for Energy-aware Routing, IEEE Global Telecommunications Conference -GLOBE-COM, p.139, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01070576

M. Gupta and S. Singh, Greening of the Internet, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, p.138, 2003.

A. Gupta, M. F. Habib, P. Chowdhury, M. Tornatore, and B. Mukherjee, On service chaining using virtual network functions in network-enabled cloud systems, IEEE International Conference on Advanced Networks and Telecommuncations Systems (ANTS), p.138, 2015.

A. Gupta, B. Mukherjee, B. Jaumard, and M. Tornatore, Service Chain (SC) Mapping with Multiple SC Instances in a Wide Area Network, IEEE Global Telecommunications Conference -GLOBECOM, p.138, 2017.

N. Huin, . Tomassilli, B. Giroire, and . Jaumard, Energyefficient service function chain provisioning, IEEE/OSA Journal of Optical Communications and Networking, vol.10, pp.114-124, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01920960

N. Huin, M. Rifai, F. Giroire, D. L. Pacheco, G. Urvoy-keller et al., Bringing energy aware routing closer to reality with SDN hybrid networks, IEEE Transactions on Green Communications and Networking, vol.2, p.139, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01595989

S. Iyer, S. Bhattacharyya, N. Taft, and C. Diot, An approach to alleviate link overload as observed on an IP backbone, Annual Joint Conference of the IEEE Computer and Communications Societies -INFOCOM, vol.1, p.153, 2003.

E. Le-rouzic, E. Bonetto, L. Chiaraviglio, F. Giroire, F. Idzikowski et al., TREND towards more energy-efficient optical networks, 2013 17th International Conference on Optical Networking Design and Modeling (ONDM), p.136, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00880944

L. Chiaraviglio, M. Mellia, and F. Neri, Minimizing ISP Network Energy Cost: Formulation and Solutions, IEEE/ACM Transactions on Networking, vol.20, issue.2, p.138, 2011.

B. Martini, F. Paganelli, P. Cappanera, S. Turchi, and P. Castoldi, Latency-aware composition of virtual functions in 5g, p.138, 2015.

D. Matsubara, T. Egawa, N. Nishinaga, P. Ved, M. Kafle et al., Toward future networks: a viewpoint from ITU-T, IEEE Communications Magazine, vol.51, p.136, 2013.

R. Mijumbi, On the Energy Efficiency Prospects of Network Function Virtualization, p.139, 2015.

R. Modrzejewski, L. Chiaraviglio, I. Tahiri, F. Giroire, E. L. Rouzic et al., Energy efficient content distribution in an ISP network, 2013 IEEE Global Communications Conference (GLOBECOM), p.138, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00865378

A. Mohammadkhan, S. Ghapani, G. Liu, W. Zhang, T. Kk-ramakrishnan et al., Virtual function placement and traffic steering in flexible and dynamic software defined networks, Local and Metropolitan Area Networks (LANMAN), pp.1-6, 2015.

, Cisco visual networking index: Forecast and methodology, p.152, 2015.

L. Niccolini, G. Iannaccone, S. Ratnasamy, J. Chandrashekar, and L. Rizzo, Building a power-proportional software router, USENIX Annual Technical Conference (USENIX ATC)

M. A. Boston and . Usa, , p.142, 2012.

S. Orlowski, M. Pióro, A. Tomaszewski, and R. Wessäly, SNDlib 1.0-Survivable Network Design Library, Networks 55.3 (2010), p.152

. Truong-khoa-phan, Design and management of networks with low power consumption, p.138, 2014.

R. Riggio, A. Bradai, T. Rasheed, J. Schulz-zander, S. Kuklinski et al., Virtual network functions orchestration in wireless networks, Intl. Conf. on Network and Service Management (CNSM), vol.138, p.11, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01292221

Y. Shang, D. Li, and M. Xu, Energy-aware routing in data center network, Proceedings of the first ACM SIG-COMM workshop on Green networking, p.138, 2010.

M. Savi, M. Tornatore, and G. Verticale, Impact of Processing Costs on Service Chain Placement in Network Functions Virtualization, IEEE Conference on Network Function Virtualization and Software Defined Network (NFV-SDN), pp.191-197, 2015.

W. Vereecken, W. Van-heddeghem, M. Deruyck, B. Puype, B. Lannoo et al., Power consumption in telecommunication networks: overview and reduction strategies, IEEE Communications Magazine, vol.49, p.136, 2011.

A. Labs, White Paper: Global What if Analyzer of NeTwork Energy ConsumpTion (GWATT). Bell labs application able to measure the impact of technologies like SDN & NFV on network energy consumption, vol.166, p.12, 2015.

F. Ahmad, T. Srimat, A. Chakradhar, T. N. Raghunathan, and . Vijaykumar, ShuffleWatcher: Shuffle-aware Scheduling in Multi-tenant MapReduce Clusters, USENIX Annual Technical Conference, p.178, 2014.

T. Chen, X. Gao, and G. Chen, The features, hardware, and architectures of data center networks: A survey, Journal of Parallel and Distributed Computing, vol.96, p.178, 2016.

M. Chowdhury, M. Zaharia, J. Ma, I. Michael-i-jordan, and . Stoica, Managing data transfers in computer clusters with orchestra, ACM SIGCOMM Computer Communication Review, vol.41, 2011.

F. Chen, M. Kodialam, and . Lakshman, Joint scheduling of processing and shuffle phases in mapreduce systems, IEEE INFOCOM 2012, p.175

B. Chen, C. N. Potts, and G. J. Woeginger, A review of machine scheduling: Complexity, algorithms and approximability". In: Handbook of combinatorial optimization, p.175, 1999.

M. Chowdhury and I. Stoica, Coflow: A networking abstraction for cluster applications, ACM Workshop on Hot Topics in Networks, p.174, 2012.

M. Chowdhury, Y. Zhong, and I. Stoica, Efficient coflow scheduling with varys, ACM SIGCOMM Computer Communication Review, vol.44, pp.443-454

J. Dean and S. Ghemawat, MapReduce: simplified data processing on large clusters, Communications of the ACM, vol.51, p.172, 2008.

T. Fahad-r-dogar, H. Karagiannis, A. Ballani, and . Rowstron, Decentralized task-aware scheduling for data center networks, ACM SIGCOMM Computer Communication Review, vol.174, p.172, 2014.

G. Even, J. Naor, S. Rao, and B. Schieber, Fast approximate graph partitioning algorithms, SIAM Journal on Computing, vol.28, p.188, 1999.

F. Giroire, N. Huin, A. Tomassilli, and S. Pérennes, When Network Matters: Data Center Scheduling with Network Tasks, p.186, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01989755

F. Giroire, N. Huin, A. Tomassilli, and S. Pérennes, When network matters: Data center scheduling with network tasks, IEEE INFOCOM 2019 -IEEE Conference on Computer Communications, vol.171, p.13, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01989755

L. Ronald and . Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, vol.45, pp.1563-1581, 1966.

A. Greenberg, N. James-r-hamilton, S. Jain, C. Kandula, P. Kim et al., VL2: a scalable and flexible data center network, ACM SIGCOMM computer communication review, vol.39, p.172, 2009.

C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang et al., Dcell: a scalable and fault-tolerant network structure for data centers, ACM SIGCOMM Computer Communication Review, vol.38, p.172, 2008.

N. Garg, V. Vijay, M. Vazirani, and . Yannakakis, Approximate max-flow min-(multi) cut theorems and their applications, ACM symposium on Theory of computing, p.179, 1993.

M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly, Dryad: distributed data-parallel programs from sequential building blocks, ACM SIGOPS operating systems review, vol.41, p.172, 2007.

V. Jalaparti, P. Bodik, I. Menache, S. Rao, K. Makarychev et al., Network-aware scheduling for data-parallel jobs: Plan when you can, ACM SIGCOMM Computer Communication Review, vol.45, p.175, 2015.

W. Brian, S. Kernighan, and . Lin, An efficient heuristic procedure for partitioning graphs, The Bell system technical journal 49, p.190, 1970.

R. Krauthgamer, J. Naor, and R. Schwartz, Partitioning graphs into balanced components, p.188

Z. Liu and S. Cho, Characterizing machines and workloads on a Google cluster, IEEE Parallel Processing Workshops (ICPPW). 2012 (cit, p.191

G. Michael and S. David, Computers and intractability: a guide to the theory of NP-completeness, p.185, 1979.

A. Munier, M. Queyranne, and A. S. Schulz, Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems, Lecture Notes in Computer Science, p.175, 1998.

G. Derek, M. Murray, C. Schwarzkopf, S. Smowton, A. Smith et al., CIEL: a universal execution engine for distributed data-flow computing, Proc. 8th ACM/USENIX Symposium on Networked Systems Design and Implementation, p.172, 2011.

D. Namiot and M. Sneps-sneppe, On micro-services architecture, International Journal of Open Information Technologies, vol.2, issue.9, p.172, 2014.

H. Christos, M. Papadimitriou, and . Yannakakis, Towards an architecture-independent analysis of parallel algorithms, SIAM journal on computing, vol.19, p.175, 1990.

J. Victor and . Smith, UET scheduling with unit interprocessor communication delays, Discrete Applied Mathematics, vol.18, 1987.

K. Ren, Y. Kwon, M. Balazinska, and B. Howe, Hadoop's adolescence: an analysis of Hadoop usage in scientific workloads, Proceedings of the VLDB Endowment, vol.6, pp.853-864, 2013.

C. Reiss, J. Wilkes, and J. L. Hellerstein, Google cluster-usage traces: format+ schema, pp.1-14, 0198.

D. Horst, S. Simon, and . Teng, How good is recursive bisection?, In: SIAM Journal on Scientific Computing, vol.18, pp.1436-1445, 1997.

K. Thomas, C. Grier, J. Ma, V. Paxson, and D. Song, Design and evaluation of a real-time url spam filtering service, IEEE Symposium on Security and Privacy (SP), pp.447-462, 2011.

M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma et al., Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing, USENIX conference on Networked Systems Design and Implementation, p.172, 2012.

A. Bocoi, M. Schuster, F. Rambach, M. Kiese, C. Bunge et al., Reach-dependent capacity in optical networks enabled by OFDM, Proc. Optical Fiber Communication (OFC), p.208, 2009.

K. Christodoulopoulos, I. Tomkos, and E. A. Varvarigos, Elastic bandwidth allocation in flexible OFDMbased optical networks, Journal of Lightwave Technology, vol.29, p.208, 2011.

F. Giroire, A. Nucci, N. Taft, and C. Diot, Increasing the robustness of IP backbones in the absence of optical level protection, Annual Joint Conference of the IEEE Computer and Communications Societies -INFOCOM, vol.1, p.217, 2003.

R. Michael and D. Garey, Computers and intractability, vol.29, p.31, 2002.

G. Iannaccone, C. Chuah, R. Mortier, S. Bhattacharyya, and C. Diot, Analysis of link failures in an IP backbone, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, p.204, 2002.

S. Irnich and G. Desaulniers, Shortest path problems with resource constraints, Column generation, pp.33-65, 2005.

M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone et al., Spectrumefficient and scalable elastic optical path network: architecture, benefits, and enabling technologies, IEEE Communications Magazine, vol.47, 2009.

M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone et al., Distance-adaptive spectrum resource allocation in spectrumsliced elastic optical path network, IEEE Communications Magazine, vol.48, p.204, 2010.

M. Law and K. , A genetic algorithm for solving RSA problem in elastic optical networks with dedicated path protection, International Joint Conference CISIS'12-ICEUTE1 2-SOCO´12 Special Sessions, p.206, 2013.

M. Law and K. , An evolutionary algorithm approach for dedicated path protection problem in elastic optical networks, Cybernetics and Systems, vol.44, p.206, 2013.

A. Kretsis, K. Christodoulopoulos, P. Kokkinos, and E. Varvarigos, Planning and operating flexible optical networks: Algorithmic issues and tools, IEEE Communications Magazine, vol.52, p.208, 2014.

M. Klinkowski and K. Walkowiak, Routing and spectrum assignment in spectrum sliced elastic optical path network, IEEE Communications Letters, vol.15, p.204, 2011.

M. Law-klinkowski and K. Walkowiak, Offline RSA algorithms for elastic optical networks with dedicated path protection consideration, Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), p.206, 2012.

B. Mukherjee, Optical WDM networks. Springer Science & Business Media, p.213, 2006.

S. Orlowski, R. Wessäly, M. Pióro, and A. Tomaszewski, SNDlib 1.0-Survivable network design library, 2010.

L. S-ramamurthy, B. Sahasrabuddhe, and . Mukherjee, Survivable WDM mesh networks, Journal of Lightwave Technology, vol.21, pp.204-206, 2003.

M. Ruiz, . Micha-l-pióro, M. Mateusz?otkiewicz, L. Law-klinkowski, and . Velasco, Column generation algorithm for RSA problems in flexgrid optical networks, Photonic network communications, vol.26, p.207, 2013.

L. Sahasrabuddhe, S. Ramamurthy, and B. Mukherjee, Fault management in IP-over-WDM networks: WDM protection versus IP restoration, IEEE journal on selected areas in communications, vol.20, pp.21-33, 2002.

G. Shen, Y. Wei, K. Sanjay, and . Bose, Optimal design for shared backup path protected elastic optical networks under single-link failure, Journal of Optical Communications and Networking, vol.6, p.206, 2014.

A. Tomassilli, F. Jaumard, and . Giroire, Path Protection in Optical Flexible Networks with Distance-adaptive Modulation Formats, 2018 International Conference on Optical Network Design and Modeling (ONDM), 2018.
URL : https://hal.archives-ouvertes.fr/hal-01921082

D. Turner, K. Levchenko, A. C. Snoeren, and S. Savage, California fault lines: understanding the causes and impact of network failures, ACM SIGCOMM Computer Communication Review, vol.40, pp.315-326, 2010.

K. Walkowiak and M. Law-klinkowski, Shared backup path protection in elastic optical networks: Modeling and optimization, Design of Reliable Communication Networks (DRCN), 2013 9th International Conference on the. IEEE. 2013, vol.216, p.206

Z. Zhu, W. Lu, L. Zhang, and N. Ansari, Dynamic service provisioning in elastic optical networks with hybrid single-/multi-path routing, Journal of Lightwave Technology, vol.31, p.214, 2013.

D. Zhou and S. Subramaniam, Survivability in optical networks, IEEE network, vol.14, pp.16-23, 2000.

, SMART 2020 Enabling the low-carbon economy in the information age, vol.166, p.12, 2008.

M. Alanyali and E. Ayanoglu, Provisioning algorithms for WDM optical networks, IEEE/ACM Transactions On Networking, vol.7, issue.5, p.109, 1999.

B. Sherif-abdelwahab, M. Hamdaoui, T. Guizani, and . Znati, Network function virtualization in 5G, IEEE Communications Magazine, vol.54, pp.84-91, 2016.

T. Achterberg, SCIP-a framework to integrate constraint and mixed integer programming, p.29, 2004.

B. Addis, D. Belabed, M. Bouet, and S. Secci, Virtual network functions placement and routing optimization, IEEE 4th International Conference on. IEEE. 2015 (cit. on pp. 10, vol.46, p.11, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01170042

J. Hatem-ben-amor, A. Desrosiers, and . Frangioni, Stabilization in column generation. Groupe d'études et de recherche en analyse des décisions, p.30, 2004.

G. Ausiello, A. D. Atri, and M. Protasi, Structure preserving reductions among convex optimization problems, Journal of Computer and System Sciences, vol.21, issue.1, p.48, 1980.

F. Ahmad, T. Srimat, A. Chakradhar, T. N. Raghunathan, and . Vijaykumar, ShuffleWatcher: Shuffle-aware Scheduling in Multi-tenant MapReduce Clusters, USENIX Annual Technical Conference, p.178, 2014.

A. Ian-f-akyildiz, P. Lee, M. Wang, W. Luo, and . Chou, A roadmap for traffic engineering in SDN-OpenFlow networks, Computer Networks, vol.71, pp.1-30, 2014.

M. Al-fares, A. Loukissas, and A. Vahdat, A scalable, commodity data center network architecture, ACM SIGCOMM Computer Communication Review, vol.38

N. Alon, D. Moshkovitz, and S. Safra, Algorithmic Construction of Sets for K-restrictions, ACM Trans. Algorithms, vol.2, issue.2, p.48, 2006.

Y. K. Agarwal and P. Venkateshan, Survivable network design with shared-protection routing, European Journal of Operational Research, vol.238, p.110, 2014.

C. Barnhart, L. Ellis, G. L. Johnson, . Nemhauser, W. P. Martin et al., Branch-and-price: Column generation for solving huge integer programs, Operations research, vol.46, p.30, 1998.

M. Beck, J. F. Botero, and K. Samelin, Resilient allocation of service Function chains, Network Function Virtualization and Software Defined Networks (NFV-SDN), IEEE Conference on, p.110, 2016.

F. Jacques and . Benders, Partitioning procedures for solving mixedvariables programming problems, Numerische mathematik, vol.4, pp.238-252, 1962.

P. Berde, M. Gerola, J. Hart, Y. Higuchi, M. Kobayashi et al., ONOS: towards an open, distributed SDN OS, Proceedings of the third workshop on Hot topics in software defined networking, pp.1-6, 2014.

D. Bhamare and R. Jain, A survey on service function chaining, Journal of Network and Computer Applications, vol.75, pp.138-155, 2016.

E. Robert and . Bixby, A brief history of linear and mixed-integer programming computation, Documenta Mathematica, p.28, 2012.

A. Bocoi, M. Schuster, F. Rambach, M. Kiese, C. Bunge et al., Reach-dependent capacity in optical networks enabled by OFDM, Proc. Optical Fiber Communication (OFC), p.208, 2009.

R. Bolla, C. Lombardo, R. Bruschi, and S. Mangialardi, DROPv2: energy efficiency through network function virtualization, IEEE Network, vol.28, p.139, 2014.

B. Bollobás, Random graphs, Modern Graph Theory

M. Bouet, J. Leguay, T. Combe, and V. C. , Cost-based placement of vDPI functions in NFV infrastructures, International Journal of Network Management, vol.25, p.45, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01307010

M. Casado, T. Koponen, R. Ramanathan, and S. Shenker, Virtualizing the network forwarding plane, Proceedings of the Workshop on Programmable Routers for Extensible Services of Tomorrow, p.44, 2010.

V. Chvatal and V. Chvatal, Linear programming. Macmillan, 1983 (cit, p.30

Z. Cai, A. L. Cox, and T. S. Ng, Maestro: A system for scalable openflow control, vol.4, 2010.

T. Chen, X. Gao, and G. Chen, The features, hardware, and architectures of data center networks: A survey, Journal of Parallel and Distributed Computing, vol.96, p.178, 2016.

C. Chaudet, E. Fleury, I. G. Lassous, H. Rivano, and M. Voge, Optimal positioning of active and passive monitoring devices, Proceedings of the 2005 ACM conference on Emerging network experiment and technology, p.44, 2005.
URL : https://hal.archives-ouvertes.fr/inria-00070725

M. Chowdhury, M. Zaharia, J. Ma, I. Michael-i-jordan, and . Stoica, Managing data transfers in computer clusters with orchestra, ACM SIGCOMM Computer Communication Review, vol.41, 2011.

C. Chu, K. Xi, M. Luo, and H. Chao, Congestion-aware single link failure recovery in hybrid SDN networks, Proceedings of IEEE INFOCOM, p.82, 2015.

V. , A greedy heuristic for the set-covering problem, Mathematics of operations research, vol.4, p.48, 1979.

V. , Linear Programming. Freeman, 1983 (cit, vol.148, p.88

. Cisco, Bidirectional Forwarding Detection, p.105

P. Crescenzi, M. Viggo-kann, and . Halldórsson, A compendium of NP optimization problems, p.31, 1995.

F. Chen, M. Kodialam, and . Lakshman, Joint scheduling of processing and shuffle phases in mapreduce systems, IEEE INFOCOM 2012, p.175

L. Chiaraviglio, M. Mellia, and F. Neri, Minimizing ISP network energy cost: formulation and solutions, IEEE/ACM Transactions on Networking (TON), p.138, 2012.

R. Cohen, L. Lewin-eytan, J. S. Naor, and D. Raz, Near optimal placement of virtual network functions, Computer Communications (INFOCOM), vol.46, p.11, 2015.

Z. Chen and W. Powell, Solving parallel machine scheduling problems by column generation, INFORMS Journal on Computing, vol.11, issue.1, p.29, 1999.

. Ibm and . Cplex, V12. 1: User's Manual for CPLEX, International Business Machines Corporation, vol.46, p.29, 2009.

B. Chen, C. N. Potts, and G. J. Woeginger, A review of machine scheduling: Complexity, algorithms and approximability". In: Handbook of combinatorial optimization, p.175, 1999.

M. Chowdhury and I. Stoica, Coflow: A networking abstraction for cluster applications, ACM Workshop on Hot Topics in Networks, p.174, 2012.

K. Christodoulopoulos, I. Tomkos, and E. A. Varvarigos, Elastic bandwidth allocation in flexible OFDMbased optical networks, Journal of Lightwave Technology, vol.29, p.208, 2011.

Y. Chen, J. Wu, and B. Ji, Virtual Network Function Deployment in Tree-structured Networks, 2018 IEEE 26th International Conference on Network Protocols (ICNP), p.11, 2018.

M. Chowdhury, Y. Zhong, and I. Stoica, Efficient coflow scheduling with varys, ACM SIGCOMM Computer Communication Review, vol.44, pp.443-454

B. George and . Dantzig, Programming in a linear structure, p.28, 1948.

G. Desaulniers, J. Desrosiers, and M. M. Solomon, Column generation, vol.5, p.30, 2006.

M. Desrochers, J. Desrosiers, and M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Operations research, vol.40, p.29, 1992.

J. Dean and S. Ghemawat, MapReduce: simplified data processing on large clusters, Communications of the ACM, vol.51, p.172, 2008.

J. Desrosiers and . Marco-e-lübbecke, A primer in column generation, Column generation, p.30, 2005.

T. Fahad-r-dogar, H. Karagiannis, A. Ballani, and . Rowstron, Decentralized task-aware scheduling for data center networks, ACM SIGCOMM Computer Communication Review, vol.174, p.172, 2014.

I. Dinur and D. Steurer, Analytical Approach to Parallel Repetition, Proceedings ACM STOC 2014, vol.85, p.44

I. Dinur and S. Safra, On the hardness of approximating minimum vertex cover, Annals of mathematics, p.62, 2005.

D. Erickson, The beacon openflow controller, Proceedings of the second ACM SIGCOMM workshop on Hot topics in software defined networking, pp.13-18, 2013.

G. Even, J. Naor, S. Rao, and B. Schieber, Fast approximate graph partitioning algorithms, SIAM Journal on Computing, vol.28, p.188, 1999.

H. Feng, J. Llorca, A. M. Tulino, D. Raz, and A. F. Molisch, Approximation algorithms for the NFV service distribution problem, IEEE INFOCOM 2017-IEEE Conference on Computer Communications, p.11, 2017.

P. Fonseca and E. Mota, A survey on fault management in software-defined networks, IEEE Communications Surveys & Tutorials, p.82, 2017.

, Open Networking Foundation

C. Fraleigh, S. Moon, B. Lyles, C. Cotton, M. Khan et al., Packet-level traffic measurements from the Sprint IP backbone, IEEE network, vol.17, p.153, 2003.

N. Feamster, J. Rexford, and E. Zegura, The road to SDN: an intellectual history of programmable networks, ACM SIGCOMM Computer Communication Review, vol.44, issue.2, pp.87-98, 2014.

B. Fortz and M. Thorup, Optimizing OSPF/IS-IS weights in a changing world, IEEE journal on selected areas in communications, vol.20, p.96, 2002.
URL : https://hal.archives-ouvertes.fr/hal-01255600

A. Fumagalli and L. Valcarenghi, IP restoration vs. WDM protection: Is there an optimal choice?, In: IEEE network, vol.14, p.82, 2000.

F. Giroire, N. Huin, A. Tomassilli, and S. Pérennes, When Network Matters: Data Center Scheduling with Network Tasks, p.186, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01989755

R. Michael and D. Garey, Computers and intractability, vol.29, p.31, 2002.

P. Gill, N. Jain, and N. Nagappan, Understanding network failures in data centers: measurement, analysis, and implications, ACM SIGCOMM Computer Communication Review, vol.41, p.107, 2011.

E. Ralph and . Gomory, Outline of an algorithm for integer solutions to linear programs, Bulletin of the American Mathematical society, vol.64, p.29, 1958.

L. Ronald and . Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, vol.45, pp.1563-1581, 1966.

A. Greenberg, N. James-r-hamilton, S. Jain, C. Kandula, P. Kim et al., VL2: a scalable and flexible data center network, ACM SIGCOMM computer communication review, vol.39, p.172, 2009.

M. Gupta and S. Singh, Greening of the Internet, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, p.138, 2003.

C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang et al., Dcell: a scalable and fault-tolerant network structure for data centers, ACM SIGCOMM Computer Communication Review, vol.38, p.172, 2008.

A. Gupta, B. Mukherjee, B. Jaumard, and M. Tornatore, Service Chain (SC) Mapping with Multiple SC Instances in a Wide Area Network, IEEE Global Telecommunications Conference -GLOBECOM, p.138, 2017.

N. Garg, V. Vijay, M. Vazirani, and . Yannakakis, Approximate max-flow min-(multi) cut theorems and their applications, ACM symposium on Theory of computing, p.179, 1993.

B. Han, V. Gopalakrishnan, L. Ji, and S. Lee, Network function virtualization: Challenges and opportunities for innovations, IEEE Communications Magazine, vol.53, pp.90-97, 2015.

J. Hrastad, Some optimal inapproximability results, Journal of the ACM (JACM), vol.48, p.92, 2001.

G. Juliver, J. F. Herrera, and . Botero, Resource allocation in NFV: A comprehensive survey, IEEE Transactions on Network and Service Management, vol.13, pp.518-532, 2016.

E. Hernandez, -. Valencia, S. Izzo, and B. Polonsky, How will NFV/SDN transform service provider opex, IEEE Network, vol.29, p.10, 2015.

N. Huin, B. Jaumard, and F. Giroire, Optimization of network service chain provisioning, 2017 IEEE International Conference on Communications (ICC). IEEE. 2017, p.29
URL : https://hal.archives-ouvertes.fr/hal-01476018

N. Huin, B. Jaumard, and F. Giroire, Optimal Network Service Chain Provisioning, IEEE/ACM Transactions on Networking, vol.26, issue.3, p.45, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01920951

N. Huin, B. Jaumard, and F. Giroire, Optimal Network Service Chain Provisioning, IEEE/ACM Transactions on Networking, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01920951

A. Hmaity, M. Savi, F. Musumeci, M. Tornatore, and A. Pattavina, Protection strategies for virtual network functions placement and service chains provisioning, pp.1-15, 2017.

K. Hoffman and M. Padberg, LP-based combinatorial problem solving, Annals of Operations Research, vol.4, p.30, 1985.

J. Hu, Diverse routing in optical mesh networks, IEEE Transactions on Communications, vol.51, p.80, 2003.

. Huawei, Huawei Releases SDN/NFV Commercial and Technological Innovations, 2017.

G. Iannaccone, C. Chuah, R. Mortier, S. Bhattacharyya, and C. Diot, Analysis of link failures in an IP backbone, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, p.204, 2002.

S. Irnich and G. Desaulniers, Shortest path problems with resource constraints, Column generation, pp.33-65, 2005.

R. R. Iraschko, M. H. Macgregor, and W. D. Grover, Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks, IEEE/ACM Transactions on Networking, vol.6, p.108, 1998.

M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly, Dryad: distributed data-parallel programs from sequential building blocks, ACM SIGOPS operating systems review, vol.41, p.172, 2007.

S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski et al., B4: Experience with a globallydeployed software defined WAN, ACM SIGCOMM Computer Communication Review, vol.43

V. Jalaparti, P. Bodik, I. Menache, S. Rao, K. Makarychev et al., Network-aware scheduling for data-parallel jobs: Plan when you can, ACM SIGCOMM Computer Communication Review, vol.45, p.175, 2015.

M. Jünger, M. Thomas, D. Liebling, . Naddef, L. George et al., 50 Years of integer programming 1958-2008: From the early years to the state-of-the-art, p.29, 2009.

A. Kvalbein, T. Cicic, and S. Gjessing, Post-failure routing performance with multiple routing configurations, Proceedings of IEEE INFOCOM, vol.83, p.82, 2007.

J. Kempf, E. Bellagamba, A. Kern, and D. Jocha, Scalable fault management for OpenFlow, Communications (ICC), 2012 IEEE international conference on, p.80, 2012.

H. Kim and N. Feamster, Improving network management with software defined networking, IEEE Communications Magazine, vol.51, p.1, 2013.

. Leonid-g-khachiyan, A polynomial algorithm in linear programming, Doklady Academii Nauk SSSR, vol.244, p.28, 1979.

S. Kandula, D. Katabi, and J. Vasseur, Shrink: A tool for failure diagnosis in IP networks, Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, pp.173-178, 2005.

W. Brian, S. Kernighan, and . Lin, An efficient heuristic procedure for partitioning graphs, The Bell system technical journal 49, p.190, 1970.

M. Law and K. , An evolutionary algorithm approach for dedicated path protection problem in elastic optical networks, Cybernetics and Systems, vol.44, p.206, 2013.

V. Klee, J. George, and . Minty, How good is the simplex algorithm, Tech. rep. WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS, p.28, 1970.

S. Knight, X. Hung, N. Nguyen, R. Falkner, M. Bowden et al., The internet topology zoo, IEEE Journal on Selected Areas in Communications, vol.29, pp.1765-1775, 2011.

R. Krauthgamer, J. Naor, and R. Schwartz, Partitioning graphs into balanced components, p.188

T. Koponen, M. Casado, N. Gude, J. Stribling, L. Poutievski et al., Onix: A distributed control platform for large-scale production networks, In: OSDI, vol.10, pp.1-6, 2010.

A. Kretsis, K. Christodoulopoulos, P. Kokkinos, and E. Varvarigos, Planning and operating flexible optical networks: Algorithmic issues and tools, IEEE Communications Magazine, vol.52, p.208, 2014.

D. Kreutz, M. V. Fernando, P. Ramos, and . Verissimo, Christian Esteve Rothenberg, Siamak Azodolmolky, and Steve Uhlig, Proceedings of the IEEE 103, vol.1, pp.14-76, 2015.

S. Kumar, . Tufail, C. Majee, S. Captari, and . Homma, Service function chaining use cases in data centers, IETF SFC WG, p.10, 2015.

T. Kuo, B. Liou, K. Lin, and M. Tsai, Deploying chains of virtual network functions: On the relation between link and server usage, Computer Communications (INFOCOM), 2016 IEEE Conference, p.46, 2016.

A. Kvalbein, S. Audun-fosselie-hansen, O. Gjessing, and . Lysne, Fast IP network recovery using multiple routing configurations, Proceedings of IEEE INFOCOM, p.83, 2006.

M. Klinkowski and K. Walkowiak, Routing and spectrum assignment in spectrum sliced elastic optical path network, IEEE Communications Letters, vol.15, p.204, 2011.

Z. Liu and S. Cho, Characterizing machines and workloads on a Google cluster, IEEE Parallel Processing Workshops (ICPPW). 2012 (cit, p.191

Y. Li and M. Chen, Software-defined network function virtualization: A survey, IEEE Access, vol.3, p.9, 2015.

H. Ailsa, A. G. Land, and . Doig, An automatic method for solving discrete programming problems, 50 Years of Integer Programming, pp.105-132, 1958.

B. Lantz, B. Heller, and N. Mckeown, Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks. Hotnets-IX. Monterey, vol.19, p.101, 2010.

A. Lara, A. Kolasani, and B. Ramamurthy, Network innovation using openflow: A survey, IEEE communications surveys & tutorials, vol.16, pp.493-512, 2014.

S. Lee and M. Shin, A self-recovery scheme for service function chaining, International Conference on Information and Communication Technology Convergence (ICTC), p.110, 2015.

L. Chiaraviglio, M. Mellia, and F. Neri, Minimizing ISP Network Energy Cost: Formulation and Solutions, IEEE/ACM Transactions on Networking, vol.20, issue.2, p.138, 2011.

R. Lougee-heimer, The Common Optimization INterface for Operations Research: Promoting open-source software in the operations research community, IBM Journal of Research and Development, vol.47, p.29, 2003.

M. C. Luizelli, L. R. Bays, L. S. Buriol, M. P. Barcellos, and L. P. Gaspary, Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions, IFIP/IEEE International Symposium on Integrated Network Management, vol.46, p.10, 2015.

L. Eugene, D. E. Lawler, and . Wood, Branch-and-bound methods: A survey, Operations research, vol.14, p.29, 1966.

Y. David-g-luenberger and . Ye, Linear and nonlinear programming, vol.2, p.28, 1984.

W. Ma, O. Sandoval, J. Beltran, D. Pan, and N. Pissinou, Traffic aware placement of interdependent nfv middleboxes, IEEE INFOCOM 2017-IEEE Conference on Computer Communications, p.11, 2017.

A. Makhorin, The GNU Linear Programming Kit (GLPK)

B. Martini, F. Paganelli, P. Cappanera, S. Turchi, and P. Castoldi, Latency-aware composition of virtual functions in 5g, p.138, 2015.

S. Marek, Update: AT&T's Stephens: More Than 40% of Network Functions Are Virtualized, 2017.

D. Matsubara, T. Egawa, N. Nishinaga, P. Ved, M. Kafle et al., Toward future networks: a viewpoint from ITU-T, IEEE Communications Magazine, vol.51, p.136, 2013.

N. Mckeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson et al., OpenFlow: enabling innovation in campus networks, ACM SIGCOMM Computer Communication Review, vol.38, pp.69-74, 2008.

H. Moens and F. D. Turck, VNF-P: A model for efficient placement of virtualized network functions, 10th International Conference on Network and Service Management (CNSM) and Workshop, p.10, 2014.

G. Michael and S. David, Computers and intractability: a guide to the theory of NP-completeness, p.185, 1979.

J. Medved, R. Varga, A. Tkacik, and K. Gray, OpenDaylight: Towards a Model-Driven SDN Controller architecture, Proceedings of IEEE WoWMoM, p.103, 2014.

J. Medved, R. Varga, A. Tkacik, and K. Gray, Opendaylight: Towards a model-driven sdn controller architecture, Proceeding of IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, pp.1-6, 2014.

T. Ahmed-m-medhat, A. Taleb, G. A. Elmangoush, S. Carella, T. Covaci et al., Service function chaining in next generation networks: State of the art and research challenges, IEEE Communications Magazine, vol.55, pp.216-223, 2017.

K. Menger, Zur allgemeinen kurventheorie, Fundamenta Mathematicae, vol.10, p.51, 1927.

R. Mijumbi, J. Serrat, J. Gorricho, N. Bouten, F. D. Turck et al., Network function virtualization: State-of-the-art and research challenges, IEEE Communications Surveys & Tutorials, vol.18, pp.236-262, 2016.

R. Mijumbi, On the Energy Efficiency Prospects of Network Function Virtualization, p.139, 2015.

S. Mehraghdam, M. Keller, and H. Karl, Specifying and placing chains of virtual network functions, Cloud Networking (CloudNet), vol.46, pp.7-13, 2014.

A. Munier, M. Queyranne, and A. S. Schulz, Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems, Lecture Notes in Computer Science, p.175, 1998.

A. Mehrotra, A. Michael, and . Trick, A column generation approach for graph coloring, In: informs Journal on Computing, vol.8, p.29, 1996.

B. Mukherjee, Optical WDM networks. Springer Science & Business Media, p.213, 2006.

, Cisco visual networking index: Forecast and methodology, p.152, 2015.

A. Van-giang-nguyen, K. Brunstrom, J. Grinnemo, and . Taheri, SDN/NFV-based mobile packet core network architectures: A survey, IEEE Communications Surveys & Tutorials, vol.19, pp.1567-1602, 2017.

L. Niccolini, G. Iannaccone, S. Ratnasamy, J. Chandrashekar, and L. Rizzo, Building a power-proportional software router, USENIX Annual Technical Conference (USENIX ATC)

M. A. Boston and . Usa, , p.142, 2012.

D. B-niven-jenkins, M. Brungard, N. Betts, S. Sprecher, and . Ueno, Requirements of an MPLS transport profile, p.80, 2009.

D. Namiot and M. Sneps-sneppe, On micro-services architecture, International Journal of Open Information Technologies, vol.2, issue.9, p.172, 2014.

B. Astuto, A. Nunes, M. Mendonca, X. Nguyen, K. Obraczka et al., A survey of softwaredefined networking: Past, present, and future of programmable networks, IEEE Communications Surveys & Tutorials, vol.16, issue.2, pp.1617-1634, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00825087

M. Obadia, J. Rougier, L. Iannone, V. Conan, and M. Brouet, Revisiting NFV orchestration with routing games, Network Function Virtualization and Software Defined Networks (NFV-SDN), IEEE Conference, pp.107-113, 2016.
URL : https://hal.archives-ouvertes.fr/hal-02287787

G. Optimization, INC. Gurobi optimizer reference manual, p.29, 2014.

S. Orlowski, M. Pióro, A. Tomaszewski, and R. Wessäly, SNDlib 1.0-Survivable Network Design Library, Networks 55.3 (2010), p.152

S. Orlowski, R. Wessäly, M. Pióro, and A. Tomaszewski, SNDlib 1.0-Survivable network design library, 2010.

K. Phemius, M. Bouet, and J. Leguay, IEEE Network Operations and Management Symposium (NOMS), p.4, 2014.

A. Pessoa, R. Sadykov, E. Uchoa, and F. Vanderbeck, Automation and combination of linear-programming based stabilization techniques in column generation, IN-FORMS Journal on Computing, vol.89, p.30, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01077984

B. Pfaff, J. Pettit, K. Amidon, M. Casado, T. Koponen et al., Extending networking into the virtualization layer, Hotnets. 2009 (cit

. Truong-khoa-phan, Design and management of networks with low power consumption, p.138, 2014.

R. Potharaju and N. Jain, Demystifying the dark side of the middle: a field study of middlebox failures in datacenters, Internet Measurement Conference, p.107, 2013.

M. Pióro and D. Medhi, Routing, flow, and capacity design in communication and computer networks, vol.80, p.12, 2004.

K. Poularakis, J. Llorca, A. M. Tulino, I. Taylor, and L. Tassiulas, Joint Service Placement and Request Routing in Multi-cell Mobile Edge Computing Networks, IEEE INFOCOM 2019-IEEE Conference on Computer Communications, p.11, 2019.

M. Paliwal, D. Shrimankar, and O. Tembhurne, Controllers in SDN: A review report, vol.6, pp.36256-36270, 2018.

H. Christos, M. Papadimitriou, and . Yannakakis, Towards an architecture-independent analysis of parallel algorithms, SIAM journal on computing, vol.19, p.175, 1990.

C. Zafar-ayyub-qazi, L. Tu, R. Chiang, V. Miao, M. Sekar et al., SIMPLE-fying middlebox policy enforcement using SDN, ACM SIGCOMM computer communication review, vol.43, pp.27-38, 2013.

P. Quinn and T. Nadeau, Problem statement for service function chaining, p.9, 2015.

J. Victor and . Smith, UET scheduling with unit interprocessor communication delays, Discrete Applied Mathematics, vol.18, 1987.

K. Ren, Y. Kwon, M. Balazinska, and B. Howe, Hadoop's adolescence: an analysis of Hadoop usage in scientific workloads, Proceedings of the VLDB Endowment, vol.6, pp.853-864, 2013.

S. Ramamurthy and B. Mukherjee, Survivable WDM mesh networks. Part I -protection, Annual Joint Conference of the IEEE Computer and Communications Societies -INFO-COM, vol.2, pp.744-751, 1999.

S. Rai, B. Mukherjee, and O. Deshpande, IP resilience within an autonomous system: current approaches, challenges, and future directions, IEEE Communications Magazine, vol.43, p.82, 2005.

L. S-ramamurthy, B. Sahasrabuddhe, and . Mukherjee, Survivable WDM mesh networks, Journal of Lightwave Technology, vol.21, pp.204-206, 2003.

C. Reiss, J. Wilkes, and J. L. Hellerstein, Google cluster-usage traces: format+ schema, pp.1-14, 0198.

Y. Sang, B. Ji, R. Gagan, X. Gupta, L. Du et al., Provably Efficient Algorithms for Joint Placement and Allocation of Virtual Network Functions, Computer Communications (INFOCOM), 2017 IEEE Conference, vol.46, p.11

A. Sgambelluri, A. Giorgetti, F. Cugini, F. Paolucci, and P. Castoldi, OpenFlow-based segment protection in Ethernet networks, Journal of Optical Communications and Networking, vol.5, p.82, 2013.

S. Sharma, D. Staessens, and D. Colle, Enabling fast failure recovery in OpenFlow networks, 2011.

. Ieee, , p.108, 2011.

S. Sharma, D. Staessens, D. Colle, M. Pickavet, and P. Demeester, OpenFlow: Meeting carrier-grade recovery requirements, Computer Communications, vol.36, issue.6, p.80, 2013.

J. Sherry, S. Hasan, C. Scott, A. Krishnamurthy, S. Ratnasamy et al., Making middleboxes someone else's problem: network processing as a cloud service, ACM SIGCOMM Computer Communication Review, vol.42, pp.13-24, 2012.

G. Sallam and B. Ji, Joint Placement and Allocation of Virtual Network Functions with Budget and Capacity Constraints, IEEE INFOCOM 2019-IEEE Conference on Computer Communications, p.11, 2019.

Y. Shang, D. Li, and M. Xu, Energy-aware routing in data center network, Proceedings of the first ACM SIG-COMM workshop on Green networking, p.138, 2010.

K. Sohrabi, J. Gao, V. Ailawadhi, and G. J. Pottie, Protocols for self-organization of a wireless sensor network, IEEE personal communications, vol.7, issue.5, p.61, 2000.

O. Soualah, M. Mechtri, C. Ghribi, and D. Zeghlache, A link failure recovery algorithm for Virtual Network Function chaining, IFIP/IEEE Symposium on Integrated Network and Service Management (IM). 2017 (cit, p.110
URL : https://hal.archives-ouvertes.fr/hal-01629687

J. Sherry, S. Ratnasamy, and J. S. At, A survey of enterprise middlebox deployments, 2012.

M. Savelsbergh and M. Sol, Drive: Dynamic routing of independent vehicles, Operations Research, vol.46, p.29, 1998.

D. Horst, S. Simon, and . Teng, How good is recursive bisection?, In: SIAM Journal on Scientific Computing, vol.18, pp.1436-1445, 1997.

D. Staessens, S. Sharma, D. Colle, M. Pickavet, and P. Demeester, Software defined networking: Meeting carrier grade requirements, 18th IEEE Workshop on Local and Metropolitan Area Networks (LANMAN), p.108, 2011.

T. Stidsen, B. Petersen, S. Kasper-bonne-rasmussen, M. Spoorendonk, F. Zachariasen et al., Optimal routing with single backup path protection, International Network Optimization Conference (INOC), p.117, 2007.

M. Savi, M. Tornatore, and G. Verticale, Impact of processing costs on service chain placement in network functions virtualization, IEEE NFV-SDN 2015 (cit. on pp. 9, vol.119, p.49

M. Suchara, D. Xu, R. Doverspike, D. Johnson, and J. Rexford, Network architecture for joint failure recovery and traffic engineering, Proceedings of ACM SIGMETRICS 2011, p.82

, Ryu Network Operating System, vol.4, 2012.

K. Thomas, C. Grier, J. Ma, V. Paxson, and D. Song, Design and evaluation of a real-time url spam filtering service, IEEE Symposium on Security and Privacy (SP), pp.447-462, 2011.

J. Michael and . Todd, The many facets of linear programming, Mathematical Programming, vol.91, p.28, 2002.

A. Tomassilli, . Huin, B. Giroire, and . Jaumard, Energyefficient service chains with network function virtualization, p.12, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01403936

A. Tomassilli, . Giroire, S. Huin, and . Pérennes, Algorithmes d'approximation pour le placement de chaines de fonctions de services avec des contraintes d'ordre, ALGOTEL 2018-20émes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, vol.43, p.11, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01774540

A. Tomassilli, F. Giroire, N. Huin, and S. Pérennes, Provably Efficient Algorithms for Placement of Service Function Chains with Ordering Constraints, IEEE INFOCOM 2018 -IEEE Conference on Computer Communications, vol.43, p.11, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01921112

A. Tomassilli, N. Huin, F. Giroire, and B. Jaumard, Resource requirements for reliable service function chaining, 2018 IEEE International Conference on Communications (ICC), vol.107, p.11, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01921096

A. Tomassilli, G. D. Lena, F. Giroire, I. Tahiri, D. Saucez et al., Poster: Design of Survivable SDN/NFV-enabled Networks with Bandwidth-optimal Failure Recovery, Annex to the IFIP Networking, p.12, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02364488

H. Pamela, C. Vance, . Barnhart, L. Ellis, G. L. Johnson et al., Solving binary cutting stock problems by column generation and branch-and-bound, Computational optimization and applications, vol.3, p.29, 1994.

V. Vijay and . Vazirani, Approximation algorithms, vol.59, p.32, 2013.

B. J. Niels-lm-van-adrichem, F. A. Van-asten, and . Kuipers, Fast recovery in software-defined networks, Software Defined Networks (EWSDN), p.80, 2014.

. Bernard-m-waxman, Routing of multipoint connections, IEEE journal on selected areas in communications, vol.6, p.96, 1988.

A. Laurence and . Wolsey, Integer programming, p.29, 1998.

. Marcel-van-wort, SDN and NFV transforming the network: where do we go from here?, 2017.

, networks / sdn -and -nfv -transforming -the -networkwhere-do-we-go-from-here (cit

D. Xu, Y. Xiong, C. Qiao, and G. Li, Failure protection in layered networks with shared risk link groups, IEEE network, p.82, 2004.

Z. Ye, X. Cao, J. Wang, H. Yu, and C. Qiao, Joint topology design and mapping of service function chains for efficient, scalable, and reliable network functions virtualization, IEEE Network, vol.30, p.110, 2016.

Y. Ye, An O (n 3 L) potential reduction algorithm for linear programming, Mathematical programming, vol.50, p.28, 1991.

X. Hao-yin, T. Liu, V. Zhan, F. Sekar, C. Qiu et al., Design and deployment of a hybrid CDN-P2P system for live video streaming: experiences with LiveSky, Proceedings of the 17th ACM international conference on Multimedia, p.61, 2009.

Y. Zhang, L. Cui, W. Wang, and Y. Zhang, A Survey on Software Defined Networking with Multiple Controllers, J. Netw. Comput. Appl. 103.C, p.105, 2018.

Z. Zhu, W. Lu, L. Zhang, and N. Ansari, Dynamic service provisioning in elastic optical networks with hybrid single-/multi-path routing, Journal of Lightwave Technology, vol.31, p.214, 2013.

D. Zhou and S. Subramaniam, Survivability in optical networks, IEEE network, vol.14, pp.16-23, 2000.