没有合适的资源?快使用搜索试试~ 我知道了~
基于Hose模型的高效网络规划
5470基于Hose的容量高效和韧性网络骨干规划0Satyajeet Singh Ahuja Facebook Varun Gupta Facebook Vinayak Dangui Facebook0Soshant Bali Facebook Abishek Gopalan Facebook Hao Zhong Facebook0Petr Lapukhov Facebook Yiting Xia Max Planck Institute for Informatics Ying Zhang Facebook0摘要本文介绍了Facebook在骨干网络规划中采用Hose模型的设计和运营经验。由于骨干扩展的容量和需求不确定性的压力,我们首次采用Hose模型进行网络规划。由于Hose模型抽象了每个站点的聚合流量需求,不同时间的峰值流量可以进行多路复用以节省容量和缓冲流量峰值。我们的核心设计涉及启发式算法来选择符合Hose的流量矩阵和光学网络与IP网络之间的跨层优化。我们在生产环境中评估了系统性能,并分享了多年的生产经验。基于Hose的网络规划可以节省17.4%的容量,并在光纤切断时减少75%的流量丢失。作为Hose在网络规划中的首次研究,我们的工作有潜力激发后续研究。0CCS概念0• 网络 →广域网;流量规划;网络可靠性;分层;网络模拟;网络实验;网络测量;• 计算机系统组织 → 可用性;0关键词0广域网,网络规划,网络建模,网络优化0ACM参考格式:Satyajeet Singh Ahuja,Varun Gupta,VinayakDangui,Soshant Bali,Abishek Gopalan,Hao Zhong,PetrLapukhov,Yiting Xia和YingZhang。2021年。基于Hose的容量高效和韧性网络骨干规划。在ACMSIGCOMM2021会议(SIGCOMM'21)上,2021年8月23日至27日,虚拟活动,美国。ACM,纽约,美国,13页。https://doi.org/10.1145/3452296.34729180SIGCOMM '21,2021年8月23日至27日,虚拟活动,美国 ©2021版权由所有者/作者所有。ACM ISBN978-1-4503-8383-7/21/08。https://doi.org/10.1145/3452296.347291801 引言0全球在线服务提供商,如Google、Facebook和Amazon,构建了广域骨干网络,用于连接成千上万个PoP站点和数百个数据中心(DCs),跨越多个大陆。为了跟上爆炸性的流量增长,不断投入大量资金和工程努力来扩展和升级骨干网络。因此,网络规划是骨干网络演进的关键,其最终目标是制定容量高效的网络建设计划,能够应对服务变化和流量动态的未知需求不确定性。Facebook通过在骨干规划中创新地采用Hose模型来实现这一目标。传统上,骨干规划是基于Pipe模型的。如图1所示,Pipe模型抽象了网络站点之间的成对流量需求。为了在需求变化时提供足够的容量,使用Pipe模型,我们必须为每个站点对之间的峰值需求进行规划。从整个网络的角度来看,这种方法旨在容纳所有连接站点的“峰值”流量。相比之下,Hose模型抽象了每个站点的聚合入口和出口流量需求。它自然地总结了站点之间的流量需求,因此使用Hose模型进行容量规划是为了“总和峰值”流量。由于不同站点之间的峰值流量需求不太可能同时发生,Hose模型提供了多路复用增益,节省了总体容量,并在部署后为流量不确定性留出了余地,其中站点之间的单个需求可能会有所变化,但其总和不会超过规划的峰值容量。除了节省容量和对不确定性的韧性外,基于Hose的骨干规划与将服务逻辑与基础设施设计分离的行业趋势相辅相成。在实践中,由于各种原因(如负载平衡、服务扩展、延迟降低、数据中心维护等),服务会从一个DC迁移到另一个DC。网络和服务器基础设施应该标记出服务行为,并为服务迁移提供灵活性。这个要求使得准确地预测站点对之间的点对点流量需求变得非常困难。此外,对于像Facebook这样不断增长的骨干网络,每年都会建立新的DC,因此几乎不可能估计尚未建立的新DC的流量需求。由于Hose模型的存在,我们只需要指定每个站点的聚合流量需求,而不必担心每个流量流的另一端。因此,使用基于Hose的规划,网络有潜力在未来像存储和计算资源一样轻松地按节点扩展。0未知数据5480未知数据0未知数据0未知数据0未知数据0未知数据0图1:聚合进出流量需求的Hose模型与3个站点网络上节点对之间的单独流量需求的管道模型。站点可以是数据中心或PoP。管道计划用于“峰值之和”流量,而Hose计划用于“峰值之峰”流量,这提供了多路复用增益,因为单独的峰值流量需求通常发生在不同的时间。0然而,无论Hose模型的优势如何,容量必须以类似管道模型的点对点方式授予站点对。因此,我们在骨干规划中的问题是将Hose每个站点的流量转换为管道成对流量。Hose模型最初是为虚拟专用网络(VPN)提供服务而发明的[9],后来用于云中的虚拟机(VM)部署[4],从未应用于网络规划环境,因此我们无法在文献中找到现成的解决方案。本文的主要贡献是解决这个新问题。管道输出流量可以表示为站点对之间的流量矩阵(TM)。Hose中的聚合流量需求映射到一个包含无限数量TM的连续空间。在Hose模型下,规划所有可能的管道TM是计算上不可行的。我们的挑战是生成一个小的TM子集来表示Hose空间。我们提出了一系列启发式算法来应对这个挑战(§4)。我们首先设计了一个采样方案,在Hose空间中均匀生成候选TM。从这些TM中,我们找到当前瓶颈链路的关键TM,这些链路是部署额外容量的潜在位置。因此,我们提出了一种快速查找网络中瓶颈链路的扫描算法。通过优化选择关键TM,并且我们还定义了“Hose覆盖率”作为一个度量,用于量化这些选择的TM的代表性。本文的另一个贡献是在Facebook的网络环境中分享生产网络规划过程中的实际考虑因素。我们的工程经验包括短期和长期规划的分离,简化光学和IP网络之间的交互的抽象,保护免受故障的弹性策略,以及光学-IP跨层容量优化(§5)。我们还评估了我们基于Hose的网络规划系统在生产中的性能(§6)。我们证明Hose相对于管道可以节省17.4%的容量,并在未计划的故障下减少高达75%的流量。据我们所知,我们是第一个在网络规划背景下研究Hose模型的人,并且这是第一次将端到端网络规划过程引入学术界。我们希望我们的工作能激发一系列新的研究,理论家们可以更好地制定我们的启发式算法,实践者们可以优化我们的规划系统。这项工作不涉及任何伦理问题。我们在整个研究过程中保护用户隐私和匿名性。02 HOSE的动机0在本节中,我们使用生产流量来展示Hose骨干规划在节省容量和对流量不确定性的韧性方面的优势。实验设置:我们收集了2020年11月23日至2020年12月28日期间Facebook北美骨干网络上每个站点对之间的生产流量。为了消除一天中时间的影响,我们只关注繁忙时间段,即骨干网络中总流量最高的时间段。在繁忙时间段,流量每分钟采样一次,共有60个数据点。对于管道模型,我们将60个数据点中的第90百分位数作为每个站点对的峰值流量需求。对于Hose模型,我们将每个数据点中与其通信的源站点/目的站点的进出流量相加。在60个聚合流量的数据点中,我们使用第90百分位数作为Hose的峰值流量需求。这种方法给出了Hose和管道模型分别的“每日峰值”流量需求。在生产中,我们通常使用移动平均法平滑流量需求。根据Facebook的标准,我们采用21天窗口对上述每日峰值需求进行平均,并将21天数据的3倍标准差加到移动平均值上作为突发流量峰值的缓冲。这种方法产生了Hose站点和管道站点对的“平均峰值”流量需求。在接下来的实验中,我们统计整个北美骨干网络中的总流量需求,包括Hose站点和管道站点对之间的流量需求。我们每天观察4个数字:骨干网络中的总每日峰值需求和总平均峰值需求,分别对应Hose和管道模型。流量减少:Hose和管道规划的关键区别在于部署“峰值之峰”和“峰值之和”流量的容量。如果使用Hose模型,多路复用增益使我们能够规划更少的容量,因为与同一源/汇相连的管道流量不太可能同时达到峰值。图2显示了Hose流量减少的相对值,即Hose中减少的总需求与管道中总需求之比。Hose的“每日峰值”需求(红色虚线曲线)比管道低10%-15%,而“平均峰值”需求(黑色实线曲线)比管道低20%-25%。由于骨干规划基于流量需求,我们有充分的理由相信,仅通过采用Hose模型进行规划,就可以节省相当大比例的容量。对流量动态的容忍度:多路复用效应还意味着Hose规划结果可以涵盖更多的流量变化。图3是每日峰值流量需求的累积分布函数(CDF)。出于保密考虑,我们将绝对流量量归一化为最大需求(来自管道模型)。如图所示,�=0.55处的垂直线对应Hose模型中的90%的天数,而在管道模型中只有40%。这意味着如果我们规划55%的最大总需求,根据Hose模型,每日峰值需求将在90%的天数内得到满足,而在管道模型中只有40%的天数。Hose中的较高百分位数表示它可以容忍更多的流量不确定性。由于Hose模型受到聚合流量而不是特定TM的限制,它有更大的余地来吸收意外的流量峰值。稳定的流量需求:我们还测量了Hose和管道流量在不同天数之间的变化。为了使不同的流量需求可比较,我们使用变异系数作为度量标准,即 10 12 14 16 18 20 22 24 2611/2812/0512/1212/1912/26 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 0 0.5 1 1.5 2 2.5 3 3.5 4 4.55490相对流量节省0天0每日峰值0平均峰值0图2:Hose流量的减少。0CDF0归一化总流量0PipeHose0图3:Hose与Pipe的总流量分布。0CDF0变异系数0PipeHose0图4:Pipe与Hose流量的变异系数。0图5:从数据中心地区B和C到地区A的服务流量。0在骨干网络中,每日峰值流量的变异系数如图4所示。Hose的相对流量分散性要比Pipe小得多,并且尾部更短。因此,Hose模型为规划提供了更稳定的信号,并简化了流量预测。有了这些,我们可以很容易地想象网络的扩展与存储和计算资源一样容易,其中一个节点可以准确估计其未来的增长,而不必担心与网络中其他节点的交互作用。0服务的演变适应服务在生产过程中会随着时间的推移而演变。可能的原因包括服务行为的变化,服务质量(QoS)类别的重新标记,负载均衡的流量转移,新服务的推出等等。图5展示了Facebook的用户数据库(UDB)服务的一个例子。由于资源和运营限制,存储用户数据的UDB服务器只位于少数几个地区,而没有UDB的地区依赖于一个名为Tao的缓存服务从附近的UDB地区获取数据。图5显示了从UDB地区B和C流向没有UDB的地区A的Tao流量的数量。这种显著的流量变化是由于Tao服务将主要的UDB地区从B更改为C,其中在03/05对几个分片进行了金丝雀测试,而在03/09进行了完整的策略更改。这两个事件都导致了数Tbps的流量转移,而使用Pipe模型将会失败。相比之下,由于总流量量保持不变,Hose入口处的流量在地区A几乎没有中断。Hose的流量聚合特性自然上更具有适应服务变化的弹性,使其成为网络规划的未来解决方案。03基于Hose的容量规划0在本节中,我们将概述容量规划问题和我们的系统设计。表1列出了本文中使用的符号。0网络模型我们的骨干网络将多个数据中心(DCs)和点对点(PoPs)连接在一起。它由在密集波长分割多路复用(DWDM)光网络上的IP路由器组成。骨干路由器通过多个光纤段上的IP链路连接。我们将这个网络表示为一个两层图:IP网络 � = (�, �),其中顶点 �是骨干路由器,边 � 是IP链路,以及光网络 �′ = (�′, �′),其中顶点 �′是光纤增加-删除复用器(OADMs),边 �′ 是光纤段。对于每个IP链路 � ∈ �,��(�)是�所经过的光纤段的集合,在光学拓扑上形成一条路径。IP链路 � 在每个光纤段 � ∈ �′上占用一部分频谱。0通过这个例子,我们可以看到,使用正交相移键控(QPSK)调制实现的100GbpsIP链路可以在其路径上的所有光纤段上占用50GHz的频谱。IP容量和光谱之间的关系在第5.1节中展示。0故障模型我们考虑骨干网中一组光纤故障。每个IP链路�在故障的光纤上都会中断。为了为服务流量提供所需的可靠性,我们预先定义了一组故障�,称为计划故障。生产网络应该规划足够的容量,以便在每个故障�∈�的情况下都可以路由所有服务流量。容量规划中的详细弹性策略将在第5.2节中介绍。0流量预测容量规划取决于未来的预测流量需求。与ISP网络中对链路流量的有机增长建模不同,对于内容提供商来说,根据服务配置文件预测未来的流量需求是常见做法。这是因为作为内容生成器的服务为流量需求提供了更可靠的真实来源。对于数据中心间的流量,服务团队校准服务器利用率,特别是CPU利用率,以制定公司分配的服务器预算下的服务增长计划。他们提供服务扩展因子,这些因子应用于当前服务流量,形成未来的需求。对于PoP-DC流量,我们通过模拟用户增长和PoP的缓存未命中来预测PoP和不同DC之间的内容检索量。需求可以以不同的方式进行聚合,例如传统的基于管道的规划以站点对为基础,基于软管的规划以站点为基础。Figure 6: System Architecture5500表1:符号说明0符号定义0�=(�,�) IP拓扑,包括骨干路由器和IP链路 �′=(�′,�′) 光学拓扑,包括OADMs和光纤段 ��(�) IP链路�经过的光纤段集合 �骨干中站点(数据中心和PoP的总和)的数量 � 一个�×�的流量矩阵(TM) ��,� 矩阵�中从站点�到站点�的流量量 ��一个1×�的全1向量,用于检索�中的源节点 �′� 一个�×1的全1向量,用于检索�中的目标节点 ��一个1×�的向量,限制源节点的出口流量 � �′� 一个�×1的向量,限制目标节点的入口流量 � �={��,�′�}出口和入口流量需求的软管约束 � 扫描算法中的边界阈值(§4.2) � 支配流量矩阵(DTM)选择中的流量松弛 �∈�切割集中的网络切割 �(�) 网络切割�下的DTM集合,流量松弛为� � 候选DTM集合 � �一个二进制0-1分配变量,指示是否选择DTM� � 一个凸多面体,用于表示高维软管空间 � 软管空间中的一组样本点 ��∈�软管空间中的一个平面,属于一组平面 ��(�) 采购和部署光纤段�的成本 �(�) 开通暗光纤�的成本 �(�)配置新波长以添加IP链路�的成本 �(�) IP链路�的光谱效率 �� IP链路�的IP容量 � 路由开销 ��∈�� QoS类别�的计划故障场景 ��,�(�,�)通过IP链路{�,�}从源�到目标�的流量 �� 要点亮的光纤段�的光纤数量 �� 部署在光纤段�上的光纤数量0问题陈述网络容量是IP网络和单个IP链路能够承载的最大吞吐量(以Gbps、Tbps或Pbps为单位)。容量规划的问题是计算未来需要建设的网络容量。构建网络涉及复杂的步骤:(1)从第三方供应商采购光纤(2)建设陆地和海底光纤路线(3)在现有管道上拉光纤(4)安装线路系统以点亮光纤(5)在光放大器和站点上获得空间和电力(6)采购、交付、安装硬件(光学和IP)在站点上。所有这些活动都需要很长的时间,需要数月甚至数年才能完成。因此,容量规划对于网络的未来发展和盈利能力至关重要。在网络规划问题中,目标是根据计划的故障集�来为预测流量确定网络的尺寸,同时最小化解决方案的总成本。网络的成本是根据设备(光纤和其他光学和IP硬件)采购、部署和维护的加权函数计算的,以实现网络计划。具体的成本模型将在第5.1节介绍。0规划方案在Facebook,我们将容量规划分为两个子问题:短期规划和长期规划。短期规划输出精确的IP拓扑,即IP链路和每条链路上的容量,而长期规划仅确定要采购的光纤和硬件。这个设计决策基于网络建设是一个迭代过程,长期规划只作为参考。例如,光纤采购计划可能会根据市场上的光纤资源的可用性在部署时发生变化。只有在确保光纤和硬件安全并就位后,才进行短期规划,因为容量的开通可以在短时间内完成。0容量规划0容量规划0和相应的需求向量 � � � � ′ �限制了源节点和目标节点的总出口和入口流量。这些约束形成了一个凸多面体,其维度为 � 2 − �0容量规划0容量规划0容量规划0次。例如,光纤采购计划可能会根据市场上的光纤资源的可用性在部署时发生变化。只有在确保光纤和硬件安全并就位后,才进行短期规划,因为容量的开通可以在短时间内完成。0图6:系统架构04 流量矩阵生成在本节中,我们介绍将Hose约束转化为规划参考TM的具体步骤,包括启发式算法、优化和性能指标。0规划流程图6展示了规划过程。骨干网络规划从流量预测开始。如前所述,我们的流量预测是基于服务的,与规划方法无关,即无论是基于Pipe还是Hose的规划。对于基于Hose的规划,我们将服务需求按照各个骨干站点聚合,生成入口和出口的Hose约束。正如在介绍中所提到的,基于Hose的网络规划的关键是将Hose约束转化为PipeTM。因此,如第4节所示,规划器采取谨慎的步骤将无限数量的可能的PipeTM缩小到一小组代表性的TM。然后,根据弹性策略,对参考TM进行短期和长期规划,考虑各种故障情景。优化过程在第5节中详细介绍。规划的输出是计划记录(POR),以站点对之间的容量格式呈现。短期规划的POR交给容量工程团队进行容量开通,长期规划的POR交给光纤采购团队进行光纤采购,并交给光学设计和IP设计团队进行光纤和光线系统的部署。本文重点介绍容量规划器的设计。0和相应的需求向量 � � � 和 � � ′ �限制了源节点和目标节点的总出口和入口流量。这些约束形成了一个凸多面体,其维度为 � 2 − �������������5510设计0容量规划0设计0容量规划0设计0容量规划0Hose约束0Hose约束0Hose约束0Hose约束0Hose约束0图7:Hose多面体空间的3D示例0维度空间中,TM中的每个非零系数都是一个变量。图7以变量�1,2,�1,3和�1,4为例,展示了一个高度简化的3D示例。每个有效的TM是连续空间中的一个点,这个连续空间中有无限多个有效的TMs。0Hose约束:�� ∙ � � ��0� ∙ �′� � �′� (1)0为了生成满足Hose约束的TM,我们的第一步是均匀采样多面体空间。算法1展示了我们的两阶段算法生成一个样本TM的过程。在第一阶段(第1-7行)中,我们在多面体空间中随机创建一个有效的TM,并在第二阶段(第8-13行)中将其拉伸到多面体表面,这是因为表面上的TMs具有更高的流量需求,并且对网络规划具有更高的容量要求。在第一阶段,我们将TM初始化为零矩阵(第1行),并按随机顺序逐个分配流量给TM条目(第2行)。对于每个条目��,�,最大允许的流量量是源�和目的地�的两个Hose约束中较小的那个。我们给它一个0到1之间的均匀随机缩放因子(第3行),并将乘积分配给条目(第4行)。为了记录,消耗的流量量从Hose约束中扣除(第5-6行)。在第二阶段,我们向TM添加剩余流量,以尽可能多地满足Hose约束。与第一阶段类似,我们按随机顺序迭代所有条目(第8行),并将最大允许的流量量添加到每个条目(第9-12行)。因为我们遍历所有条目并始终消耗最大流量,我们的第二阶段保证从第一阶段结果中耗尽最多的Hose约束。它还保证我们不能同时满足出口和入口的Hose约束(剩余约束必须全部是出口或全部是入口),因为如果是这种情况,算法将简单地增加相关的源-目的地流量,直到入口或出口约束耗尽为止。无论简单性如何,这种采样算法都非常有效。如图9a所示,使用10^5个样本TM,Hose多面体空间的覆盖率超过97%。这种有效性来自于高度的随机性:(1)我们在每次运行中对TM条目(第2行和第8行)应用不同的排列,以不同的方式分配Hose流量预算;(2)我们使用缩放因子(第3行)根据均匀分布随机调整可分配的流量。我们的两阶段采样-拉伸方法被证明是关键的。在以前的解决方案中,我们直接均匀采样多面体表面,但是在相同数量的样本下,覆盖率要低20%-30%。0算法1 ��������()0输入:网络大小�,Hose约束� = {��, �′�}在公式(1)中输出:满足�的随机�×�流量矩阵� 1: � = 0�×� 2: 对于每个��,�在�中的随机顺序执行 3: � =���(��,�′�) × ������.���� ���(0, 1) 4: ��,� = � 5: �� = �� - � 6: �′� = �′� - � 7: 结束循环 8:对于每个��,�在�中的随机顺序执行 9: � = ���(��,�′�) 10: ��,� = ��,� + � 11: �� = �� - � 12: �′� = �′� - � 13:结束循环04.2 瓶颈链路扫描考虑大量的TM样本在计算上是不可行的。幸运的是,TMs对网络规划具有不同的重要性。由于网络规划的目标是在网络中添加容量到“瓶颈链路”,在瓶颈链路上具有高流量需求的TMs起着主导作用。我们称这样的TMs为主导流量矩阵(DTMs),我们的目标是找到一小部分DTMs,这样为它们设计网络具有很高的概率也能满足剩余的TMs。从图论的角度来看,瓶颈链路是由将节点划分为两个不相交子集的网络切割所捕获的。然而,网络切割的数量与网络大小呈指数关系。一个生产骨干网络有几十到几百个节点,因此枚举所有切割是不可行的。即使骨干网络不是一个密集连接的图,可能的切割数量仍然是O(2^min(|V|,|E|)),其中|V|和|E|分别是节点和边的数量。我们提出了一种扫描算法来快速采样网络切割,扫描过程如图8所示。扫描算法有一个超参数边界阈值�,选择在[0,1]区间内。网络节点由它们的纬度和经度坐标表示。我们在包围所有节点的最小矩形上进行雷达扫描,以矩形边上的点为中心。每边有�个等间隔点,扫描在离散的方向角度�上进行。我们通常选择�=1000和�=1度。算法在每个扫描步骤中绘制一个参考切割线,该线将节点分为以下三个互斥的类别。 •边缘节点,其到切割线的距离与网络中最远节点到切割线的距离之比小于�。 • 上方节点,位于切割线上方但不属于边缘节点组。 •下方节点,位于切割线下方但不属于边缘节点组。网络切割是边缘节点与上方和下方节点分别组合的所有可能的二分划分。在该算法中,参数�和�定义了采样粒度,边界阈值�调节了每个采样步骤考虑的切割数量。随着�的增加,我们能够生成越来越多的网络切割。特别地,将�设置为1��������������������������������������������������������������������𝑇(2)0�� 约束条件0图8:扫描算法的示例。扫描以每个矩形边上的�个点为中心,并以�◦步长移动。参考切割(蓝色实线)的扫描步骤创建了2个边缘节点(黄色点),它们的排列形成了4个切割。0确保我们枚举网络的所有划分。�与网络切割之间的关系如图9b所示。04.3 选择主导流量矩阵相对于网络切割的DTM的正式定义如下。直观地说,根据第4.1节中采样的TM和第4.2节中生成的网络切割,我们希望找到为每个网络切割产生最多流量的TM。0定义4.1(主导流量矩阵-严格版本)。网络切割的主导流量矩阵是在所有采样的流量矩阵中,跨切割的流量量最大的流量矩阵。0这个定义产生了与网络切割一样多的DTM。为了进一步减少我们规划计算中涉及的TM数量,我们从最大流量的TM松弛到一组相对流量较大的TM,使得不同切割的DTM集合可能重叠,并且切割可以由较小数量的重叠DTM表示。因此,我们引入流量松弛度�,并定义如下的DTM松弛版本。在本文的其余部分,所有的DTM都指的是这个松弛定义。0定义4.2(主导流量矩阵-松弛版本)。具有流量松弛度�的网络切割的主导流量矩阵是从采样的流量矩阵中,跨切割的流量量不小于所有采样的流量矩阵中最大流量量的1-�,其中�是[0,1]范围内的一个小值。0在我们对最小集覆盖问题的制定中,宇宙是网络切割的集合�。对于每个切割� ∈�,根据定义4.2,我们根据给定的流量松弛度�得到给定切割下的DTM集合�(�)。将它们组合起来,我们有一个包含所有候选DTM的集合� ={�},其中每个DTM属于�中的一个切割子集。例如,一个DTM�可能由多个同时切割{��,��,��}生成。我们的目标是找到覆盖所有�中切割的最小数量的DTM们通过整数线性规划(ILP)来解决这个最小集覆盖问题。如下所示,我们定义一个二进制分配变量��,如果最终选择了候选DTM�,则设置为1,否则设置为0。分配变量必须保证每个网络切割至少由其候选DTM之一表示,并通过最小化分配变量的总和来最小化所选DTM的数量。0变量��,如果最终选择了候选DTM�,则设置为1,否则设置为0。分配变量必须保证每个网络切割至少由其候选DTM之一表示,并通过最小化分配变量的总和来最小化所选DTM的数量。0min最小化0��0s.t.约束条0� ∈ �(�) �� ≥ 1, �� ∈ �0我们使用商业ILP求解器FICOXpress[1]来实现低DTM数量。如图9c所示,约1%的流量松弛度可以将DTM数量减少超过75%,这在容量规划所需的计算中是一个巨大的收益。进一步增加流量松弛度会得到更令人印象深刻的结果,但代价是Hose覆盖度降低,这将在下一节中看到。04.4 Hose覆盖度作为我们进行符合Hose的容量规划时,我们需要定义一个度量标准来评估我们生成的参考TM覆盖整个Hose空间的程度。特别是,由于我们使用了一个两阶段的过程,首先我们使用大量的TM对Hose空间进行采样,然后再对它们进行进一步的下采样以达到较小数量的DTM,因此希望能够测量过程的每个阶段的Hose覆盖度。回想一下,Hose在高维向量空间中由一个凸多面体�表示,衡量一组样本�的覆盖度的一种自然方法是通过体积,即包含所有样本的凸包的体积除以Hose空间的体积。该度量标准在三维中的示意图如图7所示。0覆盖率 ( �, � ) = 体积 ( 0体积 ( � ) (3)0然而,当应用于网络规划的实际情况时,该度量是难以处理的。在 �维空间中计算 � 个点的凸包的复杂度约为 � ( � � 2 ) [ 6]。在我们的情况下,� = � 2 − �,其中 �是网络中的节点数,可能是几百个,样本大小 � = | � | 可能为 10 5。因此,我们定义Hose空间 � 在平面 � 上由样本集合 �的平面覆盖率如下,其中 Π ( �,� ) 表示样本集合 � 在平面 � 上的投影,Π( �,� ) 表示Hose多面体 � 在平面 � 上的投影。0平面覆盖 ( �, �,� ) = 面积0面积 ( Π ( �,� )) (4)0对于一组平面 �,我们定义样本集合 � 对于Hose空间 � 的覆盖率为 � 在 �上的平均平面覆盖率,覆盖所有平面 �。0覆盖率 ( �, � ) = 10�0� = 1 平面覆盖 ( �, �,� � ) (5)) × 𝜆𝑒 ≤ 𝑀𝑎𝑥𝑆𝑝𝑒𝑐(𝑙) × 𝜙𝑙, ∀𝑙 ∈ 𝐸′(6)5530选择这些平面对于真实地描绘高维Hose空间至关重要。这些平面应该刻画Hose约束中的所有变量,并且变量应该对塑造平面起到相等的贡献。方便起见,我们构造了所有Hose约束中变量的两两组合的平面。根据公式(1)可知,每个变量都是有效TM �的非对角系数,或者是网络中的源-目的地对。在图7的示例中,选择的平面为 � = { Plane ( � 1 , 2 ,� 1 , 3 ) , Plane ( � 1 , 2 ,� 1 , 4 ) , Plane( � 1 , 3 ,� 1 , 4 )}。05 交叉层优化容量规划需要对光网络和IP网络进行交叉层优化。优化输入包括DTMs,IP拓扑 � = ( �, � ),其中包含骨干路由器 � 和IP链路 �,以及光拓扑′ = ( � ′ , � ′ ),其中包含OADMs � ′ 和光纤段 �′。输出是具有相同站点但具有更多链路或更大容量的目标IP和光拓扑� + Δ � = ( �, � + Δ � ) 和 � ′ + Δ � ′ = ( � ′ , � ′ + Δ � ′)。本节详细介绍了优化过程。05.1 成本模型尽管规划不是一项时间紧迫的任务,但考虑到我们网络的规模,我们希望优化至少能在几小时内完成。为了简化优化,我们设计了一个成本模型,将光学和路由系统中的复杂性抽象为简单的成本因子乘以决策变量。这五个基本成本因子是: 光纤采购和部署成本这是在光纤可用之前购买和安装新光纤的全部成本。如果我们拥有光纤,它包括采购光纤、光放大器、可配置光纤增加/删除复用器(COADMs)、波长选择开关(WSSes)、IP路由器机箱的设备成本,以及清洁光纤、沿光纤路径部署放大器和在终端站点部署COADMs、WSSes和路由器机箱的人工成本。如果我们租用光纤,则包括租赁合同中的所有使用、运营和维护成本。这个成本因供应商、光纤长度、光纤类型(陆地、海底或空中)等因素而异,我们根据这些特征对其进行建模。我们用 � ( � ) 表示光纤段 � 在光拓扑 � ′ 上的成本。 光纤开通成本这是已经安装的暗光纤开通的成本。它包括购买额外设备(如光传输器和线路卡)的成本,以及配置设备的人工工作量。我们根据历史数据估计这个成本。我们用 � ( � ) 表示光纤段 � 在 � ′ 上的成本。容量增加成本这是在已开通的光纤上提供新波长的成本。它增加了一个单位的带宽容量,即100Gbps,到IP层。这个成本涉及波长配置和路由器端口配置的人工工作。这是一个固定成本,用 � ( � ) 表示IP链路 � 在IP拓扑 �上。 光谱效率这个因子捕捉IP容量在其路径上所有光纤段上消耗的光谱比例,这取决于为了在电路上实现无误传输所需的调制方式。我们用 � ( � )表示IP链路 � 的光谱效率,并将复杂的光链路工程计算委托给类似于 [21 ] 的光链路模拟器。0以下光谱守恒约束规定了每个光纤段�∈�′的光谱消耗。假设�有��个点亮的光纤,每个光纤具有最大允许的光谱�������(�)。对于IP链路�∈�,所需的光谱是IP容量��乘以其光谱效率�(�)。因此,通过光纤段�上的每个IP链路�所需的光谱总和必须大于或至少等于由IP-光学映射函数��(�)指定的每个IP链路所需的光谱之和。为了考虑由于光谱连续性约束[3]而导致的可用光谱的损失,我们在启用光纤时保留了�������(�)的一定百分比作为规划缓冲区。这种波长争用的抽象节省了准确波长分配的工作量,并且在实践中运行良好。0�����������(�,�′):�0路由开销这是由于路由算法的不完善而导致的带宽容量损失。我们将容量规划建模为IP层上的多商品流问题[11]。在实践中,骨干路由器只允许每个流量有少量的并行路径,例如等费用多路径(ECMP)和K短路径路由,这使得问题成为NP难。为了在多项式时间内解决它,我们转换为分数流,即每个流量可以无限分割,并且通过路由开销捕捉到与实际路由算法的差异。对于特定的路由算法,路由开销�是原始流量需求的[1,+∞)倍数,为路由的低效性提供了余量。0�∈�,�∈��(�),�(�)×��≤�������(�)×��,��∈�′(6)0��=�0如第3节所述,我们为各个服务类型预测流量。在服务聚合方面,我们有每个QoS类别�∈{���}的Hose模型��。我们设计韧性策略的方式是使来自一个QoS类别的流量受到其自身类别和所有低于它的其他类别的故障场景的保护。因此,剩余拓扑��必须承载其自身类别和所有更高类别的流量。根据第5.1节,每个QoS类别可以使用不同的路由方案,因此具有不同的路由开销。如下方程所示,QoS类别�的参考DTMs(9)(10)𝐸𝑧(𝑒) × 𝜆𝑒∀𝑞 ∈ 𝑄𝑜𝑆(11)5540��∈��(�0−��)(7)0��=���(0�=1�(�)×��)(8)0对于每个QoS类�,给定DTMs��和故障后的IP拓扑��,每个参考TM�∈�流量必须满足以下每个拓扑�∈��上的守恒约束,如下所示。也就是说,对于TM�中的每个流量,流量的源和目的地必须具有所需的流量量,流量的所有中间节点的总流量为零,并且IP链路上的流量不能超过带宽容量�。在这里,我们简单地假设所有流量都可以无限分割,因为实际路由算法的差异已经通过路由开销考虑在内。0���� ∈ � � ,� ∈ � � :0{ �,� }∈ � � �,� ( �,� ) −0 ) = � �,�0{ �,� }∈ � � �,� ( �, � ) −0{ �,� ) = � �,�0{ ∈ ≠ ≠ 0� �,� ( �, � ) −0{ �,� }∈ ≠ �,� ≠ �0� �,� ( �,� ) = 00�0{ �,� }∈ � � �,� ( �, � ) ≤ � �,� � � �,� ∈ �05.3 短期规划短期网络规划是针对未来6个月到2年的时间范围。在这段时间内,我们依赖现有的光纤基础设施。因此,我们假设IP拓扑保持不变,但是IP链路的容量可以增加。在已部署(可能是非活动的)光纤资源的限制下,可以扩展由活动光纤段组成的物理层拓扑。我们的目标是在接受基于Hose流量预测的未来流量的同时,最小化成本。ILP的公式如下所示。优化过程使用当前IP拓扑�和可扩展的光纤拓扑� ′ + Δ �′,其中Δ � ′是由暗光纤提供的扩展预算。� �是将在最终点亮的� ∈ � ′ + Δ� ′上的光纤段的数量,� �是IP链路� ∈�上的目标容量。将它们与第5.1节中描述的相应成本相乘,即每根光纤的开通成本� ( � )和每单位带宽容量增加成本� ( �),我们得到优化目标,即最小化构建最终网络的总成本。0min0� ∈ � ′ + Δ � ′ � ( � ) × � � +0� ∈ � � ( � ) × � �0s.t. ����������� ( �,� ′ + Δ � ′ )0� ∈ � � ,� ∈ � � ����������� ( �,� ) , � � ∈ �0� � ≥ Λ �,� � ∈ �,� � ≥ Φ �,� � ∈ � ′+ Δ � ′0这个目标本质上等同于最小化网络扩展的额外成本,因为建立现有网络的固定成本已经支付,但它简化了约束条件。例如,第5.1节中描述的光谱守恒约束是关于总IP容量和总光纤数量的。0在第5.2节中,流量守恒约束也必须满足。需要注意的是,我们需要针对每个QoS类别考虑这个约束。此外,根据网络持续增长的事实,我们还有额外的约束条件,即� �和��必须大于或等于现有网络中的当前值Λ �和Φ�:一旦建立了网络,我们不会减少IP容量或禁用光纤。05.4 长期规划长期网络规划目标是未来2到5年。长期规划的目的是估计最坏情况下的硬件需求,并确保提前采购足够的设备。与短期规划的一个重要区别是长期规划考虑了新光纤的安装。由于我们骨干网络的规模很大,无法对所有可能的光纤安装位置进行全局搜索。一个实际的解决方案是根据市场上的光纤供应和我们的运营经验,缩小范围,确定少量候选位置。我们绘制了一个光纤拓扑� ′ + Δ � ′,其中候选光纤在Δ �′中,并将这些光纤映射到可能的IP链路上,形成IP拓扑� + Δ�,其中潜在的IP链路在Δ�中,初始容量为零。通过这种方式,我们将长期规划问题转化为类似于短期规划问题的形式。如下所示,优化目标仍然是最小化总成本,但是增加了一个用于光纤采购和部署成本的项
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Ansys Comsol实现力磁耦合仿真及其在电磁无损检测中的应用
- 西门子数控系统调试与配置实战案例教程
- ELM多输出拟合预测模型:简易Matlab实现指南
- 一维光子晶体的Comsol能带拓扑分析研究
- Borland-5技术资料压缩包分享
- Borland 6 技术资料分享包
- UE5压缩包处理技巧与D文件介绍
- 机器学习笔记:深入探讨中心极限定理
- ProE使用技巧及文件管理方法分享
- 增量式百度图片爬虫程序修复版发布
- Emlog屏蔽用户IP黑名单插件:自定义跳转与评论限制
- 安装Prometheus 2.2.1所需镜像及配置指南
- WinRARChan主题包:个性化你的压缩软件
- Neo4j关系数据映射转换测试样例集
- 安装heapster-grafana-amd64-v5-0-4所需镜像介绍
- DVB-C语言深度解析TS流
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功