论文笔记:NFV的映射与调度

Posted by chochi on April 10, 2018

This paper “Design and Evaluation of Algorithms for Mapping and Scheduling of Virtual Network Functions”, proposes online mapping and scheduling algorithms of VNFs, there of those besed on a greedy criterion, and the rest one is tatu search, considers that we have virtual nodes already mapped onto physical nodes, and allows a given VM to process multiple VNFs, one after another from a queue, because each virtual node just can process at most one function at a time.

INTRODUCTION

NFV的提出以及解决的问题

Background

  • Network operators have physical proprietary devices and equipment for each service, leads to increased capital expenditure for operator for purchasing,storing,and maintaining such equipment.
  • A way of building dynamic virtualized networks ,it allows for the decoupling of physical network equipment from the services or functions.

    Example

    20180410-1

  • This is a example of the changes that may be achieved by NFV.

FIG 1

  • Fig 1 shows a implement(calls CPE) which is made up of those functions: DHCP, NAT, UPnP, routing, Modem, radio , switching. These functions may have precedence requirement.
  • If need to make changes to CPE,such as,by adding,removing or updating a function,it may be necessary for a technician from the ISP to individually talk to or go to each of the customers.

FIG 2

  • Fig 2 , a implement based on NFV , some of the functions are transferred to a shared infrastructure at the ISP,which could also be a datacentre.
  • This makes the changes easier,operatoring the functions for all customers would only involve changes at the ISP or in a datecentre.

Advantage of NFV

  • achieve fast,scalable,on-demand and dynamic .
  • cheaper .

Questions

  • How to define and implement network services.
  • How to efficiently map and schedule the VNFs of a given service onto physical network.

PROBLEM DESCRIPTION

数学模型描述问题以及算法初步

Variables

  • define a binary variable

    辛苦写的公式发现github不支持显示。只能用有道云笔记显示出来的截图。一点都不友好 = =

20180411-8 20180411-9

  • set N = {1,…,n} of n virtual nodes.
  • service S is made up of a sequence F = {1,…,m} of m VNFs.
  • function i (0<i<m+1) must be processed on a set N(i).
  • the processing time(including function setup time) for function i on node j in N(i)
    - NOTES: a given function may require different setup time on different nodes.
  • a function i utilizes a buffer δi from the node onto which it is mapped.
  • node j has available buffer size Bj.
  • for each VNF i and a virtual virtual node j ,we define a completion time ti.
  • for given service S ,define deadline tl.
# 没看懂的一段话
    The deadline can be used to define processing priority fro services.
    Those services that require real time processing may have a deadline 
that only takes into consideration their processing and precedence requirements
on the different virtual nodes,and zero waiting.

Mapping and scheduling example

20180411-1

  • Figs 4 - 7,show two services S1 and S2.
  • Fig 4 represented showing the different VNF processing capabilities of each node.
  • S1 = { f8 f2 f3 f6 f5}, at a time T1 the service S1 arrives.
  • S2 = {f6 f8 f4} ,arrives at a time T4.
    - notes: To aviod a long queue at n1,it may be better to use node n7 instead of n1
  • Fig 6,the processing of S2 has to wait until the completion of function f6 from S1 at time T6.
  • lead to inefficient resource utilization

Function timing restriction

20180411-2

  • There are three possibilities:
    • immediately after processing a function
    • has to wait until the virtual node is available(S2 f6)
    • the node starves while waiting fro the preceding function(Fig 7 n2)

Mapping and scheduling objectives

  • Three objectives such as minimizing flow time,cost and revenue.
    • Flowtime: the entire time for processing a given service 20180411-3
    • Revenue: R defined as the income from the total amout of physical network resources that are utilized by a given mapping and scheduling. 20180411-4
    • Cost : the cost C define as the total amount of physical network resources(Boston time and buffer)that are utilized by a given mapping and scheduling. The cost includes those time gaps.

Greedy Algorithms

这部分提出三种基于贪心的算法.

  • GFP
    • greedy fast processing,functions map to those nodes that offer the best processing times.
  • GBA
    • greedy besst availability,map to those nodes whose function queue has the earliest completion time.
  • GLL
    • greedy leather loaded,map to those nodes with the highest availabileather buffer capacity.

Greedy algorithmic procedure

  1. Pretreatment:nodes are ranked based on the greedy criterion
  2. stopping condition: the algorithms ends until the completion time exceeds,or the function has no candidate node,and all the resources allocated to other functions in there service are rolled back.

20180411-5

Tabu search-based NFMS

The algorithm dose not consider moving routing same solution repeatedly,but worsening moves can be accepted if no improving move is available.Five compenents are determined: the initial solution,the neighborhood solutions,tabu list ,aspiration criterion and stopping condition.

在短时间内访问的某一潜在解决方案,由于不符合某些规则被丢弃。 若被丢弃的方案比其他的搜索方案都优,虽然被标记为访问过,但还可以再次选取。 算法五元组,初始解,邻域解,已废弃潜在解列表,采纳标准和停止条件。

  • initial solution
    • Z0 is determined randomly,for each function i is randomly mapped a candidate virtual node j which meets the requirements.
  • neighborhood solutions
    • N(Z),we restrict the neighborhood to be based on changes in the mapping of the function with the biggest preceeding time gap.
    • 具有最大的 time gap 的函数,将作为首要需要迁移映射的目标,以确保最小的 flowtime。
  • tatu list
    • function i has been moved from node j1 to j2,so add j1 to tatu list,in order to avoid Visit j1 node in next m-1 iterations.
  • aspiration criterion
    • if all available moves are classified as tabu due tohaving a higher flow time than the best known solution, then we determine and select a “least tabu” move, which is themove with lowest flow time of all the tabu moves.
  • stopping condition
    • m次迭代找不到更少的 flowtime。
    • 所有的函数没有潜在的邻域解。

Psuedocode

20180411-6

Evaluations

何必为难自己 (⇀‸↼‶) 为什么要做英文的笔记!不想写了。直接截图。

20180411-7