Algorithms for telecommunications: class #8

Teacher: rf.airni.aihpos|treduoC.divaD#treduoC divaD

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]
    In this article, you will find the NP-completeness proof of the ring loading problem and approximation algorithms.
  • 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).

The ring loading problem

Partition problem: can we split a set of positive integers into two groups which have the same sum?

He showes (I didn't understand how) that the ring loading problem is equivalent to the partition problem, which is NP-complete. Here's a paper on this.

It has been proven that if the integers are either 0 or 1, the partition problem is in P, but if we include 2 the complexity is unknown.

For the OTA case, it can be converted into a flow problem graph (by adding links of capacity 1 to a sink) and solved in polynomial time.

Unclear, need to ask the teachers, since most is obviously derived works.