University of Southern California “EE450: Introduction to Computer Networks” Midterm Exam, 2:10 hour
October 8, 2021
Name: ______________________________ Undergraduate
Graduate
Part 1: True/False 25% Part 2: Quickies 40% Part 3: Error Detection 10% Part 4: Error/Flow Control 15% Part 5: DNS, HTTP & Web Caching 10% Total 100%
Notes:
▪ You can work the problems in any order you wish (the goal is to try to accumulate as many points as you can). If you get stuck in one problem, go to another.
▪ For on-campus students, all your answers must be on the exam paper. For remote students, you can print the exam and use the worksheets or you can use your papers.
Rules:
▪ This is a closed book, closed notes exam. You are only allowed one8″x11″ of formulas ONLY and a Calculator. No electronic gadgets are allowed including your cell phone.
▪ Adherence to the University’s Code of Ethics will be strictly monitored and enforced. Academic Integrity violations, such as cheating, will result in a series of actions and penalties including the student failing the class.
EE450-Midterm-Fall-2021
1. True or False
a. In continuous sliding window ARQ, the sender must be willing to buffer up to SWS frames.
b. In continuous sliding window ARQ, when a frame is lost, the sender can’t keep the pipe full.
c. In persistent TCP connections with pipelining, clients can send requests, back-to- back, without waiting for responses from the server. The server will then respond by sending all objects simultaneously.
d. TCPconnectionsareuniquelyidentifiedbytheNOSusingthelocalandremoteIP addresses
e. In SR ARQ, the sender window size can be no more than half the number of available sequence numbers
f. HTTP is the communications protocol between an HTTP client and an HTTP server. It determines how a web page is displayed on the client screen.
g. Each TCP connection transports exactly one request message and one response message
h. A single client can have up to ~ 64K connections to the server for the same destination port
i. Multiple client sockets can be bound to the same local IP/port pair at the same time if they are connected to different servers IP/Port pairs.
j. A user requests a Web page that consists of some text and three images. For this page, the client will send one request message and receive four response messages.
k. Two distinct Web pages www.usc.edu/research.html and www.mit.edu/grades.html can be sent over the same persistent connection
l. The DNS server and the DHCP server could be installed in the same device
EE450-Midterm-Fall-2021
m. The bandwidth-delay product of a link is how long it takes to send a frame to the other side and get a response back.
n. The .edu TLD name server knows the IP address of the authoritative name server for usc.edu
o. In sliding window ARQ, there can never be more unacknowledged frames than the receiver window size.
p. Protocolsdefinehowalayerofthenetworkingstackinteractswithadjacentlayers.
q. BitStuffingisatechniqueusedtoensurethatnobit-patternsareforbiddenfrom part of the packet payload.
r. The .edu TLD name server knows the IP address of the authoritative name server for usc.edu
s. In UDP socket, data being read from the server-side socket can been sent by more than one client.
t. A Traffic that is transmitted from a host in the US to a host in Europe MUST traverse a Tier-1 Network
u. ARP is a protocol used to resolve the “next hop IP address” to its MAC address
v. Routersonlyprocessframesthatarespecificallyaddressedtothemorframesthat are broadcasted.
w. TCP is a transport layer protocol that provides guarantees on Reliability, Delay and Throughput
x. SMTP and IMAP are two protocols used to send electronic messages.
y. Web caching can reduce the delay for all objects, even objects that are not cached,
EE450-Midterm-Fall-2021
Part 2: Quickies (every blank is worth 2 points)
1. Consider a transmission link that uses the stop and wait protocol. The ratio of the transmission delay to the propagation delay is 1/3. Frames are transmitted at a rate of 10 Mbps and each frame is 1k bits long. Bits propagate at a speed of 2×108 m/sec.
• The length of the link is ______________ meter.
• The link utilization is __________ %
2. Ten sources are multiplexed using FDM on a link that has a total bandwidth of 10K Hz. The maximum bandwidth for each source if there must be a 100 Hz guard band between the channels is _____________ Hz.
3. In a certain DLC protocol, the Flag used to indicate the start and end of the frame is 0111. Assume that zero stuffing is used (To prevent the occurrence of the flag sequence anywhere in the frame). The data sequence is 011011101101. The sender will transmit the sequence __________________________ (Do NOT include the Flags)
4. Suppose a movie studio wants to distribute a new movie as a digital file to 1,000 movie theaters across country using peer-to-peer file distribution. Assume that the studio and all the theaters have DSL connections with an 8 Mb/s downstream rate and a 4Mb/s upstream rate and that the file is 10 GB long. Ignore all delay components that are not specified in question. The time it takes to distribute the file to all the theaters under ideal conditions is _____________ seconds. Now suppose the studio wanted to use a client-server model. The smallest link rate that is required at the studio (server) that would allow distribution of the file in under 40,000 seconds is _______________ bps.
EE450-Midterm-Fall-2021
5. We have 3 information sources, generating traffic at rates 25Kbps, 35Kbps and 45Kbps respectively. The sources are active 10%, 25% and 50% respectively. They are to be multiplexed using multiple slot (each slot supporting 2 bits), synchronous TDM. Ignore any synchronization bits.
a. The minimum length of the TDM frame is = __________ bits.
b. The multiplexor bit rate is ___________ bps.
c. The TDM frame rate is ______________ frames/sec.
d. The duration of the TDM time slot is __________ sec.
6. The same information sources as above are to be multiplexed using a Statistical TDM.10% of the link capacity is used to support headers. The required MUX rate at the output is __________ bps.
7. Suppose you are using SR-ARQ sliding window protocol over a 1Gbps link. The length of the link is 20Km and the speed of propagation is 2×108 m/sec. It is desired to keep the pipe full, i.e., achieve maximum utilization. The length of each frame is 1000 bits. The “minimum” number of bits needed to sequence the frames is m = _______ bits
EE450-Midterm-Fall-2021
8. Two packets are transmitted back-to-back over a three-hop network as shown below. The length of each packet is 1K bits. The data rate on the first hop (AB) is 10Mbps. The data rate on the last hop (CD) is 5Mbps. You measure the delay t4~t5 between the end of the receptions of the two packets to be 5 ms. The propagation delay over each link is 10 msec. The data rate of the second hop is _____________ bps. The overall throughput is _______________bits/sec
EE450-Midterm-Fall-2021
9. The link between the client browser and the web server can support 100 Mbps with a round trip time RTT = 250msec. Suppose that the browser wants to download a base HTML page of 500 Kbits long. The HTML file contains 3 URL links of images each of 100 Kbits long. Two of the images are located on the same server, the third one is located on a different server. The time needed to set up a TCP connection is 1RTT. Ignore the transmission time of the HTTP commands (GET).
a. Approximately how long does it take for the page (including images) to appear on the user’s screen, assuming non-persistent HTTP using a single connection at a time? Answer: ___________________ sec
b. Repeat part “a” assuming persistent HTTP. Answer: ___________________ sec
c. Repeat part “a” assuming persistent HTTP with pipelining. Answer: ___________________ sec
d. Repeat part “a” assuming non-persistent HTTP with 2 parallel connections. Answer: ___________________ sec
EE450-Midterm-Fall-2021
10. Three nodes A, B, C are communicating with a server node S. with the indicated Source and Destination Port numbers. From this diagram determine, what is the “total” number of sockets (include both parents and childs) does “S” have to open assuming:
a. UDP Sockets: ____________
b. TCP Sockets: _________
ABC
SP 2455 DP 800
SP 1235 DP 600
SP 2455 DP 500
SP 1235 DP 600
SP 2455 DP 700
EE450-Midterm-Fall-2021
S
Work Sheet 1
EE450-Midterm-Fall-2021
Work Sheet 2
EE450-Midterm-Fall-2021
Work Sheet 3
EE450-Midterm-Fall-2021
Part 3: Error Detection (10 points)
3. An FCS error detection mechanism is used over a communications link. The message bit sequence is 110101. An FCS generator pattern of 10011 is used to generate the FCS sequence.
a) How many FCS bits are generated? What are they? What is the transmitted bit sequence? Identify the FCS bits in that sequence. Show details of your work.
b) Now suppose the received sequence is 0001111001. Did errors occur, if yes, how many? Will the receiver accept the frame? if yes, what will he decide the message sequence bits are? If no, why not?
c) Now suppose the channel introduces the following error sequence1010101010. Will the receiver be able to detect the error? Prove your answer analytically. Remember, neither the transmitter nor the receiver knows about the error sequence.
Note: Parts “b” and “c” are continuations of part “a”
EE450-Midterm-Fall-2021
Work Sheet 4
EE450-Midterm-Fall-2021
Part 4: Sliding Window ARQ (15 points)
4. Consider a link that uses Go-Back-N ARQ protocol with SWS=7. Suppose the transmission time of a frame is 1 second. Each frame uses a time-out mechanism of 2 seconds (The time-out timer starts when you transmit the last bit of your frame). Assume that one-way propagation delay is 0.5 seconds. Neglect the processing delay. Upon receiving a frame, the receiver will wait 1 second and send an accumulative ACK for all frames received with no errors up to (and including) that point in time. Neglect the transmission time of the ACK frame. Assume that station A begins with frame Fo. Draw the frame-exchange-timing diagram for the following sequence of events (Hint: Divide the timeline into 0.5 seconds intervals). Be sure to label each data frame with a sequence number and each ACK with a sequence number indicating the next frame expected to be received. There is no NAK in this implementation of the protocol. Assume that each frame is 1000 bits long. Consider the following scenario:
➢ Station A sends 5 frames in a row, starting at t=0. Frame F2 was received and detected to be in error and F4 was lost in transmission. Calculate the throughput and the link utilization. Assume that node A has only those 5 frames to transmit.
AB
EE450-Midterm-Fall-2021
Work Sheet #7
Start from t = 0 and assume every division is 0.5 sec
EE450-Midterm-Fall-2021
Part 5: Name Resolution and Web Browsing
Consider the following configuration. Host A is located on LAN1. A web Server X is located on LAN2. Suppose that the user at host “A” enters the URL of server X to download a given 1G-bit HTML file. Host A does NOT know the IP address of Server X. Host A is configured with the IP address of the local DNS server. Calculate the time elapsed from the moment user A enters the URL till the time the file is completely downloaded under the following assumptions:
a) DNS commands and HTTP commands are so small compared to the file such that you can ignore their transmission times (NOT the propagation delay)
b) The propagation delay within either LAN is negligible. The propagation delay from R1 to R2 is 100 msec. The propagation delay from anywhere in LAN1 to any other site on the Internet (except LAN2) is 250 msec.
c) Each LAN operates at 1 Gbps. The link between R1 and R2 is 100 Mbps (in each direction)
d) The DNS is iterative
e) The authoritative DNS server is located one level below the Top-Level Domain
(and hence two levels below the root name server). Only the authoritative DNS server knows the IP address of Server X. The Local DNS server is configured with the IP address of the root name server.
f) DNS runs over UDP whereas HTTP runs over TCP.
Calculate the time elapsed from the moment Client A enters the URL till the time the file is completely downloaded. You need to list the steps involved clearly in the table provided. The order is IMPORTANT.
Authoritative DNS for Server X
D N S
X
X R1
R2
Internet
Internet
Local DNS for Host A
LAN1
D N S
A
EE450-Midterm-Fall-2021
Work Sheet #8
Table maybe longer or shorter what you need. Make sure to add the total delay in the third column (Do not accumulate delays). Make sure your “actions are clear”.
Step 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Action
Delay (msec)
EE450-Midterm-Fall-2021
Make Sure to tabulate the total delay
Work Sheet #9
EE450-Midterm-Fall-2021
EE450-Midterm-Fall-2021