\documentstyle[class,11pt]{article}
\def\ClassName{Computer~Organization}
\def\ClassNumber{CS~333}
\handedout{(12/6/95) Handout \#19}
\vspace{0.5in}

\begin{document}
\begin{center}
{\large \bf Solutions to Homework \#8} \\
\end{center}

{\bf Introduction:} This assignment focuses on interconnection
networks.  Before starting the homework, you should
have read Sections 7.4 and 7.5 in the textbook.

\begin{center}
{\bf Solutions}
\end{center}

\begin{problems}
\problem \Points{10}
{\bf Huge Data Transfers} -- H\&P Exercise 7.3

{\bf Solution:}
(a)
The transfer time for the overnight service is 15 hours.
The transfer rate could be really huge.  (A couple of 747's
full of 100GB tapes !!!) so we cannot really calculate
the transfer bandwidth.

The transfer times for the two links are:
$$
Transfer\ Time = {800*2^{30} \ bits \over
	50\%*(1.5*2^{20}) \ bits/second}
	= 1.1 * 10^6 \ seconds
$$
$$
Transfer\ Time = {800*2^{30} \ bits \over
	50\%*(10*2^{20}) \ bits/second}
	= 1.6 * 10^5 \ seconds
$$
Clearly, the overnight service is faster.

Here, each GigaByte has $2^{30}$ bytes, and not $10^9$ bytes.

(b)
The transfer rate for the general case of overnight delivery
is infinite for all practical purposes as explained above.

For the specific case of 100 GB in 15 hours, we get:
$$
Transfer\ Rate = {800*2^{30} \ bits \over
        54 * 10^3 \ seconds}
        = 15.9 * 10^6 \ bits/seconds
$$
That's about 16 Mbits/sec which is faster than both cases above.

\problem \Points{10}
{\bf Interconnection Latency} -- H\&P Exercise 7.9

{\bf Solution:}
We assume there is no other network traffic.

The best and worst case for the Cross-bar switch is 1 time unit;
for the Omega switch is 3 time units, for both (P0,P6) and
(P1,P7).

For the Fat Tree, we assume switches of 4 downward and 2 upward
connections.  Thus we have 8 processors connected to 4 switches
at the first level as in Fig.7.14, and the 4 switches connected
to two more at the next level to make full
use of the switches.  Since we are asked to assume the Fat Tree
picks a path randomly, the best case for (P0,P6) is to pass through
3 switches, for a latency of 3 time units; and similarly, (P1,P7)
also gives us 3 time units.  If we take the worst case we can
go back and forth between the upper two levels of switches
through 7 switches for (P0,P6), leaving 3 time units for (P1,P7).

\begin{center}
\begin{tabular}{|l|c|c|}
\hline
Type		&(P0,P6)	&(P1,P7)	\\
\hline
Cross Bar	&1		&1	\\
Omega	&3		&3	\\
FatTree - Best Case	&3		&3	\\
FatTree - Worst Case	&7		&3	\\
\ \ \ \ - or Worst Case	&7		&7	\\
\hline
\end{tabular}
\end{center}

The last case is if you assumed the two communications were
not simultaneous.

Your solution may differ if you designed the Fat Tree for
different capacity switches.

\problem \Points{10}
{\bf Interconnection Latency and Bandwidth} -- H\&P Exercise 7.10

{\bf Solution:}
As posted on the newsgroup the ATM peak is 78 Mbps.
Half of this is 37 Mbps.  Drawing a horizontal line at
this point in the graph of Fig. 7.37, we get a packet
size of about 3300 (this is inexact and can vary by
about 100).  

Since the measurements of the graph were made for 5000
packets, the message size (i.e. $n_{1/2}$) is $5000*3300=16.5*10^6\ bytes$.
But the previous answer is fine too.

For the ethernet, we have a peak of 9 Mbps.  But the
ethernet line in Fig. 7.37 does not show us the point
at which ethernet bandwidth drops to 4.5 Mbps.  Therefore
we cannot calculate this valus, since it could be either
more than 7936 bytes/packet, or less than 256 bytes/packet,
or both.
It is likely to be in the lower range since the overhead for
messages will become significant for smaller messages, thereby
pushing down the useful bandwidth.
\end{problems}

\end{document}