%% 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,english]{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}
\usepackage{babel}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}

\makeatletter

\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}
\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.7in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.05in}
\setlength{\columnseprule}{0.2pt}

\makeatother

\makeatother

\makeatother


\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.}

Notation: {}``PLN{}'' means {}``printed lecture notes,{}'' and {}``LG{}''
means {}``Leon-Garcia.{}''

\textbf{1.} Answer the following questions about the Stop-and-Wait example in
the JSim package:

\begin{itemize}
\item (a) (10) Which variable in Main.java represents the latency of a frame? 
\item (b) (10) In this part we will consider what the event list might look like at
some time. Each of the following is a complete description of an event list,
in time order with the earliest event first. Next to each description, write
`P' if it is possible that such an event list could occur, or write `I' if it
is impossible:

\begin{itemize}
\item {}``arrive at B{}'', {}``timeout{}'' 
\item {}``arrive at B{}'', {}``done with delay{}'', {}``timeout{}'' 
\item {}``timeout{}'', {}``done with delay{}'' 
\item {}``done with delay{}'', {}``timeout{}'', {}``arrive at B{}'' 
\end{itemize}
\end{itemize}
\textbf{2.} (20) Fill in the blanks regarding the simulation program in Section
5 of our PLN unit on contention protocols: Traffic will be lighter if the command-line
argument (fill in with a variable name from the program) \_\_\_\_\_\_\_\_\_\_\_\_
is (fill in with {}``smaller{}'' or {}``larger{}'') \_\_\_\_\_\_\_\_\_\_\_\_\_\_.
If traffic is lighter, we should make the value of the command-line argument
(fill in with a variable name from the program) \_\_\_\_\_\_\_\_\_\_\_\_\_\_,
which serves as a kind of backoff parameter, (fill in with {}``smaller{}''
or {}``larger{}'') \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

\textbf{3.} (10) Consider the following compromise between slotted ALOHA and
ordinary ALOHA. Under slotted ALOHA, if our station has now produced a frame
to send, we must wait until the next integer time point. But under the compromise,
we wait only until the next time which is a multiple of 0.25. In other words,
any frame produced during the time \( (\frac{n}{4},\frac{n+1}{4}] \) will be
sent starting at time \( \frac{n+1}{4} \). Note that the interval is open on
the left but closed on the right; the corresponding interval \( (t_{0}-1,t_{0}) \)
above Equation (3) in our PLN should really be written that way too, i.e. as
\( (t_{0}-1,t_{0}] \). Transmission time is still 1.0 (you may find it easier
to think of as, say, 0.9999). What does Equation (3) change to under this new
protocol?

\textbf{4.} (5) In our Go-Back-N analysis in our PLN, we distinguished between
the two cases \( N\leq 2\alpha +1 \) and \( N>2\alpha +1 \). LG states that
the latter case is the typical and desirable one. Quote the sentence, with page
number, in which LG specifically says this.

\textbf{5.} (10) Review Sec. 5.1.1 in our PLN unit on point-to-point and multidrop
links, where the notion of peer relationships and primary/secondary relationships
is discussed. The setting we discussed for ALOHA in our PLN was that of a number
of secondary stations (terminals) accessing one primary station (a central computer).
By contrast, our discussions of Ethernet have been in the context of peer relationships.
The other difference, of course, is that in ALOHA a station only indirectly
infers that a collision has occurred (via noting the absence of an ACK), while
in Ethernet the station actively {}``listens{}'' for evidence of a collision.
LG gives an example which is a kind of hybrid between the two: The setting is
that of a primary/secondary relationship, but secondaries do actively listen
for evidence of a collision. State what this example is, citing a quote (with
page number) from LG regarding the {}``listen for collision{}'' activity by
the secondaries. Also, state the specific terms LG uses for the primary and
secondaries in this example.

\textbf{6.} In a CRC context, suppose E is a NON-detectable error vector, which
has at least one 0 and at least one 1. Either prove, or give a counterexample
to, the following statements:

\begin{itemize}
\item (a) (10) Let E' denote the result of changing some 0 in E to a 1. Then E' is
necessarily detectable.
\item (b) (5) Same as (a), but with a 1 in E replaced by a 0 to form E'.
\end{itemize}
\textbf{7.} (10) In the context of Eqn. (8), p.323 of LG, give the probability
that no packets are lost.

\textbf{8.} (10) Consider the model in the simulation program in Section 5 of
our PLN unit on contention protocols. (We are concerned here with the model
itself, not the program.) For convenience we restate that model here:

There are n nodes, each of which is either idle or has a message transmission
pending. Time is slotted. Just slightly after the beginning of each integer
time epoch, each of the idle nodes generates a message with probability p. At
time 0.5 past the integer time epoch, each node with a message will with probability
q attempt to send the message, transmitting until just before the next integer
time epoch. If more than one node attempts to send, there is a collision, and
each of the transmissions involved will fail.

This is a Markov chain, with state defined at the very beginning of a time slot
as the number of nodes currently having a message to send (before new messages
are generated). As usual, let \( \pi _{i} \) be the long-run proportion of
the time we are in state i, i = 0,1,2,...,n.

Find \( \pi _{0} \) and \( \pi _{n} \), expressed in terms of the \( \pi _{i} \)
and p and q.

\textbf{Solutions:}

\textbf{1.a.} Alpha.

\textbf{1.b.} P, I, P, I.

\textbf{2.} The preferred answers were NewMsgProb, smaller, P, larger. Those
who answered NNodes instead of NewMsgProb did receive full credit. 

\textbf{3.} Adapt the notion of {}``window of vulnerability{}'' from the PLN.
Say our reference frame transmission begins at time 0.0. What frames could collide
with it? For example, a frame which is created at time -0.82 will begin transmission
at the next available time slot, which is -0.75, and will finish transmission
at time 0.25 -- and thus collide with us. On the other hand, a frame which is
created at, say, time 0.91 will begin transmission at time 1.00, and thus not
collide with us. Inspection of various cases like this shows that the window
of vulnerability is {[}-1,0.75), i.e. an interval of length 1.75. Accordingly,
the original equation, \( S=Ge^{-G} \), changes to \( S=Ge^{-1.75G} \).

\textbf{4.} P.278: {}``\( W_{S} \) is chosen larger than the delay-bandwidth
product to ensure that the channel can be kept busy.{}'' (See p.277 for the
definition of the term \textit{delay-bandwidth product}.)

\textbf{5.} CDPD, pp.365-366. Primary = base station, secondaries = mobile stations.

\textbf{6.a.} The question is whether C(x) divides E'(x). To answer this, we
must express E'(x) in terms of E(x): \( E'(x)=E(x)+x^{k} \) for some k. We
know that C(x) divides E(x). Thus we see that C(x) divides E'(x) if and only
if C(x) divides \( x^{k} \). From our proofs in the PLN, we know that C(x)
cannot divide \( x^{k} \), and thus C(x) cannot divide E'(x), and E' must be
detectable.

\textbf{6.b.} Here \( E'(x)=E(x)-x^{k} \) but in our mod-2 setting \( -x^{k}=x^{k} \)
so the situation is the same as in part (a). 

\textbf{7.} Let X denote the number of lines needed. X has a binomial distribution
with parameters n and p. The number of lost packets L is the excess of X over
m, since we have only m lines available. (A mathematical description of this
would be \( L=max(X-m,0) \).) The numerator in equation (8) is E(L). The question
here asks for \( P(L=0)=P(X\leq m). \) The latter quantity is equal to \( \sum ^{m}_{k=0}C_{n,k}p^{k}(1-p)^{n-k} \),
where \( C_{i,j} \) is the number of ways to choose j things from i.

\textbf{8.} First, consider \( \pi _{0} \). How can we now be in state 0? Either
(a) we were in state 0 last time and no new frames were generated, or (b) we
were in state 1 and no new frames were generated but the 1 existing frame was
sent. Thus

\[
\pi _{0}=\pi _{0}\cdot (1-p)^{n}+\pi _{1}\cdot (1-p)^{n-1}\cdot q\]


The same (though more elaborate) reasoning yields that

\[
\pi _{n}=\pi _{n}\cdot [1-nq(1-q)^{n-1}]+\pi _{n-1}\cdot p\cdot [1-(n-1)q(1-q)^{n-2}]\]

\end{document}