A Heuristic with Bounded Guarantee to Compute Diverse Paths under Shared Protection in WDM Mesh Networks

Establishing a fault-tolerant connection in a network involves computation of diverse working and protection paths. The Shared Risk Link Group (SRLG) [1] 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.

Vanishing of Ext and Tor over complete intersections

Let (R,m) be a local complete intersection, that is, a local ring whose m-adic completion is the quotient of a complete regular local ring by a regular sequence. Let M and N be finitely generated R-modules. This dissertation concerns the vanishing of Tor(M, N) and Ext(M, N). In this context, M satisfies Serre's condition (S_{n}) if and only if M is an nth syzygy. The complexity of M is the least nonnegative integer r such that the nth Betti number of M is bounded by a polynomial of degree r-1 for all sufficiently large n. We use this notion of Serre's condition and complexity to study the vanishing of Tor_{i}(M, N). In particular, building on results of C. Huneke, D. Jorgensen and R. Wiegand [32], and H. Dao [21], we obtain new results showing that good depth properties on the R-modules M, N and MtensorN force the vanishing of Tor_{i}(M, N) for all i>0. We give examples showing that our results are sharp. We also show that if R is a one-dimensional domain and M and MtensorHom(M,R) are torsion-free, then M is free if and only if M has complexity at most one. If R is a hypersurface and Ext^{i}(M, N) has finite length for all i>>0, then the Herbrand difference [18] is defined as length(Ext^{2n}(M, N))-(Ext^{2n-1}(M, N)) for some (equivalently, every) sufficiently large integer n. In joint work with Hailong Dao, we generalize and study the Herbrand difference. Using the Grothendieck group of finitely generated R-modules, we also examined the number of consecutive vanishing of Ext^{i}(M, N) needed to ensure that Ext^{i}(M, N) = 0 for all i>>0. Our results recover and improve on most of the known bounds in the literature, especially when R has dimension two.

Class Notes for Math 918: Cohen Macaulay Modules, Instructor Roger Wiegand

Topics covered are: Cohen Macaulay modules, zero-dimensional rings, one-dimensional rings, hypersurfaces of finite Cohen-Macaulay type, complete and henselian rings, Krull-Remak-Schmidt, Canonical modules and duality, AR sequences and quivers, two-dimensional rings, ascent and descent of finite Cohen Macaulay type, bounded Cohen Macaulay type.