Exercises 5 (19.4.)

1. Traceroute
   With a program called traceroute you can find out what routes packets really travel in the Internet. Links to many traceroute services are to be found from the net address http://www.traceroute.org, for example the traceroute service of Funet http://www.csc.fi/cgi-bin/nph-traceroute or the traceroute service of ETSI http://portal.etsi.org/webstats/traceroute.asp. Find out how packets are routed from USA or Canada to the Computer Science Department at the University of Helsinki (cs.helsinki.fi) or some other domain or IP address chosen by you.
   What information do you get about the routes? How is the traceroute program really working to get that information?

2. Forwarding table and forwarding
   Consider a datagram networks using 32-bit host addresses. Suppose a router has four links, numbered 0 through 3, and packets are to be forwarded to the link interface as follows:

                 Destination Address Range         Link interface 
   	     
       11100000 00000000 00000000 00000000
               .............                         0
       11100000 11111111 11111111 11111111	 
       
       11100001 00000000 00000000 00000000
                ............                         1                                         
       11100001 00000000 11111111 11111111   
       
       11100001 00000001 00000000 00000000
                ...........                          2
       11100001 11111111 11111111 11111111
       
               otherwise                             3
   

   1. Provide a forwarding table that has four entries, uses longest-prefix matching, and forwards packets to the correct link interfaces.
   2. Describe how your forwarding table determines the approriate linki interface for datagrams with destination addresses:

            11001000 10010001 01010001 01010101
            11100001 00000000 11000011 00111100
            11100001 10000000 00010001 01110111
      

3. Subnet addresses
   Consider a router that interconnects three subnets: Sub1, Sub2, and Sub3. Suppose all of the intefaces in each of these three subnets are required to have the prefix 223.1.17.0/24. Also suppose that Sub1 is required to support up to 125 interfaces, and Sub2 and Sub3 are each required to support up to 60 interfaces. Provide three network addresss (of form a.b.c-d/x) that satisfy these contraints.

4. Packet fragmentation
   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 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. Flooding
   1. Suppose that, in the network below, the node A sends a packet using flooding. Presume also that for a packet to cross a link it takes one time unit for each link and the sending and receiving of packets does not consume any time. How does the sending of packets continue? How many packets in total has been sent after four time units?

                   
           A ---------------B
           |              / |
           |             /  |
           |            /   |
           |           /    | 
           |          /     |
           |         /      |
           |        E       |
           |      /   \     |
           |     /     \    |
           |    /       \   |
           |   /         \  |
           |  /           \ |
           | /             \|
           C -------------- D            
       

   2. What different ways there are to stop the continuous and increasing sending of packets in flooding?
   3. In which kind of situations is flooding useful?

6. 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.