ECE/CS 438  Communication Networks
Fall 2008

Homework 4
Assigned on October 6, 2008
Due by class time on October 13, 2008

------------------------------------------------------------------------

(1) Modify the labels in the network in Figure 3.14 of the textbook as
    follows:
	* Replace B1 by B4
	* Replace B4 by B7
	* Replace B7 by B1

    What ports would not be selected by the spanning tree algorithm
    in the textbook?
    The ID of each bridge is its number, i.e., B1 has ID 1.
    List the ports as pairs (bridge, network), for instance, (B1,A).

(2) Figure 4.18 in the 4th edition of the textbook is identical
    to Figure 4.19 in the 3th edition.
    Consider the network shown in this figure.
    Using Dijkstra's algorithm, compute the least-cost paths from
    router A to all other routers in the network. Use a table
    similar to Table 4.9 in the textbook to record your work.
    You do not need to show the "Comments" column of the table.

(3) Consider the network in question (2) above.
    Suppose that the nodes use a synchronous version of a distance
    vector algorithm. At time 0, each node only knows
    the cost of the links to its neighbors.
    Starting at time 0, once every minute, each node first sends
    its distance vector to its neighbors. Then, after receiving the
    distance vectors from all its neighbors, each node updates its
    distance vector. The new distance vector is sent to the
    neighbors the next minute.

    (i) Determine the distance vector at each node 
        after the first iteration of the algorithm.

    (ii) How many minutes will it take for all routers to reach a stable
	 state?

(4) Suppose that a router has the following routing table:

      74.21.80.0/22   if1
      74.0.0.0/10     if2
      74.21.64.0/19   if3 
      74.21.96.0/22   if4
      0.0.0.0/0       if5

   (a) For each entry in the table, list the range of IP addresses that
	will match that entry (ignoring any overlap between entries),
        and state the number of addresses in each group.

   (b) Which interface will be used for each of the following addresses?
       Recall that routers use the forwarding rule with the longest
       matching prefix.

	(i)   75.21.81.1
	(ii)  75.20.81.2
        (iii) 73.21.81.3
        (iv)  72.21.100.4 
  

(5) State true or false:

	(i) If any fragment of an IP datagram is lost, the
  	    other fragments are discarded by the destination host.

	(ii) Use of DHCP guarantees that all hosts on a given network
		can always obtain a unique IP address.

	(iii) IP checksum is designed to detect errors only within
		the IP header.

	(iv) Address Resolution Protocol assigns a unique MAC address
		to each interface.