Surviving double-link failures for near optimal heuristic routing in protected optical networks

The survivability for double-link failures in WDM optical network has been studied in recent years. In previous algorithm, to survive the double-link failures each connection request will be assigned to one primary path and two link-disjoint backup paths. However, the previous algorithm is the so-called simple algorithm which may lead to low resources utilization and high blocking probability. In this paper, we propose a new heuristic algorithm called routing with optimal solution (ROS) to protect the double-link failures. Differing from the previous algorithm, ROS can obtain near optimal solution by recomputing the primary path and two backup paths based on the rerouting policy for each connection request. Simulation results show that ROS can significantly outperform the previous algorithm.     

Resource efficient network design and traffic grooming strategy with guaranteed survivability

In WDM networks, path protection has emerged as a widely accepted technique for providing guaranteed survivability of network traffic. However, it requires allocating resources for backup lightpaths, which remain idle under normal fault-free conditions. In this paper, we introduce a new design strategy for survivable network design, which guarantees survivability of all ongoing connections that requires significantly fewer network resources than protection based techniques. In survivable routing, the goal is to find a Route and Wavelength Assignment (RWA) such that the logical topology remains connected for all single link failures. However, even if the logical topology remains connected after any single link fault, it may not have sufficient capacity to support all the requests for data communication, for all single fault scenarios. To address this deficiency, we have proposed two independent but related problem formulations. To handle our first formulation, we have presented an Integer Linear Program (ILP) that augments the concept of survivable routing by allowing rerouting of sub-wavelength traffic carried on each lightpath and finding an RWA that maximizes the amount of traffic that can be supported by the network in the presence of any single link failure. To handle our second formulation, we have proposed a new design approach that integrates the topology design and the RWA in such a way that the resulting logical topology is able to handle the entire set of traffic requests after any single link failure. For the second problem, we have first presented an ILP formulation for optimally designing a survivable logical topology, and then proposed a heuristic for larger networks. Experimental results demonstrate that this new approach is able to provide guaranteed bandwidth, and is much more efficient in terms of resource utilization, compared to both dedicated and shared path protection schemes.     

A routing framework for providing robustness to node failures in mobile ad hoc networks

Nodes in a mobile ad hoc network are often vulnerable to failures. The failures could be either due to fading effects, battery drainage, or as a result of compromised nodes that do not participate in network operations. Intermittent node failures can disrupt routing functionalities. As such, it is important to provide redundancy in terms of providing multiple node-disjoint paths from a source to a destination. In line with this objective, we first propose a modified version of the widely studied ad hoc on-demand distance vector routing protocol to facilitate the discovery of multiple node-disjoint paths from a source to a destination. We find that very few of such paths can be found. Furthermore, as distances between sources and destinations increase, bottlenecks inevitably occur and thus, the possibility of finding multiple paths is considerably reduced. We conclude that it is necessary to place what we call reliable nodes (in terms of both being robust to failure and being secure) in the network to support efficient routing operations. We propose a deployment strategy that determines the positions and the trajectories of these reliable nodes such that we can achieve a framework for reliably routing information. We define a notion of a reliable path which is made up of multiple segments, each of which either entirely consists of reliable nodes, or contains a preset number of multiple paths between the end points of the segment. We show that the probability of establishing a reliable path between a random source and destination pair increases tremendously even with a small number of reliable nodes when we use our algorithm to appropriately position these reliable nodes.     

Capacity planning providing 100 % survivability against double-link failures for WDM Networks

Survivability is always a key concern in WDM optical transport networks as failures may result in large amount of traffic disruption and significant degradation of network performance. In this paper, we investigate the capacity planning problem against double-link failures considering wavelength—continuity constraint. Our objective is to minimize the resource consumption when guaranteeing connection request 100 % survivability. We propose two efficient approaches: (1) the New Static Preplanned Path Protection (NSPPP); (2) the New Dynamic Rerouting (NDR). In NSPPP, we present a new backup resource sharing rule to compress the spare capacity. In NDR, only the working path of connection request is necessary to be given, and the rerouting path can be dynamically found on the network after double-link failures. Compared to previous algorithms, our proposed two capacity planning approaches can efficiently solve double-link failures problem of WDM networks, also obtain higher resource utilization ratio and lower network resource.     

On surviving dual-link failures in path protected optical WDM mesh networks

In this paper, we investigate the problem of enhancing dual-failure restorability in path protected mesh-restorable optical Wavelength Division Multiplexed (WDM) networks. Recent studies have demonstrated the need to survive simultaneous dual-link failures and have also provided solutions for handling such failures. A key finding of these early efforts is that designs providing complete (i.e. 100%) protection from all dual-failures need almost triple the spare capacity compared to a system that protects against all single-link failures. However, it has also been shown that systems designed for 100% single-link failure protection can provide reasonable protection from dual-link failures [M. Clouqueur, W. Grover, Mesh-restorable networks with 74 enhanced dual-failure restorability properties, in: Proc. SPIE OPTICOMM, Boston, MA, 2002, pp. 1-12]. Thus, the motivation for this work is to develop a hybrid mechanism that provides maximum (close to 100%) dual-failure restorability with minimum additional spare capacity.The system architecture considered is circuit-switched with dynamic arrival of sessions requests. We propose an adaptive mechanism, which we term active protection, that builds upon a proactive path protection model (that provides complete single-failure restorability), and adds dynamic segment-based restoration to combat dual-link failures. The objective is to optimize network survivability to dual-link failures while minimizing additional spare capacity needs. We also propose a heuristic constraint-based routing algorithm, which we term best-fit, that aids backup multiplexing among additional spare paths towards this goal. Our findings indicate that the proposed active protection scheme achieves close to complete (100%) dual-failure restorability with only a maximum of 3% wavelength-links needing two backups, even at high loads. Moreover, at moderate to high loads, our scheme attains close to 16% improvement over the base model that provides complete single-failure restorability. Also, the best-fit routing algorithm is found to significantly assist backup multiplexing, with around 15%-20% improvement over first-fit at all loads. The segment-based restoration algorithm reiterates the importance of utilizing wavelength converters in protection and is seen to provide around 15%-20% improvement over link restoration especially at moderate to high loads.     

p-Cycle Design in Survivable WDM Networks with Shared Risk Link Groups (SRLGs)

p-Cycle survivable network design under the single link failure assumption has been studied extensively. Shared risk link group (SRLG) is a concept that better reflects the nature of network failures. An SRLG is a set of links that may fail simultaneously because of a common risk they share. The capability of dealing with SRLG failures is essential to network survivability. In this paper, we extend the p-cycle survivable network design from the single link failure model to the single SRLG failure model. An integer linear programming (ILP) formulation that minimizes spare capacity requirement is provided. To avoid enumerating all cycles of a network, we also provide a polynomial-time algorithm to generate a basic candidate p-cycle set that guarantees 100% restorability in case of any single SRLG failure given enough spare capacities. Moreover, we present the SRLG failure detection problem that prevents fast restoration upon an SRLG failure. To solve this problem, we introduce the concept of SRLG-independent restorability, which enables the restoration of each link in a failed SRLG to start immediately without knowing which SRLG has failed. We present an approach to optimal p-cycle design with SRLG-independent restorability and show that it is NP-hard to generate a candidate p-cycle set such that each link can be SRLG-independently restored by at least one cycle in the set.     

A joint resilience scheme with interlayer backup resource sharing in IP over WDM networks

The survivability of IP over WDM networks gains importance as network traffic keeps growing. Recovery at the lowest layer is fast and scalable. However, it is usually considered to provide poor network utilization. In this article we propose a resilience scheme based on recovery at the lowest layer in which intralayer and interlayer backup resource sharing is utilized to improve the network utilization. By applying interlayer backup resource sharing, we can totally depend on the reserved backup resources for fiber link failures to guarantee 100 percent recovery of IP router failures. In addition, by applying intralayer backup resource sharing, the network utilization improvement of recovery at the lowest layer is much more significant than at the highest layer. Simulations results show that the proposed scheme can efficiently improve network utilization and be even more capacity-efficient than resilience schemes based on recovery at the highest layer.     

Selective survivability with disjoint nodes and disjoint lightpaths for layer 1 VPN

This paper deals with the problem of survivable routing and wavelength assignment in layer 1 virtual private networks (VPNs). The main idea is routing the selected lightpaths by the layer 1 VPN customer, in a link-disjoint manner. The customer may freely identify some sites or some connections, and have their related lightpaths routed through link-disjoint paths through the provider’s network. This selective survivability idea creates a new perspective for survivable routing, by giving the customer the flexibility of selecting important elements (nodes or connections) in its network. This study is different from previous studies which aim to solve the survivable routing problem for the whole VPN topology. The proposed scheme is two-fold: disjoint node based, and disjoint lightpath based. In disjoint node scheme, all lightpaths incident to a node are routed mutually through link-disjoint paths. In disjoint lightpath scheme, a lightpath is routed in a link-disjoint manner from all other ligthpaths of the VPN. We present a simple heuristic algorithm for selective survivability routing. We study the performance of this algorithm in terms of resources allocated by the selective survivability routing scheme compared to shortest path routing with no survivability. The numerical examples show that the amount of used resources by the selective survivability scheme is only slightly more than the amount used in shortest path routing, and this increase is linear. The extra resources used by the new scheme are justified by better survivability of the VPN topology in case of physical link failures, and the simplicity of the implementation.     

Incremental survivable network design against node failure in SDH/SONET mesh networks

Network survivability is becoming more and more important for the plenty of information each single fiber carries. Extra network resources are needed to increase network survivability level. In this paper, we investigate the problem of how to augment the network topology with adding new links and allocate spare capacity to maximize the service restorability against node failures in SDH/SONET mesh networks. A scheme called maximal node-disjoint backup paths provisioning with topology augmentation is proposed to tackle the problem, and another scheme called globally optimized path provisioning with topology augmentation, which allows adjusting the existing working paths of network flows, is investigated to optimize the augmented network globally. Both schemes are formulated as mixed integer linear programming models. Furthermore, heuristic algorithms are investigated to be implemented in software. Three algorithms, i.e., added links searching method, successive maximal survivable routing method, and random sequence routing convergence method, are designed and compared. Simulation results show the effectiveness of the algorithms.     

支持高速多媒体网络生存性的QoS体系

高速多媒体网络中,如何提供服务质量（ＱｏＳ）保障是最核心的研究问题。同时,网络的生存能力正日益受到关注。这意味着网络系统不仅要在正常情况下,而且要在故障发生时,保障关键应用的服务质量。为此,我们针对生存性要求扩展了网络系统的ＱｏＳ机制,将ＱｏＳ机制与快速故障恢复机制集成在一起,首次提出了支持生存性的ＱｏＳ体系。最后,给出了在ＡＴＭ网络中的示例原型。     

Unisource and Multisource Tree Schemes for Collision Resolution in Wireless MAN

IEEE 802.16 wireless MAN standard specifies the air interface of broadband wireless access systems providing multiple services. In the wireless MAN, the best effort service class is ranked on the lowest position in priority and is assisted by a MAC scheme based on reservation ALOHA. In such a MAC scheme, a collision of resource requests is unavoidable so that the wireless MAN standard adopted a truncated binary exponential back-off scheme to arbitrate request attempts. While an exponential back-off scheme is simple to implement, its capture or starvation effect was revealed to deteriorate the fairness in short-term throughput and delay variance in the long term. Aiming at improving the throughput and delay performance, we thus propose the unisource and multisource m-ary tree schemes as alternatives for resolving request collisions in a wireless MAN. For the unisource tree scheme, we first develop an analytical method to exactly calculate the throughput in the saturated environment. Using the analytical method and simulation method as well, we then evaluate the saturated throughput, mean of MAC PDU delay and variance of MAC PDU delay in each proposed scheme. From the numerical examples, we confirm that the unisource and multisource m-ary tree schemes invoke superior throughput and delay performance to a truncated binary exponential back-off scheme.     

Survivability evaluation of SIGMA and mobile IP

Mobile IP has been developed by IETF to handle mobility of Internet hosts at the network layer. Mobile IP suffers from a number of drawbacks, including low survivability due to single-point failure of Home Agents. Recently, Seamless IP diversity based Generalized Mobility Architecture (SIGMA) was proposed to support low latency, low packet loss mobility of IP hosts. In this paper, we show that the location management scheme used in SIGMA enhances the survivability of the SIGMA-based mobile network. We develop an analytical model to evaluate and compare the survivability of SIGMA with that of Mobile IP. Numerical results show the improvement in system response time and service blocking probability of SIGMA over Mobile IP in the presence of hardware failures and Distributed Denial of Service (DDoS) attacks. The research reported in this paper was funded by NASA Grants NAG3-2922 and NNX06AE44G     

Dynamic Establishment of Segmented Protection Paths in Single and Multi-Fiber WDM Mesh Networks

Wavelength division multiplexed (WDM) networks are matured to provide, scalable data centric infrastructure, capable of delivering flexible, value added, high speed and high bandwidth services directly from the optical (WDM) layer. But, providing fault-tolerance at an acceptable level of overhead in these networks has become a critical problem. This is due to the size of the current and future networks and diverse quality of service (QoS) requirements for multimedia and mission critical applications. Several distributed real-time applications require communication services with fault-tolerance apart from guaranteed timeliness at acceptable levels of overhead. Several methods exist in the literature which attempt to guarantee recovery in a timely and resource efficient manner. These methods are centered around a priori reservation of network resources called spare resources along a protection path. This protection path is usually routed from source to destination along a totally link disjoint path from primary path. This paper considers the problem of routing and wavelength assignment (RWA) in wavelength routed WDM optical networks. In particular, we propose an efficient algorithm to select routes and wavelengths to establish dependable connections (D-connections), called segmented protection paths. Our algorithm does not insist on the existence of totally disjoint paths to provide full protection. We present experimental results which suggest that our scheme is attractive enough in terms of average call acceptance ratio, spare wavelength utilization, and number of requests that can be satisfied for a given number of wavelengths assuming that the requests come one at time, and wavelengths are assigned according to fixed ordering. Furthermore, the results suggest that our scheme is practically applicable for medium and large sized networks, which improves number of requests that can be satisfied and helps in providing better QoS guarantees such as bounded failure recovery time and propagation delays without any compromise on the level of fault-tolerance for a given number of wavelengths and fibers. We conduct extensive simulation experiments to evaluate the effectiveness of the proposed scheme on different networks and compare with existing methods.This work was supported by the Department of Science and Technology, New Delhi, India. An earlier version of this paper was presented at Opticomm 2002 conference, July 29-August 2, Boston, USA.     

Providing fault tolerance in wireless access networks

Research and development on network survivability has largely focused on public switched telecommunications networks and high-speed data networks with little attention on the survivability of wireless access networks supporting cellular and PCS communications. This article discusses the effects of failures and survivability issues in PCS networks with emphasis on the unique difficulties presented by user mobility and the wireless channel environment. A simulation model to study a variety of failure scenarios on a PCS network is described, and the results show that user mobility significantly worsens network performance after failures, as disconnected users move among adjacent cells and attempt to reconnect to the network. Thus, survivability strategies must be designed to contend with spatial as well as temporal network behavior. A multilayer framework for the study of PCS network survivability is presented. Metrics for quantifying network survivability are identified at each layer. Possible survivability strategies and restoration techniques for each layer in the framework are also discussed     

OHS: A Novel hybrid survivability approach for WDM mesh networks

In this paper, we investigate the problem of single-link failure for multiple levels of service in wavelenght-division-multiplying (WDM) mesh networks, and propose a novel on-line hybrid survivability (OHS) approach. OHS provides differentiated survivability strategies for dynamic connection requests with multiple levels of service. For the new arriving connection requests, OHS can instantly adjust the cost of the link according to the current state of the network, and calculate the primary path or backup path (if needed). Simulation results show OHS is able to obtain better performance (in terms of network resource utilization, blocking ratio) than the previous algorithms.     

Efficient data retrieval algorithms for multiple requests in MIMO wireless networks

Given a set of multiple channels, a set of multiple requests, where each request contains multiple requested data items and a client equipped with multiple antennae, the multi‐antenna‐based multirequest data retrieval problem (DRMR‐MA) is to find a data retrieval sequence for downloading all data items of the requests allocated to each antenna, such that the maximum access latency of all antennae is minimized. Most existing approaches for the data retrieval problem focus on either single antenna or single request and are hence not directly applicable to DRMR‐MA for retrieving multiple requests. This paper proposes two data retrieval algorithms that adopt two different grouping schemes to solve DRMR‐MA so that the requests can be suitably allocated to each antenna. To find the data retrieval sequence of each request efficiently, we present a data retrieval scheme that converts a wireless data broadcast system to a special tree. Experimental results show that the proposed scheme is more efficient than other existing schemes. Copyright © 2014 John Wiley & Sons, Ltd.     

Efficiency of repeated network interactions

In this paper we consider a network with interactions by two users. Each of them repeatedly issues download requests on the network. These requests may be unsuccessful due to congestion or non-congestion-related errors. A user decides when to cancel a request (that is, what his impatience threshold is) and how long to wait before reissuing his request after cancellation of the previous request (that is, what his waiting time will be). This pair of impatience threshold and waiting time is his strategy. If a customer decides not to wait but to reissue his request immediately, that is, he sets his waiting time to zero, then he is said to use a so-called restart strategy. The goal of the user is to maximize the number of successful requests over a given time span.We study optimal strategies for the users in a game-theoretic framework. We find that in case congestion is the only cause of unsuccessful requests then each of the users will be very patient and any waiting time is optimal. Hence, restart strategies are among the optimal strategies. Second, in case non-congestion-related errors may occur, users will also set large impatience times, but now they will set waiting times to zero; in other words: they immediately reissue an unsuccessful download. In this case all optimal strategies are restart strategies. Hence, in both cases restart strategies are among the optimal strategies. Finally, implementing socially optimal strategies instead of individual optimal ones cannot improve the efficiency of the network usage.     

Service Scheduling of Vehicle-Roadside Data Access

As vehicular networks become popular, more and more people want to access data from their vehicles. When many vehicles want to access data through a roadside unit, service scheduling becomes an important issue. In this paper, we identify some challenges in vehicle-roadside data access. As vehicles move pretty fast, the requests should be served quickly. Also, vehicles may upload data to the roadside unit, and hence the download and upload requests compete for the same bandwidth. To address these challenges, we propose several service scheduling schemes. We first propose a basic scheduling scheme called $\mathcal{D*S}$ to consider both service deadline and data size. We then enhance it by using a single broadcast to serve multiple requests. Finally, we identify the effects of upload requests on data quality, and propose a Two-Step scheduling scheme to provide a balance between serving download and update requests. Simulation results show that the Two-Step scheduling scheme outperforms other scheduling schemes.     

Efficient and distributed access control for sensor networks

Sensor networks are a promising computing paradigm for monitoring the physical environment and providing observations for various uses. In hostile situations, it is critical to enforce network access control to ensure the integrity, availability, and at times confidentiality of the sensor data. A natural idea is to adopt a centralized design where every access request from users goes through a trusted base station. However, this idea is not practical due to the cost and efficiency issues. This paper proposes two efficient and distributed access control methods, uni-access query and multi-access query. The uni-access query uses only symmetric cryptographic operations; it allows (1) a user to directly access the data on any sensor node in the network without going through the base station and (2) a sensor to protect its data so that only authorized users can access. Compared to existing solutions, this scheme is much more flexible and efficient. In addition, this scheme can also support privilege delegation, which allows a user to delegate all or part of its privilege to others without using the base station. The multi-access query applies public key cryptography to provide an additional feature, which allows a user to access the data on many sensor nodes via a single query. Compared to existing solutions that require a user to send at least one request for every sensor node to be queried, the multi-access query reduces the communication overhead significantly. The theoretical analysis and simulation evaluation show that the proposed schemes are practical for access control in sensor networks.     

Physical layer performance benchmarking of two metropolitan area network configurations

This paper investigates the problem of dynamic survivable lightpath provisioning against single-node/link failures in optical mesh networks employing wavelength-division multiplexing (WDM).We unify various forms of segment protection into generalized segment protection (GSP). In GSP, the working path of a lightpath is divided into multiple overlapping working segments, each of which is protected by a node-/link-disjoint backup segment. We design an efficient heuristic which, upon the arrival of a lightpath request, dynamically divides a judiciously selected working path into multiple overlapping working segments and computes a backup segment for each working segment while accommodating backup sharing. Compared to the widely considered shared-path protection scheme, GSP achieves much lower blocking probability and shorter protection-switching time for a small sacrifice in control and management overhead.On the basis of generalized segment protection, we present a new approach to provisioning lightpath requests according to their differentiated quality-of-protection (QoP) requirements. We focus on one of the most important QoP parameters—namely, protection-switching time—since lightpath requests may have differentiated protection-switching-time requirements. For example, lightpaths carrying voice traffic may require 50 ms protection-switching time while lightpaths carrying data traffic may have a wide range of protection-switching-time requirements. Numerical results show that our approach achieves significant performance gain which leads to a remarkable reduction in blocking probability.While our focus is on the optical WDM network, the basic ideas of our approaches can be applied to multi-protocol label switching (MPLS) networks with appropriate adjustments, e.g., differentiated bandwidth granularities.