网络系统可靠性研究现状与展望

网络系统可靠性研究现状与展望姓名：杨玉学校：潍坊学院院系:数学与信息科学学院学号：10051140234指导老师：蔡建生专业：数学与应用数学班级：2010级二班一、摘要伴随着人类社会的网络化进程，人类赖以生存的网络系统规模越来越庞大、结构越来越复杂，这导致网络系统可靠性问题越来越严峻。本文首先探讨了网络系统可靠性的发展历程、概念与特点，进而从度量参数、建模、分析、优化四个方面系统综述了网络系统可靠性的研究现状，最后对网络系统可靠性研究未来的发展进行了展望。二、关键词：可靠性；网络系统；综述；现状；展望三、引言21世纪以来，以信息技术的飞速发展为基础，人类社会加快了网络化进程。交通网络、通信网络、电力网络、物流网络……可以说，“我们被网络包围着”，几乎所有的复杂系统都可以抽象成网络模型，这些网络往往有着大量的节点，节点之间有着复杂的连接关系。自从小世界效应[1]和无标度特性[2]发现以来，复杂网络的研究在过去10年得到了迅速发展，其研究者来自图论、统计物理、计算机、管理学、社会学以及生物学等各个不同领域，仅发表在《Nature》和《Science》上的相关论文就达百篇。对复杂网络系统结构、功能、动力学行为的深入探索、科学理解以及可能的应用，已成为多个学科领域共同关注的前沿热点[3-14]。随着复杂网络研究的兴起，作为复杂网络最重要的研究问题之一，网络系统可靠性研究的重大理论意义和应用价值也日益凸显出来[15,16]。人们开始关注：这些复杂的网络系统到底有多可靠？2003年8月美加大停电事故导致美国的8个州和加拿大的2个省发生大规模停电，约5000万居民受到影响，损失负荷量61800MW，经济损失约300亿美元；2005年12月台湾海峡地震造成多条国际海底通信光缆发生中断，导致整个亚太地区的互联网服务几近瘫痪，中国大陆至台湾地区、美国、欧洲等方向国际港澳台通信线路受此影响亦大量中断；2008年1月，南方冰雪灾害导致我国十余个省市交通瘫痪、电力中断、供水停止、燃料告急、食物紧张……这些我们赖以生存的网络系统规模越来越庞大，结构越来越复杂，但越来越频繁发生的事故也将一系列严峻的问题摆在我们面前：一些微不足道的事故隐患是否会导致整个网络系统的崩溃？在发生严重自然灾害或者敌对势力蓄意破坏的情况下，这些网络系统是否还能正常发挥作用？这些正是网络系统可靠性研究需要面对的问题。四、正文1网络系统可靠性的发展历程、概念及特点1.1网络系统可靠性的发展历程可靠性作为专门课题始于二战期间对电子元件可靠性的研究。从20世纪60年代开始，可靠性研究从单个电子元件可靠性逐步扩展到一般产品的可靠性（例如电视机、洗衣机、计算机等）以及更为复杂的关联系统可靠性（例如火箭发射系统、核反应控制系统，军事指挥控制系统），同时还逐步形成了可靠性数学、可靠性物理、可靠性工程等重要研究领域与分支学科[17]。网络系统作为一类特殊的系统，其可靠性研究最早可追溯到1955年Lee对电信交换网络的研究，早期主要集中于通信网络领域。其中，20世纪70年代以前主要是以网络的连通作为网络可靠性规定功能来研究。20世纪80年代，由于通信网络规模的迅速扩张，使用频度、网络负载的快速增加以及动态路由技术的采用等原因，网络拥塞和延时逐渐成为了网络可靠性主要考虑的因素。这一时期，网络系统可靠性研究主要集中于通信网络基于性能的可靠性。20世纪90年代后，伴随着人类社会网络化进程加快，网络系统可靠性逐渐成为可靠性研究领域的热点，研究对象从通信网络扩展到电力网络、交通网络、物流网络等。1.2网络系统可靠性的概念及特点从系统学的观点来看，网络系统是一类特殊的系统形态，其中网络节点是系统的组成元素，网络的边体现了元素之间相互作用、互相依赖[18]。系统可靠性指系统在规定条件下和规定时间内完成规定功能的能力[19]。网络作为一类特殊的系统形态，其基本可靠性可定义为在规定条件下和规定时间内保持连通的能力，其任务可靠性可定义为在规定条件下和规定时间内完成规定的物质流、信息流、能量流传输任务的能力。网络系统可靠性相对于一般系统可靠性具有以下特点：1）复杂性。一般系统中组成单元（子系统）之间逻辑关系简单、明确，而网络系统中节点之间的相互关系复杂，不能用简单的串联、并联、混连或者表决系统模型来刻画，系统结构呈网络状。这意味着传统的可靠性框图、故障树分析方法很难适用于网络系统可靠性研究。2）网络流。网络系统的主要任务是在网络节点之间通过网络的边传输物质流、信息流、能量流，网络系统可靠性研究不仅关注网络系统保持连通的基本能力，还关注网络系统完成传输网络流任务的能力，例如基于传输时延的可靠性、基于传输容量的可靠性等等。3）动态性。在一般系统可靠性研究中，研究对象大多是静态的、确定的，系统组成单元的数量、组成单元之间的关联方式基本保持不变。但网络系统，特别是大规模复杂网络系统，例如因特网、交通网等，往往都是动态的、不确定的，网络中节点数量会随着时间不断增减，网络结构也会随着时间不断演化。4）分布性。在一般系统可靠性研究中，无论是单个元件、产品，还是复杂的关联系统，整个系统在空间上都相对集中。但网络系统往往都具有很强的分布特性，网络节点分散在大范围的空间中，每个节点是一个相对集中的元件、产品或者子系统。这种空间上的分布特性导致了网络系统功能的特殊性，在网络系统中常常出现局域故障或者部分功能缺失的现象。2网络系统可靠性研究现状下面，我们从可靠性度量参数、可靠性分析方法、网络可靠性优化方法综述目前网络系统可靠性研究现状。2.1网络系统可靠性度量参数2.1.1基本可靠性1）抗毁性网络抗毁性（Invulnerability）是基于拓扑结构的可靠性参数，不考虑网络节点和边的可靠度，衡量的是在网络中的节点或边发生自然失效或遭受故意攻击的条件下，网络拓扑结构保持连通的能力[20]。目前，网络抗毁性研究主要基于两大理论：图论和统计物理。基于传统图论的网络抗毁性参数。图论是组合数学领域最活跃的分支之一，图的抗毁性是图论的重要研究内容。目前，在图论中有很多图的不变量被用来刻画图的抗毁性。例如，连通度（connectivity），坚韧度（toughness）[21]，完整度（integrity）[22]，粘连度（tenacity）[23]，离散数（scatteringnumber）[24]，核度（coritivity）[25]，膨胀系数（expansioncoefficient）[26]，自然连通度（naturalconnectivity）[27]。基于传统图论的抗毁性度量参数由于侧重对抗毁性的精确刻画导致绝大多数抗毁性测度指标的计算都是NP问题。这意味着从计算复杂性角度来看，传统图论的抗毁性研究很难适用大规模复杂网络。基于统计物理的网络抗毁性参数。近年来网络抗毁性研究的焦点出现了一个重要的新变迁，即从研究小规模简单网络的精确性质转变为研究大规模复杂网络的统计属性，统计物理的很多方法开始被广泛应用到复杂网络研究中[28-32]。基于统计物理的抗毁性参数通过观察节点或边移除过程中网络性能的变化，用网络状态发生相变时的临界节点（边）移除比例来刻画网络的抗毁性，常用的网络性能指标包括连通片数目、最大连通片规模、网络直径、平均最短路径长度、网络效率[33]、可达节点对数目[34]等。2）生存性网络的生存性（survivability）是指对于节点或链路具有一定失效概率的网络，在随机性破坏作用下，能够保持网络连通的概率[35]。生存性参数是概率性的，它不仅和网络的拓扑结构有关，也和网络部件的故障概率、外部故障以及维修策略等有关。常用的度量参数包括端端可靠度、K端可靠度和全端可靠度。生存性是基于概率论和图论的知识提出来的，描述了随机性破坏以及网络拓扑结构对网络可靠性的影响。2.1.2任务可靠性基于连通性能的基本可靠性是网络可靠性的一个基本要求，但网络系统一旦投入使用，就要承载一定的业务负荷，如通信网络的数据业务，输电网络的电传送量，交通网络的运输量与流量等，网络部件发生故障时会引起网络性能下降甚至瘫痪，从而不能完成预定任务，在这种情况下网络实际上是不可靠的。所以，与网络所承载的任务相结合，网络系统任务可靠性作为一个综合反映网络系统可靠性的参数更加具有实际意义。对于承载一定任务的网络系统来说，“召之即来、来之能战、战之能胜”，是决定网络系统发挥其性能的决定性要素，也是检验网络系统在任务执行过程中可靠性水平的准绳。“召之即来”需要网络系统在任意时刻的可用性；“来之能战”反映了网络使用过程中的可信性；“战之能胜”则综合衡量了网络的任务完成性。1）可用性网络系统的可用性（Availability）是描述网络在外部资源可用的条件下，在规定时间内的任何时刻，处于能执行所需功能的能力[36]。由于中英文翻译的差异，Availability也翻译成有效性。可用性的常用度量指标为可用度，包括瞬时可用度、平均可用度、极限平均可用度和稳态可用度等。经典的系统可用性参数可以用来衡量网络的可用性，但随着网络用户对网络的可用性要求越来越高，如何较公正地评估承载不同业务的网络系统的可用性成为迫切的问题[37]。2）可信性网络的可信性（dependability）是指网络已经进入开始执行任务的状态条件下，对在执行任务过程中某个瞬间或多个瞬间的网络状态量度。可信性描述了网络在完成任务期间的状态，即持续完成任务的能力。该指标受可靠性、维修性、安全性和生存性等因素的影响。网络系统的可信性问题是近年来随着人们对网络安全的日益重视开始的，主要包括网络与用户的可信性模型[38]、可信网络的体系结构[39]、服务的可生存性[40]及网络的可控性[41]。目前网络的可信性还没有形成完整的体系，许多概念尚处在摸索阶段，尤其对其基本属性和面临的关键问题上并没有清晰一致的描述[42]。3）完成性网络完成性（performability）是指系统在任务开始时可用性一定的情况下，在规定的任务剖面内，系统正常运行或降级完成服务要求的能力。完成性综合考虑了网络系统的可靠性和业务能力[43]，指出网络在不同业务性能级别上正常或降级地完成规定业务的能力。完成性的大小主要由网络部件可靠性水平、网络拓扑结构和网络部件的服务能力、网络流量分布等因素决定[44]。在实际工程应用中，网络系统具有不同的业务性能水平，并且具有全功能、降级运行、最低运行等特点，经常使用的参数据此分为全功能运行完成度、降级运行完成度、最低运行完成度等。2.2网络系统可靠性分析网络可靠性分析是网络可靠性研究中的一个重要内容，是指在给定网络部件可靠度的条件下，研究如何计算各种网络系统的可靠性度量参数。目前，计算网络可靠性度量参数的方法主要有解析方法和仿真方法两大类。2.2.1解析分析方法1）精确解析方法利用图论和概率论的方法对网络可靠性进行精确分析和计算，包括状态空间法、容斥原理法、不交积和法、因子分解法、图变换法、定界法、随机过程法等。状态空间法状态空间法是计算网络可靠性最简单的方法，通过枚举出网络正常工作的所有互斥的状态而计算相应的可靠度。网络系统环境的复杂性和任务的不确定性等因素，使得利用数学模型和方法来分析求解网络任务可靠性很难，因此，状态空间法就成为了评估网络任务可靠性的有效方法之一。文献[45]在考虑部件失效、网络容量、用户需求的基础上，利用最小路集法分析了网络的有效状态空间，进而得到网络的任务可靠性；文献[46]在讨论了电信网不同状态通过量之间的一般性关系后，得到了一种不需枚举所有网络状态来计算网络可行性精确值的方法。对于n个部件的网络，该方法需要遍历网络的所有状态，逐一分析是否可靠，其计算复杂度是O(2n)。显然，通过枚举所有状态来计算大规模网络的可靠度是很困难的，状态空间法只适合于较小网络可靠性的计算。容斥原理法容斥原理法是按照组合数学的容斥原理公式求网络的可靠度。一个路集对应着网络的一个工作状态，一个割集对应着网络的一个故障状态，因此该方法将网络可靠度表示为全部最小路集的并（或将网络故障度表示为全部最小割集的并），然后采用容