You may submit your solutions as a PDF if you wish. (Questions 16 and 19 may be easier to answer with paper and pen.)

For questions 1-6, give an IPv4 address prefix (in CIDR notation). Your answer must give the network address at the start of the range and the correct "/X" indicating the subnet size:

  1. Every IPv4 address.
  2. The subnet containing the IP address 4.100.20.100 if the subnet mask is 255.255.240.0.
  3. The subnet containing the IP address 60.4.2.221 and 511 other addresses.
  4. The /24 subnet containing the IP address 2.101.53.10.
  5. The subnet containing just the one IP address 10.0.0.20.
  6. The aggregation of these prefixes: 4.0.0.0/24, 4.0.1.0/24, 4.0.2.0/23, 4.0.0.0/22.

  7. Is 255.255.255.100 a valid IPv4 subnet mask? Why or why not?
  8. Express this IPv6 address in binary (with 128 bits, and please put a space between each group of 8 bits so we can read it clearly): 44:10:0:ee3::2a99:1
  9. Why must a router have at least two IP addresses?
  10. IP Anycast allows a single IP address to be used by multiple machines in different locations, and it allows a client to reach the closest of several machines. How can this be used to make the 8.8.8.8 Google public DNS resolver scale effectively to millions of requests per second?
  11. Why does IP Anycast work better for load balancing DNS requests than for HTTP requests? In other words, what problem might arise in an HTTP request that is routed by IP Anycast.
  12. Let's say a router has a bus switching fabric with a switching rate of 50Gbit/s, and it has 10 input ports and 10 output ports. The input and output ports are 10GBASE-SR fiber optic connections capable of 10Gbit/s each. Also assume that each input and output port has a queue with maximum capacity of 10 Mbit (1.25 Mbyte). For how long, at most, can all input ports receive data at full capacity (100Gbit/s total) before dropping any packets?
  13. In the example above, assume that the forwarding tables in the router dictate that all this traffic should be sent out on one port. Does this change the answer above, and if so, to what?
  14. If a router implements Weighted Fair Queueing (WFQ), is a packet's wait time bounded or can it be infinite?
  15. Briefly, how does BGP allow the Internet to remain interconnected even if individual links can fail? Who is the first to notice a failed link, and what action does this device take?
  16. Let's say I have two laptops on a private LAN behind a NAT, with IP addresses 10.0.0.101 and 10.0.0.102. The NAT router has private IP address 10.0.0.1 and public IP address 5.5.5.5. Now let's say that the first laptop (10.0.0.101) has two web browsers open and makes HTTP requests from each one. The second laptop also sends an HTTP request from a web browser. All of these HTTP requests are actually for the same website and the same server IP address (7.7.7.7). Fill in the following table, listing the IP addresses and ports for all three requests and their responses, both as they appear on the LAN and the WAN. It's OK to pick random port numbers when appropriate.
    Request packet on LAN Request packet on WAN Response packet on WAN Response packet on LAN
    Laptop1, browser1

    src: 10.0.0.101:8001

    dst: 7.7.7.7:80

    a)

    src:___________

    dst:___________

    b)

    src: 7.7.7.7:80

    dst:__________

    c)

    src:___________

    dst:___________
    Laptop1, browser2

    d)

    e)

    f)

    g)
    Laptop2

    h)

    i)

    j)

    k)
  17. Slide 14 of Lecture 9 shows a NAT-based load balancer. Actually it shows one of two different variations of NAT-based load balancing. In the design shown in the figure, the load balancer changes the source address on packets it receives from the public internet (eg., 4.4.4.4 to 10.0.0.1). Actually, that address change is not strictly necessary. A simpler design could leave the source address and port unchanged. For example, a packet comes in with <src=4.4.4.4:1230, dst= 2.2.2.2:80> and that gets translated into <src:4.4.4.4:1230, dst=10.0.0.2:80>. (By contrast, the original design shown in my slide shows a translation into <src=10.0.0.1:1002, dst=10.0.0.2:80>)
    a) At most how many concurrent connections can the original address-changing design support?
    b) At most how many concurrent connections can the new, simpler design support?
    c) In what scenario would it be necessary to use the address-changing design, and when is it possible to use the simpler design?
    HINT: Messages sent from server to client must pass through the NAT load balancer so that it can translate the source address from private to public. In some cases, the original design is needed to guarantee that responses pass through the NAT. What are those cases?
  18. How can the Bellman-Ford shortest path algorithm be adapted to calculate the shortest path between every pair of nodes in the graph (and not just the shortest path from one source to all destinations)?
  19. It's important in Dijkstra's shortest path algorithm that in each iteration we "visit" the closest unvisited node. We can prove this by giving a "counter example." The graph below is a starting point for constructing a counter example. Let's say that we (incorrectly) allowed the algorithm to visit any node with current distance less than infinity (instead of choosing the node with minimum distance). On the graph below, give a weighting for the edges and an order of visiting the nodes that obeys the relaxed version of Dijkstra described above, but would lead to an incorrect answer for the distance between source A and destination H:



    HINT: the algorithm only considers each edge twice (once for each of the vertices it connects). There must be sufficient information at the time an edge is considered to make a decision about whether to include it in the shortest path.