homeworka_chapter4.txt

经典网络教程 自顶向下网络第三版课后习题的答案~~

Chapter 4
 
Review Questions

2.
Datagram-based network layer: forwarding; routing. Additional function of VC-based network layer: call setup. 

3.
Forwarding is about moving a packet from a router's input link to the appropriate output link. Routing is about determining the end-to-end route between sources and destinations. 

4.
Yes, both use forwarding tables. For descriptions of the tables, see Section 4.2.

10.
Packet loss can occur if the queue size at the output port grows large because of slow outgoing line-speed.

13.
11011111  00000001  00000011  00011011

15.
8 interfaces
3 forwarding tables

16.
50% for overhead and 50% for application data

19.
See Section 4.4.4  

20.
Yes, because the entire IPv6 datagram (including header fields) is encapsulated in an IPv4 datagram

21.
Link state algorithms: Computes the least-cost path between source and destination using complete, global knowledge about the network.
Distance-vector routing: The calculation of the least-cost path is carried out in an iterative, distributed manner. A node only knows the cost of the path from itself to the neighbors and the cost of the path from its neighbors to given destination along the least-cost path.

23.
No. Each AS has administrative autonomy for routing within an AS.

24.
No. The advertisement tells D that it can get to z in 11 hops by way of A. However, D can already get to z by way of B in 7 hops. Therefore, there is no need to modify the entry for z in the table. If, on the other hand, the advertisement said that A were only 4 hops away from z by way of C, then D would indeed modify its forwarding table. 

26.
"sequence of ASs on the routes"

33.
a) uncontrolled flooding: T; controlled flooding: T; spanning-tree: F
b) uncontrolled flooding: T; controlled flooding: F; spanning-tree: F


Problems

4.
a) No VC number can assigned to the new VC; thus the new VC can be established in the network.
b) Each link has two available VC numbers. There are four links. So the number of combinations is 2(4 exponent) = 16. One example combination is (10,00,00,10). 

5.
In a virtual circuit network, there is an end-to-end connection in the sense that each router along the path must maintain state for the connection; hence the terminology connection service. In a connection-oriented transport service over a connectionless network layer, such as TCP over IP, the end systems maintain connection state; however the routers have no notion of any connections; hence the terminology connection-oriented service.

6.
To explain why there would be no input queuing, let's look at a specific design. For simplicity suppose each packet is the same size. We design the switch with time division multiplexing: time is broken into frames with each frame divided into n slots, with one slot needed to switch a packet through the fabric, and with one slot per frame devoted to each input line. Since at most one packet can arrive on each input line in each frame, the switching fabric will clear all packets in each frame.

7.
a) a forwarding table as following: 
Prefix Match				Link Interface
11100000                                    0
11100001 00000000			    1
11100001				    2
otherwise			            3

b) Prefix match for first address is 4th entry: link interface 3
   Prefix match for second address is 2nd entry: link interface 1
   Prefix match for first address is 3rd entry: link interface 2

10. 
223.1.17.0/25
223.1.17.128/26
223.1.17.192/26

13.
Any IP address in range 101.101.101.64 to 101.101.101.127 in subnet with prefix 101.101.101.64/26.

Four equal size subnets from the block of addresses of the form 101.101.128.0/17: 
101.101.128.0/19
101.101.160.0/19
101.101.192.0/19
101.101.224.0/19

14.
a)
From 214.97.254/23, possible assignments are:
Subnet A: 214.97.254.0/24  (256 addresses)
Subnet B: 214.97.255.0/25  - 214.97.255.120/29 (128-8 = 120 addresses)
Subnet C: 214.97.255.128/25 (128 addresses)
Subnet D: 214.97.255.120/31  (2 addresses)
Subnet E: 214.97.255.122/31  (2 addresses)
Subnet F: 214.97.255.124/30  (4 addresses)
or
Subnet A: 214.97.255/24  (256 addresses)
Subnet B: 214.97.254.0/25  - 214.97.254.0/29 (128-8 = 120 addresses)
Subnet C: 214.97.254.128/25 (128 addresses)
Subnet D: 214.97.254.0/31  (2 addresses)
Subnet E: 214.97.254.2/31  (2 addresses)
Subnet F: 214.97.254.4/30  (4 addresses)
b)
To simplify the solution, assume that no datagrams have router interfaces as ultimate destinations. Also, label D, E, F for the upper-right, bottom, and upper-left interior subnets, respectively. For the second schedule, we have:

            Router 1
           
            Longest Prefix Match				Outgoing Interface
            11010110 01100001 11111111                               Subnet A
            11010110 01100001 11111110 0000000                       Subnet D
            11010110 01100001 11111110 000001                        Subnet F
	
            Router 2
           
            Longest Prefix Match				Outgoing Interface
            11010110 01100001 11111111 000001                        Subnet F
            11010110 01100001 11111110 0000001                       Subnet E
            11010110 01100001 11111110 1                             Subnet C

            Router 3

            Longest Prefix Match				Outgoing Interface
            11010110 01100001 11111111  0000000                      Subnet D
            11010110 01100001 11111110  0 	                     Subnet B
            11010110 01100001 11111110  0000001     	             Subnet E

15.
The maximum size of data field in each fragment = 480 (20 bytes IP header). Thus the 
number of required fragments [(3000-20)/480] = 7. Each fragment will have Identification number 422. Each fragment except the last one will be of size 500 bytes (including IP header). The last datagram will be of size 120 bytes (including IP header). The offsets of the 7 fragments will be 0, 60, 120, 180, 240, 300, 360. Each of the first 6 fragments will have flag=1; the last fragment will have flag=0.

23.			
                                                 
                              Cost to 
		u	v	x	y	z

	v	∞	∞	∞	∞	∞
From	x	∞	∞	∞	∞	∞
	y	∞	∞	∞	∞	∞
	z	∞	5	2	10	0
	
				
                              Cost to 

		u	v	x	y	z

	v	1	0	∞	15	5
From	x	2	∞	0	1	2
	y	∞	15	1	0	10
	z	4	5	2	3	0


                              Cost to 

		u	v	x	y	z
	v	1	0	3	15	5
From	x	2	3	0	1	2
	y	3	15	1	0	3
	z	4	5	2	3	0
     

                              Cost to 
		u	v	x	y	z

	v	1	0	3	4	5
From	x	2	3	0	1	2
	y	3	4	1	0	3
	z	4	5	2	3	0

25.
a) Dx(y) = 4, Dx(w) = 1, Dx(u) = 6
b) 
First consider what happens if c(x,y) changes. If c(x,y) becomes larger or smaller (as long as c(x,y) > 0), the least cost path from x to u will still have cost 6 and pass through w. Thus a change in c(x,y) will not cause x to inform its neighbors of any changes. 
Second consider what happens if c(x,w) changes. If c(x,w) = e <= 5, then the least-cost path to u continues to pass through w and its cost changes to (e + 5);  x will inform its neighbors of this new cost. If c(x,y) = e > 5, then the least cost path now passes through y and has cost 10; again x will inform its neighbors of this new cost. 
c) Any change in link cost c(x,y) will not cause x to inform its neighbors of a new minimum-cost path to u . 

37.
The protocol must be built at the application layer. For example, an application may periodically multicast its identity to all other group members in an application-layer message.