An enhanced backward recursive PCE-based computation scheme for end-to-end disjoint paths in multi-domain networks

To efficiently provide two disjoint end-to-end paths for working and protecting in multi-domain networks is challenging the network industry. The Backward Recursive PCE-based parallel approach (PA) for disjoint paths can achieve best computation performance at high cost of computation complexity and communication overhead. In this paper, we propose an enhanced PA (EPA), based on a no-differentiated in-BNs pair strategy to decrease the computation complex and communication overhead. The simulation results show that the EPA scheme can effectively reduce the computation and communication overhead.     

Optimal K-survivable backward-recursive path computation (BRPC) in multi-domain PCE-based networks

The path computation element (PCE) enables optimal path computation in single-domain (G)MPLS networks. To overcome the lack of traffic engineering (TE) information in multi-domain networks and to preserve both computation optimality and domain confidentiality, the backward-recursive PCE-based computation (BRPC) procedure has been standardized. BRPC procedure is based on PCE protocol (PCEP) and enables synchronized computation of TE label-switched paths with the requested level of reliability and quality of service requirements (i.e., guaranteed bandwidth). In this paper, the problem of computing $K$ K -survivable optimal multi-domain paths by resorting to BRPC procedure is analyzed. Extensions to PCEP protocol are discussed to achieve path optimality when domain information is kept confidential. The optimality is theoretically proved, and the computational complexity is shown to be more efficient than existing approaches. The discussed extensions are experimentally validated in an MPLS network test bed based on commercial equipments and are shown to have performance comparable to standard PCEP approach.     

PCE-based fast path control in multi-domain photonic networks

We discuss issues for controlling an optical path in large-scale photonic networks, and introduce an inter-domain path control system based on Path Computation Elements (PCEs). In the system, maximum flow information enables the load balancing of traffic, and Path Key scheme preserve the confidentiality of internal topology information among carrier networks. Based on the experimental results, we show the path setup in the introduced system is significantly faster than the manual path setup among domains in current carriers' networks. For the additional reduction of the path setup time, we propose the domain-wise paralleled signaling method. We also show that decreasing the number of nodes per domain makes path setup faster in the introduced system with deployment of the proposed signaling method.     

基于分层PCE的多域最小代价路径启发式算法

智能光网络技术和P2MP(点对多点)技术的融合将能够极大地促进光组播业务的发展。文章针对多层多域光网络中的P2MP业务,提出了一种 MDMPH(基于分层PCE(路径计算元素)的多域最小代价路径启发式)算法,并进行了仿真分析。与传统的PDB(基于逐域路径)算法、E-BRPC(基于扩展的反向回溯)算法以及 CTB(基于核心树)算法相比,MDMPH 算法能够计算出代价更小的P 2 MP路径树。     

光网络中基于层次化PCE反向回溯路由算法

在层次化PCE架构的基础上,提出了一种光网络中支持冲突感知的反向回溯路由算法.本算法在保证提供端到端路径的基础上,可以避免波长分配过程中的资源冲突问题.与传统的反向回溯路由算法相比,本算法可以有效地提升网络中的资源利用率,降低业务阻塞率.     

On-line disjoint path routing for network capacity maximization in energy-constrained ad hoc networks

In this paper we consider on-line disjoint path routing in energy-constrained ad hoc networks. The objective is to maximize the network capacity, i.e. maximize the number of messages routed successfully by the network without any knowledge of future disjoint path connection request arrivals and generation rates. Specifically, in this paper we first present two centralized on-line algorithms for the problem. One is based on maximizing local network lifetime, which aims to minimize the transmission energy consumption, under the constraint that the local network lifetime is no less than γ times of the optimum after the realization of each disjoint path connection request, where γ is constant with 0 < γ  1. Another is based on the exponential function of energy utilization at nodes, and the competitive ratio of this latter algorithm is also analyzed if admission control mechanism is employed. We then conduct extensive experiments by simulations to analyze the performance of the proposed algorithms, in terms of network capacity, network lifetime, and the transmission energy consumption for each disjoint path connection request. The experimental results show that the proposed algorithms outperform those existing algorithms that do not take into account the power load balancing at nodes in terms of maximizing the network capacity.     

Distributed schemes for diverse path computation in multidomain MPLS networks

MPLS is currently used by several JSPs to carry some high-value traffic components, such as telephony over IP trunks and VPNs. For this type of traffic, service availability is a critical QoS dimension that needs to be protected from network failures. With MPLS-TE, this can be achieved by means of path protection schemes, where active and backup LSPs are routed along diverse paths. Besides protection, path diversity can be exploited for load balancing, another common means of QoS improvement. In order to preserve other QoS requirements, the paths must meet certain constraints (e.g., bandwidth availability, low load) and/or minimize some metric (e.g., hop count). This requires the ability to establish path diversity in an optimal way. In many cases of practical interest, the QoS traffic has an interdomain scope. This is the case for ToIP and VPN traffic between different carriers, or between different ASs owned by the same carrier, as found, for example, after corporate acquisitions or mergers. Therefore, path diversity is a requirement for interdomain traffic engineering. In this work we address path diversity in a multidomain network, where individual domains are capable of connection-oriented forwarding and endowed with an MPLS-TE control plane. For administrative and/or scalability reasons intradomain routing information is not disseminated externally, so dynamic path computation must be achieved by a distributed scheme based on interdomain collaboration. We briefly describe three alternative schemes recently proposed for interdomain diverse path computation, and quantitatively assess their performance with simulations over real ISP topologies.     

A disjoint path selection scheme with shared risk link groups in GMPLS networks

This letter proposes a disjoint path selection scheme for generalized multi-protocol label switching (GMPLS) networks with shared risk link group (SRLG) constraints. It is called the weighted-SRLG (WSRLG) scheme. It treats the number of SRLG members related to a link as part of the link cost when the k-shortest path algorithm is executed. In WSRLG, a link that has many SRLG members is rarely selected as the shortest path. Simulation results show that WSRLG finds more disjoint paths than the conventional k-shortest path algorithm.     

一种改进的多域光网络保护机制

生存性是保证业务服务质量的关键,多域光网络生存性问题中,由于存在多域间拓扑和路由信息不可见等约束,导致生存性实现较为困难.提出了将多域光网络进行逻辑聚合的思路,在此基础上分别针对域内和域间提出了非等值负载保护和M∶1保护机制.域内的非等值负载保护机制可以根据节点数以及业务量动态地分配保护路径,从而有效地提高资源利用率.     

多域全光网络快速多链路故障定位机制

提出了一种运用于多域全光网络的多链路故障定位机制.该机制根据网络中的告警信息确定多链路故障发生域;通过边界节点收集的监测信息和告警信息定位域间多链路故障;对于域内多链路故障,在分离各单故障后基于LVM协议进行故障定位.仿真结果表明,该机制不仅能够陕速定位多域全光网络中的域间、域内多链路故障,而且具有较高的故障定位率.     

Adaptive cluster-based relay-node placement for disjoint wireless sensor networks

Wireless Networks - Wireless sensor networks are formed with very small sensor devices with limited energy and short transmission range. Sensors are randomly deployed in remote areas with harsh...     

Distributed computation of shared backup path in mesh optical networks using probabilistic methods

We assess the benefits of using statistical techniques to ascertain the shareability of protection channels when computing shared-mesh restored lightpaths in optical mesh networks. These optical networks support wavelength conversion everywhere as a byproduct of the electronic nature of the switching in the optical-electronic-optical optical cross connect used. Current deterministic approaches require a detailed level of information proportional to the number of active lightpaths. Although this is not an issue for good sized networks in the foreseeable future, these approaches are not practicable for distributed route computation involving larger networks. On the other hand, distributed approaches that do not make use of shareability information require a significant amount of additional capacity compared to a centralized approach with access to complete shareability information. With the proposed approach we show that even with less information, independent of the amount of traffic demand, it is possible to predict the shareability of protection channels with remarkable accuracy. In addition, we propose a local distributed channel assignment scheme that is used in conjunction with our distributed route computation proposal to assign shared channels when provisioning the backup path. This channel assignment scheme can also be used to further optimize capacity usage in individual links upon certain events or at regular intervals. Experiments are provided that demonstrate that our approach yields faster computation times with no significant penalty in terms of capacity usage than a centralized approach using complete information.     

光网络中基于路径计算单元的路由机制研究

针对大规模多层多域光网络群故障发生时的网络受损情况,提出基于路径计算单元(PCE)架构的跨域路由算法进行快速恢复,并基于OMNet平台对多层多域路由方案进行了性能仿真分析。结果表明,基于PCE架构的路由策略在群故障发生时能够大大减少网络中的路径计算请求泛洪信息,降低路由计算收敛时间,可以提高全网剩余资源的资源利用率,为业务的快速恢复提供了路由基础。     

Maximum delay computation for interdomain path selection

One important problem when deploying interdomain path selection is advertising metrics that hold for a long period of time. In this paper we propose a method to aid interdomain path selection mechanisms in that sense. We present a means of computing a bound on the end‐to‐end delay of traversing a domain considering that the traffic varies within a given uncertainty set. This provides a robust and a verifiable quality of service value for traversing the autonomous system (AS), without revealing confidential information. Consequently, the bound can be safely conceived as a metric to be announced by each AS in the process of interdomain path selection. We show how the maximum delay value is obtained for an interdomain bandwidth demand and we propose an exact method and a numerical approximation method for computing it, neither of which rely on a complex monitoring infrastructure. Simulations with real data that illustrate the problem and validate our results are also presented. Copyright © 2011 John Wiley & Sons, Ltd.     

A novel Topology Aggregation approach for shared protection in multi-domain networks

Routing for shared protection in multi-domain networks is more difficult than that in single-domain networks because of the scalability requirements. We propose a novel approach for shared protection routing in multi-domain networks where the key feature is a special Topology Aggregation. In this Topology Aggregation, only some potential intra-domain paths (intra-paths for short) are selected for carrying working and backup traffic between domain border nodes. The abstraction of each intra-path to a virtual edge makes the original multi-domain network to become an aggregated network. On the aggregated network, a single-domain routing algorithm for shared protection can be applied for obtaining the complete routing solutions. The experiments show that the proposed approach is scalable. Moreover it is close to the optimal solution in single-domain networks and outperforms the previously proposed scalable solutions in multi-domain networks.     

New dynamic algorithms for shortest path tree computation

The open shortest path first (OSPF) and IS-IS routing protocols widely used in today's Internet compute a shortest path tree (SPT) from each router to other routers in a routing area. Many existing commercial routers recompute an SPT from scratch following changes in the link states of the network. Such recomputation of an entire SPT is inefficient and may consume a considerable amount of CPU time. Moreover, as there may coexist multiple SPTs in a network with a set of given link states, recomputation from scratch causes frequent unnecessary changes in the topology of an existing SPT and may lead to routing instability. We present new dynamic SPT algorithms that make use of the structure of the previously computed SPT. Besides efficiency, our algorithm design objective is to achieve routing stability by making minimum changes to the topology of an existing SPT (while maintaining shortest path property) when some link states in the network have changed. We establish an algorithmic framework that allows us to characterize a variety of dynamic SPT algorithms including dynamic versions of the well-known Dijkstra, Bellman-Ford, D'Esopo-Pape algorithms, and to establish proofs of correctness for these algorithms in a unified way. The theoretical asymptotic complexity of our new dynamic algorithms matches the best known results in the literature     

A novel multi-link fault-tolerant algorithm for survivability in multi-domain optical networks

With the large-scale deployment of optical network equipments, the problems of separated domains management and the multi-domain-based survivability have become the primary challenge in new generation intelligent optical networks. Aimed at resisting multi-link failures in multi-domain optical networks (MDON), a heuristic multi-link fault-tolerant (MLFT) algorithm for survivability in MDON is proposed in this article, which applied Hamiltonian cycle protection and segment-shared protection to establish a novel survivability strategy for either intra-domain??s or inter-domain??s multiple links, respectively. Furthermore, a new virtual-link mapping scheme and link-cost formulas are presented to encourage the appropriate routing selection and load balancing, which can also contributed to better resource utilization ratio and blocking ratio. Simulation results show that MLFT realizes the multi-link fault-tolerant survivability at a lower cost with better performances in redundancy ratio, blocking ratio, and computation complexity.     

A localized algorithm for finding disjoint paths in wireless sensor networks

This letter presents a localized algorithm that finds multiple node-disjoint paths in wireless sensor networks. The algorithm needs only local topology knowledge and provides automatic path restoration. We describe the algorithm, give the proof of correctness, and evaluate its performance using simulation. We conclude that the proposed algorithm is more suitable for wireless sensor networks than the existing distributed algorithms     

OBGP+: An improved path-vector protocol for multi-domain optical networks

One of the essential components for the dynamic provisioning of lightpaths across multiple domains is the Routing and Wavelength Assignment (RWA) strategy adopted. The consolidation that path-vector protocols have had in practice, has motivated the optical extension to BGP (OBGP). We claim, however, that a routing model mostly centered on the exchange of reachability information-like the one we have today with BGP or the one offered by OBGP-will not be sufficient for multi-domain optical networks. Routing domains must be able to exchange both reachability as well as aggregated Path-State Information (PSI). Understanding that this is a missing piece in the routing models provided by BGP and OBGP is easy nowadays, but contributing with solutions capable of highly improving the performance of a path-vector without impacting on key aspects of the protocol-fundamentally, its scalability, its convergence properties, and the number of routing messages exchanged between domains-is a challenging task.In this paper we propose OBGP +, which is a very simple extension of a path-vector protocol supporting the computation and advertisement of PSI between optical domains. The PSI that we propose to use is highly condensed in the form of a single integer value. In order to avoid the typical increase in the number of routing messages associated with the update of PSI, we propose to piggy-back the updates in non-dummy Keepalive messages exchanged between OBGP+ neighbors. Extensive simulations reveal that, despite its simplicity: (i) OBGP+ is able to drastically reduce the blocking experienced with a path-vector protocol like OBGP; (ii) OBGP+ needs much less number of routing messages than OBGP to achieve such performance; and (iii) the convergence and restoration features of OBGP+ are also better than those of OBGP, which is particularly important for connections that lack a protection path.     

Virtualized controller placement for multi-domain optical transport networks using machine learning

Photonic Network Communications - Optical multi-domain transport networks are often controlled by a hierarchical distributed architecture of controllers. Optimal placement of these controllers is...