哈爾濱工業(yè)大學-深圳-高級計算機網絡-2017-習題集

《哈爾濱工業(yè)大學-深圳-高級計算機網絡-2017-習題集》由會員分享，可在線閱讀，更多相關《哈爾濱工業(yè)大學-深圳-高級計算機網絡-2017-習題集（16頁珍藏版）》請在裝配圖網上搜索。

1. A channel has a bit rate of 4 kbps and a propagation delay of 20 msec. For what range of frame sizes does stop-and-wait give an efficiency of at least 50%?answer: 發(fā)送一幀的時間等于信道的傳播延遲的 2 倍，信道的利用率為 50%，所以，在幀長滿足發(fā)送時間大于延遲時間的 2 倍是，效率將會高于 50%。由于4kbps=4000bps 故4000*20*0.001*2=160bit只有在幀長不小于 160bit 時，停止等待協議的效率才會至少是 50%。解此題可供參考的公式有兩個，下面這兩種情況下都可以得到答案：一個是效率= 其中 P 是傳輸一幀所需要的時間，t 是端到端傳送時延。所以可以由 >????+2?? ????+2??=50%，解出幀 N>=160bit；二是 中第 42 張中講到的公式，公式綜合考慮了多種因素，信道丟失率，幀頭的大小 ，以及 ACK 的發(fā)送時間 。在不考慮數據幀的處理時間 tproc 和???? n???n?? n??/??ACK 發(fā)送時間的情況下，我們可以推出幀的最小大小為 160bit。答案詳情參看上次文檔。作業(yè)中得到錯誤答案有兩個（1）N>=80bit 得出此答案的同學沒有弄清楚停等協議，在停等協議公式 1 分母下面的 2t 是往返時間，而不是 t。（2 ） 160kbit，單位換算錯誤。我可以負責任的告訴你沒有哪個網絡里面幀能夠有十幾萬比特大小的，以太網里最大幀不過 1526 字節(jié)。2. Imagine a sliding window protocol using so many bits for sequence numbers that wraparound never occurs. What relations must hold among the four window edges and the window size, which is constant and the same for both the sender and the receiver?answer: 假設發(fā)送者的窗口為（S1 ，Sn）,接受者的窗口為（ R1，Rn ） ，窗口大小為 W，則需滿足：0=Sl 但一定有 Rl1 時，信道總是過載的，因此在這里信道是過載的。4．What is the baud rate of the standard 10 Mbps Ethernet?答：以太網使用曼徹斯特編碼，意味著發(fā)送每一位都有兩個信號周期，標準以太網的數據率為10MB/S，一次波特率是數據率的兩倍，為20MBaud。5．A 1-km-long, 10-Mbps CSMA/CD LAN (not 802.3)has a propagation speed of 200 m/?sec. Repeaters are not allowed in this system. Data frames are 256 bits long, including 32 bits of header, checksum, and other overhead. The first bit slot after a successful transmission is reserved for the receiver to capture the channel in order to Send a 32-bit acknowledgement frame. What is the effective data rate, excluding overhead, assuming that there are no collisions?答：依題意知道一公里的銅電纜中單程的傳播時間為1、200000=5 usec，往返的時間為2t=10 usec，我們知道，一次完整的傳輸分為六步，發(fā)送者偵聽銅電纜的時間為10 usec，若線路可用發(fā)送數據幀傳輸時間為256 bits、10MPS=25.6usec，數據幀最后一位到達時傳播的延遲為5.0usec，接聽者偵聽銅電纜的時間為10 usec，若線路可用接聽者發(fā)送確認幀所用的時間為3.2 usec，確認幀最后一位到達時的傳播延遲為5.0 usec，總共58.8 sec,在這期間發(fā)送了224 bits的數據，所以數據率為3.8MPS 。6．Two CSMA/CD stations are each trying to transmit long (multiframe) files. After each frame is sent, they contend for the channel, using the binaryexponential backoff algorithm. What is the probability that the contention ends on round k, and what is the mean number of rounds per contention period?答：把獲得通道的嘗試從 1 開始編號。第 i 次嘗試分布在 2 i-1 個時隙中。因此，i 次嘗試碰撞的概率是 2-(i-1)，開頭 k-1 次嘗試失敗，緊接著第 k 次嘗試成功的概率是：Pk=（1-2^-（k-1） ）[2^-0*2*-1*······*2^-(k-2)]=（1-2^-（k-1） ）2^-(k-1)(k-2)/2 所以每個競爭周期的平均競爭次數是Σkpk(k=1,2,3······∞)8．An IP packet to be transmitted by Ethernet is 60 bytes long, including all its headers. If LLC is not in use, is padding needed in the Ethernet frame, andif so, how many bytes?答：最小的以太幀是 64bytes，包括了以太幀頭部的二者地址、類型/長度域、校驗和。因為頭部域占用 18 bytes 報文是 60 bytes，總的幀長度是 78 bytes, 已經超過了 64-byte 的最小限制。因此，不需要填補。1. Describe distance vector (DV) algorithm. Discuss the feature of the DV routing algorithm.Solution: (1) The basic idea of DV algorithmEach node x begins with Dx(y), an estimate of thecost of the least-cost path from itself to node y, for all nodes in N. Let Dx= [Dx(y): yin N] be node x’s distance vector, which is the vector of cost estimates from x to allother nodes, y, in N. With the DV algorithm, each node x maintains the followingrouting information:? For each neighbor v, the cost c(x,v) from x to directly attached neighborv? Node x’s distance vector, that is, Dx= [Dx(y): y in N], containing x’s estimate ofits cost to all destinations, y, in N? The distance vectors of each of its neighbors, that is, Dv= [Dv(y): y in N] for eachneighbor v of xIn the distributed, asynchronous algorithm, from time to time, each node sendsa copy of its distance vector to each of its neighbors. When a node x receives anew distance vector from any of its neighbors v, it saves v’s distance vector, andthen uses the Bellman-Ford equation to update its own distance vector as follows:Dx(y) _ minv{c(x,v) + Dv(y)} for each node y in NIf node x’s distance vector has changed as a result of this update step, node x willthen send its updated distance vector to each of its neighbors, which can in turnupdate their own distance vectors. Miraculously enough, as long as all the nodescontinue to exchange their distance vectors in an asynchronous fashion, each costestimate Dx(y) converges to dx(y), the actual cost of the least-cost path from node xto node y(2) The feature of the DV routing algorithmThe distancevector(DV) algorithm is iterative, asynchronous, and distributed. It is distributedin that each node receives some information from one or more of its directlyattached neighbors, performs a calculation, and then distributes the results of itscalculation back to its neighbors.It is iterative in that this process continueson until no more information is exchanged between neighbors. (Interestingly, thealgorithm is also self-terminating—there is no signal that the computation shouldstop; it just stops.) The algorithm is asynchronous in that it does not require all ofthe nodes to operate in lockstep with each other.2. Consider a configuration in which packets are sent from computers on a LAN to systems on other networks. All of these packets must pass through a router that connects the LAN to a widearea network and hence to the outside world.Let us look at the traffic from the LAN through the router. Packets arrive with a mean arrivalrate of 5 per second. The average packet length is 144 bytes, and it is assumed that packet length is exponentially distributed. Line speed from the router to the wide-area network is9600 bps. The following questions are asked:(a) What is the utilization of the link of the router?(b) What is the mean residence time in the router?(c) How many packets are in the router, including those waiting for transmission and the one currently being transmitted (if any), on the average?Solution:(a) Mean arrival rate(throughput): X=5 packets/secAverage service time: S=((144bytes/packet)*(8bits/byte))/9600bps=0.12sec/packetUtilization(time the router is busy): U=X*S=(5 packets/sec)*(0.12 sec/packet)=0.6(b) The mean residence time is T=S/(1-U)=(0.12 sec/packet)/(1-0.6)=0.3 sec/packet(c) Number of packets in the router is E[n]=U/(1-U)=1.5 packets2. Consider the arrival traffic characterized by a token bucket with parameters ρ (average rate) = 1 Mbps, M (maximum output rate) = 2 Mbps, and C (token capacity) = 200Kb. What is the minimum rate r that needs to be allocated by a router in order to guarantee a delay no larger than 50ms?Solution:We build the equation according to the rule: the bits flowed in the router are equal to the bits flowed out the router. Let S be burst length, the maximum accumulative amount of arrival traffic to the router is C+ρS=MS.We get S=C/(M-ρ). When the router deal the arrival traffic at the minimum rate r with a delay no larger than 50ms, let D=50ms and the equation is MS=r*(S+D). So,/()2*0/(21)0.41.60.5/ .52MSCMbpsKbpsMbMpsDs s?????????3. Describe the border gateway protocol (BGP) and discuss how a packet would be transmitted among different autonomous system (AS).Solution:Border GatewayProtocol version 4 (BGP4)We just learned how ISPs use RIP and OSPF to determine optimal paths for sourcedestinationpairs that are internal to the same AS. Let’s now examine how paths aredetermined for source-destination pairs that span multiple ASs. BGPprovides each AS a means to1. Obtain subnet reachability information from neighboring ASs.2. Propagate the reachability information to all routers internal to the AS.3. Determine “good” routes to subnets based on the reachability information andon AS policy.4. Suppose that frames are 1250 bytes long including 25 bytes of head. Also assume that ACK frame are 25 bytes long. Calculate the efficiency of stop-and-wait ARQ in a system that transmits at R=1Mbps and with reaction time of 1ms for channels with a bit error of 10-6, 10-5, 10-4.Solution:From the above figure and condition, we know the total time to transmit 1 frame is t0=2(tprop+tproc)+tf+ta.Here, 2(tprop+tproc) is the reaction time of 1ms, tf is the time to transmit the fames nf=1250 bytes with the head nh=25 bytes and ta is the time to transmit the ACK frame na=25 bytes. And the useful size of the frame is (nf-nh). Moreover, the probability of transmitting a frame without errors is (1-Pe). So the transmission efficiency is as follows.0()/(1)(1) (1)(2) ()(2//()(1250*8/=(1)0.*ef fh fhe e eprocprofafh fhe eprocprofaprocrpfafhereactionfaRntnPPPRRtttttntRnbysitbyPRsM?????????????? (1)(25)/7(1)8 ee Peits???When Pe=10-6,η=87.50%, when Pe=10-5,η=87.50%, when Pe=10-4,η=87.49%.5. Describe the TCP congestion control scheme. Derive the delay modeling for TCP traffic in fixed congestion window when WS/R 10 active less than .0004Q: how did we get value 0.0004?4.Caravan analogy? Cars “propagate” at 100 km/hr? Toll booth takes 12 sec to service a car (transmission time)? car~bit; caravan ~ packet? Q: How long until caravan is lined up before 2nd toll booth?? Time to “push” entire caravan through toll booth onto highway = 12*10 = 120 sec? Time for last car to propagate from 1st to 2nd toll both: 100km/(100km/hr)= 1 hr? A: 62 minutes? Cars now “propagate” at 1000 km/hr? Toll booth now takes 1 min to service a car? Q: Will cars arrive to 2nd booth before all cars serviced at 1st booth?? Yes! After 7 min, 1st car at 2nd booth and 3 cars still at 1st booth.? 1st bit of packet can arrive at 2nd router before packet is fully transmitted at 1st router!? See Ethernet applet at AWL Web site5.6.Could the congestion problem be solved with a large buffer space?Too little memory:too much traffic will lead to buffer overflow and packet loss? Too much memory:the queues and the delays can get so long that by the time the packets come out of the switch, most of them have already timed out and have been retransmitted by higher layers packets (or their retransmissions) have to be dropped after they have consumed precious network re-sources.? Too much memory in the intermediate nodes is as harmful as too little memory.7.Could the congestion problem be solved with high-speed links?? Introducing high-speed links without proper congestion control can lead to reduced performance the same speed(a) The time to transfer a particular file was five minutes.(b) The link between the first two nodes was replace by a fast 1 Mbits link, the transfer time increased to 20 Minutes!? With the high-speed link, the arrival rate to the first router became much higher than the departure rate, leading to long queues, buffer overflows, and packet losses that caused the transfer time to increase.? The protocols have to be designed specifically to ensure that this increasing range of link speeds does not degrade the performance.8.Could the congestion problem be solved with high-speed processors?? Similar to that for links. Introduction of a high-speed processor in an existing network may increase the mismatch of speeds and the chances of congestion.? Introducing high-speed links without proper schemes Congestion occurs even if all links and processors are of the same speed.? An example of the balanced configuration? - Assume all processors and links have a throughput capacity of 1 Gbits. A simultaneous transfer of data from nodes A and B to node C can lead to a total input rate of 2 Gbits per second at the router R while the output rate is only 1 Gbits per second, thereby, causing congestion.6. solutions?? Congestion in networks is a dynamic problem. It cannot be solved with static solutions alone.? We need protocol designs that protect networks in the event of congestion.? The explosion of high-speed networks has led to more unbalanced networks that are causing congestion.? In particular, packet loss due to buffer shortage is a symptom not a cause of congestion.? Solution: proper protocols and mechanisms design, e.g. Admission Control, Scheduling, et. al7. “end to end” and “point to point”a) end to end communications:i. Data communications on a path between the source node and the destination node. The path possibly comprises multiple linksb) point to point communications: i. Data communications on a link connecting the adjacent nodes8. Performance Issue? Stop-and-wait ? Without error t0 =2tprop+2tproc+tf+tack=2tprop+2tproc+nf/R+na/R? Let Pf be the probability that a frame transmission has errors and needs to be retransmitted.? tsw=t0/(1-Pf)Efficiency is: ηsw=((nf-no)/tsw)/R? Where nf, nano are the total number of bits in the frame,number of bits in the ack, and number of bits in the overhead. R is the bandwidth.9. Constrains on Windows’ Size(a sliding window protocol)n bits sequence numberThe size of sending window: WsThe size of receiving window: WrWs+ Wr≤2n10. Binary exponential backoff? When a collision occureach station waits 0 or 1 slots before try again? In general, after i collision, a random number between 0 and 2i -1 is chosen. ? Maximum is 1023? After 16 collisions, the controller gives up and reports failure. 11. Three types of switching fabrics12. Input Port Queuingr Fabric slower than input ports combined ->queueing may occur at input queues r Head-of-the-Line (HOL) blocking: queued datagram at front of queue prevents others in queue from moving forwardr queueing delay and loss due to input buffer overflow!16IP Fragmentation and Reassembly