Survivable Network Design: The State of the Art

In the past few years the telecommunications industry has undergone significant changes. We are rapidly evolving to a state where audio/visual and data traffic is all provided on the same networks. Telecommunication companies are investing billions of dollars in the design and maintenance of telecommunication networks to provide the users with the better quality of service that they have begun to expect. Due to their high capacity, fiber optic cables have become the medium of choice in the deployment of such new networks worldwide. Such high capacities encourage telecommunication providers to create networks that are substantially more sparse than previous copper based networks. Unfortunately, with sparsity comes vulnerability to failure. Given the dependence on the varied services offered by the modern networks, the magnitudes of the investments involved and the costs of disasters it is only logical that researchers look at problems in survivable network design as an interesting research question. There have been a number of papers that have addressed these and other related issues. In this paper we try to classify the area of survivable network design and provide a classification scheme for the same.     

Improved Lower Bounds on the Price of Stability of Undirected Network Design Games

Bounding the price of stability of undirected network design games with fair cost allocation is a challenging open problem in the Algorithmic Game Theory research agenda. Even though the generalization of such games in directed networks is well understood in terms of the price of stability (it is exactly H _n , the n-th harmonic number, for games with n players), far less is known for network design games in undirected networks. The upper bound carries over to this case as well while the best known lower bound is 42/23≈1.826. For more restricted but interesting variants of such games such as broadcast and multicast games, sublogarithmic upper bounds are known while the best known lower bound is 12/7≈1.714. In the current paper, we improve the lower bounds as follows. We break the psychological barrier of 2 by showing that the price of stability of undirected network design games is at least 348/155≈2.245. Our proof uses a recursive construction of a network design game with a simple gadget as the main building block. For broadcast and multicast games, we present new lower bounds of 20/11≈1.818 and 1.862, respectively.     

支持高速网络生存性的资源管理机制

在分析故障快速恢复机制的基础上，重点研究了支持自下而上性的资源策略机制，包括空闲容量的设计和动态调整两方面。结合资源管理。提出了生存性准入控制算法，作为正在研究的生存性服务质量框架的一个重要组成部分。     

生存性分析方法中的3R量化分析

为了保障网络系统在面临攻击的时候能够稳定、可靠地提供服务,必须考虑网络系统自身的生存能力。生存性是系统在安全性之上必须面对的问题,通过对系统生存性的量化分析有助于对系统的生存性进行准确的评价和对比。该文在介绍生存性分析方法SNA基础上,分析了3R的任务和功能,提出了定量分析框架。在量化分析中,分别对入侵的危险程度、识别率、服务恢复时间等性能确定了参数模型。对这些数据的综合计算得出系统3R量化结果,作为生存性分析的重要结论。提出了提高系统3R能力的具体措施,从而实现了生存性系统的分析和设计。     

Hop-Constrained Node Survivable Network Design: An Application to MPLS over WDM

In this paper, we address a hop-constrained node survivable network design problem that is defined in the context of multi-protocol label switching (MPLS) over wavelength division multiplexing (WDM) networks. At the lower WDM layer, we consider a maximum length constraint for optical connections between MPLS routers. At the upper MPLS layer, we consider survivability as well as maximum delay constraints. Survivability is guaranteed by routing each demand through D node-disjoint paths and maximum delay is guaranteed by constraining all paths to a maximum number of hops. An Integer Linear Programming model, based on the previous works by Gouveia et al. (Proc of IEEE INFOCOM, 2003, and Telecommunications network planning: innovations in pricing, network design and management, pp 167–180, 2006) is used to model the network design problem considering two different survivability mechanisms: path diversity (where each demand is equally split over the D paths) and path protection (where any D–1 out of the D paths have enough capacity to support the total demand). For both mechanisms, we use the NSFNet and EON real world networks to make a cost analysis of the design solutions for different values of D. In the path diversity mechanism, the results consistently show that greater values of D impose a cost penalty that is greater than the gain in the percentage of demand that is protected. In the path protection mechanism, where all traffic is totally protected, the results show that the network solutions obtained with D=3 node-disjoint paths have consistently lower costs than the network solutions obtained with D=2 node-disjoint paths. However, using values of D that are greater than 3 led to network solutions with larger costs. Supported by FCT project POCTI - ISFL - 1- 152.     

生存性网络信息系统生存能力分析

通过系统生存特性的分析,能正确地指导生存性需求分析,客观地评估网络信息系统的生存能力.系统生存性特性分析是系统生存性分析的前提,本文首先通过系统状态转换图对网络信息系统的生存性特性及其相互关系进行定性分析,在此基础上,通过数学方法对3RA特性进行了量化分析,得出3RA的量化表达形式.另外,在量化分析的过程中,充分考虑了系统环境和用户的生存性需求对系统生存性的影响.     

生存光传输网络的交叉连接模块结构

基于波分复用技术的光传输网络在克服当前网络容量瓶颈的同时又面临网络生存的挑战,它必须快速、有效地恢复因网络故障而受损的工作光路。该文分析了四种基本网络恢复技术以及与之相对应的OXC节点模块结构,即:保留光纤链路方式、保留波长链路方式、保留波长路径方式以及动态波长路径方式;并从光连接恢复时间、网络资源效率和控制复杂度三个侧面比较了不同OXC结构对于网络生存的影响。     

无线传感器网络可生存路由算法

提出基于功率控制的分布式可生存路由算法,通过节点分布密度确定初始发射功率,利用转发数据进行实时反馈以动态调整节点覆盖范围,引入专用转发簇头减少普通节点的能耗。实验证明,该算法在节点分布不均、部分节点失效等情况下仍能保证低能耗和可靠传输,具有良好的可生存性。     

移动终端网络可生存数据库安全防篡改仿真

采用当前方法对可生存数据库进行安全保护时,存在对数据加密所用的时间较长、数据在数据库中的可用度较低、加密效率低和有效性差的问题,为此提出移动终端网络可生存数据库安全防篡改方法。在流控思想的基础上计算用户在可生存数据库中的可信度,通过令牌漏桶算法对用户请求进行排序,降低请求队列在数据库中的拥塞程度,在请求队列排序和用户可信度的基础上确定数据库中请求的转发总数,通过可信度管理、队列管理和请求转发管理构成可生存数据库的第一道防线。在集中式认证机制的基础上引入时间戳动态因子,采用混合动态数据加密算法对数据库中的数据进行加密,实现移动终端网络可生存数据库的安全防篡改保护。仿真结果表明,所提方法的加密效率高、有效性好。     

管理信息网抗毁构建研究

在机动通信组网时,网络管理信息网是网络管理系统对各节点设备进行参数下发和状态监控的交互通道,在基于ATM虚连接和IP路由器构建的网管信息网中,通过研究网络互连策略和IP动态路由技术,构建了不受限于节点连接接口的抗毁管理信息组网,提高了网络的顽存能力,拓宽了机动通信的适应性,该方法可在工程中推广应用。     

基于SMP的分簇WSN生存性评估模型

无线传感网(WSN)很适合用于战场侦察和应急通信等场合,增强WSN的生存能力并对其进行量化评估逐渐受到关注。本文提出一种基于半马尔可夫过程(SMP)的分簇WSN生存性评估模型,该模型在考虑应急通信中簇头生存状态的基础上建立了基于SMP的簇头生存状态转移图;结合网络生存性需求计算WSN的生存性效用函数,并定量分析了多种评价指标对网络生存能力的影响及其相关性;进而,利用该模型对采用SRPC协议和RLEACH协议的WSN生存能力进行了量化评估和比较分析。分析与验证结果表明,提出的生存性评估模型不仅可以对应急通信中WSN的生存能力进行客观有效的评估,还能对WSN的实际部署和应用提供参考依据。     

基于FC的抗毁安全关键网络体系结构

安全关键网络对于安全关键系统的生存和发展起着决定性的作用,随着安全关键系统应用环境的变化,抗毁机制和实时通信机制已成为安全关键网络研究的2个关键问题。该文分析了5种现有安全关键网络的组成技术,指出了它们存在的不足。提出了一种基于FC的抗毁安全关键网络体系结构,针对该结构设计了一种双重自愈算法以减少网络故障的恢复时间,并提高网络恢复成功率。     

一种可生存的数据库安全结构设计与实现

提出了一种基于容忍入侵的可生存的数据库安全结构.这种结构将冗余和多样性技术相结合,采用秘密共享方案,实现数据库系统的可生存性,以及关键数据的机密性.与其它容忍入侵的数据库系统相比,本文所提出的数据库安全结构,采用系统整体安全策略,综合多种安全措施,实现了系统关键功能的安全性和健壮性.     

基于业务优先级划分的虚拟网可靠性映射算法

现有研究在重映射失效虚拟网过程中未对不同类型的虚拟网承载业务进行有效区分,导致资源收益较低。为此,提出一种基于业务优先级划分的虚拟网可靠性映射算法。定义虚拟节点和虚拟链路的重要性指标,运用混合整数线性规划方法将基于业务优先级划分的虚拟网可靠性映射问题建模为最优化问题。在此基础上,提出快速可扩展的启发式虚拟网可靠性映射算法,以提高失效虚拟网的重映射效率。实验结果表明,该算法在虚拟网请求接受率、服务提供商收益和利润成本比3个指标上,表现优于FD-EVN、APG-TABU和MW-AC算法。     

节点与链路协同映射的生存性虚拟光网络映射算法

针对弹性光网络中单链路故障问题,提出一种基于匈牙利算法求解链路映射方案的节点与链路协同映射保护算法CMST-HA。将虚拟网络请求的节点与链路分别划分为主动类型与被动类型,把主动类型节点映射至邻接链路频谱资源丰富且邻接节点计算资源充足的物理节点上,在主动链路时使用匈牙利算法求解出最小映射开销方案并完成映射,确定被动节点的映射位置,利用KSP算法为被动链路选择映射路径,在此基础上为虚拟网络请求的最小生成树链路提供备份路径。仿真结果表明,与RVNM、CMST算法相比,CMST-HA算法不仅能够降低虚拟网络请求阻塞率,而且可增加物理网络收益。     

可生存系统的两类研究方法

现有安全技术己经不足以对抗日趋严重的计算机系统及网络的安全问题,根据对可生存系统技术的需求,给出了目前生存技术的两类研究方法：可生存设计和入侵响应。以文件系统为例,阐述可生存设计的思想和方法;重点以可生存数据库为对象,描述入侵响应的3种具体实现方案：入侵恢复,隔离和围堵。另外,针对每一个方案,提出并描述了实现的模型。     

宽带接入系统中的用户行为、网络价格及网络行为

介绍了网络价格、用户行为及网络行为的含义．并分析了它们三者之间的关系，在仿真实验的基础上，研究了在小区宽带接入系统中，网络价格对用户行为和网络状态的影响．     

战场环境中基于簇的WSN生存性路由协议

当无线传感网络应用于战场环境时,复杂恶劣的网络环境以及传感节点受限的能源、内存和通信能力导致节点容易失效、遭受攻击或被俘获,从而影响侦察任务的完成。本文提出一种基于簇的生存性路由协议—SRPC,该协议通过密钥协商和身份认证等机制抵御恶意节点的攻击;并在主簇头被摧毁后启用备用簇头链将监测数据传输到基站。仿真结果表明,SRPC协议可以在均衡能耗的基础上有效抵御恶意节点的攻击,并在簇头节点遭受攻击或者被摧毁后保证数据包的可靠投递,提高了WSN在战场侦察环境中的生存能力。     

Routing Regardless of Network Stability

How effective are interdomain routing protocols, such as the border gateway protocol, at routing packets? Theoretical analyses have attempted to answer this question by ignoring the packets and instead focusing upon protocol stability. To study stability, it suffices to model only the control plane (which determines the routing graph)—an approach taken in the stable paths problem. To analyse packet routing requires modelling the interactions between the control plane and the forwarding plane (which determines where packets are forwarded), and our first contribution is to introduce such a model. We then examine the effectiveness of packet routing in this model for the broad class next-hop preferences with filtering. Here each node \(v\) has a filtering list \(\mathcal {D}(v)\) consisting of nodes it does not want its packets to route through. Acceptable paths (those that avoid nodes in the filtering list) are ranked according to the next-hop, that is, the neighbour of \(v\) that the path begins with. On the negative side, we present a strong inapproximability result. For filtering lists of cardinality at most one, given a network in which an equilibrium is guaranteed to exist, it is NP-hard to approximate the maximum number of packets that can be routed to within a factor of \(n^{1-\epsilon }\) , for any constant \(\epsilon >0\) . On the positive side, we give algorithms to show that, in two fundamental cases, there exist activation sequences under which every packet will route. The first case is when each node’s filtering list contains only itself, that is, \(\mathcal {D}(v)=\{v\}\) ; this is the fundamental case in which a node does not want its packets to cycle. Moreover, every packet will be routed before the control plane reaches an equilibrium. The second case is when all the filtering lists are empty, that is, \(\mathcal {D}(v)=\emptyset \) . Thus, every packet will route even when the nodes do not care if their packets cycle! Furthermore, under these activation sequences, every packet will route even when the control plane has no equilibrium at all. Our positive results require the periodic application of route verification. To our knowledge, these are the first results to guarantee the possibility that all packets get routed without stability. These positive results are tight—for the general case of filtering lists of cardinality one, it is not possible to ensure that every packet will eventually route.