工程科学与技术   2018, Vol. 50 Issue (2): 118-125
面向收益最大化的虚拟网跨域映射策略
江逸茗, 马海龙, 卜佑军, 申涓, 贺磊     
国家数字交换系统工程技术研究中心,河南 郑州 450002
基金项目: 国家自然科学基金资助项目(61502530; 61572519; 61521003);国家重点基础研究发展计划资助项目(2013CB329104)
摘要: 虚拟网映射算法主要解决的是如何通过对资源的合理规划,在底层网络上承载更多的虚拟网络。跨域映射能够为虚拟网提供更多的底层资源,但跨域映射策略一方面需要考虑如何降低跨域映射带来的额外开销,另一方面还需要考虑如何满足网络运营商的自私性。为解决该问题,提出一种面向收益最大化的虚拟网跨域映射策略。为了建立虚拟网拓扑分割和本地映射方案的同步求解模型,该策略首先通过对本地基础设施提供商的域视图进行转换,在模型中引入域节点的概念;然后,设计了一种基于竞价的本地基础设施提供商选择策略;最后,设计了一种基于遗传进化思想的本地映射算法对模型进行求解,该算法根据虚拟网映射的约束,对遗传进化算法的初始化和染色体交叉等步骤进行相应修改。算法生成的映射方案将把虚拟节点和链路优先映射在本地域里,同时尽可能地减少虚拟链路对底层域间链路带宽资源的占用。本策略支持根据跨域映射的实际额外开销情况对参数进行调节,从而生成使本地基础设施提供商收益最大化的分割方案。仿真实验表明,若跨域映射带来的额外开销越大,则本策略将越倾向于减少跨域虚拟链路的数量;从映射效果上来看,由于本策略比同类型策略消耗的映射开销要小,所以在实际收益和映射接受率等指标方面都有明显提高。
关键词: 虚拟网    跨域映射    收益    映射开销    
Inter-domain Virtual Network Embedding Policy for Revenue Maximization
JIANG Yiming, MA Hailong, BU Youjun, SHEN Juan, HE Lei     
National Digital Switching System Eng. and Technol. Research Center,Zhengzhou 450002,China
Abstract: Virtual network embedding algorithm mainly focus on the problem of how to carry more virtual networks on the substrate network by reasonably allocating resources.Inter-domain embedding is able to offer more substrate resources for virtual networks.On the one hand,the inter-domain embedding policy needs to consider how to reduce the inter-domain embedding overhead.On the other hand,it also needs to consider how to satisfy the selfishness of network providers.Therefore,an inter-domain virtual network embedding policy for revenue maximization was presented in this paper.In order to establish a synchronization solution model of virtual network topology partition and local embedding scheme,the policy firstly transformed the domain view of the local infrastructure provider to introduce the concept of domain nodes into the model.Then an auction-based local infrastructure provider selection strategy was designed.Finally,a local embedding algorithm based on genetic evolution was designed to solve the model.The algorithm modified the steps of initialization and chromosome crossover according to the constraints of virtual network embedding.The embedding scheme generated by the algorithm preferentially embedded the virtual nodes and the links on the local domain,while reducing the virtual link occupancy of inter-domain link bandwidth resources as much as possible.The policy supported the tuning of parameters based on the actual overhead of inter-domain embedding,resulting in a partition scheme that maximizes the local infrastructure provider’s revenue.Simulation results showed that the more overhead the inter-domain embedding expends,the more the policy will tend to reduce the number of inter-domain virtual links.In terms of embedding effect,the embedding cost of the policy was lower than that of the same type of policy,so it had obvious improvement in indicators such as actual profit and acceptance rate.
Key words: virtual network    inter-domain embedding    revenue    embedding cost    

网络服务的快速部署需要克服不同设备和协议之间的差异性。但随着网络规模的扩大,部署和应用新型网络体系架构变得愈加困难。而网络虚拟化技术已成为解决上述问题的重要技术路线[1]

通过网络虚拟化技术,可以在共享的底层物理网络上创建多个虚拟网络(virtual network,VN),从而为用户提供多样化和可定制的端到端服务,例如为网络视频会议或IPTV[2]等服务建立专门的虚拟网。在网络虚拟化环境中,基础设施提供商(infrastructure provider,InP)负责管理和运营底层网络,服务提供商(service provider,SP)以虚拟网请求(virtual network request)的方式向InP申请网络资源,InP将会根据底层网络的资源状态和SP的实际需求,将各个虚拟网请求映射到底层设备上[3]

虚拟网映射算法是网络虚拟化领域的一个重要研究课题[4]。目前已有不少文献对单个底层网络域内的映射问题进行了研究[59]。但在底层网络负载较高或虚拟网规模较大时,单个域内的网络资源已无法满足新的虚拟网请求,而支持跨域的虚拟网映射策略能够有效的解决该问题。在多域环境下,由于管理各个域的InP之间会存在一定的利益冲突,因此各个InP不会公开网络拓扑等信息,在制定映射方案时也将优先考虑如何使其自身利益最大化[10]。所以,这种InP的自私性是跨域映射策略必须考虑的因素之一。

Werle等[11]提出了一种支持跨域的虚拟网络平台。Mahmud等[12]提出了一种多域环境下的虚拟网资源分配框架RAiNV。Chowdhury等[10]设计了一种虚拟网跨域映射策略PolyViNE,该策略将虚拟网中无法被单域映射的部分推送给相邻的底层网络域进行映射,但没有提出专门针对跨域映射的算法,从而导致多域映射时开销较高的问题。Fida等[13]针对InP的报价问题设计了一种竞价模型V-Mart,但没有提出相应的跨域映射策略。Zhang[14]、Houidi[15]和Jia[16]等针对如何降低开销问题设计了跨域映射算法,但都没有考虑InP之间的价格差别以及InP的自私性因素,因此无法有效提高InP和SP的收益。

针对上述文献中存在的问题,作者将提高InP和SP收益以及降低映射开销这两个问题进行综合考虑,把虚拟网跨域映射模型转化为整数规划问题,并在模型中引入域节点的概念,从而可以实现映射方案与拓扑分割方案的同步求解。在此基础上,提出了一种面向收益最大化的虚拟网跨域映射策略(inter-domain virtual network embedding policy for revenue maximization,IVERM),该策略利用价格竞争机制来使SP能够以最低的费用为虚拟网申请到足够的资源;本策略采用了一种基于遗传进化的虚拟网本地映射算法,该算法能从提高InP收益的角度进行虚拟网拓扑的分割,并可同时生成能够有效降低映射开销的域内映射方案。

1 问题描述与建模 1.1 虚拟网映射问题的形式化描述

虚拟网跨域映射问题可由以下模型描述:

1)底层网络。底层网络包括多个相互连接的网络域组成,每个域由一个InP负责管理。底层网络的拓扑可以用带权无向图 ${G_{ s}} = \left( {{G_{ s}^1},{G_{ s}^2}, \cdots ,{G_{ s}^i}} \right)$ 表示,其中, ${G_{ s}^i} = ({N_{ s}},\;{L_{ s}},\;{C_{ N}},\;{C_{ L}})$ 表示一个网络域的拓扑, ${N_{ s}}$ ${L_{ s}}$ 分别表示底层节点集合和底层链路集合。底层链路可以进一步分为域内链路与域间链路, ${C_{ N}}$ ${C_{ L}}$ 分别为底层节点的最大处理能力和底层链路的最大带宽。

2)虚拟网映射请求。一个虚拟网映射请求包括虚拟网拓扑 ${G_{ v}}$ 、请求到达时间 ${t_{{a}}}$ 和请求持续时间 ${t_{ d}}$ 。虚拟网拓扑可以用带权无向图 ${G_{ v}} = ({N_{{v}}},\;{L_{{v}}},\;{R_{{{ N}}}},\;{R_{{{ L}}}})$ 表示,其中, ${N_{ v}}$ 为虚拟节点的集合, ${L_{{v}}}$ 为虚拟链路的集合, ${R_{ N}}$ ${R_{ L}}$ 分别表示虚拟节点和虚拟链路的资源约束。虚拟网请求在 ${t_{{a}}}$ 时刻到达后,底层网络为其分配满足 ${R_{ N}}$ ${R_{ L}}$ 约束的网络资源。虚拟网在运行 ${t_{{d}}}$ 时刻后,其所占用的资源将被底层网络回收。

3)虚拟网映射。虚拟网的映射问题可以描述为一个从虚拟网请求拓扑 ${G_{{v}}}$ 到底层网络拓扑 ${G_{{s}}}$ 满足 ${R_{{{ N}}}}$ ${R_{{{ L}}}}$ 约束的映射M ${G_{ v}} \to \left( {N',L',{R_{{{ N}}}},{R_{{{ L}}}}} \right)$ ,其中, $N',L' \subset {G_{ s}}$ 。虚拟网映射可以进一步分解为节点映射和链路映射。在映射的过程中,SP首先会对多个InP发起竞价申请,各个InP在受到申请后会根据自身的情况向SP返回一个报价(满足 ${R_{ N}}$ ${R_{ L}}$ 的平均单价);然后,SP将会把虚拟网请求发送给报价最低的InP,由于该InP将会优先启动本地映射流程,因此可将其称为本地InP(记为InP#),若InP#发现自己的底层网络没有足够的可用资源映射该虚拟网请求时,则会对虚拟网的拓扑进行分割,并将部分子拓扑交由相邻的底层网络进行跨域映射。图1为一个虚拟网的跨域映射实例。

图1 虚拟网跨域映射实例 Fig. 1 Example of inter-domain virtual network embedding

1.2 跨域映射问题分析

在传统的单域映射模型中,虚拟网请求的接受率和映射代价是衡量算法优劣的两个最重要指标。在跨域映射模型中,除了考虑上述两个指标外,还要考虑InP和SP的收益问题。对于SP而言,为了降低运营成本,将选择符合基本要求且报价较低的InP负责虚拟网的构建。而从InP的角度,应从一次虚拟网的构建中获取尽可能多的收益,而映射一个虚拟网请求的收益是由该虚拟网的资源需求决定的,具体包括节点资源需求和链路资源需求,定义如下:

$I({G_{ v}}) = \sum\limits_{i \in {{N}_{ v}}} {R_{ N}^i + \sum\limits_{i \in {{L}_{ v}}} {R_{ L}^i} } $ (1)

在跨域映射时,映射收益由参与映射的几个InP共享,并按照每个InP所承载的子拓扑在 ${G_{ v}}$ 中占有的比例对映射收益进行划分。对于InP#,由于其将优先对虚拟网请求进行映射,所以为了提高自身的收益,InP#会试图将更多的虚拟节点和链路映射到自己管理的底层网络域中。综上所述,无论对于SP还是InP#,要想提高自身的收益,应尽可能将虚拟节点和链路映射到InP#管辖的底层网络上。为了便于建模,对式(1)进行简化,仅用映射在本域内的虚拟节点的资源总量衡量一个虚拟网给InP带来的映射收益。

此外对于InP,映射虚拟网请求也需要一定开销。节点映射的开销是固定的,而链路映射的开销是与映射方案相关的,比如映射在多条底层链路上的虚拟链路会消耗的更多带宽资源。由此可见,降低虚拟网映射代价的关键是降低域间链路映射的代价。域间通信的开销也比域内通信的开销要大,作者将虚拟链路映射在域间链路上的开销设为映射在域内链路上的开销的 $r$ 倍, $r$ 称为域间链路的映射代价因子。

1.3 跨域映射的整数规划模型

在跨域映射的流程里,InP#在自己管理的域内对虚拟网请求进行分割并映射的过程称为本地映射。以提高InP#的最大收益为目标,建立了虚拟网本地映射的整数规划模型。由于各个InP之间并不公开网络拓扑,所以为了便于建模,首先从InP#的角度对其所管理的域视图进行一个转换(如图2所示),也就是将其邻接的域视为本域内的一个特殊节点,称为域节点(domain node),域节点可以被同一个虚拟网请求中的多个虚拟节点重复映射,其可用资源量由该域的整体负载情况决定。转换后的底层网络模型为 $G_{{s}}^i = \left( {{N_{{s}}},{N_{{a}}},{L_{{s}}},{C_{{{ N}}}},{C_{{{ L}}}}} \right)$ ,其中, ${N_{{s}}}$ 为域内的底层节点, ${N_{{a}}}$ 为域节点。

图2 域视图转换 Fig. 2 Convert to domain view

跨域映射的整数规划模型定义如下:

输入:

1)底层网络拓扑 ${G_{ s}}$ ;2)虚拟网请求拓扑 ${G_{ v}}$ ;3)域间链路的映射代价因子 $r$ ;4)开销权重因子 $\alpha $

目标函数:

$\max \sum\limits_{i \in {{N}_{ v}}} {g({x_i}) \cdot R_{ N}^i} - \alpha \sum\limits_{i \in {{L}_{ v}}} {\sum\limits_{l \in {{L}_{ s}}} {f_l^i \cdot } R_{ L}^i} $ (2)

变量:

1) ${x^i}$ 为被虚拟节点 $i$ 映射的底层节点的编号。

2) $f_l^i$ 为该变量用于标记虚拟链路是否跨域。若虚拟链路 $i$ 映射在底层链路 $l$ 上且 $l$ 为域内链路,则该值取1;若 $l$ 为域间链路,则该值设为参数 $r$ ;若没有映射在 $l$ 上则该值取0。

约束:

${x^i} \in {N_{ s}} \cup {N_{ a}}$ (3)
$g({x_i}) = \left\{ {\begin{aligned}& 0,{{x^i} \in {N_{ a}}};\\& 1,{{x^i} \in {N_{ s}}}\end{aligned}} \right.$ (4)
${f_l^i \in \{ 0,1,r\} }, {i \in {N_{ v}},l \in {L_{ s}}},r \ge 1$ (5)
$\begin{array}{*{20}{c}}{{x^i} \ne {x^j}},{{x^i},{x^j} \in {N_{ s}};i \ne j}\end{array}$ (6)
$R_{ N}^i \le C_{ N}^{{v_i}}$ (7)
$R_{ L}^i \le \arg {\min _{j \in {L_{ s}},f_j^i \ge 1}}C_{ L}^j$ (8)

式(2)为模型的目标函数,其意义是InP#映射一个虚拟网的实际收益,其中, $\displaystyle\sum\limits_{i \in {N_{ v}}} {g({x_i}) \cdot R_N^i} $ 表示InP#的映射收益,该值主要由映射在InP#域内的虚拟节点的个数和资源需求决定; $\displaystyle\sum\limits_{i \in {L_{ v}}} {\displaystyle\sum\limits_{l \in {L_{ s}}} {f_l^i} \cdot R_{ L}^i} $ 表示映射开销,该值主要由虚拟链路占用的底层链路的数量和性质决定,权重因子 $\alpha $ 用以调节映射开销在总收益中占有的比例,确保计算得出的收益不为负。式(3)~(6)为各个变量的取值约束,其中,式(6)表示域内的底层节点不能被同一个虚拟网中的多个虚拟节点重复映射,但域节点则无此限制。式(7)~(8)为节点映射和链路映射的资源需求约束。

2 跨域映射策略

跨域策略包括InP选择策略和基于遗传进化的本地映射算法,其核心思想是先由SP向多个InP发起映射请求,各个InP首先尝试制定域内映射方案,如果因为资源不足需要进行跨域映射,则InP将利用本地映射算法生成使自身收益最大化的映射方案,并向SP返回报价,最后SP将选择报价最低的InP作为InP#,由InP#负责构建该虚拟网。

2.1 InP选择策略

在SP要构建一个虚拟网时,首先要选择由哪个InP来映射这个虚拟网请求。选择策略的目标是使SP能以最小的费用完成虚拟网的构建,其步骤如下:

Step1:SP首先根据地理位置、商业合作关系等一些因素,筛选出一些符合要求的InP作为候选的InP。

Step2:SP向候选集中的每个候选InP发送虚拟网的拓扑和资源需求等信息。

Step3:各个InP收到虚拟网请求后,首先尝试单域映射,若单域映射成功则直接返回报价;若失败则调用基于遗传进化的虚拟网本地映射算法,通过算法得到虚拟网拓扑的分割方案以及本域内映射的方案,并向邻接域的InP发起跨域联合映射请求。如果邻接域的InP同意进行联合映射,则向候选InP进行确认并返回一个报价,候选InP根据该报价估算本次跨域映射的总报价,总报价可按式(9)进行计算。

${{p_{ mu}} = {p_{ s}}{\lambda _{ s}} + \sum {{p_i}{\lambda _i}}}, {\lambda _{ s}} +\sum {{\lambda _i}} = 1$ (9)

式中, ${p_{{s}}}$ 为单域映射的报价, ${p_i}$ 为相邻InP的报价, ${\lambda _{{s}}}$ 为映射在本域的节点资源量占整个虚拟网节点资源需求总量的比例, ${\lambda _i}$ 为第 $i$ 个相邻域占有的比例。最后,跨域映射报价 ${p_{{{mu}}}}$ 将会反馈给SP。

Step4:SP收到报价后,将报价最低的InP设为InP#,若最低报价相同则根据其他因素进行选择,并向InP#发送正式的虚拟网请求。

2.2 基于遗传进化的虚拟网本地映射算法

在收到虚拟网请求后,InP需要对拓扑进行分割,从而确定哪些虚拟节点和链路是映射在自己管理的域上;然后将剩余的虚拟网子拓扑交给邻接InP进行映射。本地映射问题可以转化为第2.3节中描述的整数规划模型进行求解。遗传算法模拟了自然界中生物群体的进化过程,包括染色体的复制、交叉和变异,通过多代进化后筛选出最优个体,在求解整数规划时具有良好的性能。但在求解跨域映射模型时,由于模型中存在若干约束,因此需要对遗传算法的关键步骤进行改造。针对该问题,作者提出了一种基于遗传进化思想的虚拟网本地映射算法。本算法的关键步骤如下:

Step1:群体初始化。

当InP收到一个包含 $n$ 个节点的虚拟网请求后,生成 $m$ $n$ 维整数向量 ${ X} = \left[ {{x_1},{x_2}, \cdots ,{x_m}} \right]$ 作为群体,每个向量表示一个进化个体的基因信息,其实际意义是节点映射的一个方案,向量第 $i$ 维的值表示第 $i$ 个虚拟节点的映射目标(底层节点的编号)。在群体初始化之前,先要为每个虚拟节点的生成一个可用映射目标集合,该集合中每个底层节点的可用资源要大于该虚拟节点的资源需求,每个集合至少包含所有的域节点。在生成每个向量时,向量每一维的值是在符合式(6)约束的前提下,从可用映射目标集合中随机选取。

Step2:计算个体适应值。

适应值是衡量个体优劣的标准,本算法中适应值函数直接采用式(2)所描述的目标函数。在为群体中的所有个体计算适应值时,要先根据个体所代表的节点映射方案来生成链路映射方案,生成方法是利用最短路径算法计算出每一条虚拟链路的实际路径,且该路径要有足够的可用带宽来承载该虚拟链路,若可用路径不存在则适应值设为0。计算完成后,要在群体中挑选出适应值最高的当代最优个体。此外,算法还要维护一个全局最优解,若在进化过程中出现了适应值更高的当代最优个体,则记录该个体并更新全局最优解。

Step3:选择。

在获取所有个体的适应值之后,要将部分适应值较高的个体送入交配池,用于繁殖下一代个体。本算法采用随机联赛法进行个体的选择,也就是在个体数为 $m$ 的种群中,随机抽取 $n$ 个个体进行适应值的比较,将适应值最高的个体送入交配池,上述过程将反复进行 $m$ 次,得到个体数为 $m$ 的交配池。

Step4:交叉。

交叉就是将交配池中的个体进行杂交,从而生成新一代个体,该过程决定了遗传算法的全局搜索能力。本算法采用均匀交叉策略,方法是在交配池中任选两个个体,按给定的交叉概率 ${p_{ b}}$ 进行配对繁殖,配对的两个个体的每一位基因都以相同的概率 ${p_{ e}}$ 进行交换。由于要保证交叉生成的新个体必须满足式(6)的约束,所以如果待交换的基因值是域内底层节点,则要判断新生成的个体中是否存在域内节点被重复映射的情况,若存在则不允许该位基因进行交换。图3为一个交叉操作的实例,两个个体随机在4个基因位上进行了交换,由于第4个基因位的交换会使节点16在新生成的个体Ⅱ中被重复映射,因此在该基因位上不进行交换。

图3 交叉操作实例 Fig. 3 Example of cross

Step5:变异。

变异主要是为了防止算法陷入局部最优解,其方法是以一个较小的概率 ${p_{{m}}}$ 对于个体中的每一位基因进行重新设置,新值是从可用目标集合中随机选取的,且满足式(6)的约束。

Step6:群体灾变。

当全局最优解在连续进化 $g$ 代后未发生改变,说明算法有可能已经陷入局部最优解。此时可以启用群体灾变机制使算法跳出局部最优解,灾变的实现方法是只保留一个最优的个体,而将群体中的其他个体按照初始化的方法全部随机重置,使算法能够探索新的解空间。

Step7:进化终止。

遗传进化是一个反复迭代的随机搜索过程,本算法通过设置最大进化代数 $N$ 作为算法的终止条件。若当前的迭代次数小于 $N$ ,则流程跳至Step2;否则终止迭代并输出全局最优解作为虚拟网请求在本域内的最优映射方案。

Step8:跨域映射。

按照Step7输出的最优映射方案对虚拟网请求的拓扑进行分割,映射在域内底层节点上的虚拟节点由InP#实现相应的资源分配,将映射到域节点的虚拟节点交给该域节点所对应的邻接InP进行映射,映射算法可由这些邻接InP自行决定。当节点映射完成后,InP#先用最短路径算法求出域内虚拟链路的路径并对其进行映射,再通过与邻接InP进行协商来完成跨域虚拟链路的映射。

总体流程如下:

输入:种群个体数 $m$ ,最大进化代数 $N$ ,灾变阈值 $g$ ,变异概率 $p$

输出:跨域虚拟网的本地映射方案。

步骤1:群体初始化,将全局最优个体的适应值设为0;

步骤2:计算个体适应值,记录群体中适应值最高的最优个体;

步骤3:if 最优个体的适应值 > 全局最优个体的适应值,则

将本轮的最优个体设为全局最优个体;

步骤4:else if 连续进化 $g$ 代后,全局最优个体未发生改变,则

在本轮的个体变异过程中进行群体灾变;

步骤5:对个体进行选择,选出适应值最高的个体送入交配池;

步骤6:对交配池内的个体进行交叉;

步骤7:个体变异;

步骤8:if 迭代进化次数达到N次,则进化终止,输出全局最优解,按照最优解对虚拟网进行分割并进行本地映射,同时将映射到域节点上的虚拟网子拓扑交给邻居域进行映射;

步骤9:else

跳转到步骤2。

3 实验仿真 3.1 仿真环境设定

实验在Pentium 4 CPU 3.2 GHz,1 GB内存的PC机上运行。底层网络拓扑和虚拟网请求拓扑由GT-ITM工具[17]生成,底层网络由6个域组成,每个域包含50个底层节点、140条域内底层链路和2条域间底层链路,底层节点的最大可用资源和域内底层链路的最大带宽资源取值在[50,100]内均匀分布,域间链路的带宽取值在[150,250]内均匀分布。每个InP的初始报价在[100,200]的范围内随机取值,每经过200个单位时间对报价进行一次调整,调整时根据底层网络资源占用率的变化情况决定提高还是降低报价,报价的调整幅度在[0,20]内随机取值。

虚拟网请求的节点个数在[2,10]内均匀分布,节点连接概率为0.3,虚拟节点的资源需求取值在[1,15]之间均匀分布,虚拟链路的带宽取值在[1,5]之间均匀分布,请求的到达时间服从平均100个单位时间到达10个请求的泊松过程,持续时间服从 $\mu $ 为1 000的指数分布。

IVERM策略的部分参数取值为:交叉概率 ${p_{{b}}}$ =85%, ${p_{{e}}}$ =70%,变异概率 ${p_{{m}}}$ =15%,候选InP#数量 $k$ =3,种群个数 $m$ =20,灾变系数 $g$ 设为最大进化代数 $N$ 的0.6倍。实验选取一种跨域映射策略PolyViNE作为IVERM的比较对象。

3.2 参数影响

在PolyViNE的多域映射策略中,InP#会将自己能够承载的虚拟节点尽量映射到本域内,而将自己无法承载的虚拟节点交给邻接的InP进行映射,但这种策略可能会增加跨域映射的虚拟链路数量,从而使映射开销增大。在链路跨域映射的开销较大的情况下,对于虚拟网请求中的某些节点,即使InP#有足够的资源能够承载这些虚拟节点,但如果将其映射到邻接域,则有可能使映射开销降低的幅度大于收益降低的幅度,从而提升实际收益(如图4所示)。因此,仅仅按照底层网络域的承载能力对虚拟网拓扑进行划分,得到并不一定是实际收益最高的分割方案。

图4 减少跨域虚拟链路数量的实例 Fig. 4 Example of reduce the number of inter-domain links

跨域映射代价对实际收益的影响主要受域间链路的映射代价因子 $r$ 和开销权重因子 $\alpha $ 这两个参数的影响。 $r$ $\alpha $ 的值越小,则虚拟链路跨域映射带来的开销对InP收益产生的影响也就越小,所以算法会将更多的虚拟节点映射到InP#的域内;若 $r$ $\alpha $ 的值越大,则算法会优先减少跨域虚拟链路的数量,从而将部分虚拟节点交由邻接InP映射。用分割率(split ratio,SR)体现 $r$ $\alpha $ 对映射方案的影响,定义如下:

$SR = \left| {{N_{ id}}} \right|/\left| {{N_{ v}}} \right|$ (10)

式中, ${{N_{ id}}}$ 为映射在InP#域内的虚拟节点的数量, ${{N_{ v}}}$ 为虚拟网请求中虚拟节点的总数。两次实验的观测对象分别为 $r$ $\alpha $ 的取值发生变化后,前5个分割率发生变化的跨域虚拟网,由图56所示,当 $r$ $\alpha $ 取值较小时,计算出的映射方案的分割率则较大。由实验结果可知,本算法不是仅仅按照底层网络的实际承载能力进行虚拟网拓扑的分割,而是按照降低映射开销、提高实际收益的目标进行分割;并可以根据跨域链路映射开销的差异进行参数调节,从而计算出不同的分割方案。

图5 域间链路的映射代价因子 ${{r}} $ 对分割率的影响 Fig. 5 Impact of embedding cost factor ${{r}}$ of inter-domain links to split ratio

图6 开销权重因子 ${{\alpha}}$ 对分割率的影响 Fig. 6 Impact of cost weight factor ${{\alpha}}$ to split ratio

最大进化代数 $N$ 决定了算法的迭代次数, $N$ 取值越大,则计算出来的映射方案就越好,但算法运行的时间也就越长。实验观测了前3次跨域映射过程,参数 $r$ $\alpha $ 分别设为2和0.2,图7显示了 $N$ 的取值对最优方案的适应值和算法运行时间的影响。

图7 最大进化代数对适应值和运行时间的影响 Fig. 7 Impact of maximum generation to fitness value and run time

3.3 实际收益与开销

由式(2)可知,对于InP#映射一个虚拟网的实际收益等于映射收益减去映射开销。本实验分别用IVERM和PolyViNE策略对1 000个虚拟网请求进行映射后,随机观测了9个成功进行跨域映射的虚拟网,并记录了这些虚拟网给InP#带来的实际收益与映射开销,参数设置为 $r$ =2, $\alpha $ =0.2, $N$ =100。

图8可见,由于IVERM和PolyViNE策略都考虑了InP#的自私性,因此这两种策略的映射收益基本相同,但IVERM策略针对跨域映射时的资源分配做了合理规划,并采用较优的拓扑分割方案,使得其计算出的映射方案的映射开销明显低于PolyViNE,从而使得IVERM的实际收益要高于PolyViNE。

图8 IVERM与PolyViNE生成映射方案的开销与实际收益对比 Fig. 8 Comparison of cost and actual profits of embedding schemes which are generated by IVERM and PolyViNE

3.4 接受率

将IVERM策略的接受率与PolyViNE策略以及不支持跨域的G-SP算法[5]进行比较。

图9可见,由于IVERM在映射时产生的映射开销较小,因此其接受率要优于PolyViNE,而这两种跨域映射策略的接受率要明显高于单域映射的G-SP算法。

图9 IVERM、PolyViNE和G-SP生成映射方案的接受率对比 Fig. 9 Comparison of accept rate of embedding schemes which are generated by IVERM , PolyViNE and G-SP

4 结 论

比起单域映射,支持跨域的虚拟网映射策略能够为虚拟网提供更多的底层资源,从而有效提高虚拟网请求的接受率。但由于SP和InP存在着自私性因素,因此跨域映射策略应该在降低映射开销的同时最大程度的提高各方的收益。作者首先从SP的利益出发提出了基于竞价的虚拟网跨域映射控制流程;然后从InP的利益出发设计了基于遗传进化的虚拟网本地映射算法,该算法将本地映射问题转化整数规划模型,并利用遗传算法来进行求解。模型通过引入域节点的概念,实现了虚拟网拓扑分割与映射方案的同步生成,为InP提供了可使其利益最大化的本地映射方案。实验证明,本文提出的跨域映射策略不但在接受率上优于同类型的策略,而且能有效降低映射开销,提高InP的实际收益。

本文提出的跨域映射策略在竞价模型的设计方面仍有待进一步改进。此外,InP的报价策略以及跨域映射时各个InP之间的协商机制是有待研究的问题。

参考文献
[1]
Chowdhury M, Boutaba R. A survey of network virtualization[J]. Computer Networks, 2010, 54(5): 862-876. DOI:10.1016/j.comnet.2009.10.017
[2]
Biao S, Mohammad H, Eui-Nam H. Delivering IPTV service over a virtual network:A study on virtual network topology[J]. Journal of Communications and Networks, 2012, 14(3): 319-335. DOI:10.1109/JCN.2012.6253093
[3]
Jorge C,Javier J.Network Virtualization—A view from the Bottom[C]//Proceedings of the 1st ACM workshop on Virtualized infrastructure systems and architectures.Barcelona:DBLP,2009:73–80.
[4]
Yang Z, Guo Y. An exact virtual network embedding algorithm based on integer linear programming for virtual network request with location constraint[J]. China Communications, 2016, 13(8): 177-183. DOI:10.1109/CC.2016.7563720
[5]
Abdallah J, Ahmed K. Decomposition approaches for virtual network embedding with one-shot node and link mapping[J]. IEEE/ACM Transactions on Networking, 2015, 23(3): 1012-1025.
[6]
Peng Limin. A topology-awareness virtual network reconfiguration algorithm[J]. Journal on Sichuan University(Engineering of Science Edition), 2015, 47(5): 110-115. [彭利民. 一种拓扑感知的虚拟网络重构算法[J]. 四川大学学报(工程科学版), 2015, 47(5): 110-115.]
[7]
Chowdhury M, Rahman M R, Boutaba R. ViNEYard:Virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE Transactions on Networking, 2012, 20(1): 206-219. DOI:10.1109/TNET.2011.2159308
[8]
Mano T,Inoue T,Mizutani K,et al.Reducing dense virtual networks for fast embedding[C]//Proceedings of IEEE INFOCOM 2016.San Francisco:IEEE,2016:10–14.
[9]
Andreas F, Hermann M. Generating virtual network embedding problems with guaranteed solutions[J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 504-517. DOI:10.1109/TNSM.2016.2596802
[10]
Chowdhury M, Samuel F, Boutaba R. PolyViNE:Policy-based virtual network embedding across multiple domains[J]. Journal of Internet Services & Applications, 2013, 4(1): 1-23.
[11]
Werle C, Papadimitriou P, Houidi I. Building virtual networks across multiple domains[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(4): 412-413. DOI:10.1145/2043164
[12]
Mahmud H,Heli A,AHMED K.Network virtualization: Dealing with multiple infrastructure providers[C]//Proceedings of IEEE ICC.Ottawa: IEEE, 2012:5890-5895.
[13]
Fida-E Z,Jin X,Raouf B.Multi-provider service negotiation and contracting in network virtualization[C]//Proceedings of IEEE/IFIP Network Operations and Management Symposium.Osaka:IEEE,2010:471-478
[14]
Zhang M, Yang Q, Wu C. Hierarchical virtual network mapping algorithm for large-scale network virtualisation[J]. IET Communications, 2012, 6(13): 1969-1978. DOI:10.1049/iet-com.2011.0395
[15]
Houidi I, Louati W, Ameur W. Virtual network provisioning across multiple substrate networks[J]. Elsevier Computer Networks, 2011, 55(4): 1011-1023. DOI:10.1016/j.comnet.2010.12.011
[16]
Jia W, Xia J. Research on virtual network embedding across multiple domains[J]. Journal of Electronics & Information Technology, 2016, 38(3): 728-735. [贾伟, 夏靖波. 跨域虚拟网络映射问题研究[J]. 电子与信息学报, 2016, 38(3): 728-735.]
[17]
Zegura E W,Calvert K L,Bhattacharjee S.How to model an internetwork[C]//Proceedings of IEEE Infocom,1996.San Francisco:IEEE ,1996:594-602.