%% 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}
\usepackage[latin1]{inputenc}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}

\makeatletter


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

\makeatletter


\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

\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. Earlier problems tend to be easier.}

\textbf{1.} (10) Fill in the blank with a protocol from our course: When you
access the Internet from home using a PC, the transfer of frames along the phone
connection uses \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

\textbf{2.} (10) In the numerical example of Stop and Wait on p.277 of Leon-Garcia,
find the value of \( \alpha  \) (the \( \alpha  \) used in our printed lecture
notes on Stop and Wait, Go Back N, etc.) Do \textbf{not} use a calculator to
evaluate this number; merely leave it as a numerical expression which could
be evaluated by anyone with a calculator, e.g. (290.5-37.2)/16.28.

\textbf{3.} Answer these questions about StopAndWait.java.

\begin{itemize}
\item [(a)] (15) Fill in the blanks: In the function DoArrivalBackToA(), when we call
JSCancel(), an object/instance of class \_\_\_\_\_\_\_\_\_ (if there is any
subclassing involved, write the subclass here instead of the base class) will
be deleted from the \_\_\_\_\_\_\_\_\_\_\_. 
\item [(b)] (10) Suppose we wished to impose the condition {}``Three strikes and you're
out!{}'', meaning that if a message is received incorrectly at B three times,
we simply give up sending it, and just go on to sending the next message instead.
Show how to modify the code to do this (Warning: If you have more than, say,
four lines of code here, you are probably doing it wrong.) 
\end{itemize}
\textbf{4.} Consider the CRC divisor C = 111. In each of the following classes
of errors, answer either WDA (will detect all such Es), WDS (will detect some
such Es) or WDN (will detect no such Es). In part (c) (but not parts (a) and
(b)), give your full reasoning for your answer.

\begin{itemize}
\item [(a)] (10) Burst errors of length 2. 
\item [(b)] (10) Burst errors of length \( \geq 3 \). 
\item [(c)] (15) Triple errors spaced two positions apart (e.g. E = 00101010000). 
\end{itemize}
\textbf{5.} Consider the Internet checksum presented in Sec. 3.8.3 of Leon-Garcia.

\begin{itemize}
\item [(a)] (5) The C function in Fig. 3.54 is meant to be used on the sender side.
Write another function, whose first line is


\begin{verbatim}

int rcvcksum(unsigned short *addr, int count)
\end{verbatim}

This function will look at \textbf{count} bytes, starting with the one pointed
to by \textbf{addr}, and return either -1 or +1, indicating either an error
or no error, respectively. (Note: The value \textbf{count} includes the checksum
field.)

Your function is required to call cksum().

\item [(b)] (5) Look at the 2-bit, L = 2 example. Let us borrow the E notation from
our discussion of CRC, so that an E vector represents a possible pattern of
bit errors, where 1 means error, 0 means OK. Remember, the checksum field is
included. What is the total number of invalid codewords?
\end{itemize}
\textbf{6.} (10) Consider the setting of Section 2.2.1 of the unit in the printed
lecture notes titled {}``Utilization Analysis of Point-to-Point and Multidrop
Links.{}'' Find the long-run proportion of frames which get successfully transmitted
on the first try, expressed in terms of \( \alpha , \) p and the \( \pi _{i} \).
(The \( \pi _{i} \) are themselves functions of \( \alpha  \) and p, but do
\textbf{not} make those substitutions; the \( \pi _{i} \) must appear in your
answer.)

\textbf{Solutions:}

\textbf{1.} Point-to-Point Protocol

\textbf{2.} Transmit time = \( \frac{1000\textrm{ bits}}{1500\textrm{ bits}/\textrm{ms}} \)\( =\frac{2}{3} \). 

40 = \( 2\times \textrm{latency}+\frac{2}{3} \), so latency = \( \frac{40-\frac{2}{3}}{2} \).

\( \alpha =\frac{\textrm{latency}}{\textrm{transmit time}}=\frac{0.5(40-\frac{2}{3})}{\frac{2}{3}} \)

\textbf{3.(a)} TimeoutElt, event list

\textbf{3.(b)} The main point is that in DoArrivalBackToA(), when one checks
the Trashed member of the frame and finds that the frame has been corrupted,
we must then check the NTries member. If it is \( \geq  \) 3, then we call
SendFrame() with the argument \textbf{true}, relfecting the fact that we have
discarded the old frame and are now sending a new one.

\textbf{4.(a)} Since c = 3, all burst errors of length \( \leq  \) 2 will be
caught, from the finding in our printed lecture notes. So the answer here is
WDA.

\textbf{4.(b)} Look first at burst errors of length 3, i.e. E(x) = \( x^{k}(x^{2}+1+1) \).
C(x) divides that, so burst errors of length 3 won't be caught.

What about burst errors of length 4? Then E(x) = \( x^{k}(x^{3}+x^{2}+x+1) \).
Suppose C(x) were to divide E(x). Since x is not a factor of C(x), and since
the prime factors of \( x^{k} \) are all x, that must mean that all prime factors
of C(x) are prime factors of E(x), i.e. C(x) divides E(x). So, we would have
\( x^{3}+x^{2}+x+1=(x^{2}+x+1)h(x) \) for some h(x). The latter would have
to have degree 1, i.e. be of the form ax+b. In order to generate an \( x^{3} \)
term on the left hand side of the equation, we would need a = 1, and in order
to generate a 1 we would need b = 1. Then h(x) = x+1. But this h(x) doesn't
work after all, since the total x term from the right-hand side would be 2x,
which is 0. So, no such h(x) exists, and so burst errors of length 4 are caught
after all.

So, the answer here is WDS.

\textbf{4.(c)} Use the same approach as in 4(b) above. The polynomial h(x) here
would have to be of degree 2, so h(x) = \( ax^{2}+bx+c \). Multiplying everything
out, we find that a=1, b=1 and c=1 works. So the answer here is WDN.

\textbf{5.(a)} Simply call cksum() on the whole message, including the cksum
field, and test whether we get 0. If we do, we report that there is no error.

\textbf{5.(b) }

There are 4 bits in the message, and 2 in the checksum, for a total of 6. Thus
there are \( 2^{6}=64 \) possible codewords, 16 of which are valid (the ones
listed in the table). Thus there are 48 invalid codewords.

\textbf{6.} If assumes that a new frame is sent only after an old one is ACKed,
then a new frame will be sent out only during (some) periods in which we are
in state \( 2\alpha  \). In this case, there are \( 2\alpha  \) frames in
progress ahead of the new one, and the new one will succeed on its first try
if and only if all the frame ahead of it, plus the new frame itself, are error-free.
So, under this assumption, the answer is \( (1-p)^{2\alpha +1} \).

If on the other hand, the sender mixes new and old frames, and could send a
new one at any time, then \( \pi _{i} \) is the probability that when a new
frame is sent, the system is in state i. Accordingly, the proportion of all
new frames which succeed on the first try is \( \sum _{i=0}^{2\alpha }\pi _{i}(1-p)^{i+1} \).
\end{document}