Exercise 7

                                                 Name _____________ Pts __/10

1. (2)  Use Dijkstra's Algorithm as illustrated on page 354 of text to find the shortest path from A-D for:

   (A,E),(E,C),(C,F)

   Using 3 abstract data structures:

   1. queue ordered by minimum cost to reach a node, unexpanded nodes are added when a new node is expanded
   2. path list containing node and predecessor pairs
   3. closed list that contains nodes that have been expanded, we'll clean duplicates from the queue also.

   The node at the head of the queue is always chosen for expansion and is added to the path and closed lists.

   We halt when the goal is reached.

   Queue	Path	Closed
   A
   B4,E5		A
   E5,C7,F10	(A,B)	A,B
   C6,C7,F10,F13	(A,B),(A,E)	A,B,E
   D10,F10,F13	(A,B),(A,E),(E,C)	A,B,E,C
   F10,F13	(A,B),(A,E),(E,C),(C,F)	A,B,E,C,F

   
   
   
    

2. (1) A network on the Internet has a subnet mask of 255.255.0.0. What is the maximum number of hosts it can handle?
   
   
   
   
    
3. (2) A large number of consecutive IP addresses are available starting at 198.16.0.0. Three organizations, A, B, C request 4000, 2000, 4000 addresses respectively and in that order. For each, give the first IP address assigned, the last IP address assigned and the mask in the w.x.y.z/s notation.
   
   
   
   
   
   
    
4. (5) A router has the following (CIDR) entries in its routing table:

           Address/mask    Next hop

   1. 135.46.56.0/22    Interface 0
   2. 135.46.60.0/22    Interface 1
   3. 192.53.40.0/23    Router 1
   4. default                 Router 2

   For each of the following IP addresses, to what interface or router number does the router send a packet with that address arrives?

   1. 135.46.63.10
   2. 135.46.57.14
   3. 135.46.52.2
   4. 192.53.40.7
   5. 192.53.56.7

    

Document last modified: