BYUBRIGHAM YOUNG UNIVERSITY
Computer Science
CS 460 Computer Communications and Networking
Archive

Homework #4

Review Questions (not graded, do not turn in)

  1. Kurose & Ross, Chapter 4, Review Question R3.

    What is the difference between routing and forwarding?

  2. Kurose & Ross, Chapter 4, Review Question R8.

    Three types of switching fabrics are discussed in Section 4.3. List and briefly describe each type.

  3. Kurose & Ross, Chapter 4, Review Question R9.

    Describe how packet loss can occur at input ports. Describe how packet loss at input ports can be eliminated ( without using infinite buffers).

  4. Kurose & Ross, Chapter 4, Review Question R10.

    Describe how packet loss can occur at output ports.

  5. Kurose & Ross, Chapter 4, Review Question R13.

    What is the 32-bit binary equivalent of the IP address 223.1.3.27?

  6. Kurose & Ross, Chapter 4, Review Question R16.

    Suppose an application generates chunks of 40 bytes of data every 20 msec, and each chunk gets encapsulated in a TCP segment and then an IP datagram. What percentage of each datagram will be overhead, and what percentage will be application data?

  7. What are the advantages and disadvantages of using NAT?
  8. Kurose & Ross, Chapter 4, Review Question R19.

    Compare and contrast the IPv4 and the IPv6 header fields. Do they have any fields in common?

  9. Kurose & Ross, Chapter 4, Review Question R21.

    Compare and contrast link-state and distance-vector routing algorithms.

  10. Kurose & Ross, Chapter 4, Review Question R27.

    Why are different inter-AS and intra-AS protocols used in the Internet?

  11. Why is multicast a big improvement compared to unicasting the same data to each of the members of the group?
  12. Kurose & Ross, Chapter 4, Review Question R35.

    What are the roles played by the IGMP protocol and a wide-area multicast routing protocol?

  13. Kurose & Ross, Chapter 4, Review Question R36.

    What is the difference between a group-shared tree and a source-based tree in the context of multicast routing?

  14. Explain the advantage of SSM with respect to PIM. In particular, consider what must be done to discover a new source for a multicast group.
  15. Explain why we need application layer multicast protocols. What are their advantages as compared to native multicast protocols?

Problems (10 points each)

  1. Kurose & Ross, Chapter 4, Problem P1.

    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?
  2. Kurose & Ross, Chapter 4, Problem P8.

    Consider the switch shown below. Suppose that all datagrams have the same fixed length, that the switch operates in a slotted, synchronous manner, and that in one time slot a datagram can be transferred from an input port to an output port. The switch fabric is a crossbar so that at most one datagram can be transferred to a given output port in a time slot, but different output ports can receive datagrams from different input ports in a single time slot. What is the minimal number of time slots needed to transfer the packets shown from input ports to their output ports, assuming any input queue scheduling order you want (i.e., it need not have HOL blocking)? What is the largest number of slots needed, assuming the worst-case scheduling order you can devise, assuming that a non-empty input queue is never idle?

    router
  3. Kurose & Ross, Chapter 4, Problem P9.
  4. 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:

    addressing
    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:
      1. 11001000 10010001 01010001 01010101
      2. 11100001 01000000 11000011 00111100
      3. 11100001 10000000 00010001 01110111
  5. Kurose & Ross, Chapter 4, Problem P12.

    Consider a router that interconnects three subnets: Subnet 1, Subnet 2, and Subnet 3. Suppose all of the interfaces in each of these three subnets are required to have the prefix 223.1.17/24. Also suppose that Subnet 1 is required to support up to 63 interfaces, Subnet 2 is to support up to 95 interfaces, and Subnet 3 is to support up to 16 interfaces. Provide three network addresses (of the form a.b.c.d/x) that satisfy these constraints.

  6. Kurose & Ross, Chapter 4, Problem P17.

    Consider sending a 2400-byte datagram into a link that has an MTU of 700 bytes. Suppose the original datagram is stamped with the identification number 422. How many fragments are generated? What are the values in the various fields in the IP datagram(s) generated related to fragmentation?

  7. Kurose & Ross, Chapter 4, Problem P24.

    Consider the following network.

    Problem P24

    With the indicated link costs, use Dijkstra's shortest-path algorithm to compute the shortest path from x to all network nodes. Show how the algorithm works by computing a table similar to Table 4.3. (Note, this table shows, for each iteration of the algorithm, the current set of nodes whose shortest distances have been found, plus the current distance and previous hop for each destination.)

  8. Kurose & Ross, Chapter 4, Problem P29.

    Consider the three-node topology shown in Figure 4.30 (shown below). Rather than having the link costs shown in Figure 4.30, the link costs are c(x,y) = 3, c(y,z) = 6, c(z,x) = 4. Compute the distance tables after the initialization step and after each iteration of a synchronous version of the distance-vector algorithm (as we did in our earlier discussion of Figure 4.30).

    Figure 4.30
  9. Kurose & Ross, Chapter 4, Problem P35.

    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.

    Problem 35
    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?
  10. Kurose & Ross, Chapter 4, Problem P36.

    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 I1 or I2 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 I1 or I2? 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 I1or I2 ? Explain why in one sentence.
  11. Kurose & Ross, Chapter 4, Problem P37.

    Consider the following network.

    Problem P37

    ISP B provides national backbone service to regional ISP A. 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 not need to dig into the BGP specification.

  12. Kurose & Ross, Chapter 4, Problem P44.

    Consider the topology shown in Figure 4.44 (shown below). Suppose that all links have unit cost and that node E is the broadcast source. Using arrows like those shown in Figure 4.44) indicate links over which packets will be forwarded using RPF, and links over which packets will not be forwarded, given that node E is the source.

    Figure 4.44
  13. Kurose & Ross, Chapter 4, Problem P46.

    Consider the topology shown in Figure 4.46 (shown below), and suppose that each link has unit cost. Suppose node C is chosen as the center in a center-based multicast routing algorithm. Assuming that each attached router uses its least-cost path to node C to send join messages to C, draw the resulting center-based routing tree. Is the resulting tree a minimum-cost tree? Justify your answer.

    Figure 4.46
  14. Kurose & Ross, Chapter 4, Problem P52.

    What is the size of the multicast address space? Suppose now that two multicast groups randomly choose a multicast address. What is the probability that they choose the same address? Suppose now that 1,000 multicast groups are ongoing at the same time and choose their multicast group addresses at random. What is the probability that they interfere with each other?