本发明提供了一种多拓扑虚拟网络映射方法。该方法包括四种子算法，这四种子算法分别针对随机型(缺省)、星型、环型、树型拓扑进行了优化。当虚网请求到达时，系统可以通过变量TOPO的取值识别该请求的拓扑，并调用相应的子算法。由于子算法充分利用了相应的拓扑结构特点，因此该多拓扑映射方法大幅提升了底层物理网络资源的使用效率，增加了映射的收入支出比。同时，新的拓扑子算法也可以按照类似模式加入该多拓扑映射方法。本发明提供的方法适用于实验网络、运营商网络等已经或将要使用网络虚拟化技术进行网络分离、资源管理调度或提供定制服务的网络，该方法具有链路映射复杂度低、虚网请求映射成功率高、可扩展性强等特点。
1.一种多拓扑虚拟网络映射方法，在一个时间窗内进行一次虚拟网络映射的步骤包括：A.释放前一个时间窗内离开的虚网请求占用的底层物理网资源，离开的虚网请求包括完成服务的请求和被主动拒绝的请求；虚网请求包含虚网节点请求和虚网链路请求两部分；
B.统计本时间窗内到达的虚网请求，到达的虚网请求包括新到达的请求和重新排队的请求；
C.将步骤B中统计的到达的虚网请求按照其收入(Revenue)从大到小进行排序，然后根据虚网请求者使用的变量TOPO值，对虚网请求的拓扑类型进行识别，然后分别使用相应的随机型，星型，环形，树型拓扑映射算法将到达的虚网请求按顺序映射至底层物理网络，若其中任意一个到达的虚网请求映射成功，即虚网节点和虚网链路同时映射成功，则更新底层物理网络的状态；若映射失败，则将该虚网请求送至等待队列，等待下个时间窗或直接拒绝。
C1)首先进行虚网请求节点映射，将虚网请求按照其收入从大到小进行排序，形成请求队列(Qrequest)；
C2)判断当前请求队列中是否存在虚网请求，如果是，执行步骤C3，如果否，执行步骤C8；
C3)选择当前请求队列中排在首位的虚网请求，根据TOPO的取值0、1、2、3，分别执行下列C3.1、C3.2、C3.3、C3.4子步骤，TOPO取除0、1、2、3的其他值，则使用缺省值TOPO＝0，并执行步骤C3.1；
C3.1)TOPO＝0，将该虚网请求内的虚网节点(Vnode)按照其剩余资源(Available Resource，AR)从大到小排序，形成虚网节点队列(Qv_node)；
C3.2)TOPO＝1，将该虚网请求内的虚网节点(Vnode)按照中心节点排首位、其余节点按照剩余资源(Available Resource，AR)从大到小排序，形成虚网节点队列(Qv_node)；
C3.3)TOPO＝2，将该虚网请求内的虚网节点(Vnode)按照剩余资源(Available Resource，AR)最大节点排首位，其余节点按照环型连接顺序排序，形成虚网节点队列(Qv_node)；
C3.4)TOPO＝3，将该虚网请求内的虚网节点(Vnode)按照上层节点优先、同层节点按照父节点顺序、同一父节点按照剩余资源(Available Resource，AR)从大到小排序，形成虚网节点队列(Qv_node)；
C4)判断当前虚网节点队列中是否存在虚网节点，如果是，执行步骤C5，如果否，则将当前请求队列中排在首位的虚网请求移出请求对列，执行步骤C2；
C5)选择当前虚网节点队列中排在首位的虚网节点，在底层物理网中选择物理网节点(Snode)，选择的物理网节点的CPU资源不小于当前虚网节点队列中排在首位的虚网节点CPU资源；并将满足CPU条件的物理网节点组成物理网节点子集(Ss_node)；
C6)判断物理网节点子集中是否存在物理网节点，如果是，执行步骤C7，如果否，则当前虚网请求队列中排在首位虚网请求映射失败，将该请求移出虚网请求队列，并送至下个时间窗的等待队列或拒绝请求，执行步骤C2；
C7)根据TOPO的取值0、1、2、3，分别执行C7.1、C7.2、C7.3、C7.4子步骤，TOPO取除0、
1、2、3的其他值，则使用缺省值TOPO＝0，并执行步骤C7.1；
C7.1)TOPO＝0，选出当前物理网节点子集中随机型加权剩余资源(General Weighted Available Resource，GWAR)最大的物理网节点，并将当前虚网节点队列中排在首位的虚网节点映射至该物理网节点，将当前虚网节点队列中排在首位的虚网节点移出虚网节点队列，执行步骤C4；
C7.2)TOPO＝1，选出当前物理网节点子集中星型加权剩余资源(Star Weighted Available Resource，SWAR)最大的物理网节点，并将当前虚网节点队列中排在首位的虚网节点映射至该物理网节点，将当前虚网节点队列中排在首位的虚网节点移出虚网节点队列，执行步骤C4；
C7.3)TOPO＝2，选出当前物理网节点子集中环型加权剩余资源(Ring Weighted Available Resource，RWAR)最大的物理网节点，并将当前虚网节点队列中排在首位的虚网节点映射至该物理网节点，将当前虚网节点队列中排在首位的虚网节点移出虚网节点队列，执行步骤C4；
C7.4)TOPO＝3，选出当前物理网节点子集中树型加权剩余资源(Tree Weighted Available Resource，TWAR)最大的物理网节点，并将当前虚网节点队列中排在首位的虚网节点映射至该物理网节点，将当前虚网节点队列中排在首位的虚网节点移出虚网节点队列，执行步骤C4；
C8)开始进行链路映射，将节点映射成功的虚网请求按收入从大到小进行排序，形成请求队列(Qrequest)；
C9)判断当前请求队列中是否存在虚网请求，如果是，执行步骤C10，如果否，当前时间窗的映射算法结束；
C10)选择当前请求队列中排在首位的虚网请求，并将该虚网请求内的虚网链路(Vlink)按照其带宽(BW)从大到小排序，形成虚网链路队列(Qv_link)；
C11)判断当前虚网链路队列中是否存在虚网链路，如果是，执行步骤C12，如果否，则将当前请求队列中排在首位的虚网请求移出请求队列，执行步骤C9；
C12)选择当前虚网链路队列中排在首位的虚网链路，使用K最短路径(K-Shortest)算法依次寻找第1至K条最短路径，这些路径由一条或多条底层物理网链路(Slink)组成，K为大于1的整数，仅保留这K条路径这样的路径：组成路径的所有物理网链路的最低带宽满足当前虚网链路队列中排在首位的虚网链路带宽；保留的路径形成物理网路径子集(Ss_path)；
C13)判断当前物理网路径子集中是否存在物理网路径，如果是，执行步骤C14；如果否，则当前虚网请求队列中排在首位虚网请求映射失败，将该请求移出虚网请求队列，并送至下个时间窗的等待队列或拒绝请求，执行步骤C9；
C14)将当前虚网链路队列中排在首位的虚网链路映射至当前物理网路径子集中的最短路径，将当前虚网链路队列中排在首位的虚网链路移出虚网链路队列，执行步骤C11。
收入是指虚网映射成功获得的利润，根据映射成功的虚网带宽和CPU定义：
其中，BWR是映射成功的虚网带宽，CPUR是映射成功的虚网节点CPU资源，αR和βR是用于调节带宽和CPU的权重系数，下标R指收入Revenue。
AR是针对某底层物理网节点或某虚网请求节点的剩余资源，根据该底层物理网节点或虚网请求节点的剩余CPU资源和与其连接的剩余链路资源定义：AR＝CPUA∑BWA
其中，CPUA是底层物理网节点或虚网请求节点的剩余CPU资源，BWA是与该底层物理网节点或虚网请求节点连接的底层链路剩余带宽资源，下标A指剩余资源(Available Resource，AR)。
所述剩余资源包括：随机型加权剩余资源(General Weighted Available Resource，GWAR)、星型加权剩余资源(Star Weighted Available Resource，SWAR)、环型加权剩余资源(Ring Weighted Available Resource，RWAR)、树型加权剩余资源(Tree Weighted Available Resource，TWAR)：n_general
其中，Corr是针对某底层物理网节点Snode的相关系数，随着Corr增加，拓扑信息的作用得到增强，应设置为Corr>1；指数n_general表示当前虚网请求中已经映射成功并且映射的象节点与Snode有直接连接的虚拟网节点个数，n_general的大小表征了Snode与之前已经映射成功的所有底层物理网络节点的距离；指数n_star表示当前虚网请求的中心节点映射的象节点是否与Snode有直接连接，n_star＝0或1，表征了Snode与中心节点的距离；指数n_ring表示当前虚网请求的环结构中上一个映射成功的虚节点的象节点是否与Snode有直接连接，n_ring＝0或1，表征了Snode与环结构中上一个虚节点的距离；指数n_tree表示当前虚网请求的树结构中父节点的象节点是否与Snode有直接连接，n_tree＝0或1，表征了Snode与树结构中父节点的距离。
一种多拓扑虚拟网络映射方法
技术领域
[0001] 网络虚拟化技术是推动互联网体系架构发展的重要方法之一，其本质是通过抽象、分配、隔离机制在一个公共物理网络上独立地运营多个虚拟子网，各虚拟子网可以使用相互独立的协议体系，并能够根据用户动态变化的需求对整个网络中节点和链路资源进行合理配置，从而增强网络的灵活性与多样性，实现网络的可测可控性，最优化网络资源的分配与调度，提高安全和服务质量、降低运营维护成本，以求根本性地解决互联网现有的僵化、以补丁和更新为主的发展现状。
[0002] 网络虚拟化技术可以用于为新型网络体系结构的研究提供共享物理实验网络的基础，同时它还能够将底层物理设施提供商与网络服务运营商相分离，允许多个运营商的网络共享同一个公共的底层物理网络基础架构(链路、交换节点等)，每个网络都在其中拥有既不受其他网络影响又可以灵活调整的网络资源份额，不同网络运营商可以采用不同的网络协议，提供创新的端到端服务，因此网络虚拟化也很有希望成为一种未来网络的主流运营模式。
背景技术
[0003] 虚拟网络映射问题则是网络虚拟化技术中必不可少的环节，它的主要功能是将用户的虚拟网络请求(Virtual Request)合理地映射至运营商提供的底层物理网络设施(Substrate Network)，映射过程不仅要实现虚拟网络之间的分隔与互不影响，从而保证每个虚拟网络用户的服务质量(QoS)，同时也要尽量合理地分配底层物理网络资源，提高资源利用率。如图1所示。
[0004] 在图1中，两个不同的虚拟网络被映射在底层物理网络上，并向相应的用户提供服务。由于虚拟网络请求拓扑的多样性，以及节点和链路两组限制条件需要同时考虑，使得将多个不同的虚拟网络映射到一个公共底层物理网络成为NP-hard问题。为解决该问题，国外很多研究学者已经提出了一些求解映射匹配次优解的映射方法，但现有算法仅针对随即拓扑的虚网请求进行研究。
[0005] 虚拟网络映射的实现过程可以分为两个步骤：节点映射和链路映射。现有的主要方法是使用贪婪算法进行节点映射，使用K最短路径算法进行链路映射。系统以时间窗为单位，一个时间窗内的所有虚拟网络请求将按照其收入(Revenue)排序，从规模最大的请求开始进行映射。若映射成功，则更新底层物理网络状态；若失败，则将请求放入等待队列；或直接拒绝该请求。
[0006] 其中，对每个虚拟网络请求的映射步骤如下：
[0007] 首先进行节点映射：对虚拟网络请求中的每个虚网节点(Vnode)，使用贪婪算法寻找拥有最大剩余资源(Available Resource，AR)的底层物理网节点(Snode)；若该Snode满足该Vnode的CPU限制，则该Vnode映射成功；若对某Vnode，没有满足要求的Snode，则节点映射失败；若所有Vnode映射成功，则节点映射完成。
[0008] 节点映射完成后进行链路映射：对虚拟网络请求中的每条虚网链路(Vlink)，确定其两端点Vnode1、Vnode2映射至底层物理网络中的Snode1、Snode2；使用K最短路径算法寻找Snode1、Snode2之间的第1-K条最短路径；若其中某条路径满足该Vlink的带宽要求，则该Vlink映射成功；若所有K条路径均不满足带宽要求，则链路映射失败；若所有Vlink映射成功，则链路映射完成。
[0009] 在现阶段的虚拟网络映射算法中，仅考虑了随机拓扑的虚网请求，而在实际应用中，虚网请求往往是针对具体的需求而生成的，因此具有相应的拓扑结构。例如内容分发网络(CDN)一般是星型拓扑，交互式网络电视(IPTV)在进行多播分发时一般使用树型拓扑等等。由于没有考虑到使用拓扑信息对虚网映射算法进行专门优化，现有虚网映射算法对底层物理网络资源的利用率较低，即系统的支出(Cost)较高，收入支出比(Revenue/Cost)较低。
发明内容
[0010] 本发明分析了虚网拓扑信息对虚网映射算法的影响，发现在虚网节点映射部分，如果可以针对不同的网络拓扑进行优化，则后续链路映射的复杂度可以大大简化，并可以提高底层物理网资源的利用率。
[0011] 本发明根据该出发点设计了一种多拓扑虚网映射方法，为虚网映射问题引入了拓扑信息进行优化。该方法包括四种子算法，当相应拓扑的虚网请求到达时，系统可以识别该拓扑并调用相应的子算法。这四种子算法分别针对星型拓扑、环型拓扑、树型拓扑、随机拓扑进行了优化，经过优化的四种算法分别使用了随机型加权剩余资源(General Weighted Available Resource，GWAR)、星型加权剩余资源(Star Weighted Available Resource，SWAR)、环型加权剩余资源(RingWeighted Available Resource，RWAR)、树型加权剩余资源(Tree Weighted Available Resource，TWAR)作为节点映射的优化目标，充分利用了这些拓扑结构的特点，使映射结果使用底层物理网络资源所付出的支出大幅降低，因而大幅提高了收入支出比。
[0012] 本发明涉及的定义：
[0013] 1)收入(Revenue)
[0014] Revenue是指虚网映射成功获得的利润，根据映射成功的虚网带宽和CPU定义：
[0015] Revenue＝αR∑BWR+βR∑CPUR
[0016] 其中，BWR是映射成功的虚网带宽，CPUR是映射成功的虚网节点CPU资源，αR和βR是用于调节带宽和CPU的权重系数，也可以理解为运营商提供虚网服务时带宽和CPU资源的单价，下标R指收入。
[0017] 2)支出(Cost)：
[0018] Cost是指虚网映射成功支出的费用，根据映射使用的底层物理网络带宽和CPU定义：
[0019] Cost＝αC∑HOPS·BWC+βC∑CPUC
[0020] 其中，BWC是映射使用的底层物理网络带宽，HOPS是一条虚拟链路在底层物理网络上占用的实际链路数量，CPUC是映射使用的底层物理网络节点CPU，αC和βC是用于调节带宽和CPU的权重系数，也可以理解为运营商提供虚网服务时带宽和CPU资源的成本,下标C指Cost。
[0021] 3)剩余资源(Available Resource，AR)：
[0022] AR是针对某底层物理网节点或某虚网请求节点的剩余资源，根据该底层物理网节点或虚网请求节点的剩余CPU资源和与其连接的剩余链路资源定义：
[0023] AR＝CPUA∑BWA
[0024] 其中，CPUA是底层物理网节点或虚网请求节点的剩余CPU资源，BWA是与该底层物理网节点或虚网请求节点连接的底层链路剩余带宽资源，下标A指AR(Available Resource，剩余资源)。
[0025] 本发明，一是通过设计多拓扑虚网映射方法，为虚网映射问题引入了多拓扑信息进行优化，该方法可以识别虚网请求的拓扑，并调用相应的子算法，同时该方法具有可扩展性，新型拓扑虚网请求算法可以很容易加入该方法。二是提出了针对四种拓扑结构的虚网请求分别进行优化的四种虚网映射子算法，起到了在相应拓扑的虚网请求到达时提升虚网映射算法的收入支出比的作用，并作为多拓扑虚网映射方法的组成部分。
[0026] (1)多拓扑虚网映射方法结构：
[0027] 如上所述，现有的虚网映射算法不区分到达虚网请求的拓扑，统一使用相同的虚网映射算法。但在实际情况下，虚网请求在生成时为了实现具体功能一般会具有特殊的拓扑结构，同时这种拓扑结构是虚网请求者预先知道的，因此本发明提出由虚网请求者使用变量TOPO(随机型/缺省0，星型1，环形2，数型3)对自己的虚网请求作出标识，多拓扑映射方法可以识别该标识，并调用相应的虚网映射算法。
[0028] 该方法还具有可扩展性，目前使用随机拓扑映射算法作为缺省算法，处理随机拓扑请求和未识别标识的请求，因此新的虚网拓扑映射算法可以依照该结构加入系统，并从缺省算法中分担相应的映射任务。
[0029] (2)多拓扑虚网映射算法：
[0030] 如上所述，现有的虚网节点映射流程中，在寻找底层物理网节点时，衡量标准是节点的剩余资源，该衡量标准仅考虑了底层物理网节点的剩余资源大小，没有考虑节点之间的拓扑连接关系，因此本发明提出使用四种加权剩余资源作为新优化目标，分别对随机型拓扑、星型拓扑、环型拓扑和数型拓扑的虚网请求到达情况下的虚网映射算法进行优化，这四个新的优化目标分别为随机型加权剩余资源(General Weighted Available Resource，GWAR)、星型加权剩余资源(Star Weighted Available Resource，SWAR)、环型加权剩余资源(Ring Weighted Available Resource，RWAR)、树型加权剩余资源(Tree Weighted Available Resource，TWAR)：
[0031] GWAR＝Corrn_general·CPUA∑BWA
[0032] SWAR＝Corrn_star·CPUA∑BWA
[0033] RWAR＝Corrn_ring·CPUA∑BWA
[0034] TWAR＝Corrn_tree·CPUA∑BWA
[0035] 其中，Corr是针对某底层物理网节点Snode的相关系数，随着Corr增加，拓扑信息的作用得到增强，应设置为Corr>1。指数n_general表示当前虚网请求中已经映射成功并且映射的象节点与Snode有直接连接的虚拟网节点个数，n_general的大小表征了Snode与之前已经映射成功的所有底层物理网络节点的距离。指数n_star表示当前虚网请求的中心节点映射的象节点是否与Snode有直接连接，n_star＝0或1，表征了Snode与中心节点的距离。指数n_ring表示当前虚网请求的环结构中上一个映射成功的虚节点的象节点是否与Snode有直接连接，n_ring＝0或1，表征了Snode与环结构中上一个虚节点的距离。指数n_tree表示当前虚网请求的树结构中父节点的象节点是否与Snode有直接连接，n_tree＝0或1，表征了Snode与树结构中父节点的距离。
[0036] 在使用了这四种加权剩余资源作为优化目标以后，底层物理网节点剩余资源和链路映射的拓扑问题同时得到了考虑，显著降低了链路映射的复杂度，降低了系统支出，提升了底层物理网链路资源的利用率，提升了系统的收入支出比。
附图说明
[0037] 图1虚拟网络映射问题
[0038] 图2时间窗模式下的虚网映射总体流程
[0039] 图3多拓扑虚网映射方法的具体步骤
[0040] 图4步骤C3
[0041] 图5步骤C7
[0042] 实施方式
[0043] 本发明的具体操作流程的核心是时间窗，一个时间窗内进行一次虚拟网络映射，虚网映射在时间窗模式下的流程，如图2所示：
[0044] A.释放前一个时间窗内离开的虚网请求占用的底层物理网资源，离开的虚网请求包括完成服务的请求和被主动拒绝的请求；虚网请求包含虚网节点请求和虚网链路请求两部分；
[0045] B.统计本时间窗内到达的虚网请求，到达的虚网请求包括新到达的请求和重新排队的请求；
[0046] C.将步骤B中统计的到达的虚网请求按照其收入(Revenue)从大到小进行排序，然后根据虚网请求者使用的变量TOPO值，对虚网请求的拓扑类型进行识别，然后分别使用相应的随机型，星型，环形，树型拓扑映射算法将到达的虚网请求按顺序映射至底层物理网络，若其中任意一个到达的虚网请求映射成功，即虚网节点和虚网链路同时映射成功，则更新底层物理网络的状态；若映射失败，则将该虚网请求送至等待队列，等待下个时间窗或直接拒绝。
[0047] 该虚网映射流程保证了虚网请求可以实时处理，并且虚网请求的准入机制可以通过调节参数进行控制(如推迟、拒绝虚网请求)。
[0048] 该虚网映射流程中的核心步骤是将时间窗内的一组虚网请求映射至底层物理网络(步骤C)，这个映射过程可以用下面的流程进一步详细描述，如图3-5所示
[0049] C1)首先进行虚网请求节点映射，将虚网请求按照其收入从大到小进行排序，形成请求队列(Qrequest)；
[0050] C2)判断当前请求队列中是否存在虚网请求，如果是，执行步骤C3，如果否，执行步骤C8；
[0051] C3)选择当前请求队列中排在首位的虚网请求，根据TOPO的取值0、1、2、3，分别执行下列C3.1、C3.2、C3.3、C3.4子步骤，TOPO取除0、1、2、3的其他值，则使用缺省值TOPO＝0，并执行步骤C3.1；
[0052] C3.1)TOPO＝0，将该虚网请求内的虚网节点(Vnode)按照其剩余资源(Available Resource，AR)从大到小排序，形成虚网节点队列(Qv_node)；
[0053] C3.2)TOPO＝1，将该虚网请求内的虚网节点(Vnode)按照中心节点排首位、其余节点按照剩余资源(Available Resource，AR)从大到小排序，形成虚网节点队列(Qv_node)；
[0054] C3.3)TOPO＝2，将该虚网请求内的虚网节点(Vnode)按照剩余资源(Available Resource，AR)最大节点排首位，其余节点按照环型连接顺序排序，形成虚网节点队列(Qv_node)；
[0055] C3.4)TOPO＝3，将该虚网请求内的虚网节点(Vnode)按照上层节点优先、同层节点按照父节点顺序、同一父节点按照剩余资源(Available Resource，AR)从大到小排序，形成虚网节点队列(Qv_node)；
[0056] C4)判断当前虚网节点队列中是否存在虚网节点，如果是，执行步骤C5，如果否，则将当前请求队列中排在首位的虚网请求移出请求对列，执行步骤C2；
[0057] C5)选择当前虚网节点队列中排在首位的虚网节点，在底层物理网中选择物理网节点(Snode)，选择的物理网节点的CPU资源不小于当前虚网节点队列中排在首位的虚网节点CPU资源；并将满足CPU条件的物理网节点组成物理网节点子集(Ss_node)；
[0058] C6)判断物理网节点子集中是否存在物理网节点，如果是，执行步骤C7，如果否，则当前虚网请求队列中排在首位虚网请求映射失败，将该请求移出虚网请求队列，并送至下个时间窗的等待队列或拒绝请求，执行步骤C2；
[0059] C7)根据TOPO的取值0、1、2、3，分别执行C7.1、C7.2、C7.3、C7.4子步骤，TOPO取除0、1、2、3的其他值，则使用缺省值TOPO＝0，并执行步骤C7.1；
[0060] C7.1)TOPO＝0，选出当前物理网节点子集中随机型加权剩余资源(General Weighted Available Resource，GWAR)最大的物理网节点，并将当前虚网节点队列中排在首位的虚网节点映射至该物理网节点，将当前虚网节点队列中排在首位的虚网节点移出虚网节点队列，执行步骤C4；
[0061] C7.2)TOPO＝1，选出当前物理网节点子集中星型加权剩余资源(Star Weighted Available Resource，SWAR)最大的物理网节点，并将当前虚网节点队列中排在首位的虚网节点映射至该物理网节点，将当前虚网节点队列中排在首位的虚网节点移出虚网节点队列，执行步骤C4；
[0062] C7.3)TOPO＝2，选出当前物理网节点子集中环型加权剩余资源(Ring Weighted Available Resource，RWAR)最大的物理网节点，并将当前虚网节点队列中排在首位的虚网节点映射至该物理网节点，将当前虚网节点队列中排在首位的虚网节点移出虚网节点队列，执行步骤C4；
[0063] C7.4)TOPO＝3，选出当前物理网节点子集中树型加权剩余资源(Tree Weighted Available Resource，TWAR)最大的物理网节点，并将当前虚网节点队列中排在首位的虚网节点映射至该物理网节点，将当前虚网节点队列中排在首位的虚网节点移出虚网节点队列，执行步骤C4。
[0064] C8)开始进行链路映射，将节点映射成功的虚网请求按收入从大到小进行排序，形成请求队列(Qrequest)；
[0065] C9)判断当前请求队列中是否存在虚网请求，如果是，执行步骤C10，如果否，当前时间窗的映射算法结束；
[0066] C10)选择当前请求队列中排在首位的虚网请求，并将该虚网请求内的虚网链路(Vlink)按照其带宽(BW)从大到小排序，形成虚网链路队列(Qv_link)；
[0067] C11)判断当前虚网链路队列中是否存在虚网链路，如果是，执行步骤C12，如果否，则将当前请求队列中排在首位的虚网请求移出请求队列，执行步骤C9；
[0068] C12)选择当前虚网链路队列中排在首位的虚网链路，使用K最短路径(K-Shortest)算法依次寻找第1至K条最短路径，这些路径由一条或多条底层物理网链路(Slink)组成，K为大于1的整数，仅保留这K条路径这样的路径：组成路径的所有物理网链路的最低带宽满足当前虚网链路队列中排在首位的虚网链路带宽；保留的路径形成物理网路径子集(Ss_path)；
[0069] C13)判断当前物理网路径子集中是否存在物理网路径，如果是，执行步骤C14；如果否，则当前虚网请求队列中排在首位虚网请求映射失败，将该请求移出虚网请求队列，并送至下个时间窗的等待队列或拒绝请求，执行步骤C9；
[0070] C14)将当前虚网链路队列中排在首位的虚网链路映射至当前物理网路径子集中的最短路径，将当前虚网链路队列中排在首位的虚网链路移出虚网链路队列，执行步骤C11。
