You are here

Home » Computer Networking: Principles, Protocols and Practice » The network layer » Exercises

Principles

19 January, 2016 - 11:23
Available under Creative Commons-ShareAlike 4.0 International License.
  1. Routing protocols used in data networks only use positive link weights. What would happen with a distance vector routing protocol in the network below that contains a negative link weight ?
media/image207.png
Figure 5.75 Simple network  
  1. When a network specialist designs a network, one of the problems that he needs to solve is to set the metrics the links in his network. In the USA, the Abilene network interconnects most of the research labs and universities. The figure below shows the topology 1 of this network in 2009.
media/image208.png
Figure 5.76 The Abilene network  

In this network, assume that all the link weights are set to 1. What is the paths followed by a packet sent by the router located in Los Angeles to reach :

  • the router located in New York
  • the router located in Washington ?

Is it possible to configure the link metrics so that the packets sent by the router located in Los Angeles to the routers located in respectively New York and Washington do not follow the same path ?

Is it possible to configure the link weights so that the packets sent by the router located in Los Angeles to router located in New York follow one path while the packets sent by the router located in New York to the router located in Los Angeles follow a completely different path ?

Assume that the routers located in Denver and Kansas City need to exchange lots of packets. Can you configure the link metrics such that the link between these two routers does not carry any packet sent by another router in the network ?

  1. In the five nodes network shown below, can you configure the link metrics so that the packets sent by router E to router A use link B->A while the packets sent by router B use links B->D and D->A?
media/image209.png
Figure 5.77 Simple five nodes network  
  1. In the five nodes network shown above, can you configure the link weights so that the packets sent by router E (resp. F) follow the E->B->A path (resp. F->D->B->A)?
  2. In the above questions, you have worked on the stable state of the routing tables computed by routing protocols. Let us now consider the transient problems that main happen when the network topology changes 2. For this, consider the network topology shown in the figure below and assume that all routers use a distance vector protocol that uses split horizon.
media/image210.png
Figure 5.78 Simple network with redundant links  

If you compute the routing tables of all routers in this network, you would obtain a table such as the table below :

Destination Routes on A Routes on B Routes on C Routes on D Routes on E
A 0 1 via A 2 via B 3 via C 4 via D
B 1 via B 0 1 via B 2 via C 3 via D
C 2 via B 1 via C 0 1 via C 2 via D
D 3 via B 2 via C 1 via D 0 1 via D
E 4 via B 3 via C 2 via D 1 via E 0

Distance vector protocols can operate in two different modes : periodic updates and triggered updates. Periodic updates is the default mode for a distance vector protocol. For example, each router could advertise its distance vector every thirty seconds. With the triggered updates a router sends its distance vector when its routing table changes (and periodically when there are no changes).

  • Consider a distance vector protocol using split horizon and periodic updates. Assume that the link B-C fails. B and C update their local routing table but they will only advertise it at the end of their period. Select one ordering for the periodic updates and every time a router sends its distance vector, indicate the vector sent to each neighbor and update the table above. How many periods are required to allow the network to converge to a stable state ?
  • Consider the same distance vector protocol, but now with triggered updates. When link B-C fails, assume that B updates its routing table immediately and sends its distance vector to A and D. Assume that both A and D process the received distance vector and that A sends its own distance vector, ... Indicate all the distance vectors that are exchanged and update the table above each time a distance vector is sent by a router (and received by other routers) until all routers have learned a new route to each destination. How many distance vector messages must be exchanged until the network converges to a stable state ?
  1. Consider the network shown below. In this network, the metric of each link is set to 1 except link A-B whose metric is set to 4 in both directions. In this network, there are two paths with the same cost between D and C. Old routers would randomly select one of these equal cost paths and install it in their forwarding table. Recent routers are able to use up to N equal cost paths towards the same destination.
media/image211.png
Figure 5.79 A simple network running OSPF  

On recent routers, a lookup in the forwarding table for a destination address returns a set of outgoing interfaces. How would you design an algorithm that selects the outgoing interface used for each packet, knowing that to avoid reordering, all segments of a given TCP connection should follow the same path ?

  1. Consider again the network shown above. After some time, OSPF converges and all routers compute the following routing tables :
Destination Routes on A Routes on B Routes on C Routes on D Routes on E
A 0 2 via C 1 via A 3 via B,E 2 via C
B 2 via C 0 1 via B 1 via B 2 via D,C
C 1 via C 1 via C 0 2 via B,E 1 via C
D 3 via C 1 via D 2 via B,E 0 1 via D
E 2 via C 2 via C,D 1 via E 1 via E 0

An important difference between OSPF and RIP is that OSPF routers flood link state packets that allow the other routers to recompute their own routing tables while RIP routers exchange distance vectors. Consider that link B-C fails and that router B is the first to detect the failure. At this point, B cannot reach anymore A, C and 50% of its paths towards E have failed. C cannot reach B anymore and half of its paths towards D have failed.

Router B will flood its updated link state packet through the entire network and all routers will recompute their forwarding table. Upon reception of a link state packet, routers usually first flood the received link-state packet and then recompute their forwarding table. Assume that B is the first to recompute its forwarding table, followed by D, A, C and finally E

  1. After each update of a forwarding table, verify which pairs of routers are able to exchange packets. Provide your answer using a table similar to the one shown above.
  2. Can you find an ordering of the updates of the forwarding tables that avoids all transient problems ?
  3. Consider the network shown in the figure below and explain the path that will be followed by the packets to reach 194.100.10.0/23
media/image212.png
Figure 5.80 A stub connected to one provider  
  1. Consider, now, as shown in the figure below that the stub AS is now also connected to provider AS789. Via which provider will the packets destined to 194.100.10.0/23 will be received by AS4567 ? Should AS123 change its configuration ?
  2. Consider that stub shown in the figure below decides to advertise two /24 prefixes instead of its allocated /23 prefix.
    1. Via which provider does AS4567 receive the packets destined to 194.100.11.99 and 194.100.10.1 ?
    2. How is the reachability of these addresses affected when link R1-R3 fails ?
    3. Propose a configuration on R1 that achieves the same objective as the one shown in the figure but also preserves the reachability of all IP addresses inside AS4567 if one of AS4567‘s interdomain links fails ?
media/image213.png
Figure 5.81 A stub connected to two providers  
  1. Consider the network shown in the figure below. In this network, each AS contains a single BGP router. Assume that R1 advertises a single prefix. R1 receives a lot of packets from R9. Without any help from R2, R9 or R4, how could R1 configure its BGP advertisement such that it receives the packets from R9 via R3 ? What happens when a link fails ?
  2. Consider the network show in the figure below.
    1. Show which BGP messages are exchanged when router R1 advertises prefix 10.0.0.0/8.
    2. How many and which routes are known by router R5 ? Which route does it advertise to R6?
    3. Assume now that the link between R1 and R2 fails. Show the messages exchanged due to this event. Which BGP messages are sent to R6 ?
  3. Consider the network shown in the figure below where R1 advertises a single prefix. In this network, the link between R1 and R2 is considered as a backup link. It should only be used only when the primary link (R1-R4) fails. This can be implemented on R2 by setting a low local-pref to the routes received on link R2-R1
    1. In this network, what are the paths used by all routers to reach R1 ?
    2. Assume now that the link R1-R4 fails. Which BGP messages are exchanged and what are now the paths used to reach R1 ?
    3. Link R1-R4 comes back. Which BGP messages are exchanged and what do the paths used to reach R1 become ?
  4. On February 22, 2008, the Pakistan Telecom Authority issued an order to Pakistan ISPs to block access to three IP addresses belonging to youtube: 208.65.153.238, 208.65.153.253, 208.65.153.251. One operator noted that these addresses were belonging to the same /24 prefix. Read http://www.ripe.net/news/studyyoutube-hijacking.html to understand what happened really.
    1. What should have done youtube to avoid this problem ?
media/image214.png
Figure 5.82 A stub connected to two providers  
media/image215.png
Figure 5.83 A simple internetwork  
media/image216.png
Figure 5.84 A simple internetwork  
media/image217.png
Figure 5.85 A simple internetwork with a backup link  
          2. What kind of solutions would you propose to improve the security of interdomain routing ?
  1. There are currently 13 IPv4 addresses that are associated to the root servers of the Domain Name System. However, http://www.root-servers.org/ indicates that there are more than 100 different physical servers that support. This is a large anycast service. How would you configure BGP routers to provide such anycast service ?
  2. Consider the network shown in the figure below. In this network, R0 advertises prefix p and all link metrics are set to 1
    • Draw the iBGP and eBGP sessions
    • Assume that session R0-R8 is down when R0 advertises p over R0-R7. What are the BGP messages exchanged and the routes chosen by each router in the network ?
    • Session R0-R8 is established and R0 advertises prefix p over this session as well
    • Do the routes selected by each router change if the MED attribute is used on the R7-R6 and R3-R10 sessions, but not on the R4-R9 and R6-R8 sessions ?
    • Is it possible to configure the routers in the R1 -R6 network such that R4 reaches prefix p via R6-R8 while R2‘uses the ‘R3-R10 link ?
media/image218.png
Figure 5.86 A simple Internet 
  1. The BGP MED attribute is often set at the IGP cost to reach the BGP nexthop of the advertised prefix. However, routers can also be configured to always use the same MED values for all routes advertised over a given session. How would you use it in the figure above so that link R10-R3 is the primary link while R7-R6 is a backup link ? Is there an advantage or drawback of using the MED attribute for this application compared to local-pref ?
  2. In the figure above, assume that the managers of R8 and R9 would like to use the R8-R6 link as a backup link, but the managers of R4 and R6 do no agree to use the BGP MED attribute nor to use a different local-pref for the routes learned from.
  • 2376 reads