This paper investigates the subject of reliability via two link-disjoint paths in mesh networks. We address the issues of how reliable two-path protection can be and how to achieve the maximum reliability. This work differs from traditional studies, such as MIN-SUM, MIN-MAX, and MIN-MIN, in that the objective in this paper is to maximize the reliability of the two-path connection given the link reliability, or equivalently, to minimize the end-to-end failure probability. We refer to this problem as MAX-REL. Solving MAX-REL provides 100% protection against a single failure while maximizing the reliability regardless of how many link failures occur in the network. We prove that this problem is NP-complete and derive a corresponding upper bound, which is the theoretical maximum reliability for a source-destination pair, and a lower bound, which is the worst case of the proposed algorithm. The time efficiency of the algorithms is analyzed, and the performance of the algorithms is evaluated through simulation. We demonstrate that our heuristic algorithms not only achieve a low computing complexity, but also achieve nearly equivalent performance to the upper bound.

In this paper, we focus on the problem of effectively supporting a large number of small group multicasts in optical burst switched (OBS) networks. We first propose a multicast scheme for small group multicast in OBS networks. To reduce burst loss due to potential burst contentions, a deflection routing scheme for multicast is proposed. We then develop an analytical model to evaluate the performance of the multicast scheme and the deflection routing scheme. To the best of our knowledge, this is the first analytical model proposed for the problem of multicast with deflection routing. The model is very general in the sense that it can handle unicast traffic, multicast traffic, and the mixture of unicast and multicast traffic, with or without deflection routing. The analytical model is verified through simulations. Numerical results show that the analytical model is accurate, and that, under low or medium network load, deflection routing for multicasting can significantly reduce burst loss while slightly increasing burst delay.

In this paper, we investigate the problem of survivable grooming for anycasting over wavelength division multiplexing (WDM) networks. Anycasting is a communication paradigm in which a source node sends data to any one out of multiple candidate destinations. In WDM networks, the standard anycasting problem involves the establishment of a connection from the source to any one destination with the objective of minimizing the resources used. In order to provide survivability, the problem can be extended to find both a connection to a primary destination and a connection to a backup destination. The connections, which may require an amount of bandwidth that may be less than the bandwidth of an entire wavelength, can be groomed with other connections in the WDM network. We propose an auxiliary graph approach to solving the survivable grooming problem for anycasting in WDM networks, and we propose three different protection approaches for providing different degrees of survivability against link failures and destination failures. The effectiveness of the proposed schemes is verified through simulation.

In this paper, we discuss for the first time the issue of supporting manycasting service over optical burst- switched (OBS) networks. One of the primary challenges in providing manycasting service over OBS networks is to reduce data loss due to burst contentions. We propose two new schemes, static over-provisioning (SOP) and dynamic membership (DM), to alleviate this data loss problem. The proposed schemes take into consideration the specific properties of manycasting, and the schemes may complement existing contention resolution schemes. The effectiveness of the proposed schemes is verified through simulation.

This paper investigates the path protection problem in mesh networks under multiple generic risks. Disjoint logical links may fail simultaneously if they share the same components in the physical layer. Each component is associated with one or more risks, and each risk may involve more than one logical link. This property introduces failure dependence for different logical links in layered networks. In this paper, the network failure scenario is under multiple risks. Each risk is a generic failure event, which may result in single-link failure, multiple-link failure, or all-link failure associated with a node (node failure). The objective aims at minimizing the end-to-end failure probability, or equivalently, maximizing the survivability by using two disjoint paths under multiple generic risks. The problem is shown to be NP-complete, and a novel graph model and corresponding heuristic algorithm are proposed. The time efficiency of the algorithms is analyzed, and the simulation results show that, compared to some existing diverse routing algorithms, the proposed heuristic algorithm can significantly improve the survivability at the cost of higher hop distance.

We define and investigate the problem of multi-resource manycast over optical burst switched (OBS) networks for supporting distributed computing applications. In multi-resource manycast, each destination has multiple computing resources, and each source generates requests that require multiple resources. For a given request, the problem is to select a set of destinations that have the required available resources and to And routes to these destinations. This problem differs from the traditional manycast problem in that different destinations have different resource availability. The objective is to minimize the resource blocking rate, which results from burst contention in the OBS network and from resource unavailability at the destinations. We investigate various approaches to implement multi-resources manycast over OBS networks, and verify the effectiveness of the proposed schemes through simulation.

In this paper, we focus on the problem of effectively supporting a large number of small group multicasts in optical burst switched (OBS) networks. We first propose a multicast scheme for small group multicast in OBS networks. To reduce burst loss due to potential burst contentions, a deflection routing scheme for multicast is proposed. We then develop a generic analytical model to evaluate the performance of the multicast scheme and the deflection routing scheme. To the best of our knowledge, this is the first analytical model proposed for the problem of multicast with deflection routing. The analytical model is verified through simulations. Numerical results show that the analytical model is accurate and that deflection routing can significantly reduce burst loss probability while slightly increasing burst delay.

With the growth of mobile users and the increasing deployment of wireless access network infrastructures, the issue of quality of service is becoming an important component of efficient wireless access network design. In this paper, we study the survivability problem for users that are connected to the core network by fully or partially dual homed paths, or by a single path. Given a hierarchical wireless access network with the available capacity and reliability at each level, the problem is to minimize overall connection cost for multiple requests such that the capacity and minimum survivability requirements are not violated. We formulate the problem using mixed integer linear programming and propose a genetic-algorithm-based heuristic.

This paper investigates the problem of finding two link-disjoint paths in mesh networks. Different from traditional studies, such as MIN-SUM, MIN-MAX, and MIN-MIN, the objective in this paper is to minimize the end-to-end failure probability, or equivalently, maximize the survivability under multiple link failures. We refer to this problem as MAX-SURV. Solving MAX-SURV provides 100% protection against single failure while maximizing the survivability under multiple failures. We prove that this problem is NP-complete, and we propose a heuristic algorithm for finding a solution. The corresponding upper bound and lower bound for given networks are also found. The time efficiency of the algorithms is analyzed, and the performance of the algorithms is evaluated through simulation.

Abstract — In this paper, we study the survivability problem in hierarchical wireless access networks with dual-homed end users, who are connected to two base stations (BSs), a primary BS and a backup BS. The dual homing mechanism is resilient to a single failure of a BS. However, if a failure occurs at the base station controller (BSC) layer or at the mobile switching center (MSC) layer, dual-homing may not prevent connection loss. We address the problem of routing from BSs to BSCs and from BSCs to MSCs, with the objective of minimizing the maximum number of connections lost due to a single failure of BS, BSC, or MSC. We first formulate the problem using Integer Linear Programming (ILP). We then prove that this optimization problem is NP-hard by showing some of its subproblems with relaxed constraints are still NP-hard. A Tabu Search (TS) based heuristic is then proposed for the problem, which provides near optimal results in most cases. I.

In this paper, we propose a novel proactive scheme, burst cloning, to reduce data loss due to burst contention in optical burst-switched (OBS) networks. The idea is to replicate a burst and send duplicated copies of the burst through the network simultaneously. If the original burst is lost, the cloned burst way still be able to reach the destination. Primary design issues in burst cloning are to select the optimal nodes at which to do cloning and to prevent cloned bursts from contending for resources with original bursts. An analytical model is developed to evaluate the proposed scheme. The model is verified through extensive simulations. We observe that burst cloning could significantly reduce data loss in OBS networks.

As high capacity all-optical networks and WDM technologies advance and merge together, aggregating low-speed traffic streams onto high-speed wavelengths becomes more critical. Efficient aggregation techniques, known as traffic grooming, allow higher bandwidth utilization and can reduce request blocking probability. These algorithms can also result in lower network cost in terms of electronic switching. In this paper we focus on traffic grooming in WDM mesh networks with dynamic traffic patterns. We offer two new grooming concepts called lightpath dropping and lightpath extension. These concepts are based on an alternative node architecture in which incoming optical signals can be dropped at a node, while optically continuing to the next node. Based on these concepts, we develop several grooming algorithms and study them under various network objectives. We also compare their performance with previously proposed lightpath-based grooming algorithms. Through extensive simulation results we show that our proposed approaches lead to lower request blocking probability and lower average number of logical hops when the number of transceivers per node is limited.

We address the traffic grooming problem in WDM mesh networks with dynamic unicast traffic. We develop a dynamic tree grooming algorithm (DTGA) that can support multi-hop traffic grooming by taking advantage of light-trees. In this algorithm, a light-tree can be dropped, branched, and extended when a route is to be established for a new request. In order to implement the DTGA, we develop a layered graph model which can support different routing policies. Extensive simulation shows that DTGA has better performance than lightpath-based algorithms when transceivers are limited.