计算机网络第五章作业参考答案

计算机网络第五章作业参考 Chapter5 3. Consider the network of Fig. 5-7, but ignore the weights on the lines. Suppose that it uses flooding as the routing algorithm. If a packet sent by A to D has a maximum hop count of 3, list all the routes it will take. Also tell how many hops worth of bandwidth it consumes. Solution: It uses flooding as the routing algorithm, which means to transmit packets to all ports except the coming one. It will use: A,B,C,D,A,B,C,F,A,B,E,F,A,B,E,G,A,G,E,B,A,G,E,F,A,G,H ,D,A,G,H,F. So,24 hops bandwidth are used. 5. Consider the network of Fig. 5-12(a). Distance vector routing is used, and the following vectors have just come in to router C: from B: (5, 0, 8, 12, 6, 2); from D: (16, 12, 6, 0, 9, 10); and from E: (7, 6, 3, 9, 0, 4). The cost of the links from C to B, D and E, are 6, 3, and 5, respectively. What is C’s new routing table? Give both the outgoing line to use and the cost. Solution: If C transmit packet via B,A,B,C,D,E,F=(5,0,8,12,6,2)+(6,6,6,6,6,6) =(11,6,14,18,12,8) If C transmit packet g via D,A,B,C,D,E,F=(16,12,6,0,9,10)+(3,3,3,3,3,3)=(19,15,9, 3, 12,13) If C transmit packet via E,A,B,C,D,E,F= (7,6,3,9,0,4) + (5,5,5,5,5,5) =(12,11, 8,14,5, 9) , (11,6,0,3,5,8) So, C’s new routing table(from up to down is from C to A,B,C,D,E) Destination Cost outgoing line(next hop) A 11 B B 6 B C 0 - D 3 D E 5 E F 8 B 9. Looking at the network of Fig. 5-6, how many packets are generated by a broadcast from B, using (a) reverse path forwarding? (b) the sink tree? Solution: (a)Reverse path forwarding: when a broadcast packet arrives at a router, the router checks to see if the packet arrived on the link that is normally used for sending packets toward the source of the broadcast. This being the case, the router forward copies of it onto all links except the one it arrived on. D F hop1:2packets hop 2:4 packets hop 3:10 packets hop 4:8packets hop5:4packets total broadcast packets=2+4+10+8+4=28packets (b) the sink tree: Level1:2packets Level2:4packets Level3:5packets Level4:3packets Total broadcast packets=2+4+5+3=14packets. 10. Consider the network of Fig. 5-15(a). Imagine that one new line is added, between F and G, but the sink tree of Fig. 5-15(b) remains unchanged. What changes occur to Fig. 5-15(c)? Solution: (figure come from 谭棋) The new tree built by reverse path forwarding should be: / F 15. Describe two major differences between the ECN method and the RED method of congestion avoidance. Solution: (1) ECN(Explicit Congestion Notification) A router can tag any packet it forwards to signal that it is experiencing congestion. When the network delivers the packet, the destination can note that there is congestion and inform the sender when it sends a reply packet. The sender can then throttle its transmissions. (2) RED(Random Early Detection) This method prefer to dealing with congestion when it first starts rather than let it gum up the works and then try to deal with it. The motivation for this idea is that most Internet hosts do not yet get congestion signals from routers in the form of ECN. Instead, the only reliable indication of congestion that hosts get from the network is packet loss. Having routers drop packets early, before the situation has become hopeless can help reduce congestion. The affected sender will notice the loss when there is no acknowledgement, and then the transport protocol will slow down. (3) Their differences: a. Application environment: RED is used when hosts cannot receive explicit signal. b. Congestion notified method: ECN delivers a congestion signal explicitly as a choke packet while RED notices congestion through packet loss. 16. Imagine a flow specification that has a maximum packet size of 1000 bytes, a token bucket rate of 10 million bytes/sec, a token bucket size of 1 million bytes, and a maximum transmission rate of 50 million bytes/sec. How long can a burst at maximum speed last? Solution: The burst length S sec, the maximum output rate M bytes/sec, the token bucket capacity B bytes, the token arrival rate R bytes/sec. B+RS=MS,S=B/(M-R) From this problem, B=1MB, M=50MB/s, R=10MB/s S=B/(M-R)=25ms 20. Suppose that host A is connected to a router R1, R1 is connected to another router, R2, and R2 is connected to host B. Suppose that a TCP message that contains 900 bytes of data and 20bytes of TCP header is passed to the IP code at host A for delivery to B. Show the Total length, Identification, DF, MF, and Fragment offset fields of the IP header in each packet transmitted over the three links. Assume that link A-R1 can support a maximum frame size of 1024 bytes including a 14-byte frame header, link R1-R2 can support a maximum frame size of 512 bytes, including an 8-byte frame header, and link R2-B can support a maximum frame size of 512 bytes including a 12-byte frame header. Solution: We have an IP payload of 920 bytes to send. Assume a 20 byte IPv4 header. The first link can carry IP packets up to 1010 bytes, so there will be no fragmentation. The second link can carry IP packets up to 504 bytes, so there will be fragmentation. There may be up to 484 bytes of data, but fragments must carry a multiple of 8 bytes of data (except the last fragment). So the first fragment will carry 480 bytes of data, and the second fragment will carry 440 bytes. The third link can carry IP packets up to 500 bytes, so both fragments will fit and no other fragmentation will occur. The value of the fields is as following table: 512B(8)512B(12)1024B(14) BR1R2A Total length DF MF Fragment offset Identification(random) A,R1 940 0000 0000 0001 0101 0 0 0 R1,R2 500 0000 0000 0001 0101 0 1 0 460 0000 0000 0001 0101 0 0 60 (8*60=480) R1,R2 500 0000 0000 0001 0101 0 1 0 460 0000 0000 0001 0101 0 0 60 (8*60=480) 23. Suppose that instead of using 16 bits for the network part of a class B address originally, 20 bits had been used. How many class B networks would there have been? Solution: 20 bits had been used for the network part of a class B address，but there are 2 bits isfixed，so there 18are only 2 class B networks 18the number of networks would have been 2 or 262,144. However, all 0s and all 1s are special, so only 262,142 are available. 24. Convert the IP address whose hexadecimal representation is C22F1582 to dotted decimal notation. Solution: According to: C 2 2 F 1 5 8 2 ,1100 0010 0010 1111 0001 0101 1000 0010 ,194 47 21 130 ,194.47.21.130 25. A network on the Internet has a subnet mask of 255.255.240.0. What is the maximum number of hosts it can handle? Solution: The third 8-bit group in mask:240=11110000, So, there are network bits: 8+8+4=20bits Hosts bits: 32-20=12bits The maximum number of IP addresses it can handle:=4096 Because the network address and the broadcast network address, hosts =4094. 26. While IP addresses are tried to specific networks, Ethernet addresses are not. Can you think of a good reason why they are not? Answer: IP addresses are hierarchical, unlike Ethernet addresses. Each 32-bit address is comprised of a variable-length network partition in the top bits and a host partition in the bottom bits. Using a hierarchy lets Internet routing scale. However, the IP address of a host depends on where it is located in the network. An Ethernet address can be used anywhere in the world, but every IP address belongs to a specific network, and routers will only be able to deliver packets destined to that address to the network. Or: (from 袁子超) Each Ethernet adapter sold in stores comes hardwired with an Ethernet (MAC) address in it. When burning the address into the card, the manufacturer has no idea where in the world the card will be used, making the address useless for routing in whole internet. In contrast, IP addresses are either assigned either statically or dynamically by an ISP or company, which knows exactly how to get to the host getting the IP address. 27. A large number of consecutive IP addresses are available starting at 198.16.0.0. Suppose that four organizations, A, B, C, and D, request 4000, 2000, 4000, and 8000 addresses, respectively, and in that order. For each of these, give the first IP address assigned, the last IP address assigned, and the mask in the w.x.y.z/s notation. Solution: Organization A: allocate hosts=4096=,host partition=12bits,network partition=20bits Organization B: allocate hosts=2048=,host partition=11bits,network partition=21bits Organization C: allocate hosts=4096=,host partition=12bits,network partition=20bits Organization D: allocate hosts=8192=,host partition=13bits,network partition=19bits Organization the first address the last address amount prefix A 198.16.0.0 198.16.15.255 4096 198.16.0.0/20 B 198.16.16.0 198.16.23.255 2048 198.16.16.0/21 C 198.16.32.0 198.16.47.255 4096 198.16.32.0/20 D 198.16.64.0 198.16.95.255 8192 192.16.64.0/19 28. A router has just received the following new IP addresses: 57.6.96.0/21, 57.6.104.0/21, 57.6.112.0/21, and 57.6.120.0/21. If all of them use the same outgoing line, can they be aggregated? If so, to what? If not, why not? Solution: They can be aggregated. 57.6.96.0 , 0110 0000 57.6.104.0,0110 1000 57.6.112.0,0111 0000 57.6.120.0,0111 1000 ,They can be aggregated by 57.6.96.0/19. 29. The set of IP addresses from 29.18.0.0 to 29.18.128.255 has been aggregated to 29.18.0.0/17. However , there is a gap of 1024 unassigned addresses from 29.18.60.0 to 29.18.63.255 that are now suddenly assigned to a host using a different outgoing line. Is it now necessary to split up the aggregate address into its constituent blocks, add the new block to the table, and then see if any re-aggregation is possible? If not, what can be done instead? Solution: No, it is not necessary to split up the aggregate address. In CIDR, prefixes are allowed to overlap. The rule is that packets are sent in the direction of the most specific route, or the longest matching prefix that has the fewest IP addresses. So in this problem, we just need to add the block 29.18.60.0/22 to the table. If there is a math for both 29.18.0.0/17 and 29.18.60.0/22, 29.18.60.0/22 will be used to lookup the outgoing line for the packet. 30. A router has the following (CIDR) entries in its routing table: Address/mask Next hop 135.46.56.0/22 Interface 0 135.46.60.0/22 Interface 1 192.53.40.0/23 Router 1 default Router 2 For each of the following IP addresses, what does the router do if a packet with that address arrives? (a) 135.46.63.10 (b) 135.46.57.14 (c) 135.46.52.2 (d) 192.53.40.7 (e) 192.53.56.7 Solution: (a) 135.46.63.10,135.46.0011 1111.10 Prefix : /22 ,135.46.0011 1100.10,135.46.60.0 ,Interface 1 (b) 135.46.57.14,135.46.0011 1001.14 Prefix : /22 ,135.46.0011 1000.14,135.46.56.0 ,Interface 0 (c) 135.46.52.2,135.46.0011 0100.2 Prefix : /22 ,135.46. 0011 0100.2,135.46.52.0 ,Router 2 (d) 192.53.40.7 ,192.53.0010 1000.7 Prefix : /22 ,192.53.0010 1000.7,192.53.40.0 ,Router 1 (e) 192.53. 56.7,192.53.0011 1000.7 Prefix : /22 ,192.53. 0011 1000.7,192.53.56.0 ,Router 2 31. Many companies have a policy of having two (or more) routers connecting the company to the Internet to provide some redundancy in case one of them goes down. Is this policy still possible with NAT? Explain your answer. Answer: (modified) Yes，it’s still possible. Whenever an outgoing packet enters the NAT box, the 10x.y.z source address is replaced by a global IP address. And the same time, the segment’s source port field is replaced by an index into the NAT box’s 65536-entry translation table. This table entry contains the original IP address and original source port. When a return packet arrives at the NAT box from the outside, the Source Port in the segment header is extracted and used as an index in to the NAT box’s mapping table. From the entry located, the internal IP address and original Source are extracted and inserted into the packet. So it’s crucial for all the packets pertaining to a single connection pass in and out of the company via the same router, since that is where the mapping is kept. IPv4 ARP 报文 MAC帧头ARP头协议数据 0X0806 32. You have just explained the ARP protocol to a friend. When you are all done, he says: “I’ve got it. ARP provides a service to the network layer, so it is part of the data link layer.” What do you say to him? Answer: (modified) ARP solves the problem of finding out which physical address corresponds to a given IP address. ARP is part of the network layer because it is related to IP address which is the representation of network layer. However, when data is passed down through OSI model, header will be added from each layer and they must be independent. Add a link header to a packet isn’t the function of network layer. ARP works without using IP header. From this perspective, ARP belongs to the data link layer. (Pay attention: ARP belongs to 2 or 3 layer is not wrong. In fact, ARP is replaced by ND which is part of network layer completely in IPv6) 34. Most IP datagram reassembly algorithms have a timer to avoid having a lost fragment tie up reassembly buffers forever. Suppose that a datagram is fragmented into four fragments. The first three fragments arrive, but the last one is delayed. Eventually, the timer goes off and the three fragments in the receiver’s memory are discarded. A little later, the last fragment stumbles in. What should be done with it? Answer: To buffer all the pieces until the last fragment arrives and we can know the size. Then build a buffer with the right size, and put the fragments into the buffer, maintaining a bit map with 1 bit per 8 bytes to keep track of which bytes are present in the buffer. When all the bits in the bit map are 1, the datagram is complete. As far as the receiver is concerned, this is a part of new datagram, since no other parts of it are known. It will therefore be queued until the rest show up. If they do not, this one will time out too. 37. IPv6 uses 16-byte addresses. If a block of 1 million addresses is allocated every picosecond, how long will the addresses last? My answer: 16-byte=128bits 128 Total address amount=2 6 1 million address=10 12861213 Time lasts: 2/(10*10)/(365*24*60*60)=1.08×10years (Pay attention: It’s so big a space that we don’t worry about run-out again.) 38. The Protocol field used in the IPv4 header is not present in the fixed IPv6 header. Why not? Answer: The protocol field in IPv4 packet is replaced by next header witch tells which of the (currently) six extension headers, if any, follow this one. But if there is no extension header or next header field is in the last extension header, the meaning of next header field is same as protocol field’s. So, we can say that it’s not deleted protocol field simply, but extension. 43. Use the traceroute (UNIX) or tracert (Windows) programs to trace the route from your computer to various universities on other continents. Make a list of transoceanic links you have discovered. Some sites to try are www.berkeley.edu (California) www.mit.edu (Massachusetts) www.vu.nl (Amsterdam) www.ucl.ac.uk (London) www.usyd.edu.au (Sydney) www.u-tokyo.ac.jp (Tokyo) www.uct.ac.za (Cape Town) For problem 43, please add two sites: www.baidu.com , www.sina.com.cn , and copy the result interface (image) of tracert (all). Solution: In every test, I will used a red rectangle to show the beginning of transoceanic links. All the routers after it may form the list of transoceanic links. www.berkeley.edu (California): www.mit.edu (Massachusetts) www.vu.nl (Amsterdam) www.ucl.ac.uk (London) As follows, I used tracert in windows to trace the route(use WiFi:CMCC-HEMC) www.usyd.edu.au (Sydney) www.u-tokyo.ac.jp (Tokyo) www.uct.ac.za (Cape Town) www.baidu.com www.sina.com