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.     

External selection

Sequential selection has been solved in linear time by Blum et al. [M.B. Blum, R.W. Floyd, V.R. Pratt, R.L. Rivest, R.E. Tarjan, Time bounds for selection, J. Comput. System Sci. 7 (4) (1972) 448–461]. Running this algorithm on a problem of size N with N>M, the size of the main-memory, results in an algorithm that reads and writes O(N) elements, while the number of comparisons is also bounded by O(N). This is asymptotically optimal, but the constants are so large that in practice sorting is faster for most values of M and N.This paper provides the first detailed study of the external selection problem. A randomized algorithm of a conventional type is close to optimal in all respects. Our deterministic algorithm is more or less the same, but first the algorithm builds an index structure of all the elements. This effort is not wasted: the index structure allows the retrieval of elements so that we do not need a second scan through all the data. This index structure can also be used for repeated selections, and can be extended over time. For a problem of size N, the deterministic algorithm reads N+o(N) elements and writes only o(N) elements and is thereby optimal to within lower-order terms.     

On determining the congruence of point sets in d dimensions

This paper considers the following problem: given two point sets A and B (|A| = |B| = n) in d dimensional Euclidean space, determine whether or not A is congruent to B. This paper presents an O(n^(d−1)/2 log n) time randomized algorithm. The birthday paradox, which is well-known in combinatorics, is used effectively in this algorithm. Although this algorithm is Monte-Carlo type (i.e., it may give a wrong result), this improves a previous O(n^d−2 log n) time deterministic algorithm considerably. This paper also shows that if d is not bounded, the problem is at least as hard as the graph isomorphism problem in the sense of the polynomiality. Several related results are described too.     

The numerical stability of barycentric Lagrange interpolation

The Lagrange representation of the interpolating polynomialcan be rewritten in two more computationally attractive forms:a modified Lagrange form and a barycentric form. We give anerror analysis of the evaluation of the interpolating polynomialusing these two forms. The modified Lagrange formula is shownto be backward stable. The barycentric formula has a less favourableerror analysis, but is forward stable for any set of interpolatingpoints with a small Lebesgue constant. Therefore the barycentricformula can be significantly less accurate than the modifiedLagrange formula only for a poor choice of interpolating points.This analysis provides further weight to the argument of Berrutand Trefethen that barycentric Lagrange interpolation shouldbe the polynomial interpolation method of choice.     

Efficient hedging with coherent risk measure

The idea of efficient hedging has been introduced by Föllmer and Leukert. They defined the shortfall risk as the expectation of the shortfall weighted by a loss function, and looked for strategies that minimize the shortfall risk under a capital constraint. In this paper, to measure the shortfall risk, we use the coherent risk measures introduced by Artzner, Delbaen, Eber and Heath. We show that, for a given contingent claim H, the optimal strategy consists in hedging a modified claim ?H for some randomized test ?. This is an analogue of the results by Föllmer and Leukert.     

“舍割”摆中共轭点的妙用

文章介绍了利用共轭点可以测量等值摆长、重力加速度、周期和转动惯量等。     

Allocation search methods for a generalized class of location–allocation problems

We consider a generalized class of location–allocation problems, in which N new facilities are to be located in the plane with respect to M objects. Each object is associated with a convex cost function, specifying the expenses for serving the object from any location in the plane.     

Internal hydraulic analysis of impeller rounding in centrifugal pumps as turbines

The use of pumps as turbines in different applications has been gaining importance in the recent years, but the subject of hydraulic optimization still remains an open research problem. One of these optimization techniques that include rounding of the sharp edges at the impeller periphery (or turbine inlet) has shown tendencies of performance enhancement.In order to understand the effect of this hydraulic optimization, the paper introduces an analytical model in the pump as turbine control volume and brings out the functionalities of the internal variables classified under control variables consisting of the system loss coefficient and exit relative flow direction and under dependent variables consisting of net tangential flow velocity, net head and efficiency.The paper studies the effects of impeller rounding on a combination of radial flow and mixed flow pumps as turbines using experimental data. The impeller rounding is seen to have positive impact on the overall efficiency in different operating regions with an improvement in the range of 1-3%. The behaviour of the two control variables have been elaborately studied in which it is found that the system loss coefficient has reduced drastically due to rounding effects, while the extent of changes to the exit relative flow direction seems to be limited in comparison. The reasons for changes to these control variables have been physically interpreted and attributed to the behaviour of the wake zone at the turbine inlet and circulation within the impeller control volume.The larger picture of impeller rounding has been discussed in comparison with performance prediction models in pumps as turbines. The possible limitations of the analytical model as well as the test setup are also presented. The paper concludes that the impeller rounding technique is very important for performance optimization and recommends its application on all pump as turbine projects. It also recommends the standardization of the rounding effects over wide range of pump shapes including axial pumps.     

Performance enhancements for GROMACS nonbonded interactions on BlueGene

Several improvements to the previously optimized GROMACS BlueGene inner loops that evaluate nonbonded interactions in molecular dynamics simulations are presented. The new improvements yielded an 11% decrease in running time for both PME and other kinds of GROMACS simulations that use nonbonded table look-ups. Some other GROMACS simulations will show a small gain.     

The performance measures and randomized optimization for an unreliable server M/G/1 vacation system

This paper examines an M^[x]/G/1 queueing system with a randomized vacation policy and at most J vacations. Whenever the system is empty, the server immediately takes a vacation. If there is at least one customer found waiting in the queue upon returning from a vacation, the server will be immediately activated for service. Otherwise, if no customers are waiting for service at the end of a vacation, the server either remains idle with probability p or leaves for another vacation with probability 1 − p. This pattern continues until the number of vacations taken reaches J. If the system is empty by the end of the Jth vacation, the server becomes idle in the system. Whenever one or more customers arrive at server idle state, the server immediately starts providing service for the arrivals. Assume that the server may meet an unpredictable breakdown according to a Poisson process and the repair time has a general distribution. For such a system, we derive the distributions of important system characteristics, such as system size distribution at a random epoch and at a departure epoch, system size distribution at busy period initiation epoch, the distributions of idle period, busy period, etc. Finally, a cost model is developed to determine the joint suitable parameters (p^∗, J^∗) at a minimum cost, and some numerical examples are presented for illustrative purpose.