ECS173A代做、Computer Networks代写、代做Java，c++，Python程序设计

日期：2020-08-02 08:04

EEC152A/ECS173A - Computer Networks Summer Session I 2020

24-hour take-home Final Assessment: July 30, 2020

Duration: 24 hours (July 30, 1:30pm - July 31, 1:30pm)

a) Use the supplementary document (.docx file) provided with this exam as your answer

sheet. You can edit this document to include your answers. Submit a .pdf file.

b) The answers should be typed. For diagrams and long calculations, you may hand-write

your answers but make sure they are readable.

c) Submit your answer file in Gradescope (similar to Homeworks). No late submission

allowed. Start the submission process early; do not wait till last minute.

d) Be sure to sign the statement of academic integrity in the following page.

e) This assignment is open book, open notes. Discussion with peers in any form is not

allowed and plagiarism will not be tolerated.

f) If you are using materials from other sources (e.g., book or online resources), do not

directly copy; write in your own words. Cite any source.

g) Justify your answers by qualitative or quantitative arguments or illustrations. Write

answers briefly and precisely. Excessive description only confuses the reader.

h) Show your reasoning clearly. If your reasoning is correct, but your final answer is

wrong, you will receive partial credit. If you just show the answer without reasoning,

and your answer is wrong, you may receive no points at all.

Good luck!

Do not write in this box

Question 1 2 3 4 5 6 7 Total

Points 20 20 20 15 15 25 15 130

Score

Sifat Ferdousi ECS152A/EEC173A SS1’20

2

Statement of academic integrity (please sign below)

As a student at UC Davis, I hold myself to a high standard of integrity, and by

signing/accepting the statement below I reaffirm my pledge to act ethically by

honoring the UC Davis Code of Academic Conduct. I will also encourage other

students to avoid academic misconduct.

I acknowledge that the work I submit is my individual effort. I did not consult with

or receive any help from any person or other source. I also did not provide help

to others. I may work with others only if the instructor gave specific instructions,

and only to the extent allowed by the instructor.

I understand that suspected misconduct on this assignment/exam will be

reported to the Office of Student Support and Judicial Affairs and, if established,

will result in disciplinary sanctions up through Dismissal from the University and

a grade penalty up to a grade of “F” for the course.

I understand that if I fail to acknowledge or sign this statement, an instructor may

not grade this work and may assign a grade of “0” of “F”.

Signature (sign/type above this line)

Sifat Ferdousi ECS152A/EEC173A SS1’20

3

Problem 1 [20 points]

In each of the following questions, justify your answers by qualitative or quantitative arguments

or illustrations. Answer briefly and precisely.

(a) [4 points] Suppose a computer is moved from one department to another. Does its

physical address need to change? Does the IP address need to change? Why or why not?

(b) [4 points] Network administrators must often choose between switches and routers when

installing an interconnection device. When should an institutional network (for example, a

university campus network or a corporate campus network) use switches, and when

should it use routers?

(c) [4 points] How does the local MAC-layer retransmission help enhance the throughput

performance of the end-to-end TCP connection?

(d) [4 points] Why do HTTP and SMTP run on top of TCP rather than UDP? Why do DNS and

DHCP run on top of UDP rather than TCP?

(e) [4 points] When the loss rate is high and round trip time is long, which one is better: GoBack-N

or Selective-Repeat? Why?

Sifat Ferdousi ECS152A/EEC173A SS1’20

4

Problem 2 [20 points]

(a) [10 points] Consider an end system A connected to a router by a link of rate R1 = 1 Mbps; and

this router is connected by the Internet to another router, which is connected to an end

system B by a link of rate R2 = 10 Mbps. Let the round-trip time (RTT) between the two end

systems be 100 milliseconds. This problem will study the TCP performance between the two

end systems.

1. [2 points] If the congestion window (cwnd) is static and always fixed at W = 1000 bytes,

what is the end-to-end throughput?

2. [2 points] Now consider the case where cwnd follows a saw-tooth pattern: with linear

increase under no congestion. Congestion always occurs when cwnd exactly reaches a

peak of W = 1000 bytes and cwnd is halved to W/2 when congestion occurs. Draw the

saw-tooth pattern of cwnd.

3. [2 points] For part 2, what is the end-to-end throughput?

4. [2 points] Can we increase the throughputs in parts 1 and 3 by increasing R1 to 10 Mbps?

Justify.

5. [2 points] What is rwnd? What flow-control assumption is made in the above

calculations?

(b) [10 points] Imagine a TCP session over wireless where the congestion window is fixed at 5

segments (congestion control is turned off and no fast retransmits). Segments may get lost

but are not reordered. The receiver has infinite buffer and it sends an acknowledgment as

soon as it receives a segment, i.e., acknowledgments are not deferred. Similarly, sender

transmits a segment as soon as it is allowed to. Each segment carries 1000 bytes and the time

to transmit a segment is 2 ms. Assume that transmission of ACK takes negligible time. Note

that the retransmission timer for a segment is started after the last bit of the segment is sent.

Assume Go-Back-5, and cumulative ACK are used.

1. [4 points] Suppose two data segments with byte sequence numbers 3000 and 15000 are

lost once during the transmission. How many segments get retransmitted under each of

the following conditions?

A. Round trip time = 100 ms, Timeout = 101 ms

B. Round trip time = 100 ms, Timeout = 152 ms

2. [4 points] Suppose acknowledgments corresponding to the above data segments are lost

instead of the data segments. How many segments get retransmitted under the above

conditions?

A. Round trip time = 100 ms, Timeout = 101 ms

B. Round trip time = 100 ms, Timeout = 152 ms

3. [2 points] Briefly describe how TCP is partly GBN and partly SR?

Sifat Ferdousi ECS152A/EEC173A SS1’20

5

Problem 3 [20 points]

(a) [5 points] Consider the operation of a learning switch in the context of a network in which 6

nodes labeled A through F are star connected into an Ethernet switch.

Suppose that (i) B sends a frame to E, (ii) E replies with a frame to B, (iii) A sends a frame to B, and

(iv) B replies with a frame to A. The switch table is initially empty. Show the state of the switch

table and after each of these events. For each of these events, identify the link(s) on which the

transmitted frame will be forwarded.

Event Switch Table Link(s) on which transmitted frame will

MAC Address Interface be forwarded for each event.

(i) B 2

(ii) E

(iii) A

(iv)

(b) [15 points] You’d like to send the data bits 1011010010 using the Generator polynomial.

1. [5 points] What is the degree of the Generator polynomial? What is the CRC code

generated by the sender? Show each step.

2. [5 points] What bits are transmitted to the receiver? Show the receiver’s side of the

calculation. Show each step.

3. [5 points] What is the probability that there were errors in the transmission and the

receiver doesn’t detect them?

Sifat Ferdousi ECS152A/EEC173A SS1’20

6

Problem 4 [15 points]

(a) [9 points] We explore how to set the (configurable) link weights in link-state routing protocols

like OSPF and IS-IS inside a single Autonomous System (AS) to achieve AS-wide goals.

1. [3 points] How should the network operators set the link weights if their goal is to

minimize the number of hops each packet traverses to reach its destination? Justify your

answer.

2. [3 points] How should the operators set the link weights to minimize the end-to-end delay

the traffic experiences? Assume the network is lightly loaded, so queuing delay is

insignificant.

3. [3 points] How should the network operators set the link weights to combine different

metrics (e.g., cost, delay, congestion, etc.) into one “weight value” which will be used by

the routing algorithms to find the best path?

(b) [6 points] In the picture below, the nodes are routers, the edges are links, and the integers

correspond to the link weight on each direction of the link. The arrows on the edges to show

the shortest path from every node to the destination node d.

Suppose the link f-e is overloaded with traffic. Identify a single weight change (on just one link)

that would divert traffic from source f to destination d away from the f-e edge without affecting

the path between any other source-destination pairs. Avoid any reliance on how routers choose

between multiple paths with the same (smallest) cost.

Sifat Ferdousi ECS152A/EEC173A SS1’20

7

Problem 5 [15 points]

(a) [5 points] In each of the following questions, mark all the statements that are correct.

1. Which of the following statements is/are FALSE about routing protocols?

i. When an OSPF router sends its link state information, it is sent only to those nodes

that are directly attached neighbors.

ii. A dynamic algorithm can be run in direct response to link cost changes.

iii. When a BGP router receives an advertised path from its neighbor, it must add its own

identity to the received path and then send that new path on to all of its neighbors.

iv. LS is more robust (against router malfunction) than DV because in LS, a node computes

only its own forwarding tables whereas in DV, each node’s table is used by others.

2. Which of the following is/are FALSE about P2P applications?

i. The server process must first be running.

ii. DNS provides name to IP address mapping through a P2P model.

iii. When the number of users, N, is large, P2P performance (e.g., in terms of file

distribution time) tends to outperform client-server model.

iv. When the number of users, N, is small, P2P performance (e.g., in terms of file

distribution time) tends to under-perform client-server model.

(b) [10 points] There are 11 terms in List A. Match them with the appropriate description in List B.

As an example, the matching for the first term in List A is shown.

List A

Number Item Your Response Here

Sifat Ferdousi ECS152A/EEC173A SS1’20

8

List B

(Note: There are extra items in List B which don’t match with any term in List A.)

Number Description

1 A program which initiates a connection with a server

2 Transport protocol with minimal services

3 Protocol for reliable data transfer between end hosts

4 Router that hides the details of a local network from the rest of the Internet

5 Algorithm that calculates the shortest path between end hosts

6 Protocol that allows various different autonomous systems to communicate

7 Method to code digital data with an analog signal

8 Protocol using which a host obtains its IP address

9 Method by which an end host determines the IP address from a host name

10 Method for congestion control in TCP

11 Method by which bandwidth is divided into frequency bands for communication

12 Protocol that allows a node to obtain the MAC address of an interface, knowing its IP address

13 Method for congestion control in TCP

14 Part of a router which implements layers 1-3 functionality and is used to connect to other

routers/switches/end systems

15 Part of a router that connects its CPU, switch fabric, and line cards

16 Countdown method to ensure that a packet does not circulate in the network forever

Sifat Ferdousi ECS152A/EEC173A SS1’20

9

Problem 6 [25 points]

Download the zip file http://gaia.cs.umass.edu/wireshark-labs/wireshark-traces.zip and extract

the following files:

a. http-ethereal-trace-2

b. http-ethereal-trace-1

c. dhcp-ethereal-trace-1

Once you have downloaded these trace files, you can load it into Wireshark and view the trace

using the File pull down menu, choosing Open, and then selecting the required trace file.

Start with http-ethereal-trace-2 file, answer the following questions (write answers and also

provide screenshots of the fields you are analyzing when necessary). Only for specific subparts,

you will be asked to analyze a different trace file.

Analysis

1. [0.5x4] How many different protocols are reported? What are they?

2. [1] General question (no analysis required): What is SNMP? Answer briefly in one line.

3. [0.25] Of all the frames captured in the trace, how many are HTTP frames?

4. [0.5x2] For the HTTP request/response messages, what is the user IP address? What is the

server IP address?

5. [0.25x2] How many HTTP request messages? How many HTTP response messages?

6. [0.5x2] What version of HTTP is running at the user’s browser? What browser type is the

user using?

7. [0.5] What is the server host name?

8. [0.5] What is the user requested object? Give the file name.

9. [0.5] Is the object returned? How do you infer this information? Give the associated status

code(s).

a. [0.5] Answer this question for http-ethereal-trace-1 file also - is/are the user requested

object(s) in this trace returned? Give associated status code(s).

Refer back to http-ethereal-trace-2 file for the following questions:

10. [0.25x2] Which frames in the trace (give the frame number) are the ARP frames? Which

frame is the query frame?

a. [1] General question (no analysis required): Is ARP a link-layer protocol or a networklayer

protocol? Answer briefly in one line.

b. [1] General question (no analysis required): Do net administrators create ARP tables?

Answer briefly in one line.

11. [0.5] What is the MAC addresses of the user?

12. [0.5x2] When the user is sending an ARP query, it is looking for a MAC address

corresponding to which IP address? To what type of network device do you think this IP

address belongs to?

Sifat Ferdousi ECS152A/EEC173A SS1’20

10

Refer to dhcp-ethereal-trace-1 file for the following questions:

13. [0.5] Analyze the DHCP Offer message. Recall what information are generally included in

DHCP Offer - list them. Which particular information in the DHCP Offer message in this

trace helps to verify your answer in 12?

a. [0.5x2] What is the IP address of the DHCP server? Is the DHCP server integrated with

the router? How do you infer this information?

b. [0.5x2] What is the IP address offered by the DHCP server to the requesting user in this

DHCP Offer message? What is the lease time?

Refer back to http-ethereal-trace-2 file for the following questions:

14. [0.25x3] Which frames in the trace (give frame number) denote the TCP three-way

handshake?

15. [0.5x2] In the TCP SYNACK segment, how many flag bits are set to 1? Which one(s)?

16. [0.25x2] What are the Seq#, ACK# in the third leg of the three-way handshake?

17. [0.5] What is the maximum segment size?

18. [0.5x2] What is the initial user window size value? Is it static?

19. [0.5] What does the window size in 18 refer to: congestion window or receiver window?

a. [2] General question (no analysis required): What is bandwidth-delay product? How is it

related to TCP window size? Answer briefly.

20. [0.5] Does this trace contain TCP connection termination?

21. [0.5x4] If you want to identify this TCP connection using the 4 tuples, what are the values?

22. [2] As per this analysis, do we know the MAC address of the HTTP server? Is it

00:06:25:da:af:73? Justify your answer.

Sifat Ferdousi ECS152A/EEC173A SS1’20

11

Problem 7 Bonus Question [15 points]

(a) [12 points] Given the sequence of events listed below, plot the evolution of TCP's congestion

window. Assume TCP Reno. The x-axis is Time (in RTT) and y-axis is Congestion Window Size

(in segments). Put the plot in your answer script. Make sure your plot has gridlines and all the

data points are marked. Your plot should look something like Figure 3.58 in the textbook.

Starting at t = 1, the initial value of cwnd is 1 and TCP enters the slow start phase with the

initial ssthresh value of 8.

Give the range/interval of time during which TCP is in slow start (SS), congestion avoidance

(CA), and fast recovery (FR) phases or clearly label on the plot the different phases throughout

the evolution (either by simple marking or shading). Indicate the new value of ssthresh

whenever the value of ssthresh changes.

When we say, an event occurs after t = n (but before t = n + 1), the effect of the event (e.g.,

cwnd update, phase change, etc.) will be represented from t = n + 1.

For the fast recovery phase, apply the Fast Recovery algorithm. You can assume that after a 3-

DupAck, another duplicate ACK is received and then a new ACK is received in the subsequent

RTT. Of course you can make other assumptions; in that case, state them clearly.

Note: SS phase will advance till the next nearest cwnd value in its exponential curve past the

ssthresh value unless cwnd value matches exactly ssthresh value. E.g., if ssthresh =

2, SS will end at cwnd = 2, if ssthresh = 2.5, SS will end at cwnd = 4, and so on.

Sequence of events:

? After t = 10, a timeout event occurs. What is the value of cwnd at t = 10? Indicate

ssthresh.

? After t = 14, another timeout event occurs. Indicate ssthresh. What is the transition in

phase?

? After t = 29, a 3-DupAck event occurs. At t = 30, what is the value of cwnd? Indicate

ssthresh.

? After t = 34, a timeout event occurs. What is the value of cwnd at t = 34? Indicate

ssthresh.

? After t = 38, a 3-DupAck event occurs. At this point, what was the current phase? What does

this phase transition to? Indicate ssthresh.

? At t = 45 (end of our plot), what is the value of cwnd and what is the current phase?

(b) [3 points] What does a loss event indicated by 3-DupAck tell you about the underlying

network (in terms of congestion scenario)? For a heavily-loaded network, which loss event is

more likely to happen: a timeout or a 3-DupAck? Why does TCP Reno treat 3-DupAck

differently than TCP Tahoe?