WDM全光网络中实时组播的分布式路由与波长分配算法

在WDM网络中，由于每条链路上可用波长是动态变化的，在考虑波长转换延迟的条件下，实现实时组播连接的路由与波长分配是十分困难的．假定WDM网络中每条链路有多根光纤，只有部分结点具有波长转换器且波长转换时间是不可忽略的，据此提出了一种用于建立实时组播连接的分布式路由与波长分配算法．该算法以Prim最小生成树算法为基础，生成一棵满足给定延迟时限的最小成本树．当最小成本树不能包括所有目的结点时，对剩余目的结点生成一棵最短延迟树，然后合并两棵树得到一棵组播树．波长分配使用最少波长转换和负载平衡策略．     

基于CBT的多源Steiner树构造算法

构造最小代价树问题可形式化为图论中Steiner树问题。而Steiner树的求解已经被证明是一个NP-complete问题，不可能在多项式时间求得其精确解，所以出现许多启发式算法：在可接受时间内，得到一棵近似的最优多播树。这些算法一般先指定所有链接边的费用，通过一定方法或规则，找出包含源端和所有目的端的一棵近似最优的多播树。很显然，它们并没有考虑由于路径的共享重叠而引起最小生成树链接边费用的变化。现利用CBT算法思想对变化的费用进行建模并对典型启发式算法作了改进，以适应不断变化了的链路费用。     

WDM网络中实时组播的分布式路由与波长分配算法

在WDM网络中,由于每条链路上可用波长是动态变化的,在考虑波长转换延迟时间的条件下,实现实时组播连接的路由与波长分配是十分困难的。该文提出了一种用于建立实时组播连接的分布式路由与波长分配算法。该算法将路由与波长分配统一进行,大大减少连接的建立时间。组播路由算法以Prim最小生成树算法和K-度宽度优先搜索方法为基础,生成一棵满足给定延迟时限的最小成本树。波长分配使用最少波长转换和负载平衡策略。     

BGN：一种新的蓝牙传感器网络分散网构造算法

在蓝牙分散网中,桥节点的数量和每个桥节点的度是影响主干网性能的重要因素。在生长树的基础上提出一种新的蓝牙分散网构造算法——BGN。该算法利用生长树主干节点间预留的连接将树改造成网,所形成的分散网能够在保持一定程度连通性的同时避免过多的冗余链接。仿真实验的结果表明,该算法所生成的分散网结构在桥节点数量、平均路径长度、网络可靠性和网络最大传输流量方面具有优势。     

一种新型的WSN冗余覆盖与节能路由算法

针对无线传感器网络的冗余覆盖问题,在K-覆盖判定算法和部分冗余覆盖算法基础上,提出一种可调冗余覆盖算法。该算法遵循覆盖最大化原则,能降低网络能耗。在可调冗余覆盖算法处理后的高效网络中,给出结合最短路径和最小生成树的最短路径树算法,在网络中构建若干棵以Sink节点为根的最短路径树,进一步降低网络能耗。仿真结果表明,在随机部署网络中,当规定网络覆盖冗余度为2时,2种算法平均可降低能耗20.27%左右。     

一种时延约束的多点到多点组播路由启发式算法

多点到多点组播路由是组播研究领域内的一个重要问题。当单棵共享组播树不能满足时延约束时,需要建立多棵共享组播树,但同时又会增加管理开销。因此,如何尽量减少共享组播树的个数成为关键问题。本文提出了一种启发式算法DCMMHA,用来解决时延约束的多共享组播树问题(DCMSMT),该问题已被证明为NP完全问题。本文算法按照特定规则生成候选中心列表,在不违反时延约束条件下,将源节点和目的节点加入共享树,并且对已选择中心进行更新。仿真实验将DCMMHA算法同其它四种同类算法进行比较,结果表明本文的算法所获得的中心数最少,显著降低了共享树的管理开销。     

多媒体通信中带度约束的多播路由算法

随着多媒体业务的发展,多播技术应用日益广泛,多播路由是要寻找连接源节点和一组目的节点的一棵多播树,这个问题在数学上归结为Steiner树问题,它是一个NPC问题。在实际网络中,网络节点具备不同的多播能力,有些节点不支持多播,有些节点支持多播,但为了保证网络速度和节点负载平衡,支持多播的节点要限制其复制信息的数量,即节点的多播能力受限。在这种情况下,寻找多播树变得更加困难,该文用节点的约束来表示敏个节点具备的多播能力,节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题,其仍是一个NPC问题。该文提出了一种求解带度的约束多播路由问题的双层遗传算法。算法的基本思想是最优多播树应是一棵满足度约束的最小生成树,因此问题的关键在于如何找到包括在最优生成树中的Steiner节点。遗传算法 采用二进制编码方式,内层算法用于求解满足度约束的最小生成树;外层算法进行全局搜索。该文将算法在稀疏图上进行实验,为了更好地模拟真实网络,稀疏图中每个节点具有不同的多播能力,并且多播目的节点数目相比于网络节点数要小。实验对算法进行了三方面比较：（1）解的质量;（2）计算时间;（3）算法的收敛性。实验结果表明,文中提出的遗传算法能够找到费用较小的多播树,但是当网络规模增大时,算法的求解时间也较长。     

有向无环图最小度生成树问题的一种近似算法

计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈ V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过△*+1,其中△*为某一最优树的度.算法的时间复杂度为O(n2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多.     

BGP/MPLS VPN组播链路恢复方案

BGP/MPLS VPN组播链路失效后,一棵组播树会断开成不相连的子树。为此,使用备用路径连接子树,重构组播树,减少备用链路上的离线概率加权主机数。找出备用路径建立时失效链路对组播树的影响因子,设计组播备用路径算法,使该影响因子最小化,从而提高组播树的健壮性。分析结果表明,该算法能实现组播链路的快速恢复。     

求解度约束最小生成树问题的新算法

针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。     

Survivable telecommunications network design under different types of failures

Telecommunications networks are expected to provide near-instantaneous restoration in the event that some network elements fail. Models for designing survivable networks are very complex and difficult to solve optimally. In this paper, we provide simple heuristics that augment existing network resources to ensure restoration under several scenarios of a single failure. The goal is to demonstrate that effective, though not necessarily optimal, survivable designs can be achieved by augmenting capacities along prudently selected variants of spanning tree and ring structures, without resorting to complex mathematical programming methods. The first model considers line restoration (reroutes around the failed link) under a partial link failure. We propose a heuristic that augments capacities of selected network links by forming a "virtual" spanning tree of restoration capacity. The second model provides line restoration under a complete link failure. We propose a heuristic that ensures survivability by repeatedly constructing spanning trees to various subnetworks. The third model provides path restoration (end-to-end reroutes) under a node failure. We propose a heuristic that repeatedly constructs restoration rings that cover a subset of source-destination nodes that carry traffic through intermediate nodes.     

基于粒子群权值优化的网络可生存性增强方法

针对网络中发生频率最高的单链路瞬时故障,提出了一种应用粒子群算法优化链路权值来增强网络可生存性的方法。引入费用函数对利用率过高的链路赋以惩罚性的高费用来避免链路过载,以网络在无故障场景下最高链路费用与单链路故障场景下最高链路费用的加权和作为目标函数,建立了优化算法模型,并应用粒子群优化算法求解最优权值。实验结果表明,算法求得的权值可以使网络在故障条件下保持较低的链路利用率,避免了因流量转移而造成网络拥塞,增强了网络可生存性。     

An efficient link allocation algorithm for survivable ATM-based personal communication networks

The integration of the issue of survivability of wireless networks in the design process of the backbone network is addressed in this paper. The effectiveness of this integration plays a critical role in the success of the wireless network and the satisfaction of its mobile users. In this paper, we consider the design problem of allocating the backbone links in ATM-based personal communication networks (PCNs) that are survivable under single backbone link failures. Survivability is achieved by selecting two link-disjoint routes in the backbone network between every pair of ATM switches. We also take the novel approach of not only minimizing the diameter of the network as a primary objective but also minimizing the total length of the network as a secondary objective. We propose a new heuristic algorithm to optimize the design of the network based on both objectives. We report the results of an extensive simulation study that show that our algorithm generates backbone networks that can withstand single link failures, have shorter average diameters and smaller total lengths and achieve a higher percentage of admitted calls under a mobile environment.     

Bandwidth sensitive fast failure recovery scheme for Metro Ethernet

Restoration in Ethernet has evolved over the years as specified in various standards: first the classical reconstruction of spanning trees was proposed in 802.1d; later 802.w specified RSTP to reduce the convergence time required in the STP protocol. Recently, the use of multiple spanning tree was suggested in 802.1s standard. In addition, there have been several proposals to implement multiple tree based restoration. Even though the results are promising they fall short of elevating Ethernet to a carrier grade technology. In this paper, we develop a distributed fast failure recovery spanning tree scheme, which restores lost facilities within tens of milliseconds. Recovery algorithm is localized around the point of failure on the spanning tree, thus avoiding disruption of the entire network. Failures are repaired using pre-configured sub spanning trees which are computed based on traffic requirements and resource availability. This paper also proposes possible enhancements to the failure recovery method using IEEE link aggregation standard to further reduce restoration time and provide differentiated survivability.     

Multiple link failures survivability of optical networks with traffic grooming capability

This paper investigates the problem of survivable traffic grooming (STG) in shared mesh optical networks and proposes different frameworks for improving the survivability of low speed demands against multiple near simultaneous failures. Spare capacity reprovisioning has recently been considered for improving the overall network restorability in the event of dual failures; here, after the recovery form the first failure, some connections in the network may become unprotected and exposed to new failures. Capacity reprovisioning then allocates protection resources to unprotected and vulnerable connections so that the network can withstand a future failure. In this paper, we propose two different reprovisioning schemes (lightpath level reprovisioning, LLR, and connection level reprovisioning, CLR); they differ in the granularity at which protection resources are reprovisioned. Further, each of these schemes is suitable for a different survivable grooming policy. While LLR provides collective reprovisioning of connections at the lightpath level, CLR reprovisions spare bandwidth for lower speed connections instead. We use simulation methods to study the performance of these schemes under two grooming policies (PAL and PAC), and we show that while CLR reprovisions substantially many more connections than LLR (i.e., potentially more management overhead) CLR yields a much better network robustness to simultaneous failures due to its superior flexibility in using network resources.     

Protecting multicast services in optical internet backbones

Many applications in the future Internet will use the multicasting service mode. Since many of these applications will generate large amounts of traffic, and since users expect a high level of service availability, it is important to provision multicasting sessions in the future Internet while also providing protection for multicast sessions against network component failures. In this paper we address the multicast survivability problem of using minimum resources to provision a multicast session and its protection paths (trees) against any single-link failure. We propose a new, and a resource efficient, protection scheme, namely, Segment-based Protection Tree (SPT). In SPT scheme, a given multicast session is first provisioned as a primary multicast tree, and then each segment on the primary tree is protected by a multicast tree instead of a path, as in most existing approaches. We also analyze the recovery performance of SPT and design a reconfiguration calculation algorithm to compute the average number of reconfigurations upon any link failure. By extending SPT to address dynamic traffic scenarios, we also propose two heuristic algorithms, Cost-based SPT (CB_SPT) and Wavelength-based SPT (WB_SPT). We study the performance of the SPT scheme in different traffic scenarios. The numerical results show that SPT outperforms the best existing approaches, optimal path-pair-based shared disjoint paths (OPP_SDPs). SPT uses less than 10% extra resources to provision a survivable multicast session over the optimal solution and up to 4% lower than existing approaches under various traffic scenarios and has an average number of reconfigurations 10–86% less than the best cost efficient approach. Moreover, in dynamic traffic cases, both CB_SPT and WB_SPT achieves overall blocking probability with 20% lower than OPP_SDP in most network scenarios.     

Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures

Failure resilience is a desired feature of the Internet. Most traditional restoration architectures assume single failure assumption, which is not adequate in present day WDM optical networks.Multiple link failure models, in the form of shared risk link groups (SRLG’s) and shared risk node groups (SRNG’s) are becoming critical in survivable optical network design. We classify both of these form of failures under a common scenario of shared risk resource groups (SRRG) failures. We develop graph transformation techniques for tolerating multiple failures arising out of shared resource group (SRRG) failures.Diverse routing in such multi-failure scenario essentially necessitates finding out two paths between a source and a destination that are SRRG disjoint. The generalized diverse routing problem has been proved to be NP-Complete. The proposed transformation techniques however provides a polynomial time solution for certain restrictive failure sets. We study how restorability can be achieved for dependent or shared risk link failures and multiple node failures and prove the validity of our approach for different network scenarios. Our proposed technique is capable of improving the diverse route computation by around 20–30% as compared to approaches proposed in the literature.     

Modeling and optimization of survivable P2P multicasting

Various solutions based on Peer-to-Peer (P2P) multicasting have been gaining much popularity in recent years, since P2P multicasting can effectively support live streaming of various content. In this work we assume that the P2P multicasting is used to distribute content with high reliability requirements, e.g., weather warnings, security updates, financial data, security warnings, etc. The main idea to provide protection of the system against network failures is to establish several (at least two) disjoint multicasting trees. Our discussion in this paper centers on the problem how additional survivability constraints to provide failure-disjoint trees impact the operation of P2P multicasting systems. As the performance metrics we propose to use: streaming cost, maximum delay and throughput. The possible failure scenario we take into account is a single failure of one of the following network elements: streaming server, overlay link, uploading node and ISP link. We examine the topic of survivable P2P multicasting applying offline optimization methods and simulations. In the former case we formulate Mixed Integer Programming (MIP) models and use the CPLEX solver to obtain optimal results. For the streaming cost objective we compare two MIP formulations in terms of the complexity and execution time. Results show that our formulation provides much better performance compared to the classical P2P multicasting formulation proposed in the literature. Moreover, in the case of the streaming cost problem we propose a new evolutionary algorithm that yields results for larger networks than the CPLEX solver. The simulations are run to emulate a distributed network environment, in which each node makes its own decisions. Results obtained using both research methods confirm that the survivability of P2P multicasting can be achieved with relatively low additional system overhead for all three considered performance metrics: streaming cost, maximum delay and system throughput.     

网络生存性计算方法以及性能评价

为了解决网络中因链路失效而产生的拥塞问题,基于混合蛙跳算法和小波技术提出了一种新的网络生存性评价方法(SASFL)。该方法首先建立了生存性的评价指标,同时针对失效状态下的到达流量进行小波变换,并利用混合蛙跳优化小波系数,以此获得最佳网络剩余流量。最后利用OPNET和Matlab进行仿真实验,深入研究了网络生存性与失效链路、权重系数等参数之间的关系。结果表明,相比其他方法,SASFL表现出较好的适应性。     

基于多链路故障的网络切片生存性算法

为了保证当底层网络的多条物理链路发生故障时用户业务能够不间断,提出一种基于多链路故障的网络切片生存性算法。通过区分切片上承载的业务类型,当高可靠低延迟切片请求到达后,将物理节点按节点重要度排序后进行映射,再对故障链路采用多备份路径算法,选取带宽资源消耗最少的路径依次对故障链路进行重映射,当高带宽切片请求到达后,采用广度优先搜索的节点映射算法,再通过多备份路径对故障链路进行恢复。仿真结果表明,该算法能够提高切片平均映射成功率、长期平均收益开销比、物理链路利用率和故障恢复率,缩短平均故障恢复时延。