%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[twocolumn]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage[T1]{fontenc}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}

\makeatletter


\usepackage[T1]{fontenc}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}

\makeatletter


\setlength{\oddsidemargin}{-0.5in}
\setlength{\evensidemargin}{-0.5in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textwidth}{7.0in}
\setlength{\textheight}{9.5in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}
\setlength{\columnseprule}{0.4pt}

\makeatother

\makeatother


\makeatother

\begin{document}

Name: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

\textbf{Directions: Work only on this sheet (on both sides, if needed); do not
turn in any supplementary sheets of paper. There is actually plenty of room
for your answers, as long as you organize yourself BEFORE starting writing.
In order to get full credit, SHOW YOUR WORK.}

\textbf{1.} (10) Fill in the blank with a single word: The {}``listen before
talk{}'' feature of CSMA would have been infeasible in the environment in which
ALOHA was developed, due to the \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
in that location.

\textbf{2.} (10) Consider the worked-out CRC example from our printed lecture
notes. State what the CRC field would be if C were 1101 instead of 1011.

\textbf{3.} Look at p.185 of Tanenbaum.

\begin{itemize}
\item (a) (5) It states the the Hamming distance for the code system as a whole is
5. State (any) two of the codes which are a distance 5 apart from each other. 
\item (b) (10) Are there any triple errors which this code system will correct properly?
If so, give a specific example; if not, state clearly why not. 
\end{itemize}
\textbf{4.} (10) Consider a p-persistent CSMA protocol running on a network
of n nodes. Suppose the value of p is settable by the network administrator.
Which of the following situations would be the most likely candidate for setting
a high value of p? (i) Small n, low traffic per node. (ii) Large n, low traffic
per node. (iii) Small n, high traffic per node. (iv) Large n, high traffic per
node.

\textbf{5.} (5) According to Tanenbaum, which kind of method of interconnecting
two LANs on p.4 of the Introduction unit in our printed lecture notes is more
common---the one involving mars.xyz.com or the one involving citroen.abc.org
and moo.edu? Cite a specific sentence in our reading in Tanenbaum assigned for
this exam.

\textbf{6.} (10) Say we have a given bit string which, if sent repeatedly, would
have a certain Fourier series, with a certain value of M in Equation (13) in
our printed lecture notes on the Physical Layer. Now consider sending the same
string repeatedly under CDMA, using 8-bit codes. Which of the following would
be the likely outcome? (i) M would increase. (ii) M would decrease. (iii) M
would be multiplied by 8. (iv) M would be multiplied by \( log_{2}8=3 \). (v)
None of the above.

\textbf{7.} (5) Say in a particular application we will send 1000 IP packets,
and we will use either a SLIP or PPP connection to send them. Assume no errors
or byte-stuffing. Fill in the first and third blanks with {}``SLIP{}'' or
{}``PPP,{}'' and the second blank with a specific number: A \_\_\_\_\_\_\_\_\_\_\_\_\_
connection would use a total of \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ more bytes
of overhead than would \_\_\_\_\_\_\_\_\_\_\_\_\_\_.

\textbf{8.} (5) Consider slotted ALOHA. Suppose we have best-case throughput.
If I have a frame to send now, what is the probability that the frame will be
involved in a collision in its first try, and then gets through on the second
try?

\textbf{9.} Consider the Stop and Wait protocol, and suppose that if the sender
does not receive an ACK within \( \beta  \) time of sending out the first bit
of the frame onto the line, the sender will send the frame again.

\begin{itemize}
\item (a) (10) Fill in the blank with an expression involving \( \alpha  \): In order
for this proposal to make any sense, \( \beta  \) must be greater than \_\_\_\_\_\_\_\_\_\_\_\_\_\_. 
\item (b) (10) Suppose the probability of an ACK being lost is q (and there are no
other errors). Find the value of the utilization u. 
\end{itemize}
\textbf{10.} (10) Consider the {}``coin flipping{}'' version of CDMA, with
G = 3. Suppose we have only two nodes sending, named I and II, and we know node
I uses the code (1,-1,1). We are hoping to receive from node I. Say that node
I sends the data bit 1, and node II also sends the data bit 1. What is the probability
that we correctly identify node I's datum to be a 1? Assume we will guess the
transmitted datum to be a 1 if the received signal is strictly greater than
0.

\textbf{Solutions:}

\textbf{1.} Mountains.

\textbf{2.} 100.

\textbf{3a.} Any two of the five will work.

\textbf{3b.} For example, 1000000011 is a distance 3 away from 0000000000, but
4 away from 0000011111, etc. So if 0000000000 is corrupted to 1000000011, the
system will properly correct it to 0000000000.

\textbf{4.} (i).

\textbf{5.} Page 229, {}``...msot of the wide area infrastructure...{}''

\textbf{6.} (i); see the remark about \textbf{spread spectrum} in the discussion
of CDMA in our printed lecture notes.

\textbf{7.} PPP will have as much as 10,000 more bytes of overhead than SLIP.

\textbf{8.} \( (1-e^{-1})e^{-1} \); see p. 250.

\textbf{9a.} \( 1+2\alpha  \); we shouldn't have a timeout before the ACK even
has a chance to get back to us.

\textbf{9b.} On average it will take us 1/(1-q) attempts to get an ACK, each
of which will cost us \( \beta  \) amount of time, except for the last, which
will cost us only the usual \( 1+2\alpha  \) time. So our utilization is

\[
\frac{1}{(\frac{1}{1-q}-1)\beta +1+2\alpha }\]


\textbf{10.} Suppose node II uses the code (-1,1,-1). Then the total signal
received will be +3 from node I plus -3 from node II, for a total of 0, which
under the rules of the problem statement means the bit will be interpreted as
a 0 instead of as a 1. All other possible codes for II work OK here. Thus the
probability of correct reception is 7/8.

\end{document}