CS/ECPE 5516 Final Exam



Final Exam

EcPE/CS 5516: 5/9/2000

Name: ______________________

ID Number: ______________________

Section: ___ 9am ___ 1pm

This is a closed-book, closed-notes (except for 1 A4-size sheet of paper) examination. You may not discuss (in any form: written, oral, electronic, sign language, etc.) the content of this examination with any student who has not taken it. Failure to comply with these restrictions is an honor code violation. In addition, you are graded with the students who have not taken the exam in a common pool, so telling them anything about the exam might lower your final course grade.

Pledge: On my honor, I have neither given nor received unauthorized aid on this examination.

Signature: ______________________

Short Questions (5 points each, for a total of 40 points)

1. You attach a monitor to the network to observe the frames that "fly across" the network. The first, third, fifth, seventh, ... frames observed contain segments whose size is 1460 bytes. All other frames contain segments whose size is 588 bytes. What size TCP receive buffer, in bytes, has the server dedicated to the connection? Justify your answer.

2. In the pre-1987 TCP, why is ignoring round trip time (RTT) samples of segments that are retransmitted like "pouring gas on a fire" (quote due to Van Jacobsen), during situations in which the true RTT in the network suddenly spikes?

3. Suppose we were designing a network in which we want the size of images being sent over the network to shrink when the congestion control algorithm detects congestion. Which of the following compression algorithms would allow this: GIF and JPEG.

( GIF only ( JPEG only ( Both GIF and JPEG

Justification:

4. Which of the following congestion avoidance algorithms would it be feasible to use in the Internet, assuming that we do not modify the TCP/IP header formats but are willing to reprogram IP routers:

( RED ( DECbit ( both RED and DECbit ( neither RED nor DECBIT

Justification:

5. While looking through TCP code inside the operating system, I found the following line:

cwnd++; /* Increase data rate exponentially */

I guessed that cwnd stood for TCP’s congestion window, but the comment did not make sense. Can you clarify how incrementing a variable additively causes an exponential increase in data rate?

6. Wireless LANs transmit radio waves over air. The air space can be considered as a shared medium. So why did 802.11 come up with a new protocol for wireless networks - CSMA/CA instead of reusing CSMA/CD?

7. What is the conceptual difference between subnetting and CIDR (supernetting)?

8. Give two advantages of using small fixed sized cells in real-time networks like ATM as opposed to using variable sized packets.

Long Problems (12 points each, for a total of 60 points)

1. [Each subpart, 2 points] Upon graduation from Virginia Tech, you take a job as a Network Designer for a hot new company, Startups-R-Us. They want to design a new line of network hardware using all new (and non-standard) protocols for a new, world-wide private network. The hardware will be used for the following traffic:

• Two-way, uncompressed video conferencing.

• Two-way, uncompressed voice calls.

• There will be no traffic on the network except the previous two.

• Every conference or voice call will connect people that are in different continents.

For each of the following items, check one box to indicate which option is the best. State any assumption you make (assumptions may not be needed, but it helps to know what you were thinking when grading). Justify your answer with two or fewer sentences:

a) Use fixed or variable frame size in data link layer?

( Fixed frame size ( Variable frame size

Assumptions (if any):

Justification:

b) Use small or large (maximum if you answered "variable" in (a)) frame size in data

link layer?

( Small packet size ( Large packet size

Assumptions (if any):

Justification:

c) Use connection-oriented or connection-less network layer?

( Connection-oriented ( Connection-less

Assumptions (if any):

Justification:

d) Use resource allocation or congestion control in network and/or transport layer?

( Resource allocation ( Congestion control

Assumptions (if any):

Justification:

e) Use positive acknowledgement and retransmission?

( Yes ( No

Assumptions (if any):

Justification:

f) Use XDR in presentation layer?

( Yes ( No

Assumptions (if any):

Justification:

2. [Each subpart, 3 points] Consider the use of Remote Procedure Calls (RPCs) to deliver Web pages from Web servers to clients. Suppose Web servers had a procedure called read(...), which Web browsers could call to retrieve a Web page.

a) Suppose a user enters into a Web browser the Web location "". Does the browser pass the string "courses.cs.vt.edu" as an argument to read(...)? Justify your answer.

b) Suppose a user enters into a Web browser the Web location . What would the browser do with the string "cs5516/index.html "?

c) [2 points] Which semantics would be best:

( Exactly once ( At least once

Justification:

d) Which is likely to perform better: The current way the Web works (using TCP) or RPC (assuming the textbook's implementation of RPC using BLAST, CHAN, and SELECT)? Or is there no clear winner – sometimes TCP is better, and sometimes RPC?

( TCP always wins ( Textbooks' RPC always wins ( No clear winner

Justification:

3. Imagine that you have instrumented the code of a TCP implementation that uses the post-1987 spec without the fast recovery option to write to disk the value of the congestion window (CWND) for a certain connection every time that it is assigned a new value (including the initial value). Assume that the receiver window advertisement is infinite.

Listed below are three traces. Each trace starts when the connection is first opened. For each trace, state whether the trace could have been produced by the post-1987 TCP spec. If you believe that the trace violates one of these algorithms, explain the violation in three sentences or less.

(For simplicity, we assume that every segment sent has an identical size, such as 1K bytes, and that the numbers below represent multiples of that size (e.g., "2" in the trace means congestion window size is 2K).

a) 1,2,4,8,16,8,4,8,9,10,11,12

( Could have been produced ( Could not

Justification:

b) 2,4,8

( Could have been produced ( Could not

Justification:

c) 1,2,4,8,16,32,1,2,4,8,16,32,64

( Could have been produced ( Could not

Justification:

4. [Each subpart, 6 points] As a network protocol designer who’s out to change the world, I came up with two alternative sliding window protocols for reliable transmission. My protocols are similar to other sliding window protocols. The sender has a sending window of size SWS and the receiver has a receiver window of size RWS. The maximum sequence number (MaxSeq) is the largest sequence number possible in a packet – sequence numbers lie in the range [0, MaxSeq –1], both inclusive. The sender can have upto SWS unacknowledged packets.

Consider the following scenarios. For each scenario, determine if the protocol works correctly for all combinations of packet/acknowledgment failures. Justify your answers with examples.

a) Assume a scenario with SWS = 3, RWS =1 and MaxSeq = 4. Suppose the receiver uses the following acknowledgement policy. If the sequence number on packet received is within the receiver window, send an acknowledgement with the sequence number set to the highest in sequence packet. If the sequence number on packet received is outside the receiver window, send an acknowledgement with the sequence number set to the sequence number of the packet received. The sender associates a timer with each packet. If the sender does not receive an acknowledgement for a packet, it retransmits the entire sending window. Receiver acknowledgments are inclusive.

b) Assume a scenario with SWS = 3, RWS = 3 and MaxSeq = 6. Suppose the receive uses the following negative acknowledgement policy. If the sequence number on the packet received is the next expected sequence number, the receiver does nothing. If the sequence number of the packet received is not the next expected sequence number, the receiver buffers the packet and sends a NACK with the sequence number set to the expected sequence number. The receiver can buffer upto RWS packets. The sender associates a timer with each packet. If the sender does not receive a NACK within the timeout interval, it assumes that the transmission was successful and advances the sending window. On receiving a NACK for a sequence number, the sender resends the packet and restarts its associated timer.

5. Ethernet networks use a spanning tree to generate a loop free topology of the network. Data is only transmitted on links that belong to the spanning tree. All other links are blocked and no data is transmitted or received on them. To detect link failures, the root of the spanning tree periodically sends HELLO messages over the spanning tree. Any switch that receives a HELLO message sends it to its children and so on, until the HELLOs reach the leaves. If HELLO messages fail to arrive, the child assumes that the link leading to the root has failed and initiates the building of a new spanning tree.

a) [3 points] How does the spanning tree algorithm decide which switch should be the root of the spanning tree?

b) [6 points] For the network topology shown below, draw the corresponding spanning tree. The circles represent Ethernet switches and the numbers within the circles represent switch identifiers. Clearly indicate the root of the spanning tree.

[pic]

c) [3 points] If the link between switches 2 and 4 breaks, what is the effect on the transmission of HELLO messages and the construction of the new spanning tree?

Answers:

Short problems:

1. Buffer size=1460+588=2048 bytes.

This is because initially the window advertisement is 2048 bytes. The MSS is 1460 bytes if Ethernet is used, so the first frame contains 1460 bytes. Now suppose the receiver only sends acks for every other segment, to reduce overhead for acks. Then the sender has a remaining send window size of 2048-1460=588 bytes, so the second segment sent is 588 bytes. Suppose layer 5 at the receiver immediately remove all data received. Now the receiver sends on ack to acknowledge the first two segments, giving a window advertisement equal to the free buffer space, which is 2048 bytes.

2. True RTT increases when congestion increases. In response to congestion, hosts should reduce their rate of traffic injection. But when congestion develops, the estimated RTT is less than the true RTT, so losses occur, and thus hosts do not reduce but actually increase their injection rate.

Grading: -5 if no idea what is going on. –3 if student knows answer has something to do with congestion, but not sure what.

3. JPEG only: JPEG allows the compessed file size to vary depending on the coefficient matrix used during the quantization phase. However, the compressed size of a GIF image cannot be varied, since it simply replaces 3-byte colors by 1-byte along with a color map table, and then runs LZ.

Grading: -5 if marked GIF only. –3 if marked Both.

4. RED: DECbit requires routers to set a congestion bit in the packet header, which would require a modification to the IP header. RED requires no modification of the packet formats in TCP/IP.

Grading: -5 if marked DECbit only or "neither". –3 if marked "Both".

5. Whenever an ACK is received cwnd increments. The number of packets transmitted depends on cwnd. So initially cwnd = 1. When the first ack is received, cwnd becomes 2. So 2 packets are transmitted. When the two acks are received cwnd increments twice becoming 4. So the data rate grows exponentially.

Grading: -3 if the student knew EITHER that you increase cwnd once per ack OR that cwnd grows by powers of 2 (1,2,4,8), but did not combine both facts together.

6. Unlike wire based shared media, where a collision can be heard by all stations connection to the wire, not all wireless hosts can see each other. So a collision may not be seen by all stations. Since CSMA/CD assumes that all end-stations can hear a collision, it does not work in a wireless network.

Grading: -5 if no idea; -3 if student knew collisions were important but did not get full answer.

7. Subnetting is used within an administrative domain. It breaks an IP network (class A, B or C) class into smaller parts, which can now be managed more easily. For instance, a Class B can be broken into multiple class C’s. Supernetting combines multiple IP networks into a larger network. The aim here is to reduce the number of routing table entries in the backbone.

Grading: -2 if student knew that subnetting was dividing 1 class, and supernetting combining classes. –3 if student reversed subnetting and supernetting.

8. Any two of the following is correct:

(a) Fixed sized cells take equal amount of time to transmit. So queuing delay is bounded by the number of cells. Variable sized packets cause variable queuing delays which causes packet delay variation (jitter) for real time traffic

(b) For data sources like audio – periodic fixed data rate - it is easy to fill up a small fixed sized cell efficiently, rather than a large fixed sized cell or variable length packet.

(c) Small fixed sized cells face less latency going through the network. Large variable length packets can occupy an output line for a long time causing large delays.

(d) With a small fixed-sized cell, a switch could be built to yield higher performance that is possible with variable length or long packets, for example by allocating fixed-size buffers into which each cell is read, and then retrieving fields from cells in hardware in parallel.

Long problems:

1. Grading: -1 for each part if the wrong answer was given, but a good justification was provided. –2 if wrong answer given and justification was vague or incorrect.

a. Fixed frame size: All traffic is constant bit rate, so every video frame is fixed-size, and so there is no reason to use variable frame sizes.

b. Small: Need to carry two-way voice worldwide argues for small maximum frame sizes.

c. Connection-oriented: All traffic flows involve long-lived communication between a source/destination pair, justifying the overhead of connection establishment and release. Furthermore, since all traffic is constant bit rate, all traffic demands are known at call set-up time, just like the conventional voice network, and there is no advantage to a connection-less network's ability to route packets from the same flow over different links.

d. Resource allocation: Since all flows in the network are constant bit rate, all traffic demands are known at call set-up time, just like the conventional voice network.

e. No: The round-trip time is large because the source/destination pairs are on different continents. Because the video and voice are two-way, we cannot use buffering at the endpoints, and thus there is insufficient time to wait for a timeout period before sending a missing packet at the receiver. It would make more sense to use a forward error-correcting code.

f. No: The video or voice is binary data, so no format conversion is needed. An alternate justification is that XDR has no data types for video or voice data, so XDR is useless.

Grading: You could answer "yes" if you noted that XDR has encode/decode functions to handle octet streams that do not reformat the data, although this just adds overhead.

2.

a. No. The string "courses.cs.vt.edu" is the name of the host on which the remote procedure should be called. You could not use it as an argument to the RPC, because you need to know what machine to contact before calling the real procedure!

Grading: -3 if answered "Yes" and gave poor justification. –2 if answered "Yes" with good justification.

b. The browser should pass this string as the argument to the remote procedure call (e.g., 'read("cs5516/index.html")').

Grading: -3 if no idea what to do with string, -2 for any other answer where string was not passed as an argument to the call..

c. Because the read() procedure is not modifying Web pages, there is no penalty (other than server overhead) if read() is performed multiple times. Therefore "at least once" semantics are best, to avoid the more complex implementation of "exactly once" semantics.

Grading: -1 if "Exactly once" but good justification. –3 if "Exactly once" and poor justification.

d. No clear winner.

• RPC does save overhead of connection establishment/release, but if multiple requests for a URL are sent over the same TCP connection (persistent connections) then TCP does as well.

• RPC is synchronous, meaning sending thread must wait until Web page is returned before asking for another page. In contrast, a single-threaded client can open multiple TCP connections and retrieve multiple Uls simultaneously. However, RPC can get around this disadvantage if client is multi-threaded.

Grading: -1 if checked "TCP" or "Textbook's RPC" and give a good reason. –1 if checked "No clear winner" and gave poor justification. –3 if checked "TCP or "Textbook's" and gave poor justification.

3. Grading: each sub-part worth 4 points.

a. Could not: CWND, when reduced, must take the value 1. 16->8 violates this.

-2 if answered "could" and missed the 16->8 violation.

b. Could not: CWND must initially have value 1, not 2.

Grading: In the 9am section, if the student answered "could" and thought that the initial value of CWND was not written as part of the trace (because the original problem wording said that only changes to CWND were written), then do not deduct points. (In the 1pm section, the correction was written on the blackboard.)

c. Could not: SSTHRESH is set to CWND/2 whenever CWND is reset to 1. Thus SSTHRESH must be 32/2=16 when CWND goes from 32 to 1. Hence CWND can increase as follows: 1,2,4,8,16. However, CWND must go from 16 to 1/16th afterwards (not to 32, as show in the trace).

-2 if …………..

4. Grading: It is sufficient to give one counterexample to show that an algorithm does not work.

a. Protocol (a) does not work correctly. Consider the following example. Suppose sender sends seq no.s 0, 1 and 2. Packets 0 is received correctly, so receiver sends an ACK for 0. Receiver is expecting packet 1. Packet 1 is lost and packet 2 is received. Since packet 2 is outside the receiver window, the receiver ACKs it, but it ACKs it with seq no. 2. The sender receives this ACK and thinks that all packets were received successfully. The problem is with the bad ACK policy at the receiver. It should ACK out os sequence packets with the highest in sequence packet number. Instead it ACKs with the received packet sequence number.

Grading: Some people won't understand the "acks are inclusive" statement, not realizing that this was the same as the term "cumulative ack".

b. Protocol (b) does not work correctly. Consider the following example. Suppose the sender only had 3 packets to send. It sends seq nos. 0, 1, 2. Packet 2 is lost and the receiver sends a NACK, but the NACK is lost. Sender eventually times out and assumes that the packets were transmitted correctly. Since no more packets are transmitted, the receiver never sends another NACK. Note that no value for sender timeout can fix this problem. Also NACK’s are not acknowledged, so loss of NACKs can only be recovered if there are more packets to transmit.

Grading: Some people may interpret "the receiver does nothing" literally, and not realize that the receiver will buffer packets that are within the receiver window

5.

a. The switch with the lowest switch identifier in the entire network should be the root of the spanning tree.

b.

[pic]

Grading: If they do not answer part a correctly, then any correct spanning tree should be accepted for credit.

c. Breaking the link between 2 and 4 has no effect on HELLO messages. Note that the link between 2 and 4 is blocked, so HELLO messages are never transmitted over it in the first place. Failure of that link cannot even be detected by the HELLO message mechanism.

Grading: Answer to c depends on what they drew for b.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download