Homework 1 Solution

Description

All homework assignments must be completed by each student individually. Any copying of someone else’s work, or misrepresentation of other work as your own, will be grounds for failing this assignment or the course.

Penalty for late work is 20 points per day late.

There are 8 questions; make sure you answer all these questions.

1. An application transmits data at a steady rate (for example, the sender generates an L-bit unit of data every t time unit, where t is small and fixed). Also, when the application starts, it will continue running for a relatively long period of time. Answer the following questions, briefly justifying your answers:

1. 1. Would a packet-switched or a circuit-switched network be more appropriate for this application? Why?

1. 2. Suppose that a packet-switched network is used and the only traffic in this network comes from such applications as described above. Furthermore, assume that the sum of the application data rates is less than the capacities of each and every link. Is some form of congestion control needed? Why?

2. Suppose users share a 5 Mbps link. Also suppose each user requires 200 kbps when transmitting, but user transmit only 5 percent of the time.

1. 1. When circuit switching is used, how many users can be supported?

1. 2. For the remainder of this problem, suppose packet switching is used. Find the probability that a given user is transmitting.

1. 3. Suppose there are 75 users. Find the probability that at any given time, exactly k users are transmitting simultaneously. (Hint: Use the binomial distribution.)

1. 4. Find the probability that there are 35 or more users transmitting simultaneously.

3. Consider sending real-time voice from Host X to Host Y over a packet-switched network (VoIP). Host X converts analog voice to a digital 32 kbps bit stream on the fly. Host X then groups the bits into 64-byte packets. There is one link between Host X and Y; its transmission rate is 4 Mbps and its propagation delay is 5 msec. As soon as Host X gathers a packet, it sends it to Host Y. As soon as Host Y receives an entire packet, it converts that packet’s bits to an analog signal. How much time elapses from the time a bit is created (from the original analog signal at Host X) until the bit is decoded (as part of the analog signal at Host Y)?

4. Consider a packet of length B which begins at end system A, travels over three links to a destination end system. These three links are connected by two packet switches. Let d_i, s_i, and R_i denote the length, propagation speed and the transmission rate of link i, for i=1, 2, 3. The packet switch delays each packet by d_proc. Assuming no queuing delays, in term of d, s_i, and R_i, (i=1, 2, 3), and B, what is the total end-to-end delay for the packet? Suppose now the packet is 2,000 bytes, the propagation speed on the three links is 2.3 x 10⁸ m/s, the transmission rates of all three links are 4 Mbps, the packet switch processing delay is 2 msec, the length of the first link is 6,000 km, the length of the second link is 8,000 km, and the length of the third link is 3,000 km. For these values, what is the end-to-end delay?

4. Suppose a packet switch receives a packet and determines the outbound link to which the packet should be forwarded. When a particular packet arrives, one other packet is one fifth done being transmitted on this outbound link and six other packets are waiting to be transmitted. Packets are transmitted in order of arrival. Suppose all packets are 4,000 bytes and the link rate is 10 Mbps. What is the queuing delay for the packet? More generally, what is the queuing delay when all packets have length L, the transmission rate is R, k bits of the currently-being transmitted packet have been transmitted, and s packets are already in the queue?

4. Suppose there are M paths between the server and the client. No two paths share any link. Figure 1 shows only one of the M paths, i.e. Path i (where i = 1, …, M) which consists of N links with transmission rates R₁ⁱ , R₂ⁱ , …, R_Nⁱ . If the

server can only use one path to send to the client, what is the maximum throughput that the server can achieve? If the server can use all M paths to send data, what is the maximum throughput that the server can achieve?

Figure 1. Throughput for a file transfer from server to client

7. Consider the queuing delay in a router buffer. Let Q denote the traffic intensity; i.e. Q = Lλ/R, where all packets consist of L bits, λ is the average rate packets arrives at the queue in packets/sec. and R is the transmission rate in bits/sec.

Suppose that the queuing delay takes the form ₍₎ for Q < 1.

1. Provide a formula for the total delay, i.e. the queuing delay plus the transmission delay.

2. Plot the total delay as a function of L/R.

3. Suppose µ denote the link’s transmission rate in packets/sec. Derive a formula for the total delay in terms of λ and µ.

2

8. In modern packet-switched networks, the source host segments long, application-layer messages (for example an image or a music file) into smaller packets and sends the packets into the network. The receiver then resembles the packets back into the original message. We refer to this as message segmentation. Figure 2 illustrates the end-to-end transport of a message with and without message segmentation. Consider a message that is 15×10⁶ bits long needs to be sent from source to destination in Figure 2. Suppose the transmission rate of each link is 8 Mbps. Ignore propagation, processing and queuing delay.

Figure 2. End-to-end message transport: (a) without message

segmentation; (b) with message segmentation

1. Consider sending the message from source to destination without message segmentation. How long does it take to move the message from the source to the first packet switch? Keeping in mind that each switch uses store-and-forward packet switching, what is the total time to move the message from source host to destination host?

2. Now suppose that the message is segmented into 10,000 packets, with each packets being 1,500 bits long. How long does it take to move the first packet from the source host to the first switch? When the first packet is being sent from the first switch to the second switch, the second packet is being sent from the source host to the first switch. At which time will the second packet be fully received at the first switch?

3. How long does it take to move the file from source host to destination host when message segmentation is used? Compare this result with your answer in part (a) and comment.

4. Discuss the drawbacks of message segmentation.

3