Search

Intractable is the problem of finding two link-disjoint paths of minimal cost if the path cost is limited since it can be a special case of the partition problem. In optical networks, this limit can be introduced by the signal modulation reach. Even without this limit, the existing literature suggested the problem intractable because of the spectrum continuity and contiguity constraints, but we show that the problem can be solved exactly with the recently-proposed generic Dijkstra algorithm over a polynomially-bounded search space, thus proving the problem tractable.

The recently-proposed generic Dijkstra algorithm finds shortest paths in networks with continuous and contiguous resources. The algorithm was proposed in the context of optical networks, but is applicable to networks with finite and discrete resources. The algorithm was published without a proof of correctness, and with a minor shortcoming. We provide that missing proof and offer a correction to the shortcoming. To prove the algorithm correct, we generalize the Bellman's principle of optimality to algebraic structures with a partial ordering. We also argue the stated problem is tractable by analyzing the size of the search space in the worst-case.

We propose the novel idea of interoperator fixed-mobile network sharing, which can be software-defined and readily-deployed. We study the benefits which the sharing brings in terms of resiliency, and show that, with the appropriate placement of a few active nodes, the mean service downtime can be reduced more than threefold by providing interoperator communication to as little as one optical network unit in one hundred. The implementation of the proposed idea can be carried out in stages when needed (the pay-as-you-grow deployment), and in those parts of the network where high service availability is needed most, e.g., in a business district. While the performance should expectedly increase, we show the resiliency is brought almost out of thin air by using redundant resources of different operators. We evaluated the service availability for 87400 networks with the relative standard error of the sample mean below 1%., Comment: 19th International Conference on Optical Network Design and Modeling (ONDM), pp. 192-197, May 2015

We present a novel algorithm for dynamic routing with dedicated path protection which, as the presented simulation results suggest, can be efficient and exact. We present the algorithm in the setting of optical networks, but it should be applicable to other networks, where services have to be protected, and where the network resources are finite and discrete, e.g., wireless radio or networks capable of advance resource reservation. To the best of our knowledge, we are the first to propose an algorithm for this long-standing fundamental problem, which can be efficient and exact, as suggested by simulation results. The algorithm can be efficient because it can solve large problems, and it can be exact because its results are optimal, as demonstrated and corroborated by simulations. We offer a worst-case analysis to argue that the search space is polynomially upper bounded. Network operations, management, and control require efficient and exact algorithms, especially now, when greater emphasis is placed on network performance, reliability, softwarization, agility, and return on investment. The proposed algorithm uses our generic Dijkstra algorithm on a search graph generated "on-the-fly" based on the input graph. We corroborated the optimality of the results of the proposed algorithm with brute-force enumeration for networks up to 15 nodes large. We present the extensive simulation results of dedicated-path protection with signal modulation constraints for elastic optical networks of 25, 50, and 100 nodes, and with 160, 320, and 640 spectrum units. We also compare the bandwidth blocking probability with the commonly-used edge-exclusion algorithm. We had 48,600~simulation runs with about 41 million searches.

We present an optimal and efficient algorithm for finding a shortest path in an elastic optical network. The algorithm is an adaptation of the Dijkstra shortest path algorithm, where we take into account the spectrum continuity and contiguity constraints, and a limit on the path length. The adaptation redefines the node label in the Dijkstra algorithm, allows for revisiting nodes even at a higher cost for different slices, avoids loops, and prunes worse labels. The algorithm is generic and agnostic of a specific spectrum allocation policy, as it finds the largest set of available slices from which slices can be allocated in any way. We describe and motivate the algorithm design, and point to our freely-available implementation using the Boost Graph Library. We carried out 8100 simulation runs for large, random and realistic networks, and found that the probability of establishing a connection using the proposed algorithm can be even twice as large as the probability of establishing a connection using the edge-disjoint shortest paths, and the Yen K shortest paths., Comment: 20th International Conference on Optical Network Design and Modeling (ONDM), pp. 200-205, May 2016

We present the generic Dijkstra shortest path algorithm: an efficient algorithm for finding a shortest path in an optical network, both in a wavelength-division multiplexed network, and an elastic optical network (EON). The proposed algorithm is an enabler of real-time softwarized control of large-scale networks, and is not limited to optical networks. The Dijkstra algorithm is a generalization of the breadth-first search, and we generalize the Dijkstra algorithm further to resolve the continuity and contiguity constraints of the frequency slot units required in EONs. Specifically, we generalize the notion of a label, change what we iterate with, and reformulate the edge relaxation so that vertices are revisited, loops avoided, and worse labels discarded. We also used the typical constriction during edge relaxation to take care of the signal modulation constraints. The algorithm can be used with various spectrum allocation policies. We motivate and discuss the algorithm design, and provide our free, reliable, and generic implementation using the Boost Graph Library. We carried out 85000 simulation runs for realistic and random networks (Gabriel graphs) of 75 vertices with about a billion shortest-path searches, and found that the proposed algorithm outperforms considerably three other competing optimal algorithms that are frequently used., Comment: This is the final version that was published in the Journal of Optical Communications and Networking

We evaluate the downstream performance of our novel interoperator fixed-mobile network sharing, in which operators exchange data in their access networks. We propose a performance evaluation algorithm, and report credible performance evaluation results obtained for 204600 randomly-generated passive optical networks. We show that with the proposed sharing, operators can increase their access network performance even twofold with software-defined upgrades, and with no or minimal new hardware required., Comment: submitted to a conference

We state a new problem of \emph{itinerant routing} in elastic optical networks, which we define as the establishment and reconfiguration of an \emph{itinerant connection}. In an itinerant connection, one of the connection end nodes is allowed to change. Itinerant routing could also be considered a form of connection restoration, where a connection has to be restored to a different end node. With the introduction of new mobile-network architectures, the progressing integration of wireless and optical networks, the continuing growth of wireless high-bitrate services, and the eventual deployment of elastic optical networks, there is a need to support this itinerant routing in the elastic optical networks. We present and discuss two major use cases of the itinerant routing, and propose a \emph{novel reconfiguration algorithm}. Our algorithm does not deteriorate the network performance, and requires half as many new links to configure as the shortest-path reconfiguration algorithm. The performance evaluation was carried out with 46800 simulation runs using randomly-generated realistic transport networks., Comment: submitted for publication to an IEEE journal