Computer Networks and Network Security: Lab Assignment Five:
Routing and Forwarding

Due Dec. 24, 2023 by email to the instructor. This assignment gives you a chance to analyze network layer.

• [P1 (10 points)] In this question, we consider some of the pros and cons of virtual-circuit and datagram networks.
  1. Suppose that routers were subjected to conditions that might cause them to fail fairly often. Would this argue in favor of a VC or datagram architecture? Why?
  2. Suppose that a source node and a destination require that a fixed amount of capacity always be available at all routers on the path between the source and destination node, for the exclusive use of traffic flowing between this source and destination node. Would this argue in favor of a VC or datagram architecture? Why?
  3. Suppose that the links and routers in the network never fail and that routing paths used between all source/destination pairs remains constant. In this scenario, does a VC or datagram architecture have more control traffic overhead? Why?
  
  
• [P2 (5 points)] Consider the network shown below, and assume that each node initially knows the costs to each of its neighbors. Consider the distance-vector algorithm and show the distance table entries at node z.

  Figure for P2

  
  
  
• [P3 (5 points)] Consider a general topology (that is, not the specific network shown above) and a synchronous version of the distance-vector algorithm. Suppose that at each iteration, a node exchanges its distance vectors with its neighbors and receives their distance vectors. Assuming that the algorithm begins with each node knowing only the costs to its immediate neighbors, what is the maximum number of iterations required before the distributed algorithm converges? Justify your answer.
  
  
• [P4 (10 points)] Consider the network fragment shown below. x has only two attached neighbors, w and y. w has a minimum-cost path to destination u (not shown) of 5, and y has a minimum-cost path to u of 6. The complete paths from w and y to u (and between w and y) are not shown. All link costs in the network have strictly positive integer values.
  
  
  1. Give x's distance vector for destinations w, y, and u.
  2. Give a link-cost change for either c(x,w) or c(x,y) such that x will inform its neighbors of a new minimum-cost path to u as a result of executing the distance-vector algorithm.
  3. Give a link-cost change for either c(x,w) or c(x,y) such that x will not inform its neighbors of a new minimum-cost path to u as a result of executing the distance-vector algorithm.

  Figure for P4

  
  
• [P5 (5 points)] Consider the count-to-infinity problem in the distance vector routing. Will the count-to-infinity problem occur if we decrease the cost of a link? Why? How about if we connect two nodes which do not have a link?
  
  
• [P6 (10 points)] Consider the figure below. Suppose there is another router w, connected to router y and z. The costs of all links are given as follows: c(x,y) = 4, c(x,z) = 50, c(y,w) = 1, c(z,w) = 1, c(y,z) = 1. Suppose that poisoned reverse is used in the distance-vector routing algorithm.
  
  
  1. When the distance vector routing is stabilized, router w, y, and z inform their distances to x to each other. What distance values do they tell each other?
  2. Now suppose that the link cost between x and y increases to 60. Will there be a count-to-infinity problem even if poisoned reverse is used? Why or why not? If there is a count-to-infinity problem, then how many iterations are needed for the distance-vector routing to reach a stable state again? Justify your answer.
  3. How do you modify c(y,z) such that there is no count-to-infinity problem at all if c(y,x) changes from 4 to 60?

  Figure for P6

  
  
• [P7 (10 points)] Consider the network shown below. Suppose AS3 and AS2 are running OSPF for their intra-AS routing protocol. Suppose AS1 and AS4 are running RIP for their intra-AS routing protocol. Suppose eBGP and iBGP are used for the inter-AS routing protocol. Initially suppose there is no physical link between AS2 and AS4.
  1. Router 3c learns about prefix x from which routing protocol: OSPF, RIP, eBGP, or iBGP?
  2. Router 3a learns about x from which routing protocol?
  3. Router 1c learns about x from which routing protocol?
  4. Router 1d learns about x from which routing protocol?

  Figure for P7 and P8

  
  
• [P8 (10 points)] Referring to the previous problem, once router 1d learns about x it will put an entry (x, I) in its forwarding table.
  1. Will I be equal to I₁ or I₂ for this entry? Explain why in one sentence.
  2. Now suppose that there is a physical link between AS2 and AS4, shown by the dotted line. Suppose router 1d learns that x is accessible via AS2 as well as via AS3. Will I be set to I₁ or I₂? Explain why in one sentence.
  3. Now suppose there is another AS, called AS5, which lies on the path between AS2 and AS4 (not shown in diagram). Suppose router 1d learns that x is accessible via AS2 AS5 AS4 as well as via AS3 AS4. Will I be set to I₁ or I₂? Explain why in one sentence.
  
  
• [P9 (10 points)] Consider the following network. ISP B provides national backbone service to regional ISPA. ISP C provides national backbone service to regional ISP D. Each ISP consists of one AS. B and C peer with each other in two places using BGP. Consider traffic going from A to D. B would prefer to hand that traffic over to C on the West Coast (so that C would have to absorb the cost of carrying the traffic cross-country), while C would prefer to get the traffic via its East Coast peering point with B (so that B would have carried the traffic across the country). What BGP mechanism might C use, so that B would hand over A-to-D traffic at its East Coast peering point? To answer this question, you will need to dig into the BGP specification.

  Figure for P9

  
  
• [P10 (10 points)] In Figure for P10(1), consider the path information that reaches stub networks W, X, and Y. Based on the information available at W and X, what are their respective views of the network topology? Justify your answer. The topology view at Y is shown in Figure for P10(2).

  Figure for P10(1): A simple BGP scenario.

  Figure for P10(2): The topology view at Y.

  
  
  
• [P11 (5 points)] Consider Figure for P10(1). B would never forward traffic destined to Y via X based on BGP routing. But there are some very popular applications for which data packets go to X first and then flow to Y. Identify one such application, and describe how data packets follow a path not given by BGP routing.
  
  
• [P12 (10 points)] Consider a datagram network using 32-bit host addresses. Suppose a router has four links, numbered 0 through 3, and packets are to be forwarded to the link interfaces as follows:
  
  
  
  
  1. Provide a forwarding table that has five entries, uses longest prefix matching, and forwards packets to the correct link interfaces.
  2. Describe how your forwarding table determines the appropriate link interface for datagrams with destination addresses: