Optical grooming with grooming ratio nine

Grooming uniform all-to-all traffic in optical ring networks with grooming ratio C requires the determination of graph decompositions of the complete graph into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The minimum drop cost is determined for grooming ratio 9. Previously this bound was shown to be met when with two exceptions and eleven additional possible exceptions for n, and also when with one exception and one possible exception for n. In this paper it is shown that the bound is met for all with four exceptions for n∈{8,11,14,17} and one possible exception for n=20. Using this result, it is further shown that when and n is sufficiently large, the bound is also met.     

Optical grooming with grooming ratio eight

Grooming uniform all-to-all traffic in optical ring networks with grooming ratio C requires the determination of graph decompositions of the complete graph into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The minimum possible drop cost is determined for grooming ratio 8, and this cost is shown to be realized with six exceptions, and 37 possible exceptions, the largest being 105.     

WDM网络中的排序与波长分配问题的一个多项式时间近似方案

本文考虑基于波分复用技术 (WDM)的光学网络中的排序与波长分配问题 .在波长数目固定的情况下 ,我们证明此问题是NP 困难问题 ,并且给出一个多项式时间近似方案 .若波长数目不固定 ,我们证明此问题不存在多项式时间近似方案     

A post-optimization method for the routing and wavelength assignment problem applied to scheduled lightpath demands

We consider here a NP-hard problem related to the Routing and Wavelength Assignment (RWA) problem in optical networks, dealing with Scheduled Lightpath Demands (SLDs). An SLD is a connection demand between two nodes of the network, during a certain time. Given a set of SLDs, we want to assign a lightpath, i.e. a routing path and a wavelength, to each SLD, so that the total number of required wavelengths is minimized. The constraints are the following: a same wavelength must be assigned all along the edges of the routing path of any SLD; at any time, a given wavelength on a given edge of the network cannot be used to satisfy more than one SLD. To solve this problem, we design a post-optimization method improving the solutions provided by a heuristic. The experimental results show that this post-optimization method is quite efficient to reduce the number of necessary wavelengths.     

A note on the minimum instantaneous cost path of the dynamic traffic assignment problem

We consider an example to show that the minimum instantaneous cost path principle, as suggested in Friesz et al. [1] for generalising Wardrop's first principle to the dynamic state, may cause some drivers' routes to loop. These looping routes traverse the same link more than once - indeed, in our example six times.The work reported in this paper has been partly funded by the Science and Engineering Research Council of the United Kingdom.     

Optimal receiver scheduling algorithms for a multicast problem

This paper studies a multicast problem arising in wavelength division multiplexing single-hop lightwave networks, as well as in Video-on-Demand systems. In this problem, the same message of duration Δ has to be transmitted to a set of n receivers which are not all available simultaneously. The receivers can be partitioned into subsets, each served by a different transmission, with the objective of minimizing their overall waiting cost. When there is a single data channel available for transmission, a dynamic programming algorithm is devised which finds an optimal solution in O(nlogn+min{n²,nΔ²}) time, improving over a previously known O(n³) time algorithm. When multiple data channels are available for transmission, an optimal O(n) time algorithm is proposed which finds an optimal solution if the message has constant transmission duration, whereas an NP-completeness proof is given if the message has arbitrary transmission duration.     

An Ant Colony Optimisation algorithm for solving the asymmetric traffic assignment problem

In this paper we propose an Ant Colony Optimisation (ACO) algorithm for defining the signal settings on urban networks following a local approach. This consists in optimising the signal settings of each intersection of an urban network as a function only of traffic flows at the accesses to the same intersection, taking account of the effects of signal settings on costs and on user route choices. This problem, also known as Local Optimisation of Signal Settings (LOSS), has been widely studied in the literature and can be formulated as an asymmetric assignment problem. The proposed ACO algorithm is based on two kinds of behaviour of artificial ants which allow the LOSS problem to be solved: traditional behaviour based on the response to pheromones for simulating user route choice, and innovative behaviour based on the pressure of an ant stream for solving the signal setting definition problem. Our results on real-scale networks show that the proposed approach allows the solution to be obtained in less time but with the same accuracy as in traditional MSA (Method of Successive Averages) approaches.     

Routing to reduce the cost of wavelength conversion

We consider all-optical networks that use wavelength-division multiplexing and employ wavelength conversion at specific nodes in order to maximize their capacity usage. We investigate the effect of allowing reroutings on the number of necessary wavelength converters. We disprove a claim of Wilfong and Winkler [G. Wilfong, P. Winkler, Ring routing and wavelength translation, in: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’98, 1998, pp. 333-341] according to which reroutings do not have any effect on the number of necessary wavelength converters on bidirected networks. We show that there exist (bidirected) networks on n nodes that require Θ(n) converters without reroutings, but only O(1) converters if reroutings are allowed. We also address the cases of undirected networks and networks with shortest-path routings. In each case, we resolve the complexity of computing optimal placements of converters.     

Wavelength assignment for reducing in-band crosstalk attack propagation in optical networks: ILP formulations and heuristic algorithms

Today’s Transparent Optical Networks (TONs) are highly vulnerable to various physical-layer attacks, such as high-power jamming, which can cause severe service disruption or even service denial. The transparency of TONs enables certain attacks to propagate through the network, not only increasing their damage proportions, but also making source identification and attack localization more difficult. High-power jamming attacks causing in-band crosstalk in switches are amongst the most malicious of such attacks. In this paper, we propose a wavelength assignment scheme to reduce their damage assuming limited attack propagation capabilities. This complements our previous work in Furdek et al. (M. Furdek, N. Skorin-Kapov, M. Grbac, Attack-aware wavelength assignment for localization of in-band crosstalk attack propagation, IEEE/OSA Journal of Optical Communications and Networking 2 (11) (2010) 1000–1009) where we investigated infinite jamming attack propagation to find an upper bound on the network vulnerability to such attacks. Here, we consider a more realistic scenario where crosstalk attacks can spread only via primary and/or secondary attackers and define new objective criteria for wavelength assignment, called the PAR (Primary Attack Radius) and SAR (Secondary Attack Radius), accordingly. We formulate the problem variants as integer linear programs (ILPs) with the objectives of minimizing the PAR and SAR values. Due to the intractability of the ILP formulations, for larger instances we propose GRASP (Greedy Randomized Adaptive Search Procedure) heuristic algorithms to find suboptimal solutions in reasonable time. Results show that these approaches can obtain solutions using the same number of wavelengths as classical wavelength assignment, while significantly reducing jamming attack damage proportions in optical networks.     

Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.