论文研究-基于归一化割原则的光网络虚拟化映射策略 .pdf

所需积分/C币:5 2019-08-21 07:08:14 799KB .PDF
收藏 收藏
举报

基于归一化割原则的光网络虚拟化映射策略,曹亚松,赵峰,随着互联网的高速发展,传统光网络架构中结构臃肿、资源调度能力差、网络资源利用效率低下等缺陷也日益暴露出来,而光网络的虚拟
山国武花论文在丝 更加有效。 资源描述模型 在本文中,我们使用无向图G(V,E”来对虚拟光网终请求进行描述,其中V"表示虚拟 光网络请求节点的集合,E表小虚拟光请求链路的集合。对于每个请求节点v”∈W,都要 求分配一定的计算能力c;对于每条请求链路e∈E,都需要占用一定的链路带宽B 同样地,对于底层的灵活频谱光网络,我们使用无向图石(W,E5)米进行描述,其中W表 示底层光网终节点的集合,E表示底层光网终链路的集合。我们设定每一个底层光网终节点 υ∈V都具有ε的计算能力;每一条底层光网络链路e∈E°,都具有B个弹性频谱间隙。 为了进一步描述频谱的使用情况,我们采用一个长度为B的链路频谱状态向量b来表小链 路的频谱使用情况。其中,若第个频譜问隙未被使用,则b[为;若第个频谱冋隙 凵被使用,则b[为。 我们定义在一条光纤链路上,若由一个或多个在频域上连续并且空闲的频谱间隙组成 的集合中频谱湝间隙的数量不能再继续增加,则对于该集合中的频谱间隙组成的频谱块,我们 称之为连续频谱块( 其中某条链路上连续频谱块的数量可采用公式()加以计算: E-1 ICsB=-=>b5[i] bsilbsli+1 t=1 为了表示某条链路上频谱的可用程度,我们定义频谱可用度F, () 虚拟化映射算法 归一化割原则概述 归一化割原则是由和提出的一种无监督的图分割技术,它与 等聚关 的方法不同,该方法无需复杂的初始化过程,并且作为一种仝局准则,能够同时满足最大化 同一子图内节点的相似性和最小化不同」图之间的节点的相似性的要求。 在一幅加权无向图G=(VE)中,我们可以通过删除掉图中一些边的方式,来将该图分 割成两个彼此之间不相连的点集和,这两个部分的不相似程度可以使用之前连接在两部 分之间而现在被删去的所有边的权的总和来表示,并且我们将这些边的权的总和称之为割 集,即 Cut(A,B)= ∑ wli j IEAJJEB () 其中w(刀表示节点和节点之间的边的权值,即两点之间的相似程度 对于一幅图来说,最优化的划分方法即是使得割集的值最小,但是因为割集的大小和割 集中边的数目成比例,因此若只是求割集的最小值的话,往往会导致节点被划分成一个个孤 立的单独节点,而这并不是我们需要的结果。针对这个缺点,提出了一种新的度量相似 山国武花论文在丝 程度的方法,即归化割原则 Cut(a,b) Cut(A,B) NCut(A,B) asSoC(A, V) assoc(B, V) 其中 assoc(AV)=2eAew(L.v)表示子图中的节点与整个图中所有节点之间总的 相似程度, a5500(B,)=∑eBew(,表示子图中的节点与整个图中所有节点之间总 的相似程度 根据归一化割的原则,在图的划分方法中寻找不同分组之间相似程度最小化与寻找同 分组之内相似程度最大化是等效的,分割结果可以同时满足这两个要求。 采用归一化割原则来对图进行划分,实质上是求解使得MCut(AB)最小的割集的过程 为此我们需要首先设一个N=Ⅳ维的标记向量,用来标记哪些节点被划分在同一个子图内。 我们规定若节点属于,则x=1,否则x:=-1;a=∑w()表示节点与其他相连节 点之间相似程度的总和。则MCut(A,B可以重写成公式()的形式, Cut(A, B) Cut(A,B) 2x20,x: c0 -Wi xj NCut(A,B) ∑x0x}>0-W;x:写 assoc(A, V) assoc(B, v 构建N×N大小的对角矩阵与对称矩阵,其中D=dag(ad2,d2,,dx) W(tn=Wy这样我们可以把寻找最小割的问题简化为求解下述公式最小解的门题 y(D-W)y minCUt()=miny yDy () 其中是对的连续逼近,定义为 y=(1+x) ∑x>正 (1-x),且y 假如只选取实数解的话,则上述问题可以转化为求解广义特征值的问题 (D-W)y= ADy () 在该广义特征值问题中,对应第二最小特征值的特征向量符合约束条件,故我们通过该 特征向量的中各个元素的值作为对图进行划分的依据。由于特征向量中的每个元素通常都是 连续值,因此我们需要定义一个临界值,来作为节点划分的依据。这里我们选择该特征向量 元素的中值作为分离点,大于该值的节点属于子图,小于该值的节点属于子图 映射算法流程 第一阶段:得到计算子图序2≈-° mputcrtof° 山国武技论文在丝 将节点之间计算能力的相 似程度作为权值,构建整 个网络的无问图作为输入 根据权值大小,基于归 化割原则将输入的图 划分为子图A和子图B 否 子图中节点数量是否 满足临界条件 是 将该子图存入计 算子图序列中 算序列中每个计算子图 的计算能力值,并按照该 值从大到小的顺序,对计 算子图序列排序 输出经过排序后的 算子图序列 图流程图(步骤一) 注:)节点之间的权值Wb= nmu4ctR(门为, (e≠e) 5=E。 22t25LO? () )计算子图规模参数a取,计算子图中的节点数目需满足N≤ alvo )定义计算子图中所有节点的平均值作为该计算子图的计算能力值 FLB-EETMYUEEELEM rub-cemyutatien sub-computation i 山国武技论文在丝 第阶段:得到链路子图序、 将节点之间链路的频谱可 用度作为权值,构建整个 网络的无向图作为输入 根据权值大小,基于归 化割原则将输入的图 划分为子图A和子图B 否 子图中节点数量是否 满足临界条件 是 将该子图存入链 路了图序列中 计算序列中每个链路子图 的频谱可用度,并按照该 值从大到小的顺序,对计 算子图序列排序 输出经过排序后的 链路子图序列 图流程图(步骤∵ 注:)节点之间的权值vb- comutation(4为, Wsxb-link (i,j)=FS )链路子图规模参数β取,子图中的节点数目需满足Mb≤B|r )定义链路子图中所有链路的频谱可用度的平均值作为该链路子图的频谱可用度 vi∈umk 5mE-L 5 sub-iinkt 山国武技论文在丝 第三阶段:遄历计算子图序列Ac 与链路子图序列A 获取可映射 s1a-linR 子图G 三b sub-refLecti-'-3ub-reflecti- 并检测是否可以承载虚拟光网终 请求。 设置变量ⅰ=1,j=1 选取计算子图序列 将变量加 →中,排序为第位的 计算了图 选取链路子图序列 将变量j加 中,排序为第j位的 链路子图 两图相交,得 到可映射子图 该可映射子图是否能够承一是→该请求映射成功 否 载虚拟光网络请求 否 否 锩路子图序列中的子图 是否全部取完 是 计算子图序列中的子图 是否全部取完 该请求映射失败 图流程图(步骤三) 注:)通过求交集的方式获得可映射子图 ≤ sub-reflecti-j5ub-computationu n usub-link j )若公式()成立,则该映射子图可以承载虚拟光网络请求 G(Vr, E)EGSui-reflecti-j15ub-reflecti-ysub-reflecti-j 5 山国武花论文在丝 算法仿真 对照算法概述 为了更好的评价基于归·化割原则的光网络虚拟化策略的效果,在仿真过程中我们设置 了相应的对照组算法基于最短路的贪婪算法和单一计算资源容量算法 在基于最短路的贪婪算法中,每个到来的虚拟光网络请求都会被拆分为节点映射与 链路欥射两个阶段来进行运算,在节点映射阶段,首先对底层光网终中的节点按照计算能力 的人小来进行排序,然后选取计算能力最人的W个节点依次映射,节点映射结束后进入链 路映射阶段,对于每条虚拟链路,首先需要找到承载该虚拟链路两端虚拟节点旳底层物理节 点,然后在两端的物理节点之冋使用最短路算法来计算两者之冋的路径,并在该路径中 的每条底层链路上分配相应的频谱资源。鉴于在该算法中,网络资源的分配被分为节点映射 与链路映射两个阶段,因此,请求被阻塞的情况也会分别发生在这两个阶段。若在节点映射 过程中,无汯找到满足虚拟节点计算能力需求的底层节点,则该请求被阻塞;若已经完成节 点映射过程,而在链眳映射过程中,无法找到能够承载虚拟节点之间的虚拟链路对频谱资源 的需求的底层路径,则该请求被阻塞。 对于单一计算资源容量算法,则是在基于归一化割原则的虚拟策略上进行了一定的改 变,主要差别在于在该算法中,我们只按照计算能力的人小来对底层光网络进行划分,即只 需要求出计算子图序列,即将计算子图序列中的所有计算子图作为可映射子图。因此,若计 算子图序列中中所有的计算」图都无法承载虚拟光网络清求G(W,E),则该请求被阻塞。 在仿貞中,我们使用阻塞率作为主要指标,来比较不同算法之间的性能。其中阻隽率衣 示被阻塞的虚拟光网络请求占这段时间内总共的光网络请求的比例,即 Dc配 Ratepiock Nsam 其中 Nal表示在一次仿真过程中被阻塞的请求数量,Nxm表示这段时间内所有的请求 数量。 仿真环境设置 在彷貞中,我们采用网终拓扑生成器随机生成拓扑网络来模拟底层光网络的结构, 并比较不同算法在该种网络结构下的性能。其中在随机拓扑光网络中,我们假设每条链路的 长度都是 每个节点总的计算能力是计算单位,每条链路上总的可用频谱间隙是 个。根据此设置,我们总共生成了三种规模的随机拓扑网终,如图图所示,节点 个数分别是 和,同时在同一个随机拓扑网络中的每两个节点之间存在链路的概率 设置为 山国武技论文在丝 图随机拓扑网终(节点) 图随机拓扑网终(节点) 山国武技论文在丝 图随机扑网丝(节点) 对于虚拟光网络请求,主要参数包括虚拟节点所需的计算资源、虚拟链路所需的频谱资 源以及整个虚拟光请求的拓扑结构。其中虚拟节点所需的计算资源以及虚拟链路所需的频谱 资源,在数量上均服从从到的平均分布;对于虚拟光网络请求整体的拓扑结构,我们 主要采用最常见的节点结构和节点结构,具体结构如图所示,并且假设每种节点结构 出现的概率都相同 图虚拟光网络请求拓扑结构 仿真结果与分析 整个仿真过程持续个时间单位,其中在每个时间单位中到来的虚拟光网终的请求 数量服从参数为λ的泊松分布,对于每个请求所需要分配的资源占用的时间单位服从服从参 数为μ的负指数分布,因此,我们定义该网络所承载的负载量 Erlangs为, Erlangs=λx

...展开详情
试读 12P 论文研究-基于归一化割原则的光网络虚拟化映射策略 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-基于归一化割原则的光网络虚拟化映射策略 .pdf 5积分/C币 立即下载
1/12
论文研究-基于归一化割原则的光网络虚拟化映射策略 .pdf第1页
论文研究-基于归一化割原则的光网络虚拟化映射策略 .pdf第2页
论文研究-基于归一化割原则的光网络虚拟化映射策略 .pdf第3页

试读结束, 可继续读1页

5积分/C币 立即下载 >