[发明专利]一种多播虚拟网络的抗毁性映射方法

摘要

本发明公开了一种多播虚拟网络的抗毁性映射方法，根据多播虚拟网络中各叶子节点可接入的底层数据中心的区域要求得到每个底层数据中心可覆盖的叶子节点集合，采用最小集合覆盖算法得到以最小集合数覆盖所有叶子节点的集合方案，以对应的底层数据中心进行叶子节点的映射，同一个底层数据中心覆盖的叶子节点共享节点保护资源；将根节点可接入的底层数据中心作为备选底层数据中心，对于每个备选底层数据中心进行一次链路映射，同一个底层数据中心覆盖的叶子节点共享保护路径，链路映射完成后选择每个备选底层数据中心对应的链路映射方案中总资源消耗量最小的作为最佳链路映射方案。本发明针对多播虚拟网络实现了低成本的抗毁性映射。

主权项

一种多播虚拟网络的抗毁性映射方法，其特征在于，包括以下步骤：S1：记多播虚拟网络中根节点为v，叶子节点集合为VN，各节点可接入的底层数据中心集合为NF，根节点v可接入的底层数据中心的集合为Loc(v)，根据多播虚拟网络中各叶子节点vi可接入的底层数据中心的区域的要求，i为叶子节点的序号，得到每个叶子节点vi可接入的底层数据中心的集合Loc(vi)，以及每个底层数据中心Nj可覆盖的叶子节点集合Cov(Nj)，vi∈VN，Nj∈NF；S2：采用最小集合覆盖算法求得集合Cov(Nj)中以最小集合数覆盖所有叶子节点的集合方案，如果得到两个以上等效的集合方案，则选择一个集合方案作为执行集合方案，对应的底层数据中心集合为NE，包含的集合为Cov(Nx)，Nx∈NE；遍历执行集合方案中的各个集合，对于覆盖相同叶子节点的集合，删除叶子节点数量较小的集合中的相同叶子节点，最终得到的执行集合方案包含的集合为Cov_n(Nx)，Nx∈NE；S3：依次将步骤S2得到的执行集合方案中每个集合Cov_n(Nx)覆盖的叶子节点映射到相应的底层数据中心Nx上，其中节点保护资源需求等于覆盖的叶子节点资源需求中的最大值，计算各底层数据中心Nx映射叶子节点的节点资源消耗量Cost(Nx)；S4：将根节点v可接入的底层数据中心Ny作为备选底层数据中心，Ny∈Loc(v)，计算根节点v的节点资源消耗量Cost(Ny)；S5：对于不同的备选底层数据中心Ny，将步骤S2得到的每个集合Cov_n(Nx)覆盖的叶子节点vi到根节点v的虚拟链路ei按链路资源需求降序排列，依次对每个虚拟链路ei进行映射，映射方法为：S5.1：初始化所有底层链路l的权重Weight(l)＝1，如果虚拟链路ei是当前集合Cov_n(Nx)中的第一条虚拟链路，进入步骤S5.2，如果不是，进入步骤S5.3；S5.2：利用链路分离路径对算法计算出两条满足多播虚拟网络资源要求和时延要求的链路分离的一对底层路径，其中可用资源多的一条作为工作路径Pw(i)，另外一条作为保护路径Pb(i)，工作路径与保护路径的总链路资源消耗量即为虚拟链路资源消耗量Cost(ei)，记录虚拟链路资源消耗量Cost(ei)和映射信息，映射信息包括虚拟链路ei的工作路径和保护路径，更新已占用的底层链路l的权重 Weight(l)＝∞，l∈Pw(i)∪Pb(i)；S5.3：根据底层链路l的权重Weight(l)利用最短路算法计算底层路径，如果计算成功，则将该底层路径作为其工作路径Pw(i)，保护路径与第一条虚拟链路相同，其虚拟链路资源消耗量Cost(ei)为工作路径的链路资源消耗量，记录虚拟链路资源消耗量Cost(ei)和映射信息，更新已占用的底层链路l的权重Weight(l)＝∞，l∈Pw(i)；如果计算不成功，则进入步骤S5.2映射其工作路径和保护路径；S6：重新初始化所有底层链路l的权重Weight(l)＝1，计算步骤S5得到的所有底层路径的时延，其中最大时延记为Dmax，得到时延窗口T＝[Dmax‑CDV,Dmax]，CDV是多播虚拟网络的时延抖动约束，如果有底层路径的时延不在时延窗口T的范围内，则说明该底层路径不符合时延抖动要求，进入步骤S7，如果所有底层路径的时延都在时延窗口T的范围内，则说明所有底层路径符合时延抖动要求，进入步骤S8；S7：对于时延抖动要求不符合的底层路径，根据映射信息得到与其分离的所有底层路径，这些底层路径的链路集合记为S，重新设置权重Weight(l)＝∞，l∈S，通过前K条最短路径算法找到K条最短底层路径，按时延升序排列，选取满足时延窗口T的时延最短的底层路径作为新底层路径，对原底层路径进行更新，同时更新其对应的虚拟链路资源消耗量Cost(ei)和映射信息，进入步骤S8；S8：根据节点资源消耗量和虚拟链路资源消耗量计算每个备选底层数据中心Ny对应的总资源消耗量TotalCosty，选择总资源消耗量最小的备选底层数据中心，将其对应的链路映射方案作为最佳链路映射方案进行链路映射，虚拟资源映射结束。