复杂网络可靠性研究

1复杂网络可靠性研究——国防科技大学信息系统与管理学院谭跃进国防科大信息系统与管理学院谭跃进2/140我们被网络包围着，几乎所有的复杂系统都可以抽象成网络模型，这些网络往往具有大量的节点，节点之间有着复杂的连接关系。国防科大信息系统与管理学院谭跃进3/140报告内容1.复杂网络可靠性概述2.指标体系与模型3.复杂网络可靠性的有关研究内容4.网络可靠性研究方法论国防科大信息系统与管理学院谭跃进4/140报告内容1.复杂网络可靠性概述2.指标体系与模型3.复杂网络可靠性的有关研究内容4.网络可靠性研究的方法论国防科大信息系统与管理学院谭跃进5/1401复杂网络可靠性概述无标度网络的双重性复杂网络抗毁性举例复杂网络可靠性定义国防科大信息系统与管理学院谭跃进6/140无标度网络的双重性无标度网络定义1998年，印第安纳州圣母大学物理学教授巴拉巴斯及其同事在对万维网拓扑结构进行研究时发现，考察的情况比随机网络所描述的要复杂，即钟形曲线的连接平均数或标度不见了，它所产生的是一条不断递减的曲线。巴拉巴斯把具有这种性质的网络称之为无标度网络（scale-freenetworks）。无标度网络的双重性生机勃勃：无标度网络在随机打击下，生机勃勃，抗毁能力很强脆弱：在智能打击下，无标度网络显得异常脆弱国防科大信息系统与管理学院谭跃进7/140无标度网络的双重性巴拉巴斯等人把无标度网络置于两种类型的打击之下（随机打击、智能打击）。在前一种打击中，他们随机地攻击了个别的节点，在后一种中，则仅仅拿掉了这些活动中心──网络中四通八达的节点。在随机打击下，随机网络很容易遭受伤害。由于越来越多的节点被摧毁，所以从一个节点到达另外一个所需的步骤数量稳步增加。与此形成对照，无标度网络在这种打击面前则生机勃勃，抗毁能力很强。在智能打击下，随机网络的衰败方式与在随机打击下相同。但无标度网络一旦5％的活动中心被去除，穿越网络所需的步骤数量就增加一倍。巴拉巴斯说：“这表明无标度网络总的来说很容易受到智能打击伤害。”国防科大信息系统与管理学院谭跃进8/140复杂网络抗毁性举例之一美加电网的大崩溃事故已经过去一年了，或许瞬间的黑暗并没有使远在亚洲的我们感受到纽约人的惊栗，但是网络中无意或有意生成的安全隐患却令人无法逃避。面对与生活日渐亲密的网络，我们不禁要问：“网络到底有多可靠？”国防科大信息系统与管理学院谭跃进9/140复杂网络抗毁性举例之一北美电力网是一个由大型发电厂为集散节点，以主干电力网相互连接起来的类似无标度网络的高度集群电网。由于他们使用的是同步交流电网，只要一家电厂出事，频率异动就会瞬间波及全网。美加电网的崩溃清楚地解释了“集群现象”，并且极其吻合无标度网络理论对集散节点的定义和因此而形成的对于网络安全特性的估计。虽然所有对电力网络的研究工作还不能确定美加电网就是一种“无标度网络”，但有一点已经明确，那就是电力网是一个复杂的网络系统，对网络中一定数量集散节点的蓄意攻击，就能破坏整个网络的正常运行，而且如果这些集散节点之间的松散联系一旦相互影响、交叉感染，整个网络的安全性就将大大降低。国防科大信息系统与管理学院谭跃进10/140复杂网络抗毁性举例之二反映在互联网中，我们几乎都使用着微软的Windows开放式操作平台，针对单一安全漏洞的病毒就足以感染大部分网络连接，几位美国网络安全专家在最近的一份联合报告中极力呼吁，过分依赖微软软件可能导致“大规模、雪崩式故障”。国防科大信息系统与管理学院谭跃进11/140复杂网络抗毁性举例之三网络抗毁性分析的一个重要实例是食物链网络。对于食物链网络，由于规模限制，食物链网络的度分布没有得到最终研究结果，度分布存在幂律分布、均匀分布、以及指数分布等多种形式。在这样的网络上，如果发生个别物种的衰落或死亡会对整体生态系统产生什么影响呢？国防科大信息系统与管理学院谭跃进12/140复杂网络抗毁性举例之四野战地域通信网是由25-30个干线节点组成的拓扑结构为栅格状的大型无线通信系统，为陆军作战部队之间的信息传递提供迅速、安全和可靠的通信。综合保障网络是为了保障战争、抗洪抢险等重大行动所需，以物资贮存点等保障实体为依托，把各种保障资源按一定的要求和原则合理部署，在空间上形成网络化布局的保障体系。在这个体系中，仓库、医院、工厂、供应站等构成保障实体，铁路、公路、水路、管线、航线等构成连接网络的纽带，在网络中运行的有信息、物资、人员、技术实体等。相对于日常通信、运输等问题，这些军用网络更强调网络在恶劣环境下的抗毁能力。国防科大信息系统与管理学院谭跃进13/140复杂网络可靠性定义复杂网络的可靠性、抗毁性研究一直是一个十分棘手的问题，这主要归根于一直以来我们对复杂网络的拓扑结构知之甚少，甚至有很大偏差。以往的复杂网络抗毁性模型都是建立在随机网络模型上的，在抗毁性分析中我们也仅考虑随机打击。最新的研究表明不同拓扑结构的网络对这两种损伤的抗毁性存在很大差异。这使得我们不得不重新回过头来研究复杂网络的可靠性、抗毁性。什么样的拓扑结构可靠性更好？抗毁性更强？国防科大信息系统与管理学院谭跃进14/140复杂网络可靠性定义（复杂）网络可靠性：是指网络系统在规定条件下和规定时间内完成规定功能的能力，可靠性的概率度量称为可靠度。这个定义包含了五个方面的内容:对象、条件、时间、功能和能力。国防科大信息系统与管理学院谭跃进15/140报告内容1.复杂网络可靠性概述2.指标体系与模型3.复杂网络可靠性的有关研究内容4.网络可靠性研究的方法论国防科大信息系统与管理学院谭跃进16/1402指标体系与模型网络可靠性指标体系网络抗毁性评估模型网络抗毁性优化设计模型国防科大信息系统与管理学院谭跃进17/140网络可靠性研究的层面及任务研究层面研究任务测度指标网络拓扑层研究拓扑结构的可靠性及网络组织的要求和改进措施抗毁性、生存性网络设备层研究通信设备终端到终端的可靠性及整个网络系统设备的可靠性设备可靠性网络路由层分析网络路由算法的效率、流量控制、路由管理网络运行层研究网络环境和网络异常故障的规律对网络可靠性的影响可用性网络业务层分析网络业务能力及服务质量，对网络的性能可靠性进行综合评价完成性、有效性网络管理层研究网络维护和管理体系及提高维护管理水平的措施国防科大信息系统与管理学院谭跃进18/140网络的效能分析网络系统效能定义：系统在规定的条件下，满足给定的定量特征和服务要求的能力。它是系统可用性、可信性及固有能力的综合反映。效能分析的主要思想：无论何时，一旦需要使用某个系统，它就应该处于能正常工作的准备状态（A），并要求它在执行任务过程中具有可信性（D），同时，还必须具有完成预定任务的能力（C）。也即要求系统“招之即来、来之能战、战之能胜”。国防科大信息系统与管理学院谭跃进19/140效能分析模型E=A·D·CA：可用性向量D：可信性矩阵C：品质因素向量国防科大信息系统与管理学院谭跃进20/140网络的效能分析效能分析可用性可信性品质因素可靠性维修性保障性抗毁性生存性有效性安全性可靠性连通性信息时延信息的丢失率话务的呼损率网络的容量拥塞测度与控制国防科大信息系统与管理学院谭跃进21/140可用性可用性也称完好性，它是效能研究的目的，是衡量网络处于可工作状态的程度。这种程度往往决定于网络的可靠性、维修性和保障性。网络的可用性问题是研究在一定的网络拓扑结构下，根据网络中各种部件（节点和边）处于不同工作状态的概率，给出网络在开始执行任务时的系统状态和特性。国防科大信息系统与管理学院谭跃进22/140可信性可信性是研究网络效能问题的关键。可信性是指在人为或自然的破坏作用下，网络在规定的条件下和规定的时间内生存的能力。由网络的可信性定义中分离出研究有关网络可信性问题的基本概念有：抗毁性、生存性、有效性、安全性、可靠性（狭义）。国防科大信息系统与管理学院谭跃进23/140网络的抗毁性（Invulnerability）网络在人为破坏作用下的可靠性，它假定“破坏者具有关于网络结构的全部资料，并采用一种确定的破坏策略”。对于一个网络，网络的抗毁性是指至少需要破坏几个节点或几条链路才能中断部分节点之间的通信，即指出破坏一个网络的困难程度。抗毁性通过两个可靠性的确定测度—粘聚度和连通度来表示。国防科大信息系统与管理学院谭跃进24/140抗毁性（李德毅院士）“系统在受到敌方物理破坏或火力攻击环境下，在规定时间内，完成规定功能的能力”。换个角度看，这个定义实际是在说：因系统中的部件（如部分信道或部分设备）受损失效，系统结构发生变化或者重组后完成规定功能的能力。国防科大信息系统与管理学院谭跃进25/140抗干扰性（李德毅院士）系统在受到敌方电磁干扰和攻击环境下，在规定时间内，完成规定功能的能力。换个角度看，这个定义实际是在说：系统中的部件在电磁攻击环境下，其能力在不同程度上失效，性能指标在量的方面下降。但由于系统具有结构上的容错性，能在一定程度上承受环境的恶化。国防科大信息系统与管理学院谭跃进26/140粘聚度（Cohesion）对于一个连通网络，定义CHij为断开一对节点（i，j）之间所有通路所需去掉的最少链路数，则网络的粘聚度为：粘聚度对应着网络的最小链路割集。,minijijCHCH国防科大信息系统与管理学院谭跃进27/140连通度（Connectivity）对于一个连通网络，定义CNij为断开一对节点（i，j）之间所有通路所需去掉的最少节点数，则网络的连通度为：连通度对应着网络的最小节点割集。,minijijCNCN国防科大信息系统与管理学院谭跃进28/140粘聚度、连通度的缺陷要使一个网络解体，至少需要去掉CH条链路或者CN个节点。这种解体，可能把一个网络分解为两个或多个子网络，也可能把一个节点从网络中分离出来。对于网络业务来说，前者比后者带来更严重的后果。国防科大信息系统与管理学院谭跃进29/140粘聚度和连通度（Boesch等）在通信网中，为了把一个具有m个节点的子网络从通信网中分离出来所需去掉的最少链路数NL(m)或最少节点数NN(m)，显然：minmCHNLmminmCNNNm国防科大信息系统与管理学院谭跃进30/140粘聚度和连通度（Wilkov）如果考虑网络传输的时延，对于一个网络直径为k的通信网，为使网络直径k超过阀值km时必须去掉的最少链路数DL(k，km)或最少节点数DN(k，km)。国防科大信息系统与管理学院谭跃进31/140抗毁性小结网络的抗毁性是从图论的概念中提出来的，在通信网的可靠性分析中得到广泛应用。抗毁性从网络连通性的角度描述网络拓扑结构对通信网可靠性的影响，它是可靠性的一种确定性测度。对于军用通信网来说，网络的抗毁性无疑是一项重要的指标。网络抗毁性的实质是研究网络的拓扑结构的可靠性，是网络可靠性的一种静态指标。抗毁性包括节点连通度、节点粘聚度、网络设备地域分散密集度、敌方对网络的结构掌握程度情况和敌方的攻击力量等，可以利用可信性指标体系，通过层次分析法等综合计算方法进行计算。国防科大信息系统与管理学院谭跃进32/140网络的生存性（Survivability）基于网络连通性的概率测度。网络在随机破坏作用下的网络可靠性。在军用环境中，随机性破坏表现为“破坏者只有关于网络结构的部分资料，在采用一种随机的破坏策略”；在商用环境中，随机性破坏则表现为网络部件（节点和链路）的自然失效。网络的生存性由可靠性的概率测度——连通概率来表示。国防科大信息系统与管理学院谭跃进33/140几种连通概率端到端的连通概率。Baran：在遭受破坏后幸存下来的网络中，选出一个最大的连通子网络，其节点数的平均值（对所有样本作平均）占原网络节点数的百分率，即为通信网的连通概率。Frank：在遭受破坏后幸存下来的网络中，任意选取一个节点，所有能与它相连通的节点数占原网络节点数的百分率。整个网络构成一个连通网络的概率。国防科