Routing in Optical and Stochastic Networks

In most types of networks (e.g., optical or transportation networks), finding one or more best paths from a source to a destination, is one of the biggest concerns of network users and providers. This process is known as routing. The routing problems differ accordingly depending on different application scenarios with their respective routing goals. For example, in the field of data communication networks, with many communication applications emerging (such as Cloud Computing, Internet Protocol Television (IPTV), Video-On-Demand), finding optimum routing paths has been considered in the bandwidth-limited network or when it is expensive to increase the capacity of the existing hardware. Moreover, for network providers, the Service Level Agreements (SLA) determine the level of service that is promised to the network user. The routing problems should also incorporate these SLAs (e.g., connection availability). The energy consumption of the data communication networks is another example, due to its impact on the environment (e.g., green house effect). Energy-aware routings have been considered as one approach to efficiently deal with this issue. Apart from that, the network itself is likely to behave in a stochastic manner. For instance, especially in large networks, it is difficult to obtain an accurate view on the link characteristics like bandwidth utilization or latency, because their dynamics are usually of the same order as the time it would take to distribute information on the link state throughout the network. The routing problems become more difficult to solve if the network dynamics have to be considered. This thesis deals with routing problems in two kinds of networks, namely, (1) (deterministic) optical networks and (2) stochastic networks. Optical networks have been widely deployed because of their high capacity, low bit rate, etc. Wavelength Division Multiplexing (WDM) technology enabled optical networks divides the capacity of a fiber into several non-overlapping wavelength channels that can transport data independently. These wavelength channels make up lightpaths, which are used to establish optical connections that may span several fiber links. Chapters 2 and 3 study the energyaware path selection problem in IP-over-WDM optical networks and the energy-efficient network design problem, respectively. In Chapter 4, a more flexible optical network enabled by OFDM technology is introduced, which is here called spectrum-sliced elastic optical path (SLICE) network. In this kind of network, the capacity of a fiber link is divided into a fixed number of (overlapping) low data rate transporting units, which are called subcarriers. Subsequently, Chapter 4 studies the routing problem in SLICE networks. Connection availability, which is defined as the probability that the corresponding connection is available, is a key element of many SLAs. Establishing a path over a connection should obey the availability agreements to avoid the loss of revenue. Chapter 5 studies the availability-based path selection problem. The energy-aware path selection problem in Chapter 2 is polynomial-time solvable, but all the other problems in Chapters 3, 4 and 5 are proved NP-hard. To solve them, exact algorithms or efficient heuristics are proposed. In deterministic optical networks, the link weights (e.g., energy) are usually assumed to be known, while in the so-called stochastic networks they are uncertain. Although in some cases optical networks may behave in a stochastic manner, most of the routing problems in deterministic optical networks are already NP-hard as mentioned above, which suggests that similar routing problems in stochastic optical networks are even harder to solve. We therefore consider more general stochastic networks, which are not confined to any specified type of network. Chapter 6 studies the maximum-flow problem without and with a delay constraint under the assumption that the bandwidth and delay follow a general log-concave probability distribution. A convex optimization formulation is proposed to solve the maximum-flow problem in stochastic networks. When a delay constraint is imposed on each path, the problem becomes NP-hard. To solve it, an approximation algorithm and a heuristic are devised. So far, all the studies do not thoroughly account for the correlations between link weights, but the link weights (such as failure probability) are correlated in some real-life networks. For example, in interdependent networks, where for instance the electricity network and Internet network are coupled and inter-connected, and one node or link failure in one network may cause failures of nodes or links in the other network. Chapter 7 addresses the shortest path problem and the min-cut problem (the dual problem of the maximum-flow problem in conventional networks) in more general correlated networks.Correlated network can also be regarded as a special kind of stochastic network, since its link weight is uncertain instead of fixed. Two correlated link weight models are studied, namely (1) deterministic correlated model and (2) (log-concave) stochastic correlated model. These two problems are proved NP-hard under the deterministic correlated model, and cannot be approximated to arbitrary degree, unless P=NP. But they are shown polynomial time solvable under a (constrained) nodal deterministic correlated model. Under the (log-concave) stochastic correlated model, two convex optimization formulations are proposed to solve the shortest path problem and the min-cut problem, respectively. Finally, Chapter 8 concludes with the main findings and contributions of this thesis, and also points out possible future work.Intelligent SystemsElectrical Engineering, Mathematics and Computer Scienc