Lightpath scheduling is an important capability in next-generation wavelength-division multiplexing (WDM) optical networks to reserve resources in advance for a specified time period while provisioning end-to-end lightpaths. In a dynamic environment, the end user requests for dynamic scheduled lightpath demands (D-SLDs) need to be serviced without the knowledge of future requests. Even though the starting time of the request may be hours or days from the current time, the end-user however expects a quick response as to whether the request could be satisfied. We propose a two- phase approach to dynamically schedule and provision D-SLDs. In the first phase, termed the deterministic lightpath scheduling phase, upon arrival of a lightpath request, the network control plane schedules a path with guaranteed resources so that the user can get a quick response with a deterministic lightpath schedule. In the second phase, termed the lightpath re-optimization phase, we re-provision some already scheduled lightpaths to re-optimize for improving network performance. We study two re- optimization scenarios to reallocate network resources while maintaining the existing lightpath schedules. Experimental results show that our proposed two-phase dynamic lightpath scheduling approach can greatly reduce network blocking.

The survivable virtual topology routing problem is to route a virtual topology graph on a optical fiber physical topology such that the virtual topology remains connected when failures occur in the physical topology. In this work we study the problem of survivable virtual topology routing under single node/SRLG (Shared Risk Link Group) failure model. We prove that the survivable virtual topology routing problem under node/SRLG failures is NP-complete. We present an improved integer linear programming (ILP) formulation for computing the survivable routing of a virtual topology graph. However, ILP is not scalable when the network size scales more than a few tens of nodes. In this work, we present sub-classes of graphs which more accurately model an actual network and for which a survivable routing can be easily computed solving an ILP. We successfully computed the survivable routing of virtual topologies belonging to these sub-classes against link/SRLG failures for topologies of size up to 24 nodes.

Dynamic conferencing refers to a scenario wherein any subset of users in a universe of users form a conference for sharing confidential information among themselves. The key distribution (KD) problem in dynamic conferencing is to compute a shared secret key for such a dynamically formed conference. In literature, the KD schemes for dynamic conferencing either are computationally unscalable or require communication among users, which is undesirable. The extended symmetric polynomial based dynamic conferencing scheme (ESPDCS) is one such KD scheme which has a high computational complexity that is universe size dependent. In this paper we present an enhancement to the ESPDCS scheme to develop a KD scheme called universe-independent SPDCS (UI-SPDCS) such that its complexity is independent of the universe size. However, the UI-SPDCS scheme does not scale with the conference size. We propose a relatively scalable KD scheme termed as DH-SPDCS that uses the UI-SPDCS scheme and the tree-based group Diffie-Hellman (TGDH) key exchange protocol. The proposed DH-SPDCS scheme provides a configurable trade-off between computation and communication complexity of the scheme.

Lightpath scheduling is an important capability in next-generation wavelength-division multiplexing (WDM) optical networks to reserve resources in advance for a specified time period while provisioning end-to-end lightpaths. In this study, we propose an approach to support dynamic lightpath scheduling in such networks. To minimize blocking probability in a network that accommodates dynamic scheduled lightpath demands (D- SLDs), resource allocation should be optimized in a dynamic manner. However, for the network users who desire deterministic services, resources must be reserved in advance and guaranteed for future use. These two objectives may be mutually incompatible. Therefore, we propose a two-phase dynamic lightpath scheduling approach to tackle this issue. The first phase is the deterministic lightpath scheduling phase. When a lightpath request arrives, the network control plane schedules a path with guaranteed resources so that the user can get a quick response with the deterministic lightpath schedule. The second phase is the lightpath re-optimization phase, in which the network control plane re-provisions some already scheduled lightpaths. Experimental results show that our proposed two-phase dynamic lightpath scheduling approach can greatly reduce WDM network blocking.

Abstract — Multicommodity flow (MF) problems have a wide variety of applications in areas such as VLSI circuit design, network design, etc., and are therefore very well studied. The fractional MF problems are polynomial time solvable while integer versions are N Pcomplete. However, exact algorithms to the fractional MF problems have high computational complexity. Therefore approximation algorithms to fractional MF problems have been explored in the literature to reduce their computational complexity. Using these approximation algorithms and the randomized rounding technique, polynomial time approximation algorithms have been explored in the literature. In the design of high-speed networks, such as optical wavelength division multiplexing (WDM) networks, providing survivability carries great significance. Survivability is the ability of the network to recover from failures. It further increases the complexity of the network design and presents network designers with more formidable challenges. In this work we formulate the survivable versions of the MF problems. We build approximation algorithms for the survivable multicommodity flow (SMF) problems based on the framework of the approximation algorithms for the MF problems presented in [1] and [2]. We discuss applications of the SMF problems to solve survivable routing in capacitated networks.

Providing fault tolerance against network failures in an optical WDM network is of prime importance. In this work we study the problem of computing optimal disjoint paths for providing shared protection in fully wavelength-convertible networks. We introduce and formalize the concept of dependent cost structure of a protection path on its working path and current network status. We formulate the problem of computing optimal disjoint paths for providing shared protection in fully wavelength-convertible networks as the problem of computing least-cost disjoint paths with dependent cost structure (LDP-DCS). We prove that LDP-DCS is NP-complete and is also hard to approximate. We present an iterative modified network-flow heuristic for the problem. We provide an approach to measure the optimality of the solution computed by the heuristic. Simulation results demonstrate the superior performance of our proposed heuristic in comparison to earlier heuristic approaches which did not consider the dependent cost structure.

Establishing a fault-tolerant connection in a network involves computation of diverse working and protection paths. The shared risk link group (SRLG) (J. Strand et al. (2001) concept is used to model several types of failure conditions such as link, node, fiber conduit, etc. In this work we focus on the problem of computing optimal SRLG/link diverse paths under shared protection. Shared protection technique improves network resource utilization by allowing protection paths of multiple connections to share resources. In this work we propose an iterative heuristic for computing SRLG/link diverse paths. We present a method to calculate a quantitative measure that provides a bounded guarantee on the optimality of the diverse paths computed by the heuristic. The experimental results on computing link diverse paths show that our proposed heuristic is efficient in terms of number of iterations required (time taken) to compute diverse paths when compared to other previously proposed heuristics

One of the important issues in establishing a fault tolerant connection in a wavelength division multiplexing optical network is computing a pair of disjoint working and protection paths and a free wavelength along the paths. While most of the earlier research focused only on computing disjoint paths, in this work we consider computing both disjoint paths and a free wavelength along the paths. The concept of dependent cost structure (DCS) of protection paths to enhance their resource sharing ability was proposed in our earlier work. In this work we extend the concept of DCS of protection paths to wavelength continuous networks. We formalize the problem of computing disjoint paths with DCS in wavelength continuous networks and prove that it is NP-complete. We present an iterative heuristic that uses a layered graph model to compute disjoint paths with DCS and identify a free wavelength.

Network survivability is one of the most important issues in the design of optical WDM networks. In this work we study the problem of survivable routing of a virtual topology on a physical topology with shared risk link groups (SRLG). The survivable virtual topology routing problem against single-link failures in the physical topology is proved to be NP-complete in E. Modiano and A. Narula-Tam, May 2002. We prove that survivable virtual topology routing problem against SRLG/node failures is also NP-complete. We present an improved integer linear programming (ILP) formulation (in comparison to E. Modiano and A. Narula-Tam, May 2002) for computing the survivable routing under SRLG/node failures. Using an ILP solver, we computed the survivable virtual topology routing against link and SRLG failures for small and medium sized networks efficiently. As even our improved ILP formulation becomes intractable for large networks, we present a congestion-based heuristic and a tabu search heuristic (which uses the congestion-based heuristic solution as the initial solution) for computing survivable routing of a virtual topology. Our experimental results show that tabu search heuristic coupled with the congestion based heuristic (used as initial solution) provides fast and near-optimal solutions.

Survivable routing of a connection involves computation of a pair of diverse routes such that at most one route fails when failures occur in the network topology. A subset of links in the network that share the risk of failure at the same time are said to belong to a shared risk link group (SRLG) [J. Strand et al., Feb 2001]. A network with shared risk link groups defined over its links is an SRLG network. A failure of an SRLG is equivalent to the failure of all the links in the SRLG. For a connection to be survivable in an SRLG network, its working and protection paths must be routed on SRLG diverse paths. SRLG diverse routing problem has been proved to be NP-complete in J.Q. Hu (2003). According to the quality of service requirement of a survivable connection request, dedicated protection or shared protection can be used to establish the connection request. With dedicated protection, the connection is established on both the SRLG diverse working and protection paths. The simplest heuristic for computing SRLG diverse path pair is the two-step approach, but it suffers from the trap topology problem. In the previous study by Pin-Han Ho, an iterative heuristic (ITSH) using the two-step approach was proposed to compute the least cost SRLG diverse path pair. Suurballe's algorithm computes a pair of least cost link-disjoint paths between a node pair. In this work, we present a modified Suurballe's heuristic for computing the SRLG diverse routes between a node pair. We then propose an iterative heuristic (IMSH) which uses the modified Suurballe's heuristic for computing the least cost SRLG diverse routes. We also present an 1/2-cost-improvement optimality check criterion for dedicated protection