Comparison of two path restoration schemes in self-healing networks

The state-independent (SI) and state-dependent (SD) path restoration schemes for self-healing networks are studied in this paper. The integer programming (IP) formulations for the spare capacity allocation and restoration flow assignment are first presented. Based on the optimal IP solutions, the SI and SD restoration schemes are then compared quantitatively in terms of spare capacity requirement (SCR), restoration time, VPI (virtual path identifier) redundancy (in ATM) and nodal storage capacity requirement. The comparison is based on spare optimization, single link failure scenario and 100% restoration. The SCR is also compared under single node failure scenario. It is observed that using group VP (virtual path) restoration (for either SI or SD) can substantially reduce the restoration time with only a small increase in spare capacity cost. Further, the SI restoration seems better than the SD restoration for the cases we have studied, at least in spare optimization, as its implementation is relatively easier and the difference in SCR between SI and SD is not significant. The economies of scale in transmission facility cost is also investigated in the paper.     

OPTIMIZATION OF SPARE CAPACITY IN WDM NETWORKS FOR REAL-TIME SERVICE RESTORATION

In the case of network malfunction a network with restoration capability requires spare capacity to be used. Optimization of the spare capacity in this case is to find the minimum amount of spare capacity for the network to survive from network component failures. In this paper, the optimization of the spare capacity problem is investigated for the wavelength division multiplexing (WDM) mesh networks without wavelength conversion. To minimize the spare capacity, we will optimize both the routing and the wavelength assignment. This combinatorial problem is usually called the routing and wavelength assignment (RWA) problem and it is well known to be NP-hard. We give an integer linear programming (ILP) formulation for the problem. Due to the excessive run-times of the ILP, we propose a hybrid genetic algorithm approach (GA) for the problem. For benchmarking purpose, simulated annealing (SA) and Tabu search (TS) are also applied to this problem. To validate the effectiveness of the proposed method, the approach is applied to the China network, which has a more complicated network topology. Simulation results are very favorable to the GA approach.     

Designing tributary networks with multiple ring families

Advances in telecommunication technology result in improved service, but can also lead to difficult and challenging network design problems. For example, networks in which nodes are connected by rings of optical fiber can now be used to provide rapid service restoration in the event of a failure. However, as a result, network designers are faced with the new problem of designing networks based on topological ring structures. In this paper, we consider the particular case of tributary network design. In a tributary network, a group of nodes are connected to a hub node, which is used as a point of interconnection with other parts of the network. For a particular network architecture, we describe an algorithm to determine how many topological ring structures are required, and which nodes should be included on each. We highlight connections between this problem and problems in vehicle routing.A common architecture for a telecommunications network consists of several tributary (often called access) networks, which connect locations to hubs, and a backbone network, which interconnects the hubs. This paper describes a heuristic approach for designing tributary networks based on self-healing rings (SHRs). The tributary network consists of multiple ring families, and each of those is comprised of one or more SHRs, called “stacked” rings. The SHRs in a given ring family are routed over the same cycle of optical fiber cables, but each SHR serves only a subset of the locations along the cycle. Each demand location is assigned to a single SHR on one of the ring families, whereas the hub is assigned to all SHRs on all ring families. A link that is used by some ring family incurs a fixed cost plus a variable cost per SHR associated with that family. Each SHR is constrained by the demand volume it can handle and by the number of locations it can serve. This tributary ring network design problem can be viewed as a complex version of a vehicle routing problem with a single-depot andmultiple vehicles. Our algorithm is initiated with numerous ring families. It then attempts to merge these families, while ensuring that savings are realized in terms of the sum of fixed and variable costs.     

ATM虚通道自愈环网络的结构与控制

本文研讨了ＡＴＭ虚通道自愈环的功能、结构、控制及故障自动恢复的原理和实现,综述了 宽带自愈环的发展前景及开发阶段。     

Survivable ATM mesh networks: Techniques and performance evaluation

The Capacity and Flow Assignment problem in self-healing ATM networks is an interesting one from a Generalized Multi-Protocol Label Switching (GMPLS) prospective since IP and ATM protocols are destined to co-exist together in this unified platform. This paper continues the investigation of the path-based design approach of the network survivability problem in existing ATM mesh networks. Our contribution consists in quantifying (1) the effects the selection of candidate paths per node pair has on the restoration ratio, (2) the effect of restoration schemes on the restoration ratio, (3) the effect of failure scenarios on the restoration ratio, and finally (4) the effect of network connectivity on the restoration ratio. Numerical results are presented under representative network topologies, various traffic demands and spare capacity distribution schemes. They provide additional guidelines for the design of survivable ATM mesh-type networks, from a network reliability viewpoint.     

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

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

保证关键服务生存性的ATM网络资源管理

生存性是ＡＴＭ网络中亟待解决的问题。中针对当前研究中已提出的ＡＴＭ网络生存性资源管理机制的不足,基于网络中各种服务不同的生存重要性,引入了故障恢复过程中的音乐睚,并改进了预先的空闲容量规划,形成了析的２性资源管理机制,该机制的实施使得网络即使在空穴宋容量不足的情况下,也能够提供关键服务恢复所需的容量,结合优先级恢复机制,实现了充分的关键服务生存性保证机制。     

光传送Mesh网生存性的定量分析

生存性是光传送网络中亟待解决的问题，研究了光传送Mesh网的工作流量及所需的空闲容量的最佳分布问题，对问题进行了形式化描述，其目的是对给定的恢复需求使得后备容量最小，并根据后备容量的价值对不同的恢复策略进行比较，为实际网络的设计提供了一定的指导。     

Implementation of self-healing function in ATM networks

This paper proposes an implementation scheme for the self-healing function in ATM (Asynchronous Transfer Mode) networks and assesses its performance in a developed experimental system. First, our proposed ATM self-healing scheme is described. This scheme realizes more rapid restoration of failed Virtual Paths than other self-healing algorithms, supports the node failure case, and minimizes the spare resources required. Next, an implementation scheme is proposed. We propose that the self-healing function can be implemented as a software process, and that OAM (Operation, Administration, and Maintenance) cells be utilized for fast message transmission. Next, results of a prototype system that we implemented on an ATM cross-connect system are discussed. The fundamental characteristics of restoration performance are measured using the experimental system. Based on these results, restoration characteristics of real world scale networks are estimated by computer simulations. The simulation results indicate that any-one link failure is completely restored within 2 seconds.     

Bi-directional self-healing ring network planning

In this paper we study the network planning problem of bi-directional self-healing ring (BSHR), which is a network structure providing higher survivability when there is a failure on link or node. Given a network with nodes, links, and demand pairs, our target is to design an optimal network comprising rings, which use only the existing links to satisfy all demands. The objective is to minimize the total amount of equipment (add/drop multiplexer) on nodes, thus reducing the major cost of SHR structure. We propose two integer programming models. For larger networks, we have developed an efficient solution procedure based on its hierarchical network structure. Computational results are given to show that the solution procedure is effective in obtaining an optimal or near-optimal solution.Scope and purposeThe merging of information networking and telecommunication services has created an increasing demand for telecommunication networks of high bandwidth, aiming to exchange ever larger volumes of data in a very short time interval. The self-healing ring (SHR) is a ring network that provides redundant bandwidth in which disrupted services can be automatically restored following network failures. In this paper, we study the network planning problem of bi-directional SHR aiming to minimize the amount of equipment.     

基于稀疏树的战术通信网络路由协议研究

介绍了一种使用在战术无线通信网络环境的基于稀疏树的战术路由协议.STRP支持单向信道,它采用稀疏树路径生成算法来减少路由更新的数据量并减少网络链路的冗余,采用快速环路消除算法来消除网络拓扑动态变化过程中的环路与计数到无穷问题,采用增量更新来降低路由协议对传输带宽的需求.仿真结果表明,它较为适合战术无线通信网络环境.     

The Forcer Concept and Express Route Planning in Mesh-Survivable Networks

To date, mesh network design theory has beendeveloped for the case where working and protectioncapacity is terminated at every node. It is recognizedthat express routes, which bypass some nodes en-route, would decrease the total DCS port costs but ithas been unclear how to incorporate bypass planning inthe optimal spare capacity design for a mesh-restorablenetwork. An important issue is whether the introduction of nodal bypass will increase the total sparecapacity needed for restorability, due to a reduction ofrestoration re-routing flexibility. To address thesequestions, we introduce the forcer concept for analysis of the relationship between workingand spare capacity in a mesh-restorable network. Weapply the forcer concept to show theoretically whybypass in fact need never require an increase in sparing and may actually permit a decrease in somecases. In tests to validate and exploit these findings,an average reduction of 12% in total spare capacity and16% in DCS port count totals were obtainedsimultaneously with an Integer Programming optimization. Thesesavings are relative to an already optimized fullyterminated network design. The work thus contributes togreater theoretical understanding and designcost-effectiveness for mesh-based restorable networks.     

SDN网络中基于业务划分的路由选择机制

软件定义网络(SDN)是一种新型的网络架构,其路径是根据全局网络拓扑计算得到的。然而,当前SDN网络中依然存在负载不均衡和不能满足网络流量QoS要求的问题。为此,根据SDN控制器掌握全局网络信息的特点,结合网络感知功能和基于流量的业务划分,利用K最短路径算法,提出一种基于业务划分的路由选择机制。实验结果表明,该机制能够为不同业务类型的数据流选择一条最能满足其QoS要求的路径,并使整个网络达到负载均衡,进而提高了底层网络资源的利用率。     

二元域大型稀疏矩阵向量乘的FPGA设计与实现

作为Wiedemannn算法的核心部分,稀疏矩阵向量乘是求解二元域上大型稀疏线性方程组的主要步骤。提出了一种基于FPGA的二元域大型稀疏矩阵向量乘的环网硬件系统架构,为解决Wiedemannn算法重复计算稀疏矩阵向量乘,提出了新的并行计算结构。实验分析表明,提出的架构提高了Wiedemannn算法中稀疏矩阵向量乘的并行性,同时充分利用了FPGA的片内存储器和吉比特收发器,与目前性能最好的部分可重构计算PR模型相比,实现了2.65倍的加速性能。     

An improved scheme for self-healing in ATM networks

Broadband networks based on ATM technology can carry a large volume of data and can support diverse services like audio, video, and data uniformly. The reliability and availability levels provided by such networks should be very high. Self-healing is an elegant concept in this direction to provide highly reliable networks. A self-healing network can detect failures such as link/node failures and reroute the failed connections automatically using distributed control mechanisms. In this paper, we consider link and node failures including the VP terminating nodes unlike Kawamura and Tokizawa (Self-healing in ATM networks based on virtual path concept, IEEE Journal on Selected Areas in Communications 12 (1) (1994) 120–127). We present here an improved scheme for self-healing in ATM networks based on the concept of backup VPs. The problems we address are: (i) self-healing scheme; and (ii) backup VP routing. Two issues are addressed in the self-healing scheme: (i) backup VP activation protocol; and (ii) dynamic backup VP routing. We propose a new backup VP activation protocol which uses a VC packing strategy which allows the fast and prioritized restoration of critical VCs that were carried by failed VPs. We also propose a distributed dynamic backup VP routing algorithm which reduces the resource contention that may occur when multiple source–destination pairs contend for the routes simultaneously. The objective of the backup VP routing problem is to find a backup VP for each of the working VPs so that the cost of providing the backup is minimized. We propose a heuristic based solution for the backup VP routing problem using the concept of minimum cost shortest paths. We conducted simulation experiments to evaluate the performance of the proposed schemes. The results show that the proposed schemes are effective. Comparison of the results with those of the earlier schemes (R. Kawamura, I. Tokizawa, Self-healing in ATM networks based on virtual path concept, IEEE Journal on Selected Areas in Communications 12 (1) (1994) 120–127; C.J. Hou, Design of a fast restoration mechanism for virtual path-based ATM networks, Proceedings of IEEE INFOCOM’97, Kobe, Japan, April 1997) shows that the proposed schemes perform better.     

一种基于RAN架构无线接入网系统容量最大化的功率分配算法

针对新型RAN架构无线接入网中功率分配问题进行研究, 建立系统容量最大化的最优化数学模型, 提出了一种基于RAN架构无线接入网的系统容量最大化的功率分配算法, 并且应用人工鱼群算法求解了算法中目标函数的全局最优解, 即一组使系统容量最大化的发射功率。仿真结果表明, 与现有的分布式网络架构中非合作的功率控制博弈算法相比, 新算法可以显著提高系统容量, 即证明了该算法的有效性。     

应用于无线局域网的高速维特比译码器电路

介绍了一种应用于无线局域网的Viterbi译码器,在802．11aWLAN系统的多传输速率下工作,且可以在不同的编码率下工作。在电路的设计中采用了全并行加比选单元和幸存路径存储单元,应用了一种路径长度归一的方法,在不影响性能的前提下,使实现简单并且大大减低了运算量,并达到了高速、实现简单的标准。     

Comparing Restoration Concepts Using Optimal Network Configurations with Integrated Hardware and Routing Decisions

We investigate the impact of link and path restoration on the cost of telecommunication networks. The main observation is that the cost of an optimal network configuration is almost independent of the restoration concept if (i) the installation of network elements (ADMs, DXCs, or routers) and interface cards, (ii) link capacities, and (iii) working and restoration routings are simultaneously optimized.We present a mixed-integer programming model which integrates all these decisions. Using a branch-and-cut algorithm (with column generation to deal with all admissible routing paths), we solve structurally different real-world based problem instances and show that the cost of optimal solutions is almost independent of the used restoration concept.In addition, we optimize spare capacities based on predetermined shortest working paths with respect to different link weights. On our test instances, the additional cost of solutions obtained with this sequential approach, compared to simultaneous optimization of working and restoration routings, varies between 0 and 164%.Sebastian Orlowski has studied mathematics at the Technical University of Berlin, Germany. Since June 2003, he has been a research assistant at the Zuse Institute Berlin (ZIB), where he works on the design of cost-efficient telecommunication networks under survivability constraints. The current focus of his research within the DFG Research Center MATHEON is multi-layer network planning.Roland Wessäly graduated from the Technical University of Berlin with a Masters Degree in Computer Science. Since 1994 he has been a member of the optimization group at the Zuse Institute Berlin (ZIB). He developed optimization methods for the design of survivable capacitated telecommunication networks as part of his PhD Thesis in Mathematics (finished in April 2000). In 2001 he received the Vodafone Innovations award for his scientific work on network design. Since 2000 he has been managing director of the ZIB spin-off atesio GmbH, a company specialized on planning and optimization algorithms for telecommunication network operators.     

针对复杂多环网络拓扑的路由改进算法

网络运营商为用户提供的光纤接入主干网大多以环型网络的方式提供服务,然而目前对于大规模、环数众多、连接方式多样化的复杂多环网络缺乏性能优良的路由算法。为解决传统环网结构网络延迟高和传输效率低的问题,提出一种针对复杂多环网络拓扑的路由改进算法,将多环网络中的复杂路由问题转化为单环网中的简单路由问题。在此基础上,通过设计源溯节点还原以及路径还原算法,将单一环网改进为增强环网网络结构,使同一环内通信节点间的路径还原为完整最短路径,并从理论上证明该算法得到的最优路径是无差错的。实验结果表明,相比于现有的优化Dijkstra算法,该算法的搜索空间比提升约13%,具有更好的改进效果,且算法运行时间缩短79%,更适合复杂多环网络的路由计算。     

基于业务类型的网络切片可靠性映射算法

网络切片是5G网络的基础架构技术,为在多个切片共享同一底层网络资源的同时保证切片的可靠性,提出一种区分业务类型的网络切片可靠性映射算法,解决底层网络链路故障、网络切片可靠性与资源利用率相互矛盾的问题。通过区分切片承载业务类型,对高可靠低时延切片请求的链路提前构建备份路径,并采用基于最大生成树链路的备份资源共享保护方法,对高带宽切片请求则采用基于链路可靠性的重映射算法恢复故障链路。仿真结果验证了该算法的有效性,与SVNE1+1和DPS-VNRA算法相比,其在切片成功运行率、长期收益开销比、物理链路利用率和故障恢复率方面均具有优势。