计算机网络英文习题

EE 471 CS 471 CS 573 Fall 2012 2013 Homework 1 Solution Instructor Zartash Afzal Uzmi Due on Sept 17 2012 Handout 7EE 471 CS 471 CS 573 Fall 2012 2013Due on Sept 17 2012 Review Questions From Chapter 1 of Textbook Ch 1 RQ 1 Solution What is diff erence between a host and an end system List the types of end system Is a Web server an end system Answer There is no diff erence Throughout this text the words host and end system are used interchangeably End systems include PCs workstations Web servers mail servers Internet connected PDAs WebTVs etc Ch 1 RQ 12 Solution Why is it said that packet switching employs statistical multiplexing Contrast statistical multiplexing with the multiplexing that takes place in TDM Answer In a packet switched network the packets from diff erent sources fl owing on a link do not follow any fi xed pre defi ned pattern In TDM circuit switching each host gets the same slot in a revolving TDM frame Ch 1 RQ 13 Solution Suppose there is exactly one packet switch between a sending host and a receiving host The transmission rates between the sending host and the switch and between the switch and the receiving host are R1and R2 respectively Assuming that the switch uses store and forward packet switching what is the total end to end delay to send a packet of length L Ignore queuing propagation delay and processing delay Answer First realize that the store and forward packet switching means the packet switch completely receives the packet from the sending host before forwarding it to the receiving host In this case the end to end delay is the sum of transmission delays and propagation delays of the two links i e one link between sender and the switch and other between the switch and the receiver Let d1denote the transmission delay of the link between sender and switch and d2denote the transmission delay of the link between switch and receiver Then d1 L R1 d2 L R2 dtotal d1 d2 L 1 R1 1 R2 L R 1 R2 R1R2 Ch 1 RQ 18 continued on next page Page 2 of 16 Handout 7EE 471 CS 471 CS 573 Fall 2012 2013Due on Sept 17 2012 Ch 1 RQ 18 Solution How long does it take a packet of length 1 000 bytes to propagate over a link of distance 2 500 km propagation speed 2 5 108m s and transmission rate of 2Mbps More generally how long does it take packet of length L to propagate over a link of distance of d propagation speed s and transmission rate R bps Does this delay depends on packet length Does this delay depends on transmission rate Answer a The general expression of propagation delay is dprop d s b The propagation delay for the given data is dprop 2 5 106 2 5 108 0 01 s c The propagation delay is independent of the packet length see equation d The propagation delay is independent of the transmission rate used to transmit data Ch 1 RQ 19 Solution Suppose Host A wants to send a large fi le to Host B The path from Host A to Host B has three links of rates R1 500 kbps R2 2 Mbps and R3 1 Mbps a Assuming no other traffi c in the network what is the throughput for the fi le transfer b Suppose the fi le is 4 million bytes Dividing the fi le size by the throughput roughly how long will it take to transfer the fi le to Host B c Repeat 1 and 2 but now with R2reduced to 100 kbps Answer a When there is no other network traffi c throughput will be min R1 R2 R3 i e 500 kbps b Transmission delay of 4 106byte is calculated below dtran 32 106 500 103 32 106 500 103 64 seconds c Throughput will be min R1 R2 R3 i e 100kbps and the delay can be calculated as following dtran 32 106 100 103 32 106 100 103 320 seconds Page 3 of 16 Handout 7EE 471 CS 471 CS 573 Fall 2012 2013Due on Sept 17 2012 Problems From Chapter 1 of Textbook Ch 1 P 2 Solution Consider an application which transmits data at a steady rate for example the sender generates a N bit unit of data every k time units where k is small and fi xed Also when such an application starts it will stay on for relatively long period of time Answer the following questions briefl y justifying your answer a Would a packet switched network or a circuit switched network be more appropriate for this application Why b Suppose that a packet switched network is used and only traffi c in this network comes from such application 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 Answer a A circuit switched network would be well suited to the application described because the application involves long sessions with predictable smooth bandwidth requirements Since the transmission rate is known and the traffi c is not bursty bandwidth can be reserved for each application session circuit with no signifi cant waste In addition we need not worry greatly about the overhead costs of setting up and tearing down a circuit connection which are amortized over the lengthy duration of a typical application session b Given such generous link capacities the network needs no congestion control mechanism In the worst most potentially congested case all the applications simultaneously transmit over one or more particular network links However since each link off ers suffi cient bandwidth to handle the sum of all of the applications data rates no congestion very little queueing will occur Ch 1 P 5 Solution This elementary problem begins to explore propagation delay and transmission delay two central concepts in data networking Consider two hosts Hosts A and B connected by a single link of rate R bps Suppose that the two hosts are separted by m meters and suppose the propagation speed along the link is s meters sec Host A is to send a packet of size L bits to Host B a Express the propagation delay dpropin terms of m and s b Determine the transmission time of the packet dtransin terms of L and R c Ignoring processing and queuing delays obtain an expression for the end to end delay d Suppose Host A begins to transmit the packet at time t 0 At time t dtrans where is the last bit of the packet e Suppose dpropis greater than dtrans At time t dtrans where is the fi rst bit of the packet f Suppose dpropis less than dtrans At time t dtrans where is the fi rst bit of the packet g Suppose s 2 5 108 L 120 bits and R 56 kbps Find the distance m so that dpropequals dtrans Answer a Expression of propagation delay in term of m and s is dprop m s b Time taken to transmit L bits of data at the rate of R bps is shown in the following equation dtran L R Ch 1 P 5 continued on next page Page 4 of 16 Handout 7EE 471 CS 471 CS 573 Fall 2012 2013Due on Sept 17 2012 c We know that the end to end delay is the sum of all delays that the data encounters In this case it will be sum of transmission and propagation delays only dtotal m s L R d At time t dtransthe last bit would be at the end of transmission link which is near to Host A it would have just got out of Host A e If dprop dtransthen the bit in consideration will be in the transmission link f If dprop dtrans then the bit in consideration will be stored in the buff er at Host B g To calculate distance m for which dtrans dprop we fi nd dtranas shown below dtran 120 56 103 3 1400 Once we have calculated transmission delay we equate it with propagation delay to fi nd m as shown below 3 1400 m 2 5 108 m 3 2 5 108 1400 3 75 106 7 535714 km Ch 1 P 6 Solution In this problem we consider sending a real time voice from Host A to Host B over a packet switched network VoIP Host A converts analog voice to a digital 64 kbps bit stream on the fl y Host A then groups the bits into 56 byte packets There is only one link between Host A and B its transmission rate is 2 Mbps and its propagation delay is 10 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 to 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 Answer Host A groups 56 8 bits into packets as they arrive from the bit stream at a rate of 64 kbps The fi rst bit in a packet must wait until all of the 448 bits are grouped into that packet Clearly the last bit in a packet does not incur this packetization delay at host A The fi rst bit in a packet is also the fi rst one to be decoded at host B with no depacketization delay At host B the last bit in a packet must wait until all of the 448 bits in that packet are departed at a rate of 64 kbps Thus in total each bit in each packet undergoes a packetization and depacketization delay given by dpack 448 64 7 ms In addition there are propagation and transmission delays incurred by Ch 1 P 6 continued on next page Page 5 of 16 Handout 7EE 471 CS 471 CS 573 Fall 2012 2013Due on Sept 17 2012 each packet and hence by each bit The total delay incurred by each bit is dtotal dtran dprop dpack 56 8 2 106 0 01 56 8 64 103 0 017224 s 17 ms Ch 1 P 9 Solution Consider a packet of lenght L which begins at end system A and travels over three links to a destination end system end system These three links are connected by two packet switches Let di siand Ridenote the length propagation speed and the transmission rate of link i for i 1 2 3 The packet switch delays each packet by dproc Assuming no queuing delays in terms of di siand Ri i 1 2 3 and L what is the total end to end delay for the packet Suppose now the packet is 1 500 bytes the propagation speed on both links is s 2 5 108m s the transmission rates of all three links are 2 Mbps the packet switch processing delay is 3 msec the length of fi rst link is 5 000 km the length of the second link is 4 000 km and the length of last link is 1 000 km For these values what is the end to end delay Answer The end to end delay is sum of the dtotalof the three links and processing delay of the packet switches in the path of data End to end delay in term of di si Ri where i 1 2 3 and L is given by the following expression end to end delay 3 X i 1 d i si L Ri 2 dproc The end to end delay of all the links for given values can be calculated by adding dtotal total delay of the three links and processing delay of the packet switches as shown in following equations end to end delay dlink 1 dlink 2 dlink 3 2 0 003 1500 8 2 106 5 106 2 5 108 1500 8 2 106 4 106 2 5 108 1500 8 2 106 1 106 2 5 108 2 0 003 3 500 1 50 3 500 2 125 3 500 1 250 2 0 003 8 125 0 064 s Ch 1 P 16 Solution Consider a router buff er preceding an outbound link In this problem you will use Little s formula a famous formula for queuing theory Let N denote the average number of packets in the buff er plus the packet being transmitted Let a denote the rate of packets arriving at the link Let d denote the average delay i e the queuing delay plus the transmission delay experienced by a packet Little s formula is N a d Suppose that on average the buff er contains 10 packets and the average packet queuing delay is 10 msec The link s transmission rate is 100 packets sec Using Little s formula what is the average packet arrival rate assuming there is no packet loss Ch 1 P 16 continued on next page Page 6 of 16 Handout 7EE 471 CS 471 CS 573 Fall 2012 2013Due on Sept 17 2012 Answer The data in question is incorrect if the average queueing delay is 10 ms a packet must leave the queue on average at 100 packets sec This is only possible when there is only one packet in the queue Thus the average queue size can not be 10 packets At best the input rate must not exceed the output rate if the queue is to remain stable Thus the input rate must not exceed 100 packets sec Ch 1 P 23 Solution Suppose you would like to urgently deliver 40 terabytes data from Boston to Los Angeles You have available a 100 Mbps dedicated data link for data transfer Would you prefer to transmit data vis this link or instead use FedEx overnight delivery Explain Answer To answer this question we need to fi nd the transmission delay in case we transmit data via available 100 Mbps link First we calculate the transmission delay as shown below dtran 320 1012 100 106 3 2 106s 37 days We will prefer overnight delivery by FedEx over the data transfer using the dedicated link because it will be speedy Ch 1 P 24 Solution Suppose two hosts A and B are separated by 20 000 kilometers and are connected via direct link of R 2 Mbps Suppose the propagation over the link is s 2 5 108meters sec a Calculate the bandwidth delay product R dprop b Consider sending a fi le of 800 000 bits from Host A to Host B Suppose the fi le is sent continuously as one large message What is the maximum number of bits that will be in the link at any given time c Provide an interpretation of bandwidth delay product d What is the width in meters of a bit in the link Is it longer than a football fi eld e Derive a general expression for the width of a bit in terms of propagation delay s the transmission rate R and the length of link m Answer a Bandwidth and delay product can be calculated as banwidth delay 2 106 20 106 2 5 108 160 103bits b Number of bits in the link at any given time t are given by the following expression number of bits in link t R0 t 0 08 s 160 1030 08 t 0 32 s R 0 48 t 0 32 t 0 48 s Ch 1 P 24 continued on next page Page 7 of 16 Handout 7EE 471 CS 471 CS 573 Fall 2012 2013Due on Sept 17 2012 c Bandwidth delay product over a link is the maximum number of data bits that can be in the link d Width of a bit in the transmission link can be found by dividing the number of bits in the link by the length of link as shown below width of bit 20 106 160 103 0 125 103 125 meters According to Wikipedia org the width of football pitch for international match is 64 75 meters e Width of a bit in the transmission link in terms of s R and m is shown in equation below width of bit m R m s m R m s ms Rm s R meters Ch 1 P 32 Solution Consider sending a large fi le of F bits from Host A to Host B There are three links and two switches between A and B and the links are uncongested that is no queuing delays Host A segments the fi le into segments of size S bits each and add 80 bits of header to each segment forming packets of L 40 S Typographical error is copied as it is from book i e 80 and 40 bit bits Each links has a transmission rate of R bps Find the value of S that minimizes the delay of moving the fi le from Host A to Host B Disregard propagation delay Answer We solve the question for 40 bits header fi rst For S sized segment there will be F S number of segment Transmission delay of fi rst packet will be 3 S 40 R and for the subsequent F S 1 packets the delay will be F S 1 S 40 R Ch 1 P 32 continued on next page Page 8 of 16 Handout 7EE 471 CS 471 CS 573 Fall 2012 2013Due on Sept 17 2012 Summing the delays we get total delay as following dtotal 3 S 40 R F S 1 S 40 R S 40 R 3 F S 1 S 40 R 2 F S 1 R 2S 80 F 40F S 1 R 2S2 80S FS 40F S Now we use the derivative method to compute the minima of delay We diff erentiate the delay with respect to S d dS dtotal d dS 1 R 2S2 80S FS 40F S 1 R S 4S 80 F 2S2 80S FS 40F S2 1 R 2S2 40F S2 Equating the above equation with 0 to fi nd the optimal value of S 2S2 40F S2 0 S2 20F S 20F 2 5F choosing positive only because S can not be negative We can do the same drill for the 80 bits case as well Transmission delay of fi rst packet will be 3 S 80 R and for the subsequent F S 1 packets the delay will be F S 1 S 80 R Ch 1 P 32 continued on next page Page 9 of 16 Handout 7EE 471 CS 471 CS 573 Fall 2012 2013Due on Sept 17 2012 Summing the delays we get total delay as following dtotal 3 S 80 R F S 1 S 80 R S 80 R 3 F S 1 S 80 R 2 F S 1 R 2S 160 F 80F S 1 R 2S2 160S FS 80F S Now we use the derivative method to compute the minima of delay We diff erentiate the delay with respect to S d dS dtotal d dS 1 R 2S2 160S FS 80F S 1 R S 4S 160 F 2S2 160S FS 80F S2 1 R 2S2 80F S2 Equating the above equation with 0 to fi nd the optimal value of S 2S2 80F S2 0 S2 40F S 40F 2 10F choosing positive only because S can not be negative Additional Questions Q 1 to be answered using web search What does the term Cloud Computing mean to you Find out what is meant by Software Platform In frastructure as a Service SaaS PaaS IaaS Answer It is the delivery of computing resources both hardware and software over the network to the end users Google Apps is an example SaaS Software as a Service is a software distribution model where software and their related data are hosted by a service provider and are made available to the customers over the internet Example is Google maps PaaS Platform as a Service provides a computing platform for building and running applications over the network It includes OS Database Web server Examples are Amazon Elastic Beanstalk Microsoft Azure OrangeScape Q 1 continued on next page Page 10 of 16 Handout 7EE 471 CS 471 CS 573 Fall 2012 2013Due on Sept 17 2012 IaaS Infrastructure as a Service provides of dedicates actual computers to be used as virtual machines by the cloud clients Everything including data storage and sometimes even pro cessing is done by the resources availed by IaaS Google Compute Engine is an example Credits 13100060 13100006 13100023 13100099 Q 2 to be answered using web search Why in your opinion would the term Software as a Service ever come up in a course on Computer Networks Answer SaaS is hosted in the cloud in which applications are hosted by a vendor and made available to everyone through the network As the accessing speed latency throughput etc are determined through the network therefore it is important to talk about SaaS in networks course Credits 1310006 13100029 Analytical Problem 1 Circuit Message and Packet Switching Consider two end hosts connected through k 1 intermediate nodes such that there are k back to back communication links between the two hosts Each link has a capacity of W bits sec and introduces a propagation delay of seconds One host is the source which has an infi nite number of messages to be transmitted to the destination host Each message c