Exercise 5 (17.-20. September 2000)

1. How do distance vector routing and link state routing differ from each other? Go through all the states of link state routing.

2. Dijkstra's shortest path algorithm in routing
   1. Find using Dijkstra's algorithm the shortest (lowest cost) routes from node A to all other nodes in the network below.

                                  3
                          B . . . . . . .F
                        .  .            .  . 
                     .      .          .    .
                3  .       1 .      4 .      . 2
                 .            .      .        .
                .     3        .   .     3     .
      network  A . . . . . . .  D . . . . . . . .E
                 .             .  .             .
                  .           .    .           .
                   .         . 2    . 2       .
                 2  .       .        .       .  1
                     .     .          .     .
                      .   .            .  .
                       C . . . . . . .  G
       
                                2
      

   2. Give, based on the routes found, the routing table for node A. In the routing table there is, for each node the outlink to be used and the cost of the route. The outlinks are numbered so that the link from A to be is number 1, from A to D number 2 and from A to C number 3.

3. IP Addresses
   1. Convert the IP address whose hexadecimal representation is C22F1582 to dotted decimal notation.

   2. All together there are more than 2 billion IP addresses and the number of Internet hosts is still pretty far from that number. However one big problem with IP addressing has been the fact that IP addresses were running out. How was this possible? What solutions were proposed for this problem?

4. The network layer of host A gets from its transport layer 3000 bytes of data to be sent to the host B. A and B are situated in different networks that are connected by one router. A's LAN can carry at most 1500 bytes of data in one packet and the maximum size of data in B's LAN is only 1000 bytes. Suppose that the next sequence number for A's IP packet (datagram) is 100.

   
           A - XXXXXXXXX  -  router  -  XXXXXXXXXXXX - B
   
                LAN  a                     LAN b 
         max. 1500 bytes data        max. 1000 bytes  data
   

   What kind of IP packets does A send? What does the router do to these packets? What kind of IP packets does B receive? Give the contents of the IP header fields involved in fragmentation in the sent and received IP packets.

5. More about fragmentation
   1. Some fragments can get lost in the transmission. For this reason, the reassembler of fragments uses a timer. In case of time-out the unfinished packet is destroyed. Suppose 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 receiver's memory are discarded. A little later, the last fragments arrives. What should be done with it?
   2. An IP datagram using the Strict source routing option has to be fragmented. Do you think the option has to be copied into each fragment, or is it sufficient to just put it in the first fragment? Explain your answer.

6. For what reasons is the UDP protocol needed? Couldn't the application use straight IP protocol?