\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}

\begin{document}

{\bf Tutorial 13 solutions.}

\date{}
\bigskip

\begin{enumerate}
\item 
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 = \left\{ \begin{array}{ll} 1 & \mbox{ if call $i$ gets routed thru $e$},\\ 
       0 & \mbox{ otherwise}.
  \end{array} \right.$$

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

$$ T_e = \sum_{i \,\mbox{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{eqnarray*}
E[T_e] &=& E[\sum_{i \,\mbox{on $e$`s row}} T_i]\\
&=& \sum_{i \,\mbox{on $e$`s row}} E[T_i]\\
&=& \sum_{i \,\mbox{on $e$`s row}} \Pr(T_i = 1)\\
&=& \sum_{i \, \mbox{left of $e$}} \Pr(T_i = 1) + \sum_{i \, \mbox{right of $e$}} \Pr(T_i = 1)
\end{eqnarray*}

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{eqnarray*}
E[T_e] &=& \frac{j\cdot(100-j)}{100} + \frac{(100-j)\cdot j}{100}\\
&=& \frac{j\cdot (100-j)}{50}
\end{eqnarray*}

The analysis for a vertical edge is similar. 
Note that for any edge $E[T_e] \leq 50$.

  
\item 
Let $P$ be the overall
failure probability in 10 years. Then, $P$ can be bounded as follows:
$$P \leq \sum_{i=1}^N Pr(\mbox{network fails in the }i^{th} \mbox{ second})$$
Where $N= 315360000$ is the number of seconds in 10 years.
Hence 
$$P \leq 315360000 P_f$$
where $P_f$ is the failure probability during a single second.
Since we need $P  = 0.01$, 
$$P_f = 3.17 \times 10^{-11} \leq {0.01 \over 315360000}$$
is sufficiently small.
 
\item Next we compute the
probability of overload of a particular edge $e$ in a particular
second using Chernoff's bound. The capacity of $e$ will be 136.  Chernoff's bound tells us:\\
$$ Pr(T_e \geq c_e \cdot E[T_e]) \leq e^{-\alpha_e c_e E[T_e]}$$

Define $c_e$ so that $c_e E[T_e]=136$ is the capacity on edge $e$.  Since $E[T_e] \leq 50$, this means that $c_e \geq {\bf e}$ for all edges $e$ (where ${\bf e}$ denotes the base of the natural logarithm).  For $c_e \geq {\bf e}$, $\alpha_e = \ln c_e + \frac{1}{c_e}-1 \geq \ln {\bf e} + \frac{1}{\bf e} - 1 = \frac{1}{\bf e}$ since $\alpha_e$ is an increasing function of $c_e$.

Thus,

\begin{eqnarray*}
P_r(T_e \geq 136) &\leq& {\bf e}^{- \alpha_e136}\\
&\leq& {\bf e}^{- \frac{136}{\bf e}}\\
&\leq& {\bf e}^{-50}
\end{eqnarray*}

Then, using Boole's inequality, we deduce

\begin{eqnarray*}
P_f &\leq& \sum_e P_r(T_e \geq 136)\\ 
&\leq& \sum_e {\bf e}^{-50}\\
&\leq& 19800 \cdot {\bf e}^{-50}\\
&\approx& 3.8 \cdot 10^{-18}
\end{eqnarray*}

In fact, our probability of failing in ten years is less than 1 in 100 million.
Since $ 3.8 \cdot 10^{-18} \le 3.17 \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
do not need as much capacity as others. So let's try to do better.\\

\item 
Let's divide the probability $P_f$ 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 will want that for any
edge $e$,\\ 

\begin{eqnarray*}
\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{eqnarray*}

We know that ${\bf 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, i.e.,
$E[T_e] = {j(100-j) \over 50}$. 
We then solve the following inequality for $c_e$ (notice that
$\alpha_e$ is a function of $c_e$).\\ 
$${\bf e}^{-\alpha_e \cdot c_e E[T_e]} \leq 1.6 \cdot 10^{-15}$$
Or 
$$ c_e\ln c_e + 1 - c_e \geq {34.07 \over E[T_e]}$$
The bandwidth of $e$ is then $c_e\cdot E[T_e]$. We will not solve this
inequality in general here, but here are some sample values that suffice:
\begin{eqnarray*}
j = 50 &  E[T_e] = 50 & c_e E[T_e] \geq 120    \\
j = 25 &  E[T_e] = {25 \cdot 75 \over 50} = 37.5  & c_e E[T_e] \geq 99 \\
j= 1 &  E[T_e] = {1 \cdot 99 \over 50} = 1.98  & c_e E[T_e] \geq 24 
\end{eqnarray*}
 
\end{enumerate}

\end{document}



