SNDlib【传统网络数据库】

admin管理员组

文章数量:1621659

SNDlib【Survivable Network Design Library】

• SNDlib是什么？
• SNDlib怎么来的？
• SNDlib的规划流程
• SNDlib数据概念
• SNDlib网络
• • SNDlib网络的示例
• SNDlib模型
• • Demand model
  • Link model
  • Link capacity model
  • Fixed-charge model
  • Routing model
  • Admissible path model
  • Hop limit model
  • Survivability model
  • Other models
  • Example of the SNDlib model
  • Naming conventions
• SNDlib解决方案
• 网络设计实例
• • 具有工业背景的实例
  • 来自国际研究项目的实例
  • 其他实例
• 参考文献

SNDlib是什么？

SNDlib，Survivable Network Design Library，简单来说就是一个网络数据的数据库，可以在http://sndlib.zib.de上访问。

进入网页你可以看到很多传统网络的网络数据，这些数据都是真实的。

SNDlib的目的是为网络设计社区提供现实的网络规划数据，可用于比较不同的数学模型和优化算法。

SNDlib怎么来的？

学习过机器学习的小伙伴很清楚数据的重要性，这对于网络的设计和优化也是如此。SDNlib应运而生，作为可用标准化基准实例库，大家做的模型都可以用它里面的数据进行比较。

自2005年12月以来，SNDlib作为可生存固定电信网络设计的标准化测试实例库，已在http://sndlib.zib.de在线提供。这些 instances，以及最著名的 solutions和dual bounds，都可以从SNDlib网站上以各种格式查看和下载。此外，SNDlib还包含以BiBTeX条目形式提供的网络设计中相关出版物的参考文献的集合、与此领域相关的会议列表和邮件列表。SNDlib旨在成为未来测试和演示新的优化模型和算法的有效性的标准。

SNDlib的规划流程

1、首先需要准备SNDlib问题实例，网络数据和模型参数，也就是确定我们的问题和数据集。

2、通过数学建模的方法得到数学模型，网络数据就等同于我们的输入数据，问题转化为一个优化问题。

3、通过设计算法得到解决优化问题的方法。

4、再进行形式化转化得到SNDlib问题实例的解决办法。

SNDlib problem及其solution独立于任何数学模型或算法。为了解决这一问题，必须选择一个能够反映SNDlib模型中指定的设计参数的合适的数学模型。通常，相同的SNDlib模型可以用几个数学模型来表示，如边流公式或等效的路径流公式。这种数学模型与来自SNDlib网络的输入数据相结合，形成了一个数学意义上的特定问题实例。在求解得到的数学优化问题后，必须将其解转换为SNDlib解。库提供的数据属于图的上半部分，而库的用户可以通过研究不同的数学模型和解决方法来填写下半部分。

SNDlib数据概念

SNDlib提供了网络规划问题的 benchmark instances，solutions和 dual bounds。与Zimplimp[5]或AMPL[6]等混合整数编程建模语言所采用的方法类似，在SNDlib中，模型和数据彼此分离。SNDlib网络规划问题描述包括以下两部分：

1、一个SNDlib网络部分(也称为SNDlib network instance)，描述节点、链接、需求、容量、成本和其他规划数据。

2、一个SNDlib模型部分(也称为SNDlib model instance)，指定设计参数，例如，链接是定向的还是无定向的，需求的路由是否可以在多个路径上分割，或者应该使用哪个容量模型或生存性概念。

一个特定的SNDlib网络通常可以与各种SNDlib模型相结合，从而导致SNDlib网络规划问题的不同instance。

例如，一个给定的网络可能是没有生存能力的规划问题的一部分，也可能是另一个具有1+1保护的问题的一部分，或者具有分叉多商品流路由问题的网络和另一个具有单路径路由保护的问题的一部分。

针对特定SNDlib problem instance的SNDlib solution包括在SNDlib网络中指定的需求的路由和在满足SNDlib模型中指定的侧边约束的链路上安装适当的容量。

SNDlib网络

SNDlib网络描述了网络的结构、要路由的流量以及可允许的路由路径集。网络结构被定义为节点和链路的集合。这组链接定义了可用于承载流量的节点之间的潜在连接；允许并行链接。对于每个链路，容量和成本信息都包含预装容量的量及其成本，以及可在该链路上安装的具有相关成本的容量模块列表。此外，还定义了使用该链路的固定费用成本，以及通过该链路路由流量所产生的流量成本。

通信需求集描述了要路由的流量。每个需求的特征是其端节点和必须通过以某些基本路由单元的倍数表示的路由的网络进行路由的通信量。需求的路由单元定义了需求流量的一个单元(例如，对应于2Mbit/s、155Mbit/s或2.5Gbit/s)所消耗的链路容量。

最后，允许路由路径集定义为空列表，这意味着每个可能的路径都是允许的，或者为每个需求指定非空路径集。可以对每个需求施加跳点限制，即对每个可允许的路由路径的最大链路数。如果SNDlib模型指定使用特定的跳限制，那么它将进一步限制允许路径集。

SNDlib网络的示例

考虑一个表示SDH传输网络的三节点网络示例。针对本例，假设点对点需求请求是2Mbit/s或155Mbit/s的基本路由单元的整数倍。链路带宽可分别安装为155Mbit/s或622Mbit/s的整数倍。由于需要监测所需的开销带宽，如果2Mbit/s的比特率对应1个单元的容量，则155Mbit/s对应63个单元，622Mbit/s对应252个单元。

示例网络（SNDlib本机ASCII格式）：

节点部分描述了网络中的节点位置集。这些坐标仅用于图纸目的。

链接部分描述了一组潜在的链接及其可安装的能力和成本。假设该单元1对应于2个Mbit/s。然后，链路LAB有63个预装容量单元，成本为100个，而其他链路没有预装容量。对于所有链路，流单元的路由成本为10，而链路的固定收费成本为1000。每个链路上均可安装尺寸为63和252的容量模块；对于链路LAB，一个模块的成本分别为1200或3700（对于其他链路则类似）。

需求部分描述了需求及其参数。上面的例子包含了从A到B的两个并行需求，在不同的路由单元中给出。需求DAB1有65个单元，2Mbit/s（路由单元1），无跳限制。需求DAB2具有4个63x2Mbit/s单元（路由单元63），跳限制等于1；如果SNDlib模型指定考虑跳限制值（参见下一节），则最多只允许一条链接的直接路径。

允许路径部分描述了需求DAB1和DAB2的允许路径集。如果在SNDlib模型中，允许的路径模型是显式的列表，那么这里列出的路径最多是允许的，否则所有的路径都是允许的。需求DAB2的路径集可能进一步受到跳限制值的限制。更多的细节可在第3节和SNDlib网站上找到。

SNDlib模型

SNDlib模型指定设计参数值组合。设计参数作为一组属性及其可允许值给出（每个属性必须选择一个值），并在后续中进行描述。表1给出了属性及其允许值的概述。括号中给出的缩写将在本节结尾的示例中使用。

Demand model

此属性指定了流量的类型。允许的值是有向的和无向的。根据网络技术，流量可以对应于从需求的一个端节点到另一个（定向）的（定向）数据流（例如，IP数据包流）。在其他情况下，通信可能对应于一对节点（无向）之间的无向传输连接（例如，SDH网络中的VC-N）。

Link model

此属性指定如何使用链接的容量。允许的值是有向的、双向的和无向的。如果流量的性质是定向流量，则链接的容量可以仅适用于在一个方向（定向）流动的流量，或者可以由相反方向的流量（无方向）共享。在双向情况下，在链路的每个方向提供相同的容量用于路由定向的流量。

Link capacity model

此属性指定如何提供链路的容量。可接受的值包括线性链接容量、模块化链接容量和显式链接容量。在线性链接容量的情况下，可以安装任何数量的容量，甚至是分数值。否则，只允许使用离散的容量值。使用模块化的LINK容量，可以安装某些容量模块的整数倍的任何组合，例如表示光网络中不同光路比特率的混合物。使用显式的LINK容量，在给定列表中最多可以安装一个单一容量，例如，在SDH网络中选择一个特定的STM-N端口容量。

Fixed-charge model

此属性指定是否使用链接会导致固定收费成本。可接受的值为YES和NO。如果该值为YES，则会考虑网络数据中每个链路的固定电荷参数，否则将被忽略。固定收费成本反映了这样一个事实，即在一个链路上提供容量模块可能需要独立于实际容量量的初始投资。例如，要在一对节点之间安装多个传输系统，电缆段可能是容量独立的前提条件。

Routing model

此属性指定如何在可用路径之间分配需求的流量。允许值为单路径、连续数和整数。出于技术或操作上的原因，例如，为了避免数据包的重新排序，可能需要在单一路径（单路径）上路由需求的所有流量。否则，一个需求的流量可以在几条路径之间进行分割（分岔）。在这种情况下，在任何路径上流动的流量可以是任意的（连续的），例如在MPLS网络中，或者需要是需求路由单元（整数）的倍数，就像在传输网络中一样。

Admissible path model

此属性指定可用于路由流量的路径。可容许的值是显式列表和所有路径。通常，需求的流量可以在需求的端节点（ALL路径）之间的任何路径上进行路由。但是，有时还需要提供一组精心选择的路径，并要求流量只沿着这些路径进行路由(显式LIST)。

Hop limit model

此属性指定路径中的链接数是否有显式限制。允许值是个别HOP限制，忽略HOP限制。通常，交换和传输延迟是通过限制允许的路由路径上的中间节点(例如，IP路由器)或链路（例如，光传输系统）的数量来间接限制的。这进一步限制了可用于需求的可用路径集。如果将该模型参数的值设置为单个HOP限制，则任何允许路由路径中的链路数量将受到网络数据相应需求的跳限制的限制。另一方面，如果该值忽略HOP限制，则忽略所有跳限制值。

Survivability model

此属性指定要使用的生存性概念。此属性的允许值为无生存能力、一加一保护、共享路径保护和不受限制的FLOW重新配置。在最简单的情况下，网络不提供任何针对节点和链路故障的保护（没有生存性）。否则，将考虑几种机制来保护流量以防止故障。使用1+1保护（一加一保护），需求流量同时在两条链路或节点不相交路径上路由，一条是工作路径，另一条是热备用备份路径。交通恢复更为复杂，因为在发生故障的情况下，它需要重新路由交通流量。例如，可以选择将重新路由限制到受故障影响的流（共享PATH保护），或者也允许对未受影响的流进行重新路由（不受限制的FLOW重新配置）。

Other models

某些设计参数，在SNDlib的当前版本中没有被考虑在内，例如硬件模型。此外，迄今为止唯一考虑的设计目标是将总链路成本最小化。每个链路的成本包括固定费用成本、预装容量和选定容量模块的成本，以及路由成本。

Example of the SNDlib model

为每个属性选择一个可接受的值将定义一个SNDlib模型实例。请注意，并非所有允许值的组合都是有意义的；例如，无向需求只能与无向链路能力相结合。

使用SNDLib的本机ASCII格式构建的完整模型实例可能如下所示：

Naming conventions

我们为SNDlib问题引入了一个命名约定，它同时反映了网络的名称和模型的特性。该名称由SNDlib网络名称的缩写和指定选定设计参数值的字母序列组成。这些字母如表1所示，它们如上例那样排序，即首先是需求模型，然后是链接模型，以此类推。即，将根据网络示例和上述模型建立的问题实例命名为示例-U-U-M-N-C-A-N-N。

SNDlib解决方案

基本上，对SNDlib问题的解决方案包括链路配置和需求的路由配置，以满足所有方面的约束。在不详细说明的情况下，可以通过前面介绍的问题实例例子U-U-M-N-C-A-N-n来说明这一点。

在这个解决方案中，链路LAB除了具有尺寸为63的预装容量(对应于155Mbit/s)外，还配备了一个尺寸为252的模块(即622Mbit/s)。在LAC和LBC上安装了一个尺寸为63的模块。需求DAB1的65个2Mbit/s单元在两条路径上路由。相比之下，需求DAB2的所有4个大小为63的单元都在直接链路LAB上路由。在SNDlib网站上可以找到对可用的解决方案描述格式的详细描述，以及一个稍大一点的详细成本分析示例。

网络设计实例

目前，SNDlib包含22个网络，其拓扑结构如下图所示。每个网络都与几个SNDlib模型(基本上，每个网络的所有合理的SNDlib模型)相结合，构建了830个问题实例。SNDlib中包含的网络实例具有不同的背景。其中一些是来自于工业项目，其他项目被定义为涉及各种工业和学术伙伴的国际研究项目的参考网络。对于第三组网络实例，由于保密协议，背景无法公开。

具有工业背景的实例

以下网络实例已由网络运营商或网络设备制造商直接或通过学术合作伙伴提供。我们知道，在某些情况下，工业或学术合作伙伴已经修改了这些数据，以避免泄露内部信息。根据我们在行业项目方面的经验，我们怀疑其他网络实例也是如此。然而，我们假设这些数据集中提供的成本和需求结构离现实并不远。

网络实例	说明
DFN-BWIN, DFN-GWIN	源自于德国研究网络上的IP/OSPF规划问题，该网络由DFN-Verein运营，连接着大多数大学和研究机构。这些需求是基于网络中的流量测量值提出的。
FRANCE	由网络运营商提供的WDM规划数据。
GIUL39	源自于以SDH为底层传输技术的两层都市网络中的VPN规划问题。由设备供应商提供。已经为SNDlib构建了可安装的能力。
PDH	由网络运营商提供的PDH规划数据。
POLSKA	从20世纪90年代初起，波兰电信的SDH运输网络。
TA1, TA2	由网络运营商奥地利电信提供的SDH规划问题。
ZIB54	稍微修改一下来自电信网络运营商的真实世界的实例。

来自国际研究项目的实例

这一组中的网络实例已被定义为由欧洲委员会资助的大型研究项目中的参考网络。这些项目涉及主要的电信网络运营商和设备制造商，以及学术合作伙伴。因此，即使项目中定义的参考网络不能代表真实的网络，它们也会被精心构建，以符合现实的规划场景。

网络实例	说明
COST266	来源于COST266-欧洲科学和技术研究领域的合作组织(COST)的光子网络高级基础设施[7]项目。
NOBEL-US, NOBEL-EU, NOBEL-GERMANY, GERMANY50	诺贝尔网络是源自欧洲Nobel[8]项目的参考网络，该项目为各种SDH和WDM设备开发了详细的成本模型，如光纤、转发器、中继器、多路复用器和线卡，例如[9]。由德国国际t系统公司提供的德国50号网络，是诺贝尔-德国网络的延伸。

其他实例

下面的网络实例要么不属于上述类别之一，或者我们不知道它们的来源。这些网络实例在发送给我们之前就已经在网络设计文献中使用过；如果有的话，我们参考它们在文献中首次出现。对于一些旧的数据集，解决一个线性问题几乎足以解决整数问题，因为容量粒度比需求要小。在这种情况下，我们已经扩展了需求或能力，以使问题实例更具挑战性。

网络实例	说明
ATLANTA, NEWYORK, NORWAY	亚特兰大网络代表洛杉矶的ATM网络，纽约网络代表大纽约地区的电信网络，挪威网络代表挪威的骨干网络。这些网络已经在[10]等中使用。对SNDLib的需求和可安装容量已经进行了扩展。
DI-YUAN	一个背景未知的光城市网络。
JANOS-US, JANOS-US-CA	贾诺斯-美国网络首次在[11]上播出。janos-US-CA实例是在[12]中发布的该网络的一个扩展。
PIORO40	一个未发表的随机生成的具有SDH成本结构的网络。
SUN	该网络，首先在[10]中提出，是从纽约通过双定向所有链接和改变需求模式而构建的。我们已经将所有的需求缩放了10，以使它们成为整数。

参考文献

[1] Tobias Achterberg, Thorsten Koch, and Alexander Martin. MIPLIB 2003. Operations Research
Letters, 34(4):1–12, 2006. http://miplib.zib.de.
[2] G. Reinelt. TSPLIB–A Traveling Salesman Problem library. ORSA Journal on Computing, 3:376–384, 1991. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95.
[3] T. Koch, A. Martin, and S. Voß. SteinLib: An updated library on Steiner tree problems in graphs.
Technical Report ZR-00-37, Konrad-Zuse-Zentrum f¨ur Informationstechnik Berlin, 2000. http:
//elib.zib.de/steinlib.
[4] FAP web–A website devoted to frequency assignment. http://fap.zib.de, 2000–2007.
[5] T. Koch. Zimpl user guide. ZIB Report ZR-01-20, Konrad-Zuse-Zentrum f¨ur Informationstechnik
Berlin, 2001. http://zimpl.zib.de.
[6] R. Fourer, D. M. Gay, and B. W. Kernighan. A modeling language for mathematical programming.
Management Science, (36):519–554, 1990. http://www.ampl.
[7] S. De Maesschalck, D. Colle, I. Lievens, M. Pickavet, P. Demeester, C. Mauz, M. J¨ager, R. Inkret, B. Mikac, and J. Derkacz. Pan-European optical transport networks: An availability-based comparison. Photonic Network Communications, 5(3):203–225, 2003.
[8] NOBEL–Next generation Optical networks for Broadband European Leadership. http://www.
ist-nobel, 2004–2007.
[9] M. Gunkel, R. Leppla, M. Wade, A. Lord, D. Schupke, G. Lehmann, C. F¨urst, S. Bodamer, B. Bollenz, H. Haunstein, H. Nakajima, and J. Martensson. A cost model for the WDM layer. In International Conference on Photonics in Switching (PS 2006), Herakleion, Crete, Greece, October 2006.
[10] D. Bienstock, O. G¨unl¨uk, S. Chopra, and C.Y. Tsai. Minimum-cost capacity installation for multicommodity flows. Mathematical Programming, 81:177–199, 1998.
[11] M. De, V. Mariappan, V. Chandramouli, and S. Kuppusamy. US national network design. Presentation held at CReWMaN, University of Texas, Arlington, 2002.
[12] J. Tapolcai. Routing Algorithms In Survivable Telecommunication Networks. PhD thesis, Budapest University of Technology and Economics, March 2005.

本文标签： 传统数据库网络SNDlib