Algorithms for telecommunications: class #8

## Topics

Load, chromatic number & RWA (routing on wavelenghts assigment)
WDM optical networks (Wavelength Division Multiplexing)

## Articles

• A. Schrijver, P. Seymour, P. Winkler, The ring loading problem, SIAM Review 41 (1999) 777-791. [pdf]
• J-C. Bermond, D. Coudert, and M-L. Yu. On DRC-Covering of K_n by Cycles.
Journal of Combinatorial Designs, 11(2):100-112, 2003. [pdf]
Completely solve the load problem for all-to-all set of requests on undirected and directed cycles.
• B. Beauquier, J.-C. Bermond, L. Gargano, P. Hell, S. Perennes and U. Vaccaro.
Graph problems arising from Wavelength-Routing in All-Optical Networks.
In Proc. Conference WOCS97, Geneva, April 1997, 1997. [pdf] [other version].
Survey results on the relation between the load and the chromatic number.
• B. Beauquier, P. Hell, and S. PĂ©rennes. Optimal Wavelength-routed Multicasting.
DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 84(1-3), May 1998. [pdf] [Report]
Proof that the load equals the chromatic number for one-to-all and one-to-many sets of requests in any WDM network
• B. Beauquier. All-To-All Communication in some Wavelength-Routed All-Optical Networks.
Networks, 33(3):179—187, May 1999. [pdf]
Consider all-to-all set of requests in some particular classes of WDM networks.

## The model

Circuit switch networks: PSTN, ATM, SONET/SDM, WDM.

• $G = (V, E)$is the network; can be undirected or directed symmetric.
• $P(x, y)$is a path from x to y in G
• I is an instance: set of requests, usually represented on a matrix $n \times n$ where $A_{ij}$represents the number of circuits that need to be set up between nodes i and j (can be the same path for all, or not).
• $\Pi(G, I, \mathbb{P}, e)$is the load (number of paths) on edge e for the network G, the instance I, and the set of paths $\mathbb{P}$that satisfy I.
• $\Pi(G, I, \mathbb{P}) = \max_{e \in E} \Pi(G, I, \mathbb{P}, e)$ is the load of a routing.
• $\Pi(G, I) = \min_{e \in E} \Pi(G, I, \mathbb{P}, e)$is the load of the network.

Example:

(1)
\begin{eqnarray} V &=& \{0, 1, 2, 3\} \\ E &=& \{(0, 1), (1, 2), (2, 3), (3, 0)\} \\ I &=& \{(0, 2), (1, 3)\} \\ \mathbb{P} &=& \{(0, 1, 2), (1, 2, 3)\} \\ \end{eqnarray}

Then:

(2)
\begin{eqnarray} \Pi(G, I, \mathbb{P}, \{0, 1\}) &=& 1 \\ \Pi(G, I, \mathbb{P}, \{1, 2\}) &=& 2 \\ \Pi(G, I, \mathbb{P}, \{2, 3\}) &=& 1 \\ \Pi(G, I, \mathbb{P}, \{3, 0\}) &=& 0 \\ \end{eqnarray}

If we use a directed graph, we have to find paths for both directions of each circuit:

(3)
\begin{eqnarray} V &=& \{0, 1, 2, 3\} \\ E &=& \{(0, 1), (1, 2), (2, 3), (3, 0), \\ & & (1, 0), (2, 1), (3, 2), (0, 3)\} \\ I &=& \{(0, 2), (1, 3), (2, 0), (3, 1)\} \\ \mathbb{P} & = & \{(0, 1, 2), (1, 2, 3), (2, 3, 0), (3, 0, 1)\} \\ \end{eqnarray}

The load on (2, 3) is 2. This can be improved:

(4)
\begin{align} \mathbb{P} = \{(0, 1, 2), (1, 0, 3), (2, 3, 0), (3, 2, 1)\} \end{align}
(5)
\begin{align} \Rightarrow \forall e \in E, \Pi(G, I, \mathbb{P}, e) = 1 \end{align}

## Some predefined routings

• OTA = one to all; one request from x_0 to all other nodes (a broadcast).
• ATA = all to all; one request between each pair of nodes (a gossip).
• OTM = one to many; $x_0 \rightarrow Y \subseteq V$

(some exercises on linear and circular configurations)

## Lower bound (on the circle)

Each path of length d, adds one unit of load to each edge: d units.
In a circly there is n pairs of distance $1, 2, \dots \lfloor \frac n 2 \rfloor$.
If the number of nodes is odd: in total $n \frac {n^2 - 1} 8$, so the lower bound is to have all of the edges with the same load: $\frac {n^2 - 1} 8$

For even number of nodes, there is only $\frac n 2$ paths of length $\frac n 2$, the lower bound would be: $\frac {n^2} 8$

## Upper bound

For this same problem, the upper bound on a optimal routing is defined only by how we choose the paths of length $\frac n 2$ (in the odd nodes case, there's no choice to make). And its $\lceil \frac {n^2 + 4} 8 \rceil$.

## Excercise

Calculate $\Pi(C^*_n, ATA)$ (directed circle).