Problem set 3 (Tuesday 6.2.2001)

1. What are the network addresses and host addresses of the IP address 192.31.63.8
   1. when using class addresses,
   2. when using classless addressing (CIDR) 192.31.63.8/20,
   3. when using classless addressing and a subnet mask, with 28 ones in the beginning and rest of the mask zeroes?

2. When an organization is using both classless addresssing and subnetting, what kind information is stored in the routing tables of the routers belonging to that organization? How do these routers route packets?

3. In distanse vector routing "split horizon" helps, when routing loops include only two routers. But three routers can still cause the "count-to-infinity" -problem.
   1. Show how this problems becomes evident in a situation where 4 routers are connected the way shown in the picture below.

            A ........  B
             .         .
              .      .  
                .   .
                  C
                  .
                  .
                  .
                  D
      

   2. One solution "triggered updates" to the problem in a) is given below.

      "Triggered updates simply add a rule that whenever a gateway changes the metric for a route, it is required to send update messages almost immediately, even if it is not yet time for one of the regular update message. (The timing details will differ from protocol to protocol. Some distance vector protocols, including RIP, specify a small time delay, in order to avoid having triggered updates generate excessive network traffic.) Note how this combines with the rules for computing new metrics. Suppose a gateway's route to destination N goes through gateway G. If an update arrives from G itself, the receiving gateway is required to believe the new information, whether the new metric is higher or lower than the old one. If the result is a change in metric, then the receiving gateway will send triggered updates to all the hosts and gateways directly connected to it. They in turn may each send updates to their neighbors. The result is a cascade of triggered updates.

      It is easy to show which gateways and hosts are involved in the cascade. Suppose a gateway G times out a route to destination N. G will send triggered updates to all of its neighbors. However, the only neighbors who will believe the new information are those whose routes for N go through G. The other gateways and hosts will see this as information about a new route that is worse than the one they are already using, and ignore it. The neighbors whose routes go through G will update their metrics and send triggered updates to all of their neighbors. Again, only those neighbors whose routes go through them will pay attention. Thus, the triggered updates will propagate backwards along all paths leading to gateway G, updating the metrics to infinity. This propagation will stop as soon as it reaches a portion of the network whose route to destination N takes some other path."

      Show how this solution would work in the situation of a). Is it possible, by using triggered updates, to get rid of "count-to-infinity" -problem totally?

4. Distance vector algorithm is used. Suppose that in the network of the picture below each node only knows the distance to its neighbours. Show the content of the routing table in the node E after it has been changing routing information with its neighbours.

   
            1
   A --------------- B
   |              /  |
   |          5 /    |
   | 2        /      | 15
   |        E        |
   |     /     \     |
   |   /2     10 \   |
   | /             \ |
   C --------------  D
           1
           
   

5. A routing table stores entries in a tree data structure. Each level in the tree can be thought of as corresponding to a bit in the destination address. To look up an address, the router starts at the root node and, according to the value of the first address bit continues to search the right or the left subtree. The value of the next address bit leads the search again to the rigth or to the left subsubtree. Suppose each step in the addredd search (each level in the tree) demands one memory access and each memory access takes 40 nanoseconds. How many lookups for 32 bit IP-addresses can this kind of router at most handle in one second. What about if the addresses contain 128 bits?

6. Take the subnetwork of the picture 5.20 on page 371 in Tanenbaums book. Supposing that the link costs are equal on all links, what kind of "reverse path forwarding" -tree would you make for node F? How is this tree actually formed? When node F sends a broadcast packet, how many packets are really sent in the subnetwork?