CSCI5273 PS1 Solutions PDF

Preview

Summary

It is the solution of PS1...

Description

Problem Set #1 Assume that 1 Kbps = 103 bits/sec, 1 Mbps = 106 bits/sec, 1 Gbps = 109 bits/sec, and 1MB = 106 x 8 bits. The capital ‘B’ typically means ‘byte’ while the lowercase ‘b’ indicates ‘bit’.

1. (3pts) What advantage does a circuit-switched network have over a packetswitched network? A circuit-switched network can guarantee a certain amount of end-to-end bandwidth for the duration of a call. Most packet-switched networks today (including the Internet) cannot make any end-to-end guarantees for bandwidth. 2. (3pts) What advantage does TDM have over FDM in a circuit switched network? FDM requires sophisticated analog hardware to shift signal into appropriate frequency bands. TDM is simple to implement but it needs clock synchronization among nodes.

3. (8pts) We consider sending real-time voice from Host A to Host B over a packet-switched network. Host A converts analog voice to a digital 65kbps bit stream and send these bits into 56-byte packets. There is one link between Hosts A and B and the transmission rate is 1 Mbps and its propagation delay is 20 msec. As soon as Host A gathers a packet, it sends it to Host B. As soon as Host B receives an entire packet, it converts the packet’s bits into an analog signal. How much time elapses from the time a bit is created (from the original analog signal at Host A) until the bit is decoded (as part of the analog signal at Host B)? Consider the first bit in a packet. Before this bit can be transmitted, all of the bits in the packet must be generated. This requires

(56 x 8) / (65 x 103) = 0.006892sec The time required to transmit the packet is (56 x 8) / 1 x 106 = 0.000448 sec Propagation delay = 0.02 sec. The delay until decoding is 0.006892 sec + 0.000448 sec + 0.02 sec = 0.02734 sec = 27.34 msec A similar analysis shows that all bits experience a delay of 27.34 msec. Note that the answer could include the decoding time at Host B as well. 4. (12pts) Consider a Go-Back-N sliding window algorithm (1 packet is 250 bytes long) running over a 100km point-to-point fiber link with bandwidth of 100 Mbps. a. Compute the one-way propagation delay for this link, assuming that the speed of light is 2 x 108 m/s in the fiber. 100 km / (2 x 108 m/s) = 0.0005 sec = 0.5 msec b. Suggest a suitable timeout value for the algorithm to use. List factors you need to consider. Solution 1: If we assume the transmission time of acknowledgement packets is similar to the data packet, the timeout needs to be greater than 2 x (packet transmission delay + propagation delay) = 2 x ((250 x 8)/(1x108) + 0.5 ms)) = 2 x (0.02ms + 0.5ms) = 1.04 ms Solution 2: If we assume the transmission time of the acknowledgement packets is negligible, the timeout could be the transmission time of the packet and forward and reverse propagation delay. Thus, (250 x 8)/(1x108) + 2 x 0.5ms = 1.02ms

c. Suggest N to achieve 100% utilization in this link (consider one-way delay). Bandwidth x one-way delay = 1x108 x 0.0005 = 50000 bits = 50000/ (8 x 250) = 25 packets 5. (12pts) Suppose a 1-Gbps point-to-point link is being set up between the Earth and a new lunar colony. The distance from the moon to the Earth is approximately 385,000 km, and data travels over the link at the speed of light—3×108 m/s. a. Calculate the minimum RTT for the link. Assume that the packet transmission time is negligible. The minimum RTT = (2 x distance from the moon to the Earth) / (speed of light) = (2 x 385,000,000 m) / (3 x 108 m/sec) = 2.57 sec b. Using the RTT as the delay, calculate the delay × bandwidth product for the link. BDP = bandwidth x delay = 1Gbps x 2.57 sec = 2.57 x 109 bits c. What is the significance of the delay × bandwidth product computed in (b) ? This is an open-ended question. Your answer is correct as long as it includes “number of bits/bytes/packets in flight.” BDP - This represents the amount of data the sender can send before it would be possible to receive a response. In data communications, bandwidth-delay product refers to the product of a data link's capacity (in bits per second) and its round-trip delay time (in seconds). The result, an amount of data measured in bits (or bytes), is equivalent to the maximum amount of data on the network circuit at any given time, i.e., data that has been transmitted but not yet acknowledged.

6. (12pts) Host A wants to send a 1,000 KB file to Host B. The Round Trip Time (RTT) of the Duplex Link between Host A and B is 160ms. Packet size is 1KB. A handshake between A and B is needed at the beginning and at the end of data transmission, which takes 2xRTT for each. Calculate the total required time of file transfer in the following cases. The transfer is considered complete when the acknowledgement for the final packet reaches A. a. The bandwidth of the link is 4Mbps. Data packets can be continuously transferred on the link. Total time = hand shake at the beginning + transmit time for 1000 packets + RTT + hand shake at the end = 2 x RTT + 1000 KB / 4 Mbps + RTT + 2 x RTT = 5 x 160ms + (1000 x 1000 x 8) / (4 x 1000 x 1000) = 800ms + 2secs = 2.8secs b. The bandwidth of the link is 4Mbps. After sending each packet, A need to wait one RTT before the next packet can be transferred. Total time = hand shake at the beginning + (transmit time for 1 packet + RTT) x 1000 packets + hand shake at the end = 2 x RTT + 2secs + RTT x 1000 + 2 x RTT = 320ms + 2secs + (160ms x 1000) + 320ms = 162.640 secs c. Assume we have “unlimited” bandwidth on the link, meaning that we assume transmit time to be zero. After sending 50 packets, A need to wait one RTT before sending next group of 50 packets. Total time = hand shake at the beginning + [(transmit time + RTT) for 50 packets] x 20 + hand shake at the end = 2 x RTT + (0ms + RTT) x 20 + 2 x RTT = 320ms + (160ms x 20) + 320ms = 3.840 secs

d. The bandwidth of the link is 4Mbps. During the first transmission A can send one (21-1) packets, during the 2nd transmission A can send 22-1 packets, during the 3rd transmission A can send 23-1 packets, and so on. Assume A still need to wait for 1 RTT between each transmission. 1000 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 489 Between each transmission it requires 1 RTT, so we need 10 RTTs Total time = hand shake at the beginning + transmission time for 1000 packets + 10 RTT + hand shake at the end = 2 x RTT + 2secs + 10 RTT + 2 x RTT = 14 x 160ms + 2secs = 4.24 secs 7. (5pts) Determine the width of a bit on a 10 Gbps link. Assume a copper wire, where the speed of propagation is 2.3 108 m/s. The width of a bit on a 10 Gbps link = speed / bandwidth = 2.3 x 108 m/s / (10 x 109 bit/s) = 0.023 m/bit = 2.3 cm/ bit A single bit has a width of 2.3 cm on the wire. 8. (12 pts) Suppose two hosts, A and B, are separated by 20,000 kilometers and they are connected by a direct link of R=1Gbps. Suppose the propagation speed over the link is 2.5 x 108 meters/sec. a. Calculate the bandwidth delay product (BDP) of the link. BDP = 1 x 109 bps x ((20,000 x 103 m) / (2.5 x 108 meters/sec)) = 80,000,000 bits b. Consider sending a file of 800,000 bits from Host A to Host B as one large message. What is the maximum number of bits that will be in the link at any given time? min (file size, BDP) = 800,000 bits c. What is the width (in meters) of a bit in the link?

(2.5 x 108 meters/sec) / (1 x 109 bits/sec) = 0.25 meters d. Suppose now 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 acknowledgement 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? Propagation delay = (20,000 x 103 m) / (2.5 x 108 meters/sec) = 0.08sec Transmission time per packet = 40,000/1 x 109 = 0.00004 sec Then the total time = 20 x (transmission time per packet + 2 x propagation delay) = 20 x (0.00004 + 0.16) = 3.2 sec 9. (12 pts) Suppose there is a 10 Mbps microwave link between a geostationary satellite and its base station on Earth. Every minute the satellite takes a digital photo and sends it to the base station. Assume a propagation speed of 2.4 x 108 meters/sec. Geostationary satellite is 36,000 kilometers away from earth surface a. What is the propagation delay of the link? Propagation delay = distance / speed = 36000 km / 2.4 x 108 = 150 msec b. What is the bandwidth-delay product, R x (propagation delay)? 150 msec x 10 x 106 = 1500000 bits = 1.5 Mbits c. Let x denote the size of the photo. What is the minimum value of x for the microwave link to be continuously transmitting? 10 Mbits for 1 second and so 600 Mbits for 60 secs. 600 Mbits / 8 = 75 Mbytes

10. (6pts) Explain collision domain and broadcast domain with respect to a hub, switch, and a router. Collision domain: It is the part of the network where packet collisions can occur. Broadcast domain: It is the part of the network in which a broadcast packet is forwarded, hence it dictates how far a broadcast packet can traverse. Hub: Combines collision domains. Each port in the hub is in the same collision domain. Thus, only one device can send a packet at a time. Switch: Separates collision domain (provide separate collision domains on each port) and combines broadcast domain. Router: Separates broadcast domains. 11.

(5pts)

Consider the following networked computers connected by Bridge X and Y. Bridge X has interface 1,2 and3. Bridge Y has interface 1 and 2. Assume at the beginning the address tables of Bridge X and Y are all empty. Write down the address tables of Bridge X and Y after the following communication finished. 1. 2. 3. 4. 5.

A send a packet to C B send a packet to D C send a packet to E E send a packet to A D send a packet to A

Figure 1 Bridge X

Address

12.

Bridge Y

Interface

Address

Interface

A

1

A

1

B

1

B

1

C

2

C

1

E

3

E

2

D

3

D

1

(5pts)

Given the extended LAN shown in Figure 2, indicate which ports are not selected by the spanning tree algorithm. Note that the bridge with the smallest ID becomes a root.

Figure 2 Answer:

13. (5pts) Still considering Figure 2. If Bridge B1 suffers catastrophic failure. Again indicate which ports are not selected by the spanning tree algorithm.

14.

(6pts)

Consider the GBN protocol with a sender window size of N=4 and a sequence number range of 1,024. Suppose that at time t, the next in-order packet that the receiver is expecting has a sequence number of k. Assume that the medium does not reorder messages. Answer the following questions:

(a)

What are the possible sets of sequence numbers inside the sender’s

window at time t? Justify your answer. (2 pts) Here we have a window size of 𝑁 = 4. Suppose the receiver has received packet 𝑘 − 1, and has ACKed this packet and all other preceding packets. If all of these ACK's have been received by the sender, then the sender's window is [𝑘, 𝑘 + 𝑁 − 1]. Suppose next that none of the ACKs have been received by the sender. In this second case, the sender's window contains 𝑘 − 1 and the 𝑁 packets up to and

including 𝑘 − N. The sender's window is thus [𝑘 − 𝑁 , 𝑘 − 1_]. By these arguments, the senders window is of size 3 and begins somewhere in the range [𝑘 − 𝑁, 𝑘]. (b)

What are all possible values of the ACK field in all possible messages

currently propagating back to the sender at time t? Justify your answer. (2 pts) If the receiver is waiting for packet k, then it has received (and ACKed) packet k-1 and the N-1 packets before that. If none of those N ACKs have been yet received by the sender, then ACK messages with values of [k-N,k-1] may still be propagating back. Because the sender has sent packets [k-N, k-1], it must be the case that the sender has already received an ACK for k-N-1. Once the receiver has sent an ACK for k-N-1 it will never send an ACK that is less than k-N-1. Thus, the range of in-flight ACK values can be in the range [k-N-1, k1].

With the Go-Back-N protocol, is it possible for the sender to receive an ACK for a packet that falls outside of its current window? Justify your answer with an example. (2 pts) (c)

Yes, it is possible. Consider the following example scenario. Suppose the sender has a window size of 3 and sends packets 1, 2 and 3 at time t0. At t1, the receiver ACKs packets 1, 2 and 3. At t2 , the sender times out and resends 1, 2 and 3. At t3, the receiver receives the duplicates and re-acknowledges 1, 2 and 3. At t4 , the sender receives the ACKs that the receiver sent at and advances its window to packets 4, 5 and 6. Finally, at t5, the sender receives the ACKs that the receiver sent at t2 . These ACKs are outside its window....