We develop traffic grooming algorithms for WDM networks with multi-layer switches. We consider a node as an N-layer switch, in which a given layer k is an aggregated set of elements of layer k-1. Typical examples of layers are wavelengths, bands and fibers. The cost of a given node depends on the number of input and output ports of each layer. Assuming this model and a traffic matrix - with unity elements in layer 0 - minimizing the cost of the network consists of grooming traffic in such a way that as much traffic as possible is switched in the highest possible layer (fibers in our example). When some traffic is switched along a path in the network within the same layer, we represent it with a pipe. Each pipe has an associated linear cost depending on the current layer and on the number of nodes crossed in that pipe. In the case of a two layers model the problem was considered in Gerstel et al. (2000) for rings or in Cinker et al. (2000) for general topologies. We present an integer linear programming formulation for this model that aims to minimize the overall cost of the network for a given input traffic matrix. We ran experiments using the CPLEX optimization package on various topologies such as actual networks like the Pan-European all optical network (Batchelor et al. (1999)) as well as rings and meshes of various sizes.

Given a graph G = (V, E), we define e(X), the mean eccentricity of a vertex X, as the average distance from X to all the other vertices of the graph. The computation of this parameter appears to be nontrivial in the case of the de Bruijn networks. In this paper, we consider upper and lower bounds for e(X). For the directed de Bruijn network, we provide tight bounds as well as the extremal vertices which reach these bounds. These bounds are expressed as the diameter minus some constants. In the case of undirected networks, the computation turns out to be more difficult. We provide lower and upper bounds which differ from the diameter by some small constants. We conjecture that the vertices of the form a· · ·a have the largest mean eccentricity. Numerical computations indicate that the conjecture holds for binary de Bruijn networks with diameters up to 18. We also provide a simple recursive scheme for the computation of the asymptotic mean eccentricity of the vertices a· · ·a. Finally, we prove that the asymptotic difference, when the diameter goes to infinity, between the mean eccentricities of an arbitrary vertex and that of a· · ·a is smaller than a small constant tending to zero with the degree. A byproduct of our analysis is that in both directed and undirected de Bruijn networks most of the vertices are at distance near from the diameter and that all of the mean eccentricities (and therefore the average distance) tend to the diameter when the degree goes to infinity. © 1997 John Wiley & Sons, Inc. Networks 30:187–203, 1997

In this paper we present three broadcast algorithms and lower bounds on the three main components of the broadcast time for 2-dimensional torus networks (wrap-around meshes) that use synchronous circuit-switched routing. The first algorithm is based on a recursive tiling of a torus and is optimal in terms of both phases and intermediate switch settings when the start-up time to initiate message transmissions is the dominant cost. It is the first broadcast algorithm to match the lower bound of log/sub 5/ N on number of phases (where N is the number of nodes). The second and third algorithms are hybrids which combine circuit-switching with the pipelining and arc-disjoint spanning trees techniques that are commonly used to speed up store-and-forward routing. When the propagation time of messages through the network is significant, our hybrid algorithms achieve close to optimal performance in terms of phases, intermediate switch settings, and total transmission time. They are the first algorithms to achieve this performance in terms of all three parameters simultaneously.