基于最短路径介数的虚拟网络快速拓扑设计

© 2014.由Elsevier B.V.出版。信息工程研究院负责评选和同行评议可在www.sciencedirect.com上在线获取ScienceDirectIERI Procedia 10（2014）105 - 1112014未来信息工程基于最短路径介数的虚拟网络快速拓扑设计浦山康弘a，橘拓二aa日本福井县文京3-9- 1福井大学工学研究生院摘要近来，网络虚拟化技术作为新一代网络技术之一已经引起了相当大的关注。为了使虚拟网络的拓扑结构能够快速变化，本文提出了一种基于最短路径介数的虚拟网络构造方法。在我们提出的方法中，首先，服务提供商接收用户的请求，重新配置所构建的虚拟网络。在这种情况下，服务提供商基于最短路径介数快速地重新配置所构建的虚拟网络的拓扑。我们评估我们所提出的方法的性能与仿真，我们表明我们所提出的方法的有效性。© 2014由Elsevier B.V.发布 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究院负责评选和同行评议关键词：虚拟网络;最短路径介数;鲁棒性;拓扑设计;重构;1. 介绍近来，网络虚拟化技术作为新一代网络技术之一已经吸引了相当多的关注。在网络虚拟化技术中，可以利用CPU、内存、带宽等物理网络资源的一部分，在物理网络上构建虚拟网络。这里，对于网络虚拟化，重要的是考虑在物理网络上应该如何构建多个虚拟网络。这是因为物理网络中可用网络资源的量是有限的，虚拟网络必须共享有限的资源。因此，人们研究了一些构建虚拟网络的方法[1]。2212-6678 © 2014由Elsevier B. V.发布 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究所负责的选择和同行评审106Yasuhiro Urayama and Takuji Tachibana/IERI Procedia 10（2014）105为了构建更多的虚拟网络，[2]提出了一种可以在节点和链路上保持负载平衡的虚拟网络构建方法。此外，[3]还提出了另一种虚拟网络构建方法。在该方法中，在物理网络上构建虚拟网络，其中已经利用了诸如现有因特网服务的传统数据传输服务。这里，传统服务具有高优先级，并且必须避免这些服务的质量降低。在这种情况下，期望在物理网络上构建虚拟网络，以便不降低这些质量。因此，在[3]中提出的方法利用用于虚拟网络构造的接纳控制。通过该接纳控制，仅当物理网络的鲁棒性满足构造条件时，才能够构造新的虚拟网络。注意，当物理网络的使用结束时，一些构建的虚拟网络被返回到物理网络。此外，可以通过使用从用户返回的网络资源来连续地构造新的虚拟网络。因此，每个节点和链路上的可用网络资源的量随时间变化。因此，为了保持网络资源的有效利用，一些方法来执行虚拟网络的拓扑结构重新设计进行了研究。[4]提出了一种利用路径分裂和路径迁移的虚拟网络的构建方法。在该方法中，在物理网络上构造虚拟网络，使得通过使用路径分裂和路径迁移，来自用户的报酬变为最大。特别地，通过使用路径迁移，周期性地重新设计所构造的虚拟网络的拓扑。[5]提出了一种考虑拓扑变化的虚拟网络构建方法。在该方法中，每次虚拟网络返回到物理网络时，已经构建的拓扑被最佳地重新设计。由于该方法考虑了拓扑改变的代价，因此不改变服务周期短的拓扑。这里，[3]中的方法没有考虑已经构建的虚拟网络的拓扑变化。在该传统方法中，如果用户请求虚拟网络的拓扑改变，则必须将拓扑构造为新的请求。这是因为没有考虑虚拟网络的重新配置。结果，由于利用KMB算法，改变拓扑需要很长时间。这可能会导致一些节点和链路上的拥塞，浪费网络资源。因此，在本文中，我们提出了一种新的虚拟网络的建设方法，以迅速改变拓扑结构。在我们所提出的方法中，当从用户接收到关于拓扑变化的请求时，服务提供商尝试基于最短路径介数来改变拓扑。在我们提出的方法中，拓扑结构的变化是完成与虚拟网络的部分变化。因此，拓扑结构可以通过使用我们提出的方法迅速改变。我们通过仿真评估了我们提出的方法的性能，并将其性能与传统方法的性能进行了比较[3]。本文的其余部分组织如下。第二节介绍相关工作。第3节详细介绍了我们提出的方法。第四节给出了一些数值例子，第五节给出了结论。2. 相关工作2.1 基于网络健壮性在本节中，我们将介绍一种基于网络鲁棒性的虚拟网络构建方法。在该方法中，首先，用户向服务提供商发送请求。这里，该请求包括虚拟网络中应该包括的节点的集合和虚拟网络中应该需要的资源量。服务提供商收到用户的请求后，用KMB算法设计出满足用户KMB算法由一个Yasuhiro Urayama and Takuji Tachibana/IERI Procedia 10（2014）105107Dijkstra算法和Prim的MST（最小生成树）算法。在完成虚拟网络的拓扑设计之后，服务提供商在向用户提供虚拟网络时检查物理网络的鲁棒性。在这里，物理网络的鲁棒性是通过使用网络关键性来评估的[7]。然后，如果可以保持物理网络的鲁棒性，则构造设计的虚拟网络并将其提供给用户。否则，由于物理网络的鲁棒性下降，用户的请求被拒绝。(a) 节点i的跳数di和权重wi。（b）最短路径介数。图1.最短路径介数的计算示例。2.2 最短路径介数为了研究链路的特性，提出了最短路径介数[8]。每条链路的最短路径介数表示通过链路的最短路径的数量。在下文中，节点i和节点j之间的链路表示为Iij，并且Iij的最短路径介数表示为bij。现在，让物理网络中的一组节点表示为V。在V中，我们专注于节点s，用于计算每条链路的最短路径介数。这里，将包含节点s的V与包含节点i的V之间的跳数表示为di。节点i的跳数di是用广度优先搜索算法计算的。此外，对于节点i，wi表示跳数为di的路径的数量（参见图1（a））。这里，ds的初始值被设置为0，ws的初始值被设置为1。为了计算最短路径介数，利用每个节点的di和wi最短路径介数的计算从不是所有最短路径的中间节点并且对于每个相邻节点j满足djdt的节点t开始。对于该节点t，链路ljt的最短路径介数bjt由下式给出：没关系（一）对于尚未计算最短路径介数的链路lij，按照di的降序，链路lij的最短路径介数bij计算为：ሺ σ你好（二）א图1（b）示出了在图1的情况下每个链路的最短路径介数。1（a）.108Yasuhiro Urayama and Takuji Tachibana/IERI Procedia 10（2014）1053. 该方法在本节中，我们提出了一种新的虚拟网络重建方法，用于保持物理网络的鲁棒性并执行快速拓扑更改。在下文中，用户关于新的虚拟网络连接的请求被记录下来。Int he re ues t，是指一套ଵ ு� ଵ ு�节点的数量，H表示虚拟网络中应该包括的节点的数量，并且l表示虚拟网络中利用的资源量。此外，将虚拟网络的拓扑改变请求表示为虚拟网络拓扑改变请求。在请求Rc中，k表示虚拟网络的编号，并且k表示应该被包括在新的虚拟网络中的节点的集合。3.1 概述现在，我们假设在物理网络中有N个节点，并且在物理网络上已经构造了K个虚拟网络。另外，将用户的虚拟网络的拓扑结构用d表示，将在虚拟网络中使用的节点的集合用d表示，如以下所示，进行新的首先，服务提供商接收来自用户的请求。在这种情况下，与小节2.1所述的方法的情况一样，通过使用由Dijkstra算法和Prim的MST算法组成的KMB算法来设计满足用户请求的虚拟网络。然后，如果能够在维持物理网络的鲁棒性的同时构建虚拟网络，则构建虚拟网络并将其提供给用户。另一方面，如果服务提供商接收到来自用户k的对拓扑优化的请求，则服务提供商基于最短路径介数来改变拓扑优化如果在执行拓扑改变时能够满足构造条件，则根据请求Rc改变拓扑，并且向用户k提供拓扑。否则，不执行拓扑改变并且拒绝请求Rc3.2 基于最短路径介数的在这一小节中，我们详细介绍了基于网络间最短路径的拓扑重新设计方法。现在，服务提供者可以接收到一系列的信息，这些信息是指一组其中，节点是按时间分配的，时间是指按时间分配的一组链路，时间是指从用户k请求的资源。当从用户k发送请求Rc时，服务提供商如下执行拓扑改变步骤1服务提供商从集合中选取一个节点，并将该节点设置为最小，然后根据2.2小节中解释的过程计算从节点最小每个链路的成本被设置为与链路的最短路径介数相同的值。步骤2如果存在邻接节点的节点，并且节点包含在节点中，则节点和链接在步骤4中，将节点B1和节点B2之间的节点B1和B2添加到虚拟网络B1，并进行到步骤4。否则，转到步骤3。步骤3：服务提供商在与节点节点B相邻的链路中选择链路成本最大的链路B，并添加链路B和节点B然后，将节点设置为节点，并返回到步骤2.Step4节点 将从“已删除”中删除“已删除”。 如果是空集，则拓扑重新设计完成。否则，返回步骤1。Yasuhiro Urayama and Takuji Tachibana/IERI Procedia 10（2014）105109图2显示了执行基于最短路径介数的拓扑重新设计时的示例。在该图中，用户k具有由节点A、节点C和节点E组成的虚拟网络，并且用户发送请求Rc。.在这里，注意节点集合是{H}。然后，服务提供者认为节点具有起始节点，并计算每个链路的最短路径介数。之后，添加网络资源，以便在节点H和虚拟网络间进行连接。现在，节点G和节点F与节点H相邻。此外，这两个节点不包括在网络中。因此，服务提供商考虑到最短路径的值是中间性，将节点F和链路长度添加到G节点Ž 接下来，我们关注节点F。然后，我们发现节点C与节点F相邻，并且包含在G中。这样，节点C和链路A就被确定了，拓扑设计也就完成了。图2.基于最短路径介数的拓扑重新设计。4. 数值算例在本节中，我们通过模拟一个N × N格型拓扑的物理网络来评估我们提出的方法的性能。在该物理网络中，每个节点的资源量为60，每个链路的资源量为50。在下文中，我们假设用户关于虚拟网络构建的请求按照速率为1.0的泊松过程随机到达服务提供商，并且用户关于所构建的虚拟网络的拓扑改变的请求按照速率为0.2的泊松过程随机到达服务提供商。对于所需的节点，ଵ ு� ଵ ு�随机确定从用户请求的资源量L，并且在（1，15）上均匀地选择资源量L。此外，对于请求，包含在请求中的节点的数量等于1，并且它是随机选择的。最后，我们假设虚拟网络的利用时间服从指数分布，平均值为1.0。图3（a）示出了在从用户请求的节点的数量H从5改变为15的情况下虚拟网络的平均重新设计时间。这里，我们将物理网络的节点数N设置为5。从这个结果，我们发现，传统方法的平均重新设计时间增加时，H增加。这是因为，在传统方法中，拓扑是从头开始重新设计的。因此，平均再设计时间随着H的增加而变长。另一方面，在我们提出的方法中，由于拓扑结构的改变是通过添加新的节点和链接完成的，即使当H增加时，平均重新设计时间也不会增加太多。图3（b）表示将物理网络的节点数N从4变更为7时的虚拟网络的平均设计时间。这里，数H是5并且是固定的。从这个结果中，我们发现，我们提出的方法的平均重新设计时间总是短于传统的110Yasuhiro Urayama and Takuji Tachibana/IERI Procedia 10（2014）105法因此，我们提出的方法是有效的，无论节点的数量5. 结论提出了一种基于最短路径介数的虚拟网络拓扑快速变换方法。在我们所提出的方法中，当服务提供商收到一个请求的拓扑结构改变的虚拟网络，服务提供商重新设计的拓扑结构迅速，以满足用户的请求的基础上的最短路径介数。我们评估了我们所提出的方法与模拟的性能。从数值例子中，我们发现，我们提出的方法执行快速的拓扑结构变化比传统的方法，无论节点的数量。因此，预计我们提出的方法在未来会得到广泛的应用。(a)平均重新设计时间与节点数H的关系。 （b）平均重新设计时间与节点数N的关系。图3.我们提出的方法的性能。确认这项工作得到了日本总务省引用[1] H.Aun、P.Richard和N.Akihiro，“网络虚拟化中资源分配的挑战”，第20届ITC网络虚拟化专家研讨会论文集，越南会安，2009年5月。[2]J.Lu和J·特纳，``高效映射的虚拟网络到一共享基板，”华盛顿大学，技术报告，WUCSE-2006-35，2006年。[3] M.Mori、T.Tachibana、K.Hirata和K.Sugimoto，“A Proposed Topology Design and Admission ControlApproach for Improved Network Robustness in Network Virtualization” ， Proc. IEEE Globecom 2011 ，2011年12月。[4] 余明明，易义，蒋明，“虚拟网路嵌入的再思考：路径分割与迁移的基底支援”，电脑通讯期刊，第38卷，第2期，第17 -29页，2008年4月。Yasuhiro Urayama and Takuji Tachibana/IERI Procedia 10（2014）105111[5] 赵顺利，陈学松，“一种新的虚拟网络映射算法，”网络期刊：多学科期刊，电信领域（JSAT），1月版，2011年1月。[6] 郭文贵，“一种快速的树算法”，国立成功大学计算机科学研究所硕士论文，1981年6月。[7]A.Tizghadam和A.Leon-Garcia，“Autonomic Traffic Engineering for Network Robustness”，IEEEJournal on Selected Areas in Communication，vol.28，no.1，pp.39-50，Jan.2010。[8]M.E.J.Newman和M.Girvan，“Finding and Evaluating Community Structure in Networks”，PhysicalReview，E69，Feb.2004。