Algorithms for telecommunications: class #1

Jean-Claude BERMOND rf.airni.aihpos|dnomreb#rf.airni.aihpos|dnomreb

Classes for Friday 16 will be swapped with the course at Thursday 15 (morning).

Book: chapters 3, 4 & 7 from
Kleinberg, Tardos; Algorithm design; Pearson Addison-Wensley; 2005.
http://www.aw-bc.com/info/kleinberg/

Topics:

• Level test on graphs, complexity, and linear programming
• Description of problem from article 1.

# Satellites problem

Problem brought by Alcatel Space Industries

• n inputs
• n + k outputs (at most k failures)
• n inputs => any n valid outputs: disjoint paths
• Needs to minimize the number of switches: $\textbb N(n, k)$

Originally they couldn't tell if a given solution was valid, but they found a way of constructing valid solutions starting with small networks and growing them by replication.

## Description of the solution

If a switch is connected to two inputs and there's an amplifier, it cannot stand even one failure. Then there's two outputs: in that case, the switch can be just removed.

Lemma 5. If $k \geq 1$ in any minimum valid network, no switch is connected to 2 or more inputs.

For k up to 2, the network proposed is the one shown in Figure 4 and is easily shown that it is valid.

Theorem: If $k = 1 \lor k = 2 \Rightarrow \textbb{N}(n, k) = n$

Other cases are constructed recursively like shown in Figure 6.
With k even, if $G(n, k)$ is a valid network with N switches, and $G'(n', k)$ is a valid network with N' switches, then the constructed graph $H(n+n', k)$ is a valid network with $\textbb N + \textbb{N'}$ switches.

For odd values, the approach is to take one output out of the even case, but it is not proven to be optimal.

For proving that the network is valid, first look at the case where the k failings are evenly split in the two original networks. We can assume that the merged links are $\frac k 2$ outputs failing, so each side has $\frac k 2 + \frac k 2 = k$ failures and the original networks could sustain k failures.

For the uneven case, the side with more than $\frac k 2$ failures, it is solved as if the links weren't there, and then those are routed to the other side, as if the original outputs on that side had failed.

For all this to work, the original networks need to have $\frac k 2$ type I2 switches.

page revision: 5, last edited: 15 Oct 2009 07:35
Unclear, need to ask the teachers, since most is obviously derived works.