Combined_Exam_without_solutions.tex

%\documentclass[10pt,addpoints]{exam}
\documentclass[answers,addpoints]{exam}


\usepackage{times}
\usepackage{enumerate}
\usepackage{graphicx}

\newcommand{\theclass}{CSCI 353}
\newcommand{\theexamdate}{May 9th 2017}
\newcommand{\theexamnum}{3}

\pagestyle{headandfoot}
\headrule
\firstpageheader{\theclass}{Exam \theexamnum}{\theexamdate}
\runningheader{\theclass}
              {Exam \theexamnum, Page \thepage\ of \numpages}
              {\theexamdate}
\firstpagefooter{}{}{}
\runningfooter{}{}{}


\begin{document}

\begin{center}
  \fbox{\fbox{\parbox{5.5in}{\centering \begin{itemize} 
             \item \textbf{READ THESE INSTRUCTIONS CAREFULLY.}
       \item Before you begin, \textbf{write your USC ID}.
        \item The exam is closed book and closed notes, all ELECTRONICS should be put away 
        \item Please write neatly 
        \item Answer
          the questions \emph{only} in the spaces provided on the question sheets.
          If you run out of room for an answer, your answer is
          probably incorrect.
        \item Your answers do not need to be complete, grammatically
          correct sentences. 
          \item You have 50 minutes for the Quiz
        \end{itemize}
    }}}
\end{center}
\vspace{0.5in}
\makebox[\textwidth]{\textbf{USC ID}:\enspace\hrulefill}

\begin{center}
  \gradetable[h][questions]
\end{center}

\newpage
\begin{questions}


\question 
Answer the following

\begin{parts} 

\part[3] 
What is the difference between Address Translation Protocol (ARP) and Dynamic Host Configuration Protocol(DHCP)?
\fillwithdottedlines{1in} 
   


\part[3] 
A new(cold) host has to do which one first? 
\fillwithdottedlines{0.5in} 

\end{parts}

\question 
What is a problem that using carrier sense with wi-fi could cause? explain. What is the solution for collision avoidance in wi-fi?
\fillwithdottedlines{1in}


\question
Does the IPv4 header contain the subnet mask information?
\fillwithdottedlines{0.5in}


\question
Broadcast address for 172.16.0.0/16
\fillwithdottedlines{0.5in}

\question
The IPv4 header has a Fragment Offset field. Explain why is this needed. Does IPv6 have this field? Explain.
\fillwithdottedlines{1in}

\question Briefly describe NAT.
\fillwithdottedlines{1in}

\newpage
%%%% Next Question 
\question 
Answer the following questions regarding the basics of computer networks and the Internet.

\begin{parts}

\part[3] 
What are the fundamental measures of interest for a communications system?
\fillwithdottedlines{0.5in}

\part[3] 
What are the basic tasks or functions of a communications system?
\fillwithdottedlines{0.5in}


\end{parts}


%%%%% Next Question 
\question 
Answer the following questions regarding the Internet.
\begin{parts}

\part[3] 
What are the four causes of packet delay?
\fillwithdottedlines{0.5in}

\part[3] 
What are the possible mechanisms of packet loss?
\fillwithdottedlines{0.5in}
\part[3]
What is a tool that can be used to determine the number of hops to a destination and the round trip time (RTT) for each hop?
\fillwithdottedlines{0.5in}


\end{parts}

\question 
What is DHCP, how does it work?
\fillwithdottedlines{1in}

\question 
What is ARP, how does it work?
\fillwithdottedlines{1in}

\question 
TCP Connection Questions
\begin{parts}
\part[3] 
Sketch the TCP connection initiation and connection termination packet flows using a timing diagram.
\vspace{3in}
\part[3]
What are the important attributes for a good routing algorithm?
\vspace{2in}
\part[3]
What is a key difference between a distance vector and link state routing protocol?
\vspace{2in}

\part[3]
For the following five node network topology with link costs as shown, find the shortest path from node A to all other nodes using Dijkstra’s algorithm. Clearly describe the order of links as they as added one-by- one by the algorithm and give the path costs.\\
\includegraphics[width=18cm, height=5cm]{_1}\\
\vspace{4in}
\end{parts}



\question
The diagram below shows a network with 3 routers (shown as hexagons) connected by an Ethernet switch. The routing table for the left-hand router is shown. 
\begin{parts}
\part[3]
Complete the routing table for the right-hand router, so that packets will be delivered appropriately (use no more than 5 route table entries).\\
\includegraphics[width=10cm, height=10cm]{_4}\\

\part[3]
Are all the entries in the left-hand router’s table necessary? If not, show how to reduce the number of entries, without changing the routing behavior.
\vspace{2in}
\end{parts}

\question
Consider the stop-and- wait protocol on a wired link between nodes A and B. Suppose that the propagation delay in each direction is 10 ms. The transmission rate is 10 Mbps.Assume that data packet size is 1000 bytes.
What is the maximum data throughput (in bits/second) achievable using the stop-and-wait protocol, if none of the packets are lost?
\fillwithdottedlines{0.5in}

\question
Suppose that a sender and a receiver are using ARQ to perform reliable data delivery. In a Go-Back- N ARQ protocol, the window size is 6. Frames with sequence numbers 1, 2, 3, 4 and 5 have been sent. The sender just received an ACK for frame 1. Frames 6, 7, 8, 9 and 10 are waiting to be sent. Draw the time diagram showing this scenario.
\vspace{3in}


\question
Can Selective-Repeat ARQ use cumulative ACKs? Explain.
\fillwithdottedlines{1in}

\question
What are the trade-offs between Go-Back-N ARQ and Selective-Repeat ARQ?
\fillwithdottedlines{1in}


\question
Suppose two hosts, A and B, are separated by 10,000 kilometers and are connected by a direct link of R = 2 Mbps. 
\begin{parts}
\part[3]
Suppose the propagation speed over the link is $2.5 * 10^8$ meters/sec.Calculate the bandwidth-delay product , $R * d_{prop}$.
\fillwithdottedlines{1in}

\part[3]
Consider sending a file of 1000,000 bits from host A to host B. Suppose the file is sent continuously as one large message. What is the maximum number of bits that will be in the link at any given time?
\fillwithdottedlines{1in}
\end{parts}


\question
DNS uses a distributed approach as opposed to a single server. Why? If DNS were to crash or entirely go down, what would happen? Could the Internet still be used and, if so, how?
\fillwithdottedlines{1in}

\question
Consider two hosts, A and B, connected by a single link of rate R bps. Suppose that the two hosts are separated by m meters, and suppose the propagation speed along the link is s meters/sec. Host A is to send a packet of size L bits to Host B.
\begin{parts}
\part[3]
Express the propagation delay, dprop in terms of m and s.
\fillwithdottedlines{0.5in}
\part[3]
Determine the transmission time of the packet, dtrans in terms of L and R.
\fillwithdottedlines{0.5in}
\part[3]
Ignoring the processing and queuing delays, obtain an expression for the end-to- end delay.
\fillwithdottedlines{0.5in}
\part[3]
Suppose Host A begins to transmit the packet at time $t=0$. At time $t=dtrans$,where is the last bit of the packet?
\fillwithdottedlines{0.5in}
\part[3]
Suppose d prop is greater than dtrans. At time $t= dtrans$, where is the first bit of the packet?
\fillwithdottedlines{0.5in}
\part[3]
Suppose d prop is less than dtrans. At time $t=dtrans$, where is the first bit of the packet?
\fillwithdottedlines{0.5in}
\end{parts}

\question
\begin{parts}
\part[3]
Why is Collision Detection (CD) not feasible in a wireless network?
\fillwithdottedlines{1in}

\part[3]
Describe (i.e., give) the CSMA/CA algorithm as used in WiFi (IEEE 802.11).
\vspace{3in}
\end{parts}


\question
Assume that source S and destination D are connected through two intermediate routers labeled R. Determine how many times each packet has to visit the network layer and the data link layer during a transmission from S to D.\\
\begin{parts}
\part Network layer – 4 times and Data link layer – 4 times
\part Network layer – 4 times and Data link layer – 3 times
\part Network layer – 4 times and Data link layer – 6 times
\part Network layer – 2 times and Data link layer – 6 times
\end{parts}
\includegraphics[width=12cm, height=3cm]{_7}\\

\question
The Client is connected to Cache with propagation delay of 0 ms. The  same client is connected to server with 1 Gbps line and 0 ms propagation delay. Assuming client is active and cache is on and behaves like HTTP cache. A client’s GET request is always first directed to Cache. 60\% of the request are satisfied by local cache. What is the average rate at which client can receive data in this case. \\
\includegraphics[width=12cm, height=7cm]{_8}\\
\vspace{2in}
\question
What is an advantage of a hierarchical name space over a flat name space for a system the size of the Internet.
\fillwithdottedlines{1in}


\question
Fill in the blank
DNS uses \underline{\hspace{3cm}} associated with each entry to ensure that entries are invalidated after a particular threshold.

\question
Suppose host A is sending a large file to host B over a TCP connection. The two end hosts are 10 msec apart (20 msec RTT) connected by a 1Gbps link. Assume that they are using a packet size of 1000 bytes to transmit the file. Also assume for simplicity that ACK packets are extremely small and can be ignored. 

\begin{parts}
\part[]
At least how big would the window size (in packets) have to be for the channel utilization to be greater than 80\%.(Assume RTT as entire delay)
\fillwithdottedlines{1in}
\end{parts}


\question
TCP waits until it has received three duplicate ACKs before performing a fast retransmit. Why do you think the TCP designers chose not to perform a fast retransmit after the first duplicate ACK for a segment is received?
\fillwithdottedlines{1in}


\question
Ethernet frames must be at least 64 bytes long to ensure than the transmitter is still going in the event of a collision at the far end of the cable. Fast Ethernet (100 Mb/s) has the same 64 byte minimum frame size, but can get the bits out ten times faster. How is it possible to maintain the same frame size?
\fillwithdottedlines{1in}



\question
Why does UDP exist? Would it not have been sufficient to let applications send raw IP packets?
\fillwithdottedlines{1in}


\question
\begin{parts}
\part[]
 Many enterprise networks only allow registered machines to access the local area network. Some of these networks configure the DHCP server to assign a computer (or MAC address) the same IP address every time it connects to the network. Give one reason why.
 \fillwithdottedlines{1in}
 
 \part[]
 What is the disadvantage of associating each registered MAC address with a pre-determined IP address?
 \fillwithdottedlines{1in}
\end{parts}


\question
Host A initiates a TCP connection with host B by sending a SYN packet, and B responds with a SYN-ACK packet. Upon receiving the SYN-ACK packet, A responds with an ACK packet. 
\begin{parts}

\part Immediately after sending the SYN packet to B
\part Immediately after receiving the SYN-ACK packet from B 
\part Immediately after receiving data from B
\end{parts}


\question
Suppose process A calls close() after the operating system has transmitted all of the outstanding data. What kind of packet does the operating system send in response to A’s call to close()? 
 \fillwithdottedlines{0.5in}
 


\question
Which of the following is/are true about a communications channel that uses time- division multiplexing? (Circle ALL that are correct)
\begin{parts}
\part There may be times when the channel is idle, even if a sender has data to send on the channel. 
\part  The channel requires the sender’s and receiver’s clocks to be closely synchronized. 
\part  Data in the channel could experience variable delays due to queuing. 
\part  In times of high utilization, a sender could be completely denied access to the channel.
\end{parts}

\question 
You need to transfer large amounts of data cheaply, therefore, you are considering using FedEx as your communication network. FedEx will deliver an external hard drive of any size, for \$5, to the destination of your choosing in 1 hour. 

\begin{parts} 

\part[3] 
How much data would the external hard drive have to hold for FedEx network to deliver the data faster than one dedicated 10 Mbps line?
\fillwithdottedlines{1in}
   


\part[3] 
If you had to deliver 200 Gbits of data, and if you could multiplex this delivery on several 10 Mbps lines, and if the cost of a connection on each line was \$1/line (regardless of connection time), is it possible to use enough such lines to make the delivery at least as fast as the FedEx network, but cheaper? Explain your answer. (Assume that one external hard drive can hold 200 Gbits.)
\fillwithdottedlines{1in} 

\end{parts}


\question 
Sliding window protocols (an example of such a protocol is the Go-back-N protocol)
\begin{parts} 

\part[3] 
Consider a sliding window protocol across a channel in which the one-way propagation delay is always 50 msec. Assume that (1) ACK packets are very small, (2) you can ignore queueing delays, and (3) each packet is 10000 bits in size (including the header information). If the channel is reliable and has a guaranteed transmission rate of 100 kbps, is there any performance benefit to using a sender’s window larger than 2 packets in size? Be sure to show all your work. 
\fillwithdottedlines{1in} 
   


\part[3] 
What problem/issue is the sliding window protocol trying to address? Please limit your answer to no more than a couple of sentences. \fillwithdottedlines{0.5in} 



\part[3] 
Now consider a specific sliding window protocol, namely the Go-Back-N protocol, with a sender window size of 10 and a sequence number range of $2^{10}$. Suppose that at time T, the next in-order packet that the receiver is expecting has a sequence number K. Assume that the medium does not reorder messages. The, what are the possible set of sequence numbers inside the sender’s window at time T? Justify your answer. \fillwithdottedlines{1in} 


\end{parts}


\question
Consider using the slow start algorithm on a connection with a 10 ms round-trip time and no congestion. If the initial congestion window (I.e., the maximum segment size) is 8KB, and the initial threshold is set at 64KB, and the receiver window is set at 85KB, how long does it take before the first full window (i.e., of maximum window size) can be sent? Justify your answer. 
\fillwithdottedlines{1in}

\question
TCP uses implicit congestion control. What is the “signal” implying the presence of congestion? What does TCP do when it detects congestion? What problems may this cause in wireless networks?
\fillwithdottedlines{2in}

%%%% Next Question 
\question 
Consider sending a 2400-byte datagram into a link that has an MTU of 700 bytes. Suppose the original datagram is stamped with the identification number 422. How many fragments are generated? What are the values in the various fields in the IP datagram(s) generated related to fragmentation?
\vspace{3in}



%%%%% Next Question 
\question 
Consider a datagram network using 8-bit host addresses. Suppose a router uses longest prefix matching and has the following forwarding table:
\begin{center}
 \begin{tabular}{|c | c|} 
 \hline
 Prefix Match & Interface \\ [0.5ex] 
 \hline
 00 & 0 \\ 
 \hline
 010 & 1 \\
 \hline
 011 & 2 \\
 \hline
 10 & 2 \\
 \hline
 11 & 3 \\ [1ex] 
 \hline
\end{tabular}
\end{center}

For each of the four interfaces, give the associated range of destination host addresses and the number of addresses in the range.
\fillwithdottedlines{2in}


\question 
True or False? A client can open multiple TCP connections to the same server process. 
\fillwithdottedlines{0.5in}

\question 
Describe the fundamental difference between circuit and packet switching.
\fillwithdottedlines{1in}

\question 
Mention the five layers of the network stack. 
\fillwithdottedlines{1in}

\question 
Why was IPv6 created? Describe the most significant changes of IPv6 compared to IPv4.
\fillwithdottedlines{1in}

\question 
Consider the count-to-infinity problem in the distance vector routing. Will the count-to-infinity problem occur if we decrease the cost of a link? Why? How about if we connect two nodes which do not have a link?
\fillwithdottedlines{1in}

\question 
How does TCP estimate the Round-Trip Time (RTT)? Your answer must be in equation form. Be sure to define each variable in your equation. 
\fillwithdottedlines{0.5in}


\question 
True or False, explain
\begin{parts} 
\part[3] 
In stop&wait, the receiver always send an ACK frame each time it receives a frame with the wrong sequence number. 
\fillwithdottedlines{0.5in} 
\part[3] 
Statistical Multiplexing is more efficient when the Peak Rate is much higher than the average data rate.
\fillwithdottedlines{0.5in} 
\part[3] 
Stop&Wait works well when propagation time is much less than transmission time.
\fillwithdottedlines{0.5in} 
\part[3] 
Disconnected private organizations “Intranets” can use any network address.
\fillwithdottedlines{0.5in} 
\part[3] 
A client computer on a shared network is assigned a MAC address and an IP address by the network administrator.
\fillwithdottedlines{0.5in} 
\part[3] 
In UDP, if you have badly configured networks, the appication can receive the same packet multiple times.
\fillwithdottedlines{0.5in} 
\part[3] 
If a computer has multiple Network Interface Cards, the DHCP process must occur separately over each interface to obtain a separate dynamically assigned IP address for each interface.
\fillwithdottedlines{0.5in} 
\part[3] 
Iterative DNS queries require shorter socket connections with DNS servers than recursive DNS queries.
\fillwithdottedlines{0.5in} 
\part[3] 
Wireless station can’t transmit and receive at same time.
\fillwithdottedlines{0.5in} 

\end{parts}

\question 
Short Answer
\begin{parts} 
\part[3] 
What can a web cache be used to?
\fillwithdottedlines{0.5in} 
 \part[3] 
Consider transmitting a packet from host A to host B via a router (i.e. hosts A and B are located on different networks). All ARP tables (in hosts and router) are empty. Let x denotes the time (in seconds) to transmit the packet. Let y denotes the time (in seconds) elapsed from the beginning of transmitting an ARP query until receiving an ARP response. Ignoring propagation delay, the total time it takes to forward the packet from A to B is (   ) sec.
\fillwithdottedlines{0.5in} 
 \part[3] 
A CSMA/CD station on an Ethernet LAN is contending for the channel, trying to transmit a frame, using the binary exponential backoff algorithm. After experiencing the nth collision in a row for this frame, the station chooses a value K and waits K* 512 bit times before attempting retransmission. How does it choose the value of K?
\fillwithdottedlines{0.5in} 
 \part[3] 
A point-to-point link over which a sliding window algorithm of SWS = 5 frames is running. Each frame is 1 Kbits long. The propagation delay is 0.5 sec. The maximum bit rate over which this implementation can operate and still keep the link fully utilized is \underline{\hspace{2cm}} bps (Ignore the transmission time of the ACK).
\fillwithdottedlines{0.5in} 
 \part[3] 
You are designing a Go-Back-N sliding window protocol to be used over a 1 Mbps link from a ground terminal to a geosynchronous satellite at a distance of 30,000 Km. Each frame carry 1 Kbyte of data. The speed of light is 3x108 m/sec. It is desired to keep the “pipe” full. The minimum number of bits you need for sequencing the frames is (   ) bits.
\fillwithdottedlines{0.5in} 
 \part[3] 
Suppose two hosts, A and B, are separated by 20,000 kilometers and are connected by a direct link of R = 2 Mbps. Suppose the propagation speed over the link is 2.5 x 108 m/s. A wants to send a file to B. Suppose the file is broken up into 20 packets with each packet containing 40,000 bits. Suppose that each packet is acknowledged by the receiver and the transmission time of an acknowledgment packet is negligible. Finally, assume that the sender cannot send a packet until the preceding one is acknowledged. How long does it take to send the file?
\fillwithdottedlines{0.5in} 
 \part[3] 
List at least three reasons that the packet will get dropped.
\fillwithdottedlines{0.5in} 
 \part[3] 
Why would the token-ring protocol be inefficient if a LAN had a very large perimeter?
\fillwithdottedlines{0.5in} 
 \part[3] 
Suppose an ISP owns the block of addresses of the form 128.119.40.64/26. Suppose it wants to create four subnets from this block, with each block having the same number of IP addresses. What are the prefixes (of form a.b.c.d/x) for the four subnets?
\fillwithdottedlines{0.5in} 
\end{parts}

\question
Consider the TCP congestion-control algorithm that uses slow-start but has no fast retransmit/fast recovery. The algorithm starts each connection with a window size equal to one segment. Assume the only delay is latency only, and a single ACK is sent for a group of segments. Assume a perfect timeout mechanism that detects a lost segment exactly 1 RTT after it is transmitted. Round up the fractional numbers encountered in window size to greater integers (like 2.5 -> 3).
\begin{parts}
\part Fill in the table below assuming segments 7, 12 and 15 are lost. \\
\includegraphics[width=15cm, height=5cm]{_9}\\
\part  Sketch the variation of congestion window with respected to time. (Time starts from 0, 0 means the start of the first RTT, 1 means the end of the first RTT)
\vspace{2in}
\end{parts}

\question
An organization has a class C network 200.1.1 and wants to form subnets for four departments, with hosts as follows:\\
A: 72 Hosts\\
B: 35 Hosts\\
C: 20 Hosts\\
D: 18 Hosts\\
There are 145 hosts in all.\\
Give a possible arrangement of subnet masks to make this possible.
\vspace{2in}


\end{questions}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: