\documentclass[11pt]{article}
\usepackage{handout2e}
\usepackage[dvips]{graphicx}
\usepackage{epsfig}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSU640}{Network Fundamentals}{Fall 2004}{15 November 2004}{11}

\begin{center}
\Large{\bf Problem Set 4 (due Wednesday, December 1)}
\end{center}

\medskip

{\bf 1. (10 points) CRC code} 

Suppose we want to transmit the message 11100011 and protect it from
errors using the CRC generator is 10011.
\begin{itemize}
\item[{\bf (a)}] 
Use long division to determine the message that should be transmitted.

\item[{\bf (b)}]
Suppose the leftmost bit and the rightmost bit of the message (that is
sent) get inverted.  What is the result of the receiver's CRC
calculation?  Does the receiver recognize that an error has occurred?
\end{itemize}

{\bf 2. (20 points) Addresses and packet headers} 

An organization has a network address of 200.1.1 and wants to form
subnets for three departments, one connected through LAN1, another
through LAN2, and a third through LAN3, as shown below.  The first
department has 100 hosts, the second has 52 hosts, and the third has
20 (not all hosts are shown).

\begin{figure}[h]
\begin{center}
\epsfig{file=practice_network.eps,width=0.5\textwidth}
\end{center}
\end{figure}

\begin{itemize}
\item[{\bf (a)}]
Give a possible arrangement of subnet masks to make the above
organization possible.

\item[{\bf (b)}]
Draw the routing table stored at the router R1.  The fields of the
table are SubnetNumber, SubnetMask, and NextHop.  Set the default
entry to be R2.

\item[{\bf (c)}]
Choose IP addresses for all interfaces of H1, H2, H3, H4, and R1.

\item[{\bf (d)}]
Suppose host H1 wants to send packet P1 to H2 and packet P2 to H3
(using UDP, say), in that order.  H1 does not know the Ethernet
address of H2, H3, R1, and H4.  H1 only knows the IP address of the
other hosts and router.  Show the flow of packets sent and received
(including ARP request and reply packets) by H1.  Specify the source
and destination IP addresses, Ethernet addresses of the packets, and
type of protocols that are used.

Assume that ETH1 is the Ethernet address of H1, ETH2 is the Ethernet
address of H2, etc.
\end{itemize}

{\bf 3. (20 points) Ethernet capture effect} 

Let A and B be two stations attempting to transmit on an Ethernet.
Each has a steady queue of frames ready to send; A's frames will be
numbered $A_1$, $A_2$, and so on, and B's similarly.  Let $T$ denote
the exponential backoff base unit; this is the time taken to send 512
bits over the Ethernet channel.  Suppose A and B simultaneously
attempt to send frame 1, collide, and happen to choose backoff times
of $0 \times T$ and $1
\times T$, respectively, meaning A wins the race and transmits $A_1$
while B waits.  At the end of this transmission, B will attempt to
retransmit $B_1$ while A will attempt to transmit $A_2$.  These first
attempts will collide, but now A backs off for either $0 \times T$ or
$1 \times T$, while B backs off for time equal to one of $0 \times T$,
\ldots, $3 \times T$.
\begin{itemize}
\item[{\bf (a)}] Give the probability that A wins this second backoff
race immediately after this first collision; that is, A's first choice
of backoff time is less than B's.

\item[{\bf (b)}] Suppose A wins this second backoff race.  A transmits
$A_3$, and when it is finished, A and B collide again as A tries to
transmit $A_4$ and B tries once more to transmit $B_1$.  Give the
probability that A wins this third backoff race immediately after the
first collision.

\item[{\bf (c)}] {\bf (Bonus problem)} Give an approximate lower bound for
the probability that A wins all the remaining backoff races.

\item[{\bf (d)}] What then happens to the frame $B_1$?
\end{itemize}
\end{document}

