\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 step
$t$ in a can be bounded above using Boole's theorem as follows.
Denote this probability by $P_t$. Then we have that:\\ 

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

We can also use Boole's inequality to bound the probability that any
edge fails at any given time step in the 10 year period. denote this
probability by $P$. We have that:\\

$$P \leq \sum_{\text{10 years}}\sum_e\Pr(T_e \geq c_e \cdot E[T_e])$$

We want this probability to be less than 1\%. Now, there are $60\cdot
60 \cdot 24\cdot 365\cdot 10 < 3.2\cdot 10^{8}$ seconds in the 10 year
interval, and $19800$ edges. Hence if we can make the probability of
an edge failing in any given second less than $1/100 \cdot 1/19800
\cdot 1/{3.2 \cdot 10^8} \leq 1.6 \cdot 10^{-15}$, the requirements
will be satisfied.  So we need to assign bandwidths to each particular
edge such that this bound is satisfied.  A correct and very good
(!) approach is to use a $50e < 136$ capacity on each edge. In this
case, we have that\\ 

\begin{align*}
 \Pr(T_e \geq c_e \cdot E[T_e]) &= \Pr(T_e \geq 50e)\\
&\leq e^{-\alpha_e \cdot 50 e}\\
&\leq e^{-50}\\
&\leq  2 \cdot 10^{-22}
\end{align*}

Since $ 2 \cdot 10^{-22} \le 1.6 \cdot 10^{-15}$, this particular
assignment of capacities works fine .. in fact, with $50e$ capacity
edges, we will expect to be up to spec for a good $ \sim 10^7$ years. This
estimate might perhaps seem somewhat crude, however, as it does not
take into account the fact that some edges will need more capacity
than others. So we might be tempted to try to do better. We should not
get our hopes up too high, however. If we try a capacity $100$ link at
an edge with expectation 50, for example, then the probabiliy bound we
get from Chernoff is $4x10^{-9}$, which is not sufficient to last for
$10$ years with $99\%$ probability even for just a $9\%$ single edge.
Now, Chernoff's bound is just an upper bound so there is still a
chance capacity $100$ links will be up to spec, but we would have to
work harder to be able to decide for sure.  Note that better bounds
relative to the expectation would be possible if the expectation were
higher.
       
\end{document}

