\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}{6 December 2004}{14}

\begin{center}
\Large{\bf Practice Exercises for the Final}
\end{center}


{\bf 1.} The purpose of both distance-vector and link-state protocols
is to construct routing tables.  What is the difference in their
mechanisms?

\junk{In distance-vector protocols, the nodes exchange their
distance vectors (distances to all nodes) with neighbors and update
the distance information to each node.  In link-state protocols, the
nodes send their local link state (state of links to neighbors) to all
nodes and then locally compute the shortest paths by constructing the
whole topology.  }

{\bf 2.} The sequence number field in the TCP header is 32 bits long,
which is big enough to cover over 4 billion bytes of data.  Even if
these many bytes were never transferred over a single connection, why
might the sequence number still wrap around from $2^{32} - 1$ to $0$?

\junk{Because a connection starts with a random number.}

{\bf 3.} Packet loss and packet jitter can significantly degrade the
quality of multimedia streams (at the receiver end).  Forward-error
correction schemes address these problems by adding redundancy to the
original packet stream, thus allowing the receiver to reconstruct
approximations of the original packet stream in the presence of packet
loss and packet jitter.  Describe one forward error correction scheme
for multimedia streaming.

\junk{
XOR every n packets.
}

{\bf 4.} Recall that the Address Resolution Protocol (ARP) is a
protocol for translating IP addresses into hardware addresses (also
referred to as Ethernet or MAC addresses).  The ARP entries at a node
in a local area network usually time out after 10-15 minutes.
Describe the problems that can occur if the timeout value is too small
or too large.

{\bf 5.} Consider our symmetric-key based authentication protocol in
which Alice authenticates herself to Bob as follows: (i) Alice sends
an ``I am Alice'' message to Bob; (ii) Bob chooses a nonce R and sends
it to Alice; (iii) Alice encrypts the nonce using the shared key
$K_{A-B}$ and sends the cipher text to Bob; and (iv) Bob decrypts the
received message and compares with the nonce.

Suppose that while Alice is authenticating herself with Bob, Bob must
authenticate himself with Alice.  Describe a scenario in which Trudy,
pretending to be Alice, can now authenticate herself to Bob as Alice.

{\bf 6.} A message with data 1001000 is to be sent using the standard
CRC method, with the CRC generator 1001.  Calculate the actual bit
string transmitted.

{\bf 7.} An organization has a network address of 210.10.10.  As shown
below, the network is organized as 4 Ethernet LANs, two of which are
connected to each other through a bridge, and the entire network is
connected via a router.  LAN1 has 27 hosts, LAN2 has 72 hosts, and
LAN3 has 54 hosts, and LAN4 has 20 hosts.

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

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

\junk{
LAN1 and LAN2 are connected together by a bridge to form an extended
LAN.  So they will form the same subnet.  Their total number of hosts
is 99.  So we will allocate 128 addresses.  For LAN3, we will allocate
64, and for LAN4 64.  So we have

LAN1 + LAN2 210.10.10.0 255.255.255.128 /0

LAN3 210.10.10.128 255.255.255.192 /10

LAN4 210.10.10.192 255.255.255.192 /11
  }

\item[{\bf (b)}]
Draw the routing table at router R1.  The fields of the table are
SubnetNumber, SubnetMask, and NextHop.  Set the default entry to be
R2.  (You may assign your own labels to all interfaces of R1.)

\junk{
At R1, we have four interfaces:

210.10.10.0 255.255.255.128 I1

210.10.10.128 255.255.255.192 I2

210.10.10.192 255.255.255.192 I3

Default R2
}

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

\junk{
H1 210.10.10.1

H2 210.10.10.2

H3 210.10.10.129

H4 210.10.10.193

}

\item[{\bf (d)}]
Now H1 sends a UDP packet to H3 and H3 replies with another UDP packet
to H1.  Initially, none of the hosts or routers know the Ethernet
addresses of any interfaces.  H1 knows the IP address of H3.  Show the
flow of packets sent and received in the process of this exchange.
Specify the source and destination IP addresses, Ethernet addresses of
the packets and the type of protocols that are used.

\junk{
For the first packet, it is the same sequence as in the practice
exercise.

During the response packet, both H3 and R1 are aware of the other
nodes Ethernet addresses.  So we have only two packet transmissions.

H3->R1

R1->H1
}

\end{itemize}

{\bf 8.} Suppose we use the distance vector protocol to compute the
distances and next hops between different node pairs.  Given the
initial distance vector table (the first table), fill in the distance
vector table entries of node A (the second table) after one round of
distance vector exchange with its neighbors.

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

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}\hline
Information & \multicolumn{7}{c|}{Distance to Reach Node}\\\cline{2-8}
Stored at Node & A & B & C & D & E & F & G\\\hline
A & 0 & 2 & 7 & 4 & $\infty$ & 3 & 3 \\
B & 2 & 0 & 4 & $\infty$ & $\infty$ & $\infty$ & $\infty$ \\
C & 7 & 4 & 0 & $\infty$ & 2 & $\infty$ & 4 \\
D & 4 & $\infty$ & $\infty$ & 0 & 10  & 1 & 2 \\
E & $\infty$ & $\infty$ & 2 & 10 & 0 & 3 & 2\\
F & 3 & $\infty$ & $\infty$ & 1 & 3 & 0 & 1\\
G & 4 & $\infty$ & 4 & 2 & 2 & 1 & 0\\\hline
\end{tabular}

\begin{tabular}{|c|c|c|c|c|c|c|c|}\hline
Information & \multicolumn{7}{c|}{Distance to Reach Node}\\\cline{2-8}
Stored at Node & A & B & C & D & E & F & G\\\hline
& & & & & & &\\
A & & & & & & &\\
& & & & & & &\\\hline
\end{tabular}
\end{center}

{\bf 9.} By computing the shortest path from node B to every other
node in the following graph, determine the forwarding table that is
stored at node B (assuming the network has reached a steady state).

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

{\bf 10.} Using RSA, choose $p=3$ and $q = 11$, and encode the word
``hello''.  Apply the decryption algorithm to the encrypted version to
recover the original plaintext.
\end{document}