Data Communications II, Autumn 2004

Problem set 3 (18.10.2004)

1. Use Traceroute program (http://www.traceroute.org) to find out on which routes the messages travel from the the computer science department to FUNET and then to Wiskit in Oregon, USA. You can also try out other destinations.

2. Find out what is meant by dynamic and static NAT router. What other types of NAT routers do exist? In the course book (pp. 339-342) there is a short explanation about NAT routers. More information will be found in the Web, eg. www.firewall.cx/nat-intro.php.

3. In distance 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. In the network below link state routing is used. The cost of each link is 1 and the number next to the link is its identity number. (In real life the link identity numbers are local to the router.)
   1. How is the routing table for E constructed and what could be its content?
   2. What happens, when the link 2 is disconnected?
   3. What happens, when after that also link 7 is disconnected?
   4. What happens, when link 2 is made operational again?

             1            2
      (A)--------- (B) ------- (C)
      |             |           |                             
      |             |           |
      |3            |4          |5       
      |             |           |
      |             |           |
      |             |           |
      |             |           |
      (D)----------(E)--------- (F)
              6           7
      

5. BGP-protocol
   1. How do BGP routers detect routing information loops?
   2. Can the information provided by BGP in AS_PATHs be considered as a distance metric?
   3. Why does the BGP protocol need a KEEPALIVE message of its own? As BGP uses TCP protocol, why cannot it use the permanence of the TCP connection as the keepalive indication?
   4. A router has collected the following path information to access the network 192.9.9.0. Show the network topology that can be drawn from the collected information (i.e. How the different ASs are connected to each other).

        Network          Next Hop       M/LP/Weight Path
     *  192.9.9.0        204.212.44.128           0 234 266 237 3561 701 90 i
     *                   205.238.48.3             0 2914 1 90 i
     *                   144.228.240.93           0 1239 701 90 i
     *                   204.70.4.89              0 3561 1 90 i
     *                   194.68.130.254           0 5459 5413 1 90 i
     *                   202.232.1.8              0 2497 701 90 i
     *                   158.43.133.48            0 1849 702 701 90 i
     *                   131.103.20.49            0 1225 2548 1 90 i

   With the next hops being:

     blackrose.org (Ann Arbor)     204.212.44.128  through AS234
     Verio         (MAE-WEST)      205.238.48.3    through AS2914
     Sprint        (Stockton)      144.228.240.93  through AS1239
     MCI           (San Francisco) 204.70.4.89     through AS3561
     LINX          (London)        194.68.130.254  through AS5459
     IIJ           (Japan)         202.232.1.8     through AS2497
     PIPEX         (London)        158.43.133.48   through AS1849
     IAGnet        (Chicago)       131.103.20.49   through AS1225
          

6. The topology of the network is given below. A, B and C are networks of different service providers (ISP) and x, y and z normal company networks. The BGP (Border Gateway Protocol)is used for routing between networks.

Network x, although connected to two provider networks, doesn't want to relay packets between those networks. The service providers relay traffic from other service providers only to their own customers. For example network X wants from A only that traffic going to x, but doesn't not want to relay traffic going to y.
1. Is it really possible just by withdrawing information about some known routes to stop unwanted traffic? If it is possible, what path information should the BGP routers of these networks exchange with each others, ie. which routes should they reveal to the other networks and which not?
2. Based on the information available, networks x, y and z form each their own view of the network topology. What are the topology views of the x, y and z?

Ps. The figure is from the course book (figure 4.39 in the page 383). In the same page there is a discussion about these kind of matters.