SCIENCE CHINA Information Sciences, Volume 61 , Issue 9 : 092107(2018) https://doi.org/10.1007/s11432-017-9357-7

Virtual network function scheduling via multilayer encoding geneticalgorithm with distributed bandwidth allocation

More info
  • ReceivedMay 15, 2017
  • AcceptedDec 19, 2017
  • PublishedAug 13, 2018


Network function virtualization represents a revolutionary approach to network service deployment. This software-oriented approachfor virtual network functions (VNFs) deployment enables more flexible and dynamic networkservices to meet diversified demands. To minimize the executiontime of all VNFs in service function chains, VNF scheduling must be addressed.In this paper, we improve upon the flexible job-shop model byintroducing the process of bandwidth allocation. First, we propose a multilayer encodinggenetic algorithm to solve the VNF scheduling model. In addition,we design a distributed method for bandwidth allocation based on the Nash bargainingsolution. Finally, by combining the genetic algorithm with distributedbandwidth allocation, we present a heuristic algorithm that solves the VNFscheduling problem in one stage. Using a multilayer encoding geneticalgorithm, we simplify the constraints of the VNF scheduling problem and reduce itstime complexity. At the same time, our Nash game solution refines the granularity of bandwidthallocation to further reduce the transmission delay between VNFs. The effectiveness ofour proposed heuristic algorithm is verified through numerical evaluation. Compared withexisting approaches, our method exhibits shorter scheduling time andreduces CPU time by 45$%$ in simulated scenarios.


[1] Gil Herrera J, Botero J F. Resource Allocation in NFV: A Comprehensive Survey. IEEE Trans Netw Serv Manage, 2016, 13: 518-532 CrossRef Google Scholar

[2] Cao J, Zhang Y, An W. VNF-FG design and VNF placement for 5G mobile networks. Sci China Inf Sci, 2017, 60: 040302 CrossRef Google Scholar

[3] Riera J F, Escalona E, Batalle J, et al. Virtual network function scheduling: concept and challenges. In: Proceedings of International Conference on Smart Communications in Network Technologies, Vilanova i la Geltru, 2014. 1--5. Google Scholar

[4] Mijumbi R, Serrat J, Gorricho J L, et al. Design and evaluation of algorithms for mapping and scheduling of virtual network functions. In: Proceedings of IEEE Conference on Network Softwarization, London, 2015. 1--9. Google Scholar

[5] AL-Dhahir N. Editorial A Message From the New Editor-in-Chief. IEEE Trans Commun, 2016, 64: 1-1 CrossRef Google Scholar

[6] Riera J F, Hesselbach X, Escalona E, et al. On the complex scheduling formulation of virtual network functions over optical networks. In: Proceedings of International Conference on Transparent Optical Networks, Graz, 2014. 1--5. Google Scholar

[7] Riera J F, Hesselbach X, Zotkiewicz M, et al. Modelling the NFV forwarding graph for an optimal network service deployment. In: Proceedings of International Conference on Transparent Optical Networks, Budapest, 2015. 1--4. Google Scholar

[8] Kong Z, Xu C Z, Guo M. Mechanism design for stochastic virtual resource allocation in non-cooperative cloud systems. In: Proceedings of IEEE International Conference on Cloud Computing, Washington, 2011. 614--621. Google Scholar

[9] Bari M F, Boutaba R, Esteves R. Data Center Network Virtualization: A Survey. IEEE Commun Surv Tutorials, 2013, 15: 909-928 CrossRef Google Scholar

[10] Correa E S, Fletscher L A, Botero J F. Virtual Data Center Embedding: A Survey. IEEE Latin Am Trans, 2015, 13: 1661-1670 CrossRef Google Scholar

[11] Beck M T, Botero J F. Coordinated allocation of service function chains. In: Proceedings of 2015 IEEE Global Communications Conference (GLOBECOM), San Diego, 2015. 1--6. Google Scholar

[12] Bari M F, Chowdhury S R, Ahmed R, et al. On orchestrating virtual network functions. In: Proceedings of International Conference on Network and Service Management, Barcelona, 2015. 50--56. Google Scholar

[13] Luizelli M C, Bays L R, Buriol L S, et al. Piecing together the NFV provisioning puzzle: efficient placement and chaining of virtual network functions. In: Proceedings of IFIP International Symposium on Integrated Network Management, Ottawa, 2015. 98--106. Google Scholar

[14] Moens H, Turck F D. VNF-P: a model for efficient placement of virtualized network functions. In: Proceedings of International Conference on Network and Service Management, Rio de Janeiro, 2014. 418--423. Google Scholar

[15] Kim H, Feamster N. Improving network management with software defined networking. IEEE Commun Mag, 2013, 51: 114--119. Google Scholar

[16] Guo J, Liu F, Lui J C S, et al. Fair network bandwidth allocation in IaaS datacenters via a cooperative game approach. IEEE/ACM Trans Netw, 2015, 24: 873--886. Google Scholar

[17] Ballani H, Costa P, Karagiannis T, et al. Towards predictable datacenter networks. In: Proceedings of ACM SIGCOMM 2011 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Toronto, 2011. 242--253. Google Scholar

[18] Guo J, Liu F, Zeng D, et al. A cooperative game based allocation for sharing data center networks. In: Proceedings IEEE INFOCOM, Turin, 2013. 2139--2147. Google Scholar

[19] Mazumdar R, Mason L G, Douligeris C. Fairness in network optimal flow control: optimality of product forms. IEEE Trans Commun, 1991, 39: 775-782 CrossRef Google Scholar

[20] Touati C, Altman E, Galtier J. Generalized Nash Bargaining Solution for bandwidth allocation. Comput Networks, 2006, 50: 3242-3263 CrossRef Google Scholar

[21] Yaiche H, Mazumdar R R, Rosenberg C. A game theoretic framework for bandwidth allocation and pricing in broadband networks. IEEE/ACM Trans Networking, 2000, 8: 667-678 CrossRef Google Scholar

[22] Nisan N, Papadimitriou C H. Algorithmic game theory. Commun ACM, 1950, 53: 78--86. Google Scholar

[23] Boyd S, Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press, 2004. Google Scholar

[24] Martini B, Paganelli F, Cappanera P, et al. Latency-aware composition of virtual functions in 5G. In: Proceedings of the 2015 1st IEEE Conference on Network Softwarization (NetSoft), London, 2015. 1--6. Google Scholar

  • Figure 1

    (Color online) Network service deployment on NFV-enabled platform.

  • Figure 2

    Flexible composition of SFC. (a) VNF with precedence dependencies; (b) possible chaining options of VNFs.

  • Figure 3

    (Color online) An example of VNF scheduling.

  • Figure 4

    (Color online) Chromosome crossover process.

  • Figure 5

    (Color online) Chromosome mutation process.

  • Figure 6

    (Color online) Hose model for VNF bandwidth allocation.

  • Table 1   Comparison of different methods in control plane
    Method Scheduling time (ms) CPU time (s) Optimality gap (%)
    UB-MIP 28 6.3 0
    BRV-GA 26.1 1.31 6.8
    ME-GA 26.1 0.98 6.8

    Algorithm 1 Multi-layer encoding algorithm (MEA)

    Require:chaining matrix (C_s× v) and placement constraints vector (M_1× v);

    Output:population (rm chrom_rm NIND× l) and scheduling matrix (S_rm NINDltext/2);

    Generate VNF number vector (N_s× 1=N_s× 1^'=rm sumC_s× v2)) ;


    while $j~\neq~{\rm~NIND}$ do


    while $i~\neq~{\frac{{{l}_{i}}}{2}}$ do



    while ${{N}_{{\rm~val},1}}=0$ do


    end while





    $j={\rm~unidrnd}\left(~{\rm~size}({{M}_{1,{\rm~vnf}}}) \right)$;



    end while

    end while

  • Table 2   The comparison of different methods in data plane
    Method Scheduling time (ms) CPU time (s) Optimality gap (%)
    UB-MIP 57.8 6.3 0
    BRV-GA 39.1 1.31 32.3
    ME-GA 33 0.98 42.9

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号