ICTON 2014 We.C1.1 978-1-4799-5601-2/14/$31.00 ©2014 IEEE 1 On the Complex Scheduling Formulation of Virtual Network Functions over Optical Networks Jordi Ferrer Riera1, Xavier Hesselbach2, Eduard Escalona1, Joan A. García-Espín1, and Eduard Grasa1 1 Fundació i2CAT, Distributed Applications and Networks Area, C./ Gran Capità 2-4, Barcelona, Catalonia, Spain, 08034 email: {jordi.ferrer,eduard.escalona, joan.antoni.garcia, eduard.grasa}@i2cat.net 2 Universitat Politècnica de Catalunya, Departament d’Enginyeria Telemàtica, Jordi Girona, 1-3, C3 Campus Nord, Barcelona, Catalonia, Spain, 08034, email:
[email protected] ABSTRACT Software-Defined Networking and Network Functions Virtualisation has brought a revolution within the telecom market landscape. Initial proof-of-concept prototypes for NFV-enabled solutions are being developed at the same time SDN models are identified as the futures solutions within the telecom realm. We provide in this article an overview of the SDN/NFV technologies over optical networks, as well as we provide the first formalisation model for the virtual network function complex scheduling problem. The article aims at being used as starting point in order to optimally solve the scheduling problem of virtual network functions that compose network services to be provisioned within the SDN paradigm. Keywords: complex scheduling, network functions virtualisation, software-defined optical networks. 1. INTRODUCTION The economic and technological landscape where trends of computing and networking are converging creates the motivation for new engineering paradigms. One emerging paradigm is Software-Defined Networking (SDN), whose attributes include separation of control plane from forwarding, enabling joint optimisation of computing and networking deployments, software-defined functions at a number of layers, including the optical transport layer, enabling simpler interworking of different administrative and technology domains, and application-aware transport network resources [1]. This trend promises to bring radical improvements in both cost and functionality to the networking field [2]. Configuring and managing networks continues to be about network element operations, rather than networks or high-level network services, i.e. without having the network-wise component in place. The mix of ever-growing networks and ever-advancing configuration requirements makes network agility, service velocity, operation, and debugging increasingly difficult and expensive. Software-defined networks are widely seen as a promising solution for resolving those challenges [2]. In particular, SDN promises to provide a multi-layer platform that encompasses programmability not only at the forwarding and control planes, but also at the transport layer below and orchestration and services layers above the data and control planes. However, at the same time, SDN poses many fundamental questions, including deep architectural issues such as whether control should be centralized or distributed, and whether control and data planes should be separated or share fate, among others. Formally, Open Networking Foundation defines SDN as a control framework that supports programmability of network functions and protocols by means of decoupling the data plane and the control plane, which are currently integrated vertically in most network equipment [3]. SDN technology allows the underlying infrastructure to be abstracted and used by applications and network services as a virtual entity. This allows network operators to defined and manipulate logical maps of the network, creating multiple co-existing network slices (virtual networks) independent of underlying transport technology and network protocols. Furthermore, the separation of the control plane and data plane makes SDN a suitable candidate for an integrated control plane supporting multiple network domains and multiple transport technologies [4]. Several examples of SDN transport networking use cases are given by McDysan in [1]. The most significant ones are (i) coordinated networking and computing for cloud-bursting, (ii) global optimisation of transmission, switching, computing, and storage, and (iii) inter-domain and multi-layer optimisation. In parallel to the SDN trend in the telecom ecosystem, a novel approach to implement specific network functions has acquired momentum. Network Functions Virtualisation (NFV) [5] has arisen as an operator- promoted initiative with the objective of increasing the flexibility of network services deployment and integration within the operators’ networks. This is achieved by means of implementing network functions through software, avoiding specific hardware-based devices and increasing the return of investment. This concept involves implementing network functions in software that can run on a range of industry standard server hardware, which could be located in a variety of infrastructures, including data centres, network nodes, or even end-user premises, and which can be moved to, or instantiated without the need to install new equipment. The European Telecommunications Standards Institute (ETSI), through its NFV technological group, is promoting the NFV approach. ICTON 2014 We.C1.1 2 ETSI NFV group claims that the NFV technology could provide significant benefits for network operators and their associated customers: • Reduced operator capital expenditures (CapEx) and operational expenditures (OpEx) through reduced equipment costs and reduced power consumption; • Reduced time-to-market to deploy new network services; • Improved return on investment from new services; • Greater flexibility to scale up, scale down, or even evolve services; • Openness to the virtual appliance market and pure software entrants; • Opportunities to trial and deploy new innovative services at lower risk. NFV is highly complementary to SDN. These topics are mutually beneficial but are not dependent on each other. Network operators and service providers are interested in NFV-powered approaches because they enable the establishment of new mechanisms to operate and deploy network and infrastructure services [5]. However, currently NFV is still at the initial implementation stages [6]. Considering this telecom landscape, several research challenges emerge, which include the specifics of optical transport networks. Since NFV provide a network architecture vision to virtualize network node functions into blocks that can be chained, one of the most relevant research questions that appear, is how to concatenate the different virtual network functions (VNFs) efficiently in order to compose a set of network services. Thus, in order to address this aspect, we formulate a generic approach, which provides the formal description of the problem of scheduling a set of virtual network functions, which operate over an optical substrate. The rest of the manuscript is structured as follows. Section 2 contains a description of the related work, including the different approaches present in the research community addressing the specifics of SDN over optical infrastructures and the different NFV early-implementation approaches. In Section 3, we present the VNF scheduling problem formalisation. Finally, in Section 4, we provide the next steps to be taken in this research direction as well as we provide the initial set of conclusion extracted from the materialisation of our approach. 2. RELATED WORK OpenFlow [7] is the most common protocol for enabling SDN. It is already functional in different research, educational and even production infrastructures. Additionally, there are several open source projects developed by the community that provide new services and tools for such operational networks. Open-Flow controllers provide basic features such as routing, topology discovery, security, or even firewall rules. The first implementations of the controllers are centralized, so these components hold a complete view of the network. We believe that the integration of these functions inside the controller is useful in small-sized networks; however, when applied to bigger scenarios, moving such features into an external element enables (i) the management of the network function from a centralized point of view, and (ii) the management of the host where the network function is deployed. The authors in [4] proposed a novel control plane architecture based on OpenFlow for software-defined optical networks suitable for cloud computing services that takes into account the specific requirements. The proposed architecture allows implementation of agile, elastic cloud networks that can adapt to application requirements on demand. The article contains the different extensions required in the OpenFlow protocol to support optical networks. They also evaluate the performance of the proposed architecture through the use of relevant cloud computing use cases, e.g. content delivery. Furthermore, authors in [8] proposed and evaluated an optical SDN model, which enables performance comparison of different optical SDN scenarios, as well as network optimisation with respect to target parameters (e.g. path provisioning latency). In that model, all that was assumed a priori is a unified control plane with a centralized controller that governs an arbitrary set of software-defined entities, and can establish either vertical or horizontal paths between them, subject to a basic set of rules. The problem was formalised as a liner optimisation problem that could be further customised for given scenarios. Latency results presented corroborated and synthesized previous experimental data. In [9] the authors proposed the extension of SDN and OpenFlow principles to optical access/aggregation networks for dynamic flex-grid wavelength circuit creation. The first experimental demonstration of an OpenFlow1.0-based flex-grid λ-flow architecture for dynamic 150Mb/s per-cell 4G Orthogonal Frequency Division Multiple Access (OFDMA) mobile backhaul overlays onto 10GB/s passive optical networks was also detailed. On the other hand, initial proof-of-concept prototypes for specific virtual network functions are appearing in the literature. Authors in [6] proposed one of the first implementations of the functional NFV concept, through the virtualisation of the routing function over an OpenFlow-enabled network. The implementation was performed over the OpenNaaS framework, as detailed in Fig. 1. The solution consisted of the virtualization of the routing network function decisions from the actual equipment, logically centralizing the routing knowledge, and enabling to move its location along the network and duplicating it if required by the load; as well as being capable of maintaining dynamic and simplified forwarding tables between the different network elements. The solution was evaluated in terms of performance and it was demonstrated that although achieving lower ICTON 2014 We.C1.1 3 performance, it was still under reasonable terms. Additionally, authors in [4] experimented with the virtualisation of the PCE function including SDN over optical networks (with OpenFlow extensions). Figure 1. VNF (Routing) Implementation over OpenNaaS framework as proposed in [6]. It is clear that current work in the literature on optical SDN has been focused on extending the existing protocols (i.e. OpenFlow) in order to move the SDN concept to the optical network characteristics, and providing proof-of-concept implementations of Virtual Network Functions. This NFV concept is still on the design phase through the ETSI NFV 3. PROBLEM FORMALISATION This section introduces the VNF scheduling problem. Following Brucker’s [10] guidelines, in a scheduling problem one has to find time slots in which activities should be processed under given constraints, such as resource constraints and precedence constraints between those activities (i.e. we need to find the corresponding time slots for the virtual network functions composing different network services to be executed over a given set of machines – or servers – considering that each service consists of a set of ordered virtual network functions). This problem can be formulated as a Resource Constrained Project Scheduling Problem (RCPSP), in detail, a flexible job-shop problem. We have a set of N network services 1,..., NNS NS , where each network service is composed of a set of virtual network functions, i.e. each jNS consists of jn virtual network functions ijF with ( 1,..., )ji n= , which have to be processed in the corresponding order 1 2 ...j j njF F F→ → → , satisfying the precedence constraints between the different virtual network functions that compose the corresponding service. Additionally, we have a set of m multi-purpose servers or machines 1,..., mM M that can process the different virtual network functions. Each virtual network function ijF must be processed for 0ijp > time units without pre-emption on a dedicated machine { }1,...,ij mu M M∈ . Each multi-purpose server can process only one virtual network function at a time. Furthermore, let us assume that there is sufficient buffer space between the different servers to store a network service if it finishes on one server and next server is still occupied by another function. Let us now define a schedule ( )ijS S= , which is defined by the starting time of all network functions ijF . We say an schedule is feasible if • 1,ij ij i jS p S ++ ≤ for all network services 1,...,j N= and 1,..., 1ji n= − , i.e. the precedence 1,ij i jF F +→ are respected, and • ij ij uvS p S+ ≤ or uv uv ijS p S+ ≤ for all pairs ,ij uvF F of functions with ij uvu u= , i.e. each server processes only one job at a time. The objective is to determine a feasible schedule S with minimal makespan { }max 1max N jj C C = = , where , ,j jj n j n j C S p= + is the completion time of the Network Service jNS . For the sake of simplicity, let us identify the different network functions ijF by numbers 1,...,n , where 1 : N j j n n = = . We use then the index i for the network functions 1,...,i n= . Then, the processing time for the network function i is denoted as ip , the network service to which virtual function i belongs is denoted as ( )NS i , and iu denotes the server on which i has to be executed. We introduce a dummy starting point function at 0 and a dummy terminating function at n+1 with 0 1 0np p += = . For a network function uvi F= let ICTON 2014 We.C1.1 4 1,( ) u vi Fσ += be its successor where ( ) 1i nσ = + if i is the last virtual network function of a network service. Furthermore, we say the first operation of each service is a successor of the starting operation 0. Let us assume also that with each virtual network function i a set of servers indices { }( ) 1,...,M i m⊆ is associated indicating that the given function i can be executed by any server within this set (i.e. each server can execute one or a group of different network function types). If operation i is executed into server ( )k M i∈ , then its processing time its equal to ikp . One has to assign to each operation i a server from the machine set identified by ( )M i in such a way that a corresponding optimal makespan is minimal over all possible assignments. Authors in [10] state that such a model with flexible servers may for example be used when the operations need certain tools for processing and the machines are only equipped with a few of them, which is clearly the case for the virtual network functions and the physical infrastructures where they must be executed. Thus, ( )M i denotes all the servers, which are equipped with the tools needed by operation i. In order to give a mathematical description of this new constrained problem, we follow the generic model proposed by [REF-BOOK]. Thus, we introduce assignment variables 1, if operation is assigned to server ( ) 0, otherwiseik i k M i x ∈ = For each assignment ( )ikx x= , we define disjunctions ( ) { | 1 for some ( ) ( )}ik jkD x i j x x k M i M j= − = = ∈ ∩ between functions i,j assigned to the same server. Then, the problem can be formulated as follows: 1 ( ) ( ) ( ) ( ) min . . ( ) ( ( )) 1 ( 1,..., ) 0 n i ik ik j k M i i ik ik j j jk jk i k M i k M j ik k M i i S s t S p x S i j C S p x S S p x S i j D x x i n S + ∈ ∈ ∈ ∈ + ≤ → ∈ + ≤ ∨ + ≤ − ∈ = = ≥ ( 0,..., 1) {0,1} ( 1,..., ; ( ))ik i n x i n k M i = + ∈ = ∈ Given a server assignment ( )ikx x= satisfying the last three statements, the problem reduces to a linear program with additional disjunctive constraints (so-called disjunctive linear program) [10] with virtual network function processing times ( ) i ik ik k M i p p x ∈ = and disjunctions D = D(x). Thus, the problem may be solved with a two-stage approach, where at first servers are assigned to the corresponding virtual network functions and afterwards the resulting classical job-shop problem is solved. 4. CONCLUSIONS AND FUTURE WORK The paper introduces the concept of network function virtualisation as first materialised by the ETSI NFV standardisation group, defining a service as a concatenation of NFV functions to be executed. We provide an overview of the SDN and NFV approaches, considering its status over optical networks and its specific constraints. The paper shows that the execution of the service with restrictions coming from the optical domain constitute a problem that can be formulated as a Resource Constrained Project Scheduling Problem (RCPSP). Then, to the best of our knowledge, we provide the first formalisation of the VNF scheduling problem, using the flexible job-shop problem. We provide the basis to formally resolve the problem as future work. ACKNOWLEDGEMENTS This work has been partially granted by the European Commission through the FP7 619520 T-NOVA project. REFERENCES [1] D. Mcdysan, "Software defined networking opportunities for transport," IEEE Communications Magazine, vol. 51, no. 3, pp. 28-31, Mar. 2013. [2] D. Meyer, "The software-defined-networking research group," IEEE Internet Computing, vol. 17, no. 6, pp. 84-87, Nov.-Dec. 2013. [3] ONF, “Software-defined networking: The new norm for networks”, Mar. 13, 2012 [Online] Available: www.opennetworking.org/images/stories/downloads/white-papers/wp-sdn-newnorm.pdf . ICTON 2014 We.C1.1 5 [4] M. Channegowda, R. Nejabati, and D. Simeonidou, "Software-defined optical networks technology and infrastructure: Enabling software-defined optical network operations [invited]," IEEE/OSA Journal of Optical Communications and Networking, vol. 5, no. 10, pp. A274-A282, Oct. 2013. [5] “White paper on Network Functions Virtualization”, ETSI NFV. [Online] Available: http://portal.etsi.org/NFV/NFV_White_paper.pdf. [6] J. Batalle, J. Ferrer Riera, E. Escalona, and J.A. Garcia-espin, "On the implementation of NFV over an OpenFlow infrastructure: Routing function virtualization," 2013 IEEE SDN for Future Networks and Services (SDN4FNS), pp. 1-6, 11-13 Nov. 2013. [7] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner. “Openfiow: Enabling innovation in campus networks”, SIGCOMM Comput. Commun. Rev., vol. 38, pp. 69-74, Mar. 2008. [8] N. Cvijetic, M. Angelou, A. Patel, P.N. Ji, and Ting Wang, "Defining optical software-defined networks (SDN): From a compilation of demos to network model synthesis," in Proc. Optical Fiber Communication Conference and Exposition and the National Fiber Optic Engineers Conference (OFC/NFOEC 2013), pp.1-3, 17-21 Mar. 2013. [9] N. Cvijetic, A.Tanaka, P.N. Ji, K. Sethuraman, S. Murakami, and Ting Wang, "SDN and OpenFlow for dynamic flex-grid optical access and aggregation networks," Journal of Lightwave Technology, vol. 32, no. 4, pp.864-870, Feb.15, 2014. [10] P. Brucker and S. Knust, Complex Scheduling, Springer Berling-Heidelberg. ISBN-10 3-540-29545-3. /ColorImageDict > /JPEG2000ColorACSImageDict > /JPEG2000ColorImageDict > /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 200 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict > /GrayImageDict > /JPEG2000GrayACSImageDict > /JPEG2000GrayImageDict > /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 400 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict > /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (None) /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description > >> setdistillerparams > setpagedevice