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

Chapter53. 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: ABCD,ABCF,ABEF,ABEG,AGEB,AGEF,AGHD,AGHF.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 Cs new routing table? Give both the outgoing line to use and the cost.Solution:If C transmit packet via BA,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 DA,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 EA,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, Cs new routing table(from up to down is from C to A,B,C,D,E) DestinationCostoutgoing line(next hop)A11BB6BC0-D3DE5EF8B 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. DFhop1:2packetshop 2:4 packetshop 3:10 packetshop 4:8packetshop5:4packetstotal broadcast packets=2+4+10+8+4=28packets(b) the sink tree:Level1:2packetsLevel2:4packetsLevel3:5packetsLevel4:3packetsTotal 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=MSS=B/(M-R)From this problem, B=1MB, M=50MB/s, R=10MB/sS=B/(M-R)=25ms20. 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:Total lengthIdentification(random)DFMFFragment offsetAR19400000 0000 0001 0101000R1R25000000 0000 0001 01010104600000 0000 0001 01010060 (8*60=480)R1R25000000 0000 0001 01010104600000 0000 0001 01010060 (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 are only 218 class B networksthe number of networks would have been 218 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 21100 0010 0010 1111 0001 0101 1000 0010194 47 21 130194.47.21.13025. 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=12bitsnetwork partition=20bitsOrganization B: allocate hosts=2048=host partition=11bitsnetwork partition=21bitsOrganization C: allocate hosts=4096=host partition=12bitsnetwork partition=20bitsOrganization D: allocate hosts=8192=host partition=13bitsnetwork partition=19bitsOrganizationthe first addressthe last addressamountprefixA198.16.0.0198.16.15.2554096198.16.0.0/20B198.16.16.0198.16.23.2552048198.16.16.0/21C198.16.32.0198.16.47.2554096198.16.32.0/20D198.16.64.0198.16.95.2558192192.16.64.0/1928. 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.00110 1000 57.6.112.00111 0000 57.6.120.00111 1000They 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 hop135.46.56.0/22 Interface 0135.46.60.0/22 Interface 1192.53.40.0/23 Router 1default 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.7Solution:(a) 135.46.63.10135.46.0011 1111.10Prefix : /22 135.46.0011 1100.10135.46.60.0 Interface 1(b) 135.46.57.14135.46.0011 1001.14Prefix : /22 135.46.0011 1000.14135.46.56.0 Interface 0(c) 135.46.52.2135.46.0011 0100.2Prefix : /22 135.46. 0011 0100.2135.46.52.0 Router 2(d) 192.53.40.7 192.53.0010 1000.7Prefix : /22 192.53.0010 1000.7192.53.40.0 Router 1(e) 192.53. 56.7192.53.0011 1000.7Prefix : /22 192.53. 0011 1000.7192.53.56.0 Router 231. 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，its 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 segments source port field is replaced by an index into the NAT boxs 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 boxs mapping table. From the entry located, the internal IP address and original Source are extracted and inserted into the packet. So its 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.32. You have just explained the ARP protocol to a friend. When you are all done, he says: “Ive 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 isnt 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 receivers 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 Total address amount=2128 1 million address=106 Time lasts: 2128/(106*1012)/(365*24*60*60)=1.