Solutions for Homework 1 ======================== Ch1: --------------------- Q 13: (a) - 2.5 minimum RTT = 2 * (distance / speed) = 2 * (385000 * 10^3 / 3 * 10^8) = 2.566 sec (b) - 2.5 delayed bandwidth product = RTT * bandwidth = 2.566 * 100 Mb = 256.66 * 10^6 bits = 30.596 MB (c) - 2.5 data equal to delay bandwidth product will be in pipeline before sender can get any reply from receiver. (d) - 2.5 time for sending request = RTT / 2 time for data to be transferred = RTT / 2 + (25 MB / 100 Mb) so total time = RTT + (25 MB / 100 Mb) = 2.566 + 25 * 8 * 2^20 / 100 * 10^6 = 4.663 sec ---------------------- Q15: (a) - 3 latency of a single link = ( propagation delay + packet size/bandwidth) = 10 us + 5000 / 10 * 10^6 = 510 us total latency = 2 * 510 = 1020 us (b) - 3 total latency = 4 * latency of single link = 4 * 510 = 2040 us (c) - 4 cut-thru switch - latency for 1st switch will invlove only the time taken for 200 bits as it will start tranmitting data after receiving 200 biys.. so total latency = 10 us + 200 / 10 * 10^6 + 10 us + 5000 / 10 * 10^6 = 540 us ----------------------- Q16: Effective bandwidth (a) - 3 effective bandwidth = 10 Mbs as switches can send on one link and receive on another.. so after first packet the links will be utilized to the full. (b) - 4 A - S1 - S2 - S3 - B time needed to send a 5000 bit data packet = 2040 us (from 15 b) time needed to send ack = 4 * (10 us + 50 * 8 / 10 * 10^6) = 4 * 50 us = 200 us effective bandwidth = data sent / time taken = 5000 / 2240 * 10^-6 = 2.23 Mb/s (c) - 3 overnight shipment effective bandwidth = data sent / time taken = 100 * 650 MB / 12 hr = 100 * 650 * 8 * 2^20 / 12 * 60 * 60 = 12.621748 Mb/s -------------------------- Q 21: a) (5 points) Delay BW prod = 250 Bytes = Bw * delay => 250 bytes = 10Mbps * (c / (2* 10^8)) => c= 4000 m b) (5 points) Delay BW prod = 250 Bytes = Bw * delay => 250 bytes = 10Mbps * (c/(2 * 10^8) + (c / 100 ) * 10 bits/ 10Mbps) => c = 3333 m -------------------------- Q23: calculate the bandwidth necessary (a) - 2.5 bandwidth = 640 * 480 * 3 * 8 * 30 bits /second = 221.184000 Mb/s (b) - 2.5 bandwidth = 160 * 120 * 1 * 8 * 5 bits /second = .768 Mb/s (c) - 2.5 bandwidth = 650 MB / 75 min = 650 * 8 * 2^20 / 75 * 60 = 1.21168 Mb/s (d) - 2.5 amount of data = 8 * 10 * 72 * 72 * 1 bits time taken = amount of data / bandwidth = 8 * 10 * 72 * 72 / 14.4 * 10^3 = 28.8 s -------------------------------- Q26: (a) - 3 There is no need of sequence number as there is no confusion about duplication of packets or reordering of packets at receivers end. At a time there is only one packet in the network and it can never be lost. (b) - 3 yes, 2 bit sequence number is enough. even 1 bit will do. Cases: - A sends the packet to B and it's lost.. A will not get any ack and will resend the packet. - A sends the packet to B (seq no 0), B gets the packet but ack is lost. A will resend the packet the packet (seq no 0)...but now B is expecting seq no. 1. so when B will get seq no 0 again, it will know that ack has been lost. it will drop the packet and resend the ack. (c) - 4 as packets can arrive out of order, we need a mechanism to take care that different packets having same sequence number don't conflict. i.e. we shpuld have enough long sequence number so that there is no need of reusing a sequence number in 1 min time interval. --------------------- ch 2: Q 2: - 10 bit sequence: 1110 0101 0000 0011 4B/5B encoding: 11100 01011 11110 10101 --------------- Q 15: message : 11001001 CRC polynomial = x^3 + 1 divisor = 1001 (a) - 5 k = 3 1- zero extended message : 11001001 000 2 - divide 11001001 000 by 1001 : remainder is 011 so the message to be transmitted is 11001001011 (b) - 5 received signal - 01001001011 - divide received signal by 1001. remainder is not 0 that tells the receiver something wrong has happened. --------------- Q 19: a) (3 points) Propogation delay = (20 * 10^3) / (2 * 10^8) = 100 us b) (3 points) RTT = 2 * prop. delay = 200 us Timeout value >=200 usec Since its a point to point link, there wont be delays because of queueing or congestion at intermediate links. But there could be delays due to processing overhead at the receiver. (What was expected was a qualitative answer which describes the need for a timeout greater than RTT and bounded by the additional delay because of the recvr. processing. The exact numbers do NOT matter as long as they are reasonable.) c) (4 points total) Packets/acks can get corrupted resulting in timeouts ( 2 points ) Rcvr. might introduce delays which are more than expected. (2 points) ---------------- Q 26: (bonus question, total 5 points) a) (2.5 points) Since SWS=RWS=3, the sender sends packets 1,2,3 to fill the pipe. Starting at (1 * RTT), it sends packets 4,5,6 clocked by the receipt of the ACK for 1,2,3 respectively. Since 4 gets lost, the sender does not receive any acknowledgement for 4. Non-selective Ack. variation: ++++++++++++++++++++++++++++ The receiver buffers 5 and 6 but does not send ack for any of them. Eventually after 2 * RTT from the time that the sender sent packet 4, its timer for packet 4 expires and the sender then sends packet 4. After another RTT, it gets back an ack for packet 6 (Which is a cumulative ack for 4,5,6). In the meantime, the sender might send out retransmissions for packets 5 and 6 too ( if their timers expire before the cumulative ack 6 is recd.) Selective ack. variation ++++++++++++++++++++++++ The recv. buffers 5,6 and sends acknowledgements for them. After 2 * RTT from the time that the sender sent packet 4, its timer for packet 4 expires, and it then sends 4,7,8. After one more RTT,it starts getting the acknowledgements for these packets. b) (2.5 points) Same as above, except, since 4,5,6 all are lost, all are retransmitted after 2 * RTT timeout. In both the variations (selective ack and non-selective ack), the timeline would look the same. ------------------ Q 39: ( 10 points: It was difficult to grade this question by splitting points, because almost every student had a different way of expressing the solution. If you think your solution is correct, or you deserve more points, come and meet me during the TA hours) One possible scenario +++++++++++++++++++++ A, B, C attempt to transmit, detect the line to be busy (carrier sense of CSMA) and wait for the line to go idle. When D finishes transmitting, all three of them attempt to transmit and collide (1 persistent). [1st collision] They backoff and assume that all three of them choose k = 1. After one time slot, they all collide again [2nd collision] They backoff, lets say all choose 3 again. After 3 more slots, they again try to retransmit and collide (3rd collision) This time C chooses K = 0, B and A choose k = 6. C succeeds. Then B and A collide again (4th collision) Then B chooses 11 and A chooses 13. B starts transmitting after 11 slots, A senses the line at the end of 13, detects a busy line, waits for B to finish. When B finishes, A starts transmitting and finishes.