\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial11}{Solutions for Tutorial 11}{December 12, 1996}

\section {Network Routing}

We first compute the expected traffic on any given edge. Consider
first the case of a horizontal edge $e$. Suppose $e$ is the $j$th edge
from the left on its row. The only nodes that can possibly send
packets through $e$ are the ones that lie on the same row. So let $i$
be any node on $e$'s row, and define the indicator $T_i$ as follows:\\

$$T_i =\begin{cases} 
   1\,\,  \text{if call $i$ gets routed thru $e$},\\ 
   0 \,\, \text{otherwise}.
  \end{cases}$$

Then the total number of packets sent through $e$ at any given time
is:\\

$$ T_e = \sum_{i \,\text{on $e$`s row}} T_i$$

The expected traffic $E[T_e]$ across $e$ at any given time is then, by
linearity of expectations, given by:\\

\begin{align*}
E[T_e] &= E[\sum_{i \,\text{on $e$`s row}} T_i]\\
&= \sum_{i \,\text{on $e$`s row}} E[T_i]\\
&= \sum_{i \,\text{on $e$`s row}} \Pr(T_i = 1)\\
&= \sum_{i \, \text{left of $e$}} \Pr(T_i = 1) + \sum_{i \, \text{right of $e$}} \Pr(T_i = 1)
\end{align*}

For any node $i$ to the left of $e$, there are $(100-j)\cdot 100$ out
of $10000$ destinations that would require passage through $e$. There
are $j$ such nodes.  Similarly, for any node $i$ to the right of $e$,
there are $j\cdot 100$ out of $10000$ destinations that would require
passage through $e$. There are $100-j$ such nodes. Hence we have
that:\\

\begin{align*}
E[T_e] &= \frac{j\cdot(100-j)}{100} + \frac{(100-j)\cdot j}{100}\\
&= \frac{j\cdot (100-j)}{50}
\end{align*}

The analysis for a vertical edge is similar. We now compute the
proability of an overload of a particular edge $e$ at a particular
time using Chernoff's bound. The capacity of $e$ will be $c_e \cdot
E[T_e]$, where $c_e$ is a constant yet to be determined.\\

$$ \Pr(T_e \geq c_e \cdot E[T_e]) \leq e^{-\alpha_e \cdot c_e \cdot E[T_e]}$$

  The probability that some edge gets overloaded at any given time can
  be bounded above using Boole's theorem as follows. Denote this
  probability by $P_O$. Then we have that:\\

$$P_O \leq \sum_e \Pr(T_e \geq c_e \cdot E[T_e])$$

The probability that no edge gets overloaded at a given time, then, is
simply $1-P_O$. Finally, we want the probability that no edge gets
overloaded over a period of 10 years to be at at least 99\%, so we
have that:\\ 

$$(1-P_O)^{3.1536 \cdot 10^8} \geq 99 \%$$
$$ \Downarrow$$
$$P_O \leq 1 - (99/100)^{1/3.1536\cdot 10^8}$$


This inequality can be solved for $P_O$ using, for example, matlab, or
an advanced calculator, to obtain the answer $P_O \leq 3.2 \cdot
10^{-11}$. We now need to find the bandwidth of each particular edge.
A quick and dirty approach is to use $50e < 136$ capacity on each
edge. In this case, we have that\\

\begin{align*}
P_O &\leq \sum_e e^{-\alpha_e \cdot 50 e}\\
&\leq \sum_e e^{-50}\\
&\leq 19800 \cdot e^{-50}\\
&\approx 3.8 \cdot 10^{-18}
\end{align*}

Since $ 3.8 \cdot 10^{-18} \le 3.2 \cdot 10^{-11}$, this particular
assignment of capacities works fine. This estimate is rather crude,
however, as it does not take into account the fact that some edges
will need more capacity than others. So let's try to do better.\\

Let's divide the probability $P_O$ evenly between the $2\cdot100\cdot
99 = 19800$ edges (this is a simplifying assumption, and hence our
solution is still not necessarily optimal). So we have that for any
edge $e$,\\ 

\begin{align*}
\Pr(T_e \geq c_e \cdot E[T_e]) &\leq \frac {3.2 \cdot 10^{-11}}{19800}\\
& \leq 1.6 \cdot 10^{-15}
\end{align*}

We know that $e^{-\alpha_e \cdot c_e \cdot E[T_e]}$ is an upper bound
on the probability of overload on any given edge. So we can just
choose $c_e$ large enough such that this bound is less than $1.6 \cdot
10^{-15}$, and we are done. We first compute $E[T_e]$ as shown above.
We must then solve the following inequality for $c_e$ (notice that
$\alpha_e$ is a function of $c_e$).\\ 

$$e^{-\alpha_e \cdot c_e} \leq \frac{1.6 \cdot 10^{-15}}{E[T_e]}$$

The bandwidth of $e$ is then $c_e\cdot E[T_e]$. We will not solve this
inequality here. To those of you who want to give your HP some
exercise: feel free.

\end{document}

