A linear programming duality approach to analyzing strictly nonblocking d-ary multilog networks under general crosstalk constraints

When a switching network topology is used for constructing optical cross-connects, as in the circuit switching case, no two routes are allowed to share a link. However, if two routes share too many switching elements, then crosstalk introduced at those switching elements degrades signal quality. Vaez and Lea (IEEE Trans. Commun. 48:(2)316–323, 2000) introduced a parameter c which is the maximum number of distinct switching elements a route can share with other routes in the network. This is called the general crosstalk constraint. This paper presents a new method of analyzing strictly nonblocking multi-log networks under this general crosstalk constraint using linear programming duality. We improve known results on several fronts: (a) our sufficient conditions are better than known sufficient conditions for log d (N,0,m) to be strictly nonblocking under general crosstalk constraints, (b) our results are on d-ary multi-log networks while known results are on binary networks, and (c) for several ranges of the parameter c, we give the first known necessary conditions for this problem which also match our sufficient conditions from the LP-duality approach. One important advantage of the LP-duality approach is the ease and brevity of sufficiency proofs. All one has to do is to verify that a solution is indeed dual-feasible and the dual-objective value automatically gives us a sufficient condition. Earlier works on this problem relied on combinatorial arguments which are quite intricate and somewhat error-prone.